求解最大割问题的多启动禁忌搜索算法

doi:10.11772/j.issn.1001-9081.2014.05.1271

计算机应用 ›› 2014, Vol. 34 ›› Issue (5): 1271-1274.DOI: 10.11772/j.issn.1001-9081.2014.05.1271

求解最大割问题的多启动禁忌搜索算法

张爱君,秦新强,龚春琼

西安理工大学应用数学系，西安 710048

收稿日期:2013-11-11 修回日期:2014-01-02 出版日期:2014-05-01 发布日期:2014-05-30
通讯作者: 张爱君
作者简介:张爱君（1979- ），女，陕西渭南人，讲师，硕士，主要研究方向：应用数学微分方程数值解及其应用、求解NP问题的高效算法；秦新强（1962- ），男，陕西蓝田人，教授，博士，主要研究方向：微分方程数值解及其应用、计算机高效算法；龚春琼（1975- ），女，云南弥渡人，讲师，硕士，主要研究方向：应用数学微分方程数值解及其应用、求解NP问题的高效算法。
基金资助:
国家自然科学基金资助项目

Multi-start tabu search algorithm for solving maximum cut problem

ZHANG Aijun,QIN Xinqiang,QIONG Chunqiong

Department of Applied Mathematics, Xi'an University of Technology, Xi'an Shaanxi 710048, China

Received:2013-11-11 Revised:2014-01-02 Online:2014-05-01 Published:2014-05-30
Contact: ZHANG Aijun
Supported by:
National Natural Science Foundation

摘要/Abstract

摘要：

为了增强局部搜索算法在求解最大割问题上的寻优能力，提高解质量，提出了一种多启动禁忌搜索（MSTS）算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想，综合利用了“构造”和“扰动”这两种方法生成新的起始解，来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算, 并与多个先进算法进行比较，MSTS算法在18个算例上得到最好解值，高于其他对比算法。实验结果表明，MSTS算法具有更强的寻优能力和更高的解质量。

Abstract:

A Multi-Start Tabu Search (MSTS) algorithm was proposed for the maximum cut problem to improve the solution quality. The proposed algorithm included two key components, one of which was tabu search used to identify high-quality local optimal solutions and the other of which was the multi-start strategy used for the global exploration. Firstly, a local optimum solution was acquired by tabu search component. Secondly, new starting solution was produced by multi-start strategy and then tabu search procedure was restarted. Based on the random greediness, the proposed multi-start strategy integrated the constructive and perturbation methods to produce new starting solutions, thus escaping from being trapped in local optimum and finding higher quality solutions. Experiments on 21 standard maximum cut benchmark instances and comparisons with several state-of-the-art algorithms show that 18 best solutions was obtained by MSTS, higher than compared algorithms. The experimental results indicate that the proposed algorithm outperforms the reference algorithms in terms of the solution quality.

中图分类号:

TP301.6

张爱君秦新强龚春琼. 求解最大割问题的多启动禁忌搜索算法[J]. 计算机应用, 2014, 34(5): 1271-1274.

ZHANG Aijun QIN Xinqiang QIONG Chunqiong. Multi-start tabu search algorithm for solving maximum cut problem[J]. Journal of Computer Applications, 2014, 34(5): 1271-1274.

参考文献

［1］CROCE F, KAMINSKI M J, PASCHOS V T. An exact algorithm for MAX-CUT in sparse graphs ［J］. Operations Research Letters, 2007,35(3):403-408.
［2］KRISHNAN K, MITCHELL J E. A semidefinite programming based polyhedral cut and price approach for the maxcut problem ［J］. Computational Optimization and Applications, 2006,33(1):51-71.
［3］BURKER S, MONTEIRO R D C, ZANG Y. Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs ［J］. SIAM Journal on Optimization, 2002,12(2):503-521.
［4］FESTA P, PARDALOS P M, RESENDE M G C, et al. Randomized heuristics for the MAX-CUT problem ［J］. Optimization Methods and Software, 2002,7:1033-1058.
［5］LAGUNA M, DUARTE A, MART R. Hybridizing the cross-entropy method: an application to the MAX-CUT problem ［J］. Computers and Operations Research, 2009,36(2):487-498.
［6］MART R, DUARTE A, LAGUNA M. Advanced scatter search for the MAX-CUT problem ［J］. INFORMS Journal on Computing, 2009,21(1):26-38.
［7］GLOVER F. Tabu search—Part Ⅰ ［J］. ORSA Journal on Computing, 1989,1(3):190-206.
［8］LIU J. Improved maximum cut problem solution with tabu machine network ［J］. Computer Applications and Software, 2011,28(8):169-172. (刘建军.改进的Tabu Machine网络求解最大割问题［J］.计算机应用与软件,2011,28(8):169-172.)
［9］KOCHENBERGER G A, GLOVER F. A unified framework for modeling and solving combinatorial optimization problems: a tutorial ［EB/OL］. ［2013-08-15］. http://www.researchgate.net/profile/Fred_Glover/publication/226808473_A_Unified_Framework_for_Modeling_and_Solving_Combinatorial_Optimization_Problems_A_Tutorial/file/79e415088442e490f9.pdf
［10］FIDUCCIA C M, MATTHEYSES R M. A linear-time heuristics for improving network partitions ［C］// Proceedings of the 19th Conference on Design Automation. Piscataway: IEEE Press, 1982:175-181.
［11］GAO L, ZENG Y, DONG A. An ant colony algorithm for solving MAX-CUT problem ［J］. Progress in Natural Science, 2008,18(9):1173-1178.
［12］RENDL F, RINALDI G, WIEGELE A. Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations ［J］. Mathematical Programming, 2009,121(2):307-335.
［13］ARRIZ E, OLIVO O. Competitive simulated annealing and tabu search algorithms for the MAX-CUT problem ［C］// GECCO '09: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2009:1797-1798.
［14］KARISH S E, RENDL F, CLAUSEN J. Solving graph bisection problems with semidefinite programming ［J］. INFORMS Journal on Computing, 2000,12(3):177-191.
［15］KARP R M. Reducibility among combinatorial problems ［G］// MILLER R E, THATCHER J W, BOHLINGER J D. Complexity of Computer Computation. New York: Springer-Verlag, 1972:85-103.

[1]	段玉先刘昌云. 基于Sobol序列和纵横交叉策略的麻雀搜索算法[J]. 计算机应用, 0, (): 0-0.
[2]	李太全肖柏勋. 求解三对角线性方程组的迭代对角占优算法[J]. 计算机应用, 2012, 32(10): 2742-2744.
[3]	周伟罗建军靳凯王凯. 基于模糊高斯学习策略的粒子群-进化融合算法[J]. , , (): 0-0.
[4]	陈闯 Ryad Chellali 邢尹. 采用动态权重和概率扰动策略改进的灰狼算法[J]. , , (): 0-0.

求解最大割问题的多启动禁忌搜索算法

Multi-start tabu search algorithm for solving maximum cut problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics