Less is more: Solving the Max-Mean diversity problem with variable neighborhood search
Less is more: Solving the Max-Mean diversity problem with variable neighborhood search
复制标题
DOI：
10.1016/j.ins.2016.12.021
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
J. Brimberg;N. Mladenović;R. Todosijević;D. Urošević
中科院分区：
文献类型：
--
作者：
J. Brimberg;N. Mladenović;R. Todosijević;D. Urošević
在广泛的类的多样性/分散性问题，我们发现一个重要的变种称为最大均值多样性问题，这需要找到一个子集的一组给定的元素，以最大限度地提高商的总和属于该子集的所有边缘和基数的子集。在本文中，我们开发了一个新的应用程序的一般可变邻域搜索解决这个问题。大量的计算结果表明，我们的新的启发式显着优于当前国家的最先进的启发式。此外，最知名的解决方案已被改进的58出的60个大型测试实例从文献中。换句话说，尽管我们的方法很简单，这是一个理想的属性，任何启发式，我们实现了显着更好的结果比一个更复杂的启发式，代表了国家的最先进的。因此，简单可以导致更有效和更有效的方法：当使用启发式，少可以多。
Within the broad class of diversity/dispersion problems we find an important variant known as the Max–Mean Diversity Problem, which requires finding a subset of a given set of elements in order to maximize the quotient of the sum of all edges belonging to that subset and the cardinality of the subset. In this paper we develop a new application of general variable neighborhood search for solving this problem. Extensive computational results show that our new heuristic significantly outperforms the current state-of-the-art heuristic. Moreover, the best known solutions have been improved on 58 out of 60 large test instances from the literature. In other words, despite the simplicity of our method, which is a desirable property for any heuristic, we achieve significantly better results than a more complex heuristic that represents the state-of-the-art. Thus, simplicity can lead to more efficient and effective methods: when heuristics are used, less can be more.