首页 | 官方网站   微博 | 高级检索  
     

求解最大割问题的多启动禁忌搜索算法
引用本文:张爱君,秦新强,龚春琼.求解最大割问题的多启动禁忌搜索算法[J].计算机应用,2014,34(5):1271-1274.
作者姓名:张爱君  秦新强  龚春琼
作者单位:西安理工大学 应用数学系,西安 710048
基金项目:国家自然科学基金资助项目
摘    要:为了增强局部搜索算法在求解最大割问题上的寻优能力,提高解质量,提出了一种多启动禁忌搜索(MSTS)算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想,综合利用了“构造”和“扰动”这两种方法生成新的起始解,来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算, 并与多个先进算法进行比较,MSTS算法在18个算例上得到最好解值,高于其他对比算法。实验结果表明,MSTS算法具有更强的寻优能力和更高的解质量。

关 键 词:最大割  组合优化  智能算法  局部搜索  禁忌搜索
收稿时间:2013-11-11
修稿时间:2014-01-02

Multi-start tabu search algorithm for solving maximum cut problem
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.
Authors:ZHANG Aijun QIN Xinqiang QIONG Chunqiong
Affiliation:Department of Applied Mathematics, Xi'an University of Technology, Xi'an Shaanxi 710048, China
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.
Keywords:
本文献已被 CNKI 等数据库收录!
点击此处可从《计算机应用》浏览原始摘要信息
点击此处可从《计算机应用》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号