A simple and effective algorithm for the MaxMin diversity problem
A simple and effective algorithm for the MaxMin diversity problem
复制标题
DOI：
10.1007/s10479-011-0898-z
复制
发表时间：
2011-05
影响因子：
4.8
通讯作者：
D. Porumbel;Jin-Kao Hao;F. Glover
中科院分区：
文献类型：
--
作者：
D. Porumbel;Jin-Kao Hao;F. Glover
最大化点集合的多样性的挑战出现在各种设置中，包括硬优化问题的搜索方法的设置。该问题的一个版本称为最大多样性问题 (MDP)，它产生受基数约束的二次二元优化问题，并且已成为众多研究的主题。这项研究的重点是最大最小多样性问题 (MMDP)，但我们还引入了一种使用 MDP 作为次要目标的新公式。我们提出了一种基于单独的添加和删除操作以及简单的禁忌机制的快速本地搜索。与之前的局部搜索方法相比，每次迭代中搜索最佳移动的复杂度从二次降低为线性；只有某些简化计算可能（很少）需要每次迭代的二次时间。此外，掉落策略的强大禁忌规则保证了强大的多元化能力。尽管该方法很简单，但事实证明该方法优于文献中的大多数更先进的方法，可以在几秒钟内为许多问题提供经过优化证明的解决方案，甚至达到新的下限。
The challenge of maximizing the diversity of a collection of points arises in a variety of settings, including the setting of search methods for hard optimization problems. One version of this problem, called the Maximum Diversity Problem (MDP), produces a quadratic binary optimization problem subject to a cardinality constraint, and has been the subject of numerous studies. This study is focused on the Maximum Minimum Diversity Problem (MMDP) but we also introduce a new formulation using MDP as a secondary objective. We propose a fast local search based on separate add and drop operations and on simple tabu mechanisms. Compared to previous local search approaches, the complexity of searching for the best move at each iteration is reduced from quadratic to linear; only certain streamlining calculations might (rarely) require quadratic time per iteration. Furthermore, the strong tabu rules of the drop strategy ensure a powerful diversification capacity. Despite its simplicity, the approach proves superior to most of the more advanced methods from the literature, yielding optimally-proved solutions for many problems in a matter of seconds and even attaining a new lower bound.