A Tabu Search Approach With Dynamical Neighborhood Size for Solving the Maximum Min-Sum Dispersion Problem
A Tabu Search Approach With Dynamical Neighborhood Size for Solving the Maximum Min-Sum Dispersion Problem
复制标题
求解最大最小和色散问题的动态邻域大小禁忌搜索方法
DOI：
10.1109/access.2019.2959315
复制
发表时间：
2019
期刊：
影响因子：
3.9
通讯作者：
Fu Zhang-Hua
中科院分区：
文献类型：
--
作者：
Lai Xiangjing;Fu Zhang-Hua
最大最小和离散问题（Max-Minsum DP）是一类典型的二元优化问题，被证明是NP-难的，具有广泛的实际应用和潜在的应用价值。在本文中，为了有效地解决这个计算上具有挑战性的问题，我们提出了一个禁忌搜索算法与动态的邻域大小（TSDNS）集成基于解决方案的禁忌策略，三个新的哈希函数，并自适应调整的机制，利用该算法的邻域大小。通过对文献中广泛使用的160个基准实例的大量实验，对所提TSDNS算法的性能进行了评估，实验结果表明，与文献中的现有算法相比，所提算法具有很强的竞争力，特别是对于大规模实例，并且在一些基准实例上，最佳已知结果得到了改善。分析实验表明，新的禁忌策略中使用的哈希函数比文献中的哈希函数在大规模情况下更有效，而自适应控制邻域大小的机制对算法的高性能起着关键作用。
The maximum min-sum dispersion problem (Max-Minsum DP for short) is a representative binary optimization problem that is proved to be NP-hard and has a number of real-world or potential applications. In this paper, to solve efficiently this computationally challenging problem, we propose a tabu search algorithm with a dynamical neighborhood size (TSDNS) by integrating a solution-based tabu strategy, three new hash functions, and a mechanism of adjusting adaptively the size of neighborhood exploited by the algorithm. The performance of the proposed TSDNS algorithm is assessed through extensive experiments on 160 benchmark instances widely used in the literature, and the experimental results show that the proposed algorithm is very competitive compared with the state-of-the-art algorithms in the literature especially for the large scale instances, and that the best known results are improved for a number of benchmark instances. Analysis experiments show that the new hash functions used in the tabu strategy are more efficient than those from the literature for the large scale instances, and that the mechanism of controlling adaptively neighborhood size plays a key role for the high performance of proposed algorithm.
登录
查看更多内容
影响因子：
2.4
作者：
P. Ekins
通讯作者：
P. Ekins
影响因子：
1.9
作者：
F. Blattner
通讯作者：
F. Blattner
影响因子：
1.6
作者：
Vicki D Crinis
通讯作者：
Vicki D Crinis
影响因子：
0.2
作者：
R. Eglash
通讯作者：
R. Eglash
DOI：
10.1080/13573320701467344
发表时间：
2004-01
期刊：
Wiley-Blackwell: Development Policy Review
影响因子：
--
作者：
J. Roberts;D. Shaw;P. Sahoo;N. Harris;B. Persaud;M. Thakur;I. Gillson;A. Suleiman
通讯作者：
J. Roberts;D. Shaw;P. Sahoo;N. Harris;B. Persaud;M. Thakur;I. Gillson;A. Suleiman