计算机应用 ›› 2012, Vol. 32 ›› Issue (02): 425-431.DOI: 10.3724/SP.J.1087.2012.00425

• 人工智能 • 上一篇    下一篇

提高链式Lin-Kernighan算法性能的一种新策略

王东1,李娅1,吴臣1,林冬梅2   

  1. 1. 佛山科学技术学院 电子与信息工程学院,广东 佛山 528000
    2. 佛山科学技术学院 信息与教育技术中心,广东 佛山 528000
  • 收稿日期:2011-06-15 修回日期:2011-09-05 发布日期:2012-02-23 出版日期:2012-02-01
  • 通讯作者: 王东
  • 作者简介:王东(1970-),男,黑龙江甘南人,副教授,博士,CCF会员,主要研究方向:组合优化、智能计算、计算机视觉;
    李娅(1978-),女,湖北黄石人,讲师,硕士,主要研究方向:智能优化算法;
    吴臣(1974-),男,重庆人,讲师,硕士,主要研究方向:模式识别、智能计算;
    林冬梅(1969-),女,黑龙江肇东人,副教授,硕士,CCF会员,主要研究方向:组合优化、智能计算、虚拟现实、信息安全。
  • 基金资助:
    广东省科技计划工业攻关项目(2011B010200031);广东省自然科学基金资助项目(10152800001000029)

New strategy for improving performance of chained Lin-Kernighan algorithm

WANG Dong1,LI Ya1,WU Chen1,LIN Dong-mei2   

  1. 1. College of Electronics and Information Engineering, Foshan University, Foshan Guangdong 528000, China
    2. Center of Information and Education Technology, Foshan University, Foshan Guangdong 528000, China
  • Received:2011-06-15 Revised:2011-09-05 Online:2012-02-23 Published:2012-02-01
  • Contact: WANG Dong

摘要: 在笔者前期工作(王东, 吴湘滨. 提高链式Lin-Kernighan算法性能的策略. 计算机应用,2007,27(11): 2826-2829)的基础上,通过对经典旅行商问题(TSP)优化解边集之间交集的特性分析,给出了一种新的Lin-Kernighan算法参照优化边集生成模型。该模型建立的边集中边的数量少于常规方法以及前期研究成果生成边集中边的数量,同时以更高概率保留全局最优解中的边。将该模型应用于Lin-Kernighan算法,在不损失单次调用该算法求解精度的前提下,进一步缩短了算法的执行时间,从而进一步提高了链式Lin-Kernighan算法的求解性能。结合前期研究成果,能进一步提高使用Lin-Kernighan算法作为启发式算法的所有混合算法性能。

关键词: 链式Lin-Kernighan算法, 旅行商问题, 边交集, 参照优化边集

Abstract: Through analyzing the characteristics of the edge sets of the optimal solutions from Traveling Salesmen Problem (TSP), a kind of new model was proposed to produce the referring optimization edge sets for Lin-Kernighan algorithm on the basis of authors' previous research (WANG DONG, WU XIANG-BIN. Strategy for improving the performance of chained Lin-Kernighan algorithm. Journal of Computer Applications, 2007,27(11): 2826-2829). The number in the edge sets produced by the new model is less than those produced by normal algorithms or previous research. Meanwhile, the new edge sets include more edges that belong to the global optimal solution than them. Applying the new model to Lin-Kernighan algorithm, the execution time of the algorithm is further reduced, without losing the algorithm accuracy for a single call. Furthermore, the solution performance of Lin-Kernighan algorithm is improved also. With previous research achievement, the performance of all hybrid algorithms using Lin-Kernighan algorithm as the local search algorithm could be improved too.

Key words: chained Lin-Kernighan algorithm, Traveling Salesmen Problem (TSP), intersect edge set, reference optimization edge set

中图分类号: