Heuristics and metaheuristics for the maximum diversity problem
Heuristics and metaheuristics for the maximum diversity problem
复制标题
DOI：
10.1007/s10732-011-9172-4
复制
发表时间：
2011-06
影响因子：
2.7
通讯作者：
R. Martí;M. Gallego;A. Duarte;Eduardo G. Pardo
中科院分区：
文献类型：
--
作者：
R. Martí;M. Gallego;A. Duarte;Eduardo G. Pardo
本文提出了广泛的计算实验，以比较最大多样性问题 (MDP) 的 10 种启发式方法和 20 种元启发式方法。该问题包括从给定的元素集中选择最大多样性的子集。它出现在广泛的现实世界环境中，我们可以找到大量的研究，其中提出了启发式和元启发式方法。然而，可能由于这个问题以不同的名称被引用，我们只在某些实例集上发现了与几种方法的有限比较。本文回顾了所有用于寻找 MDP 近乎最优解决方案的启发式方法和元启发式方法。我们提出了新的基准库 MDPLIB，其中包括以前用于此问题的大多数实例以及新实例，总共 315 个实例。我们还对 MDPLIB 上的 30 种方法进行了详尽的计算比较。我们的研究报告了非参数统计检验，以得出重要的结论。
This paper presents extensive computational experiments to compare 10 heuristics and 20 metaheuristics for the maximum diversity problem (MDP). This problem consists of selecting a subset of maximum diversity from a given set of elements. It arises in a wide range of real-world settings and we can find a large number of studies, in which heuristic and metaheuristic methods are proposed. However, probably due to the fact that this problem has been referenced under different names, we have only found limited comparisons with a few methods on some sets of instances.This paper reviews all the heuristics and metaheuristics for finding near-optimal solutions for the MDP. We present the new benchmark library MDPLIB, which includes most instances previously used for this problem, as well as new ones, giving a total of 315. We also present an exhaustive computational comparison of the 30 methods on the MDPLIB. Non-parametric statistical tests are reported in our study to draw significant conclusions.