作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (12): 122-124. doi: 10.3969/j.issn.1000-3428.2012.12.036

• 人工智能及识别技术 • 上一篇    下一篇

一种求解旅行商问题的混合路径重连算法

张晓霞,童杰伟,刘 哲   

  1. (辽宁科技大学软件学院,辽宁 鞍山 114051)
  • 收稿日期:2011-08-26 出版日期:2012-06-20 发布日期:2012-06-20
  • 作者简介:张晓霞(1966-),女,副教授、博士,主研方向:智能优化算法,组合优化;童杰伟、刘 哲,硕士研究生
  • 基金资助:
    辽宁省教育厅基金资助项目(L2010196)

Hybrid Path Relinking Algorithm for Solving Traveling Salesman Problem

ZHANG Xiao-xia, TONG Jie-wei, LIU Zhe   

  1. (College of Software Engineering, University of Science and Technology Liaoning, Anshan 114051, China)
  • Received:2011-08-26 Online:2012-06-20 Published:2012-06-20

摘要: 提出一种求解旅行商问题的新型混合路径重连算法,将贪婪随机自适应搜索方法的构建机制引入到路径重连算法中,从而在搜索过程中同时考虑解的质量及分散性。在重连过程中,将向导解的属性逐步引入到起始解属性中,以快速获得该线路上的最优解,并采用动态更新参考集策略加快收敛速度。实验结果表明,该算法的解质量优于其他算法。

关键词: 旅行商问题, 贪婪随机自适应搜索方法, 路径重连, 局部搜索, 限制候选列表, 参考集

Abstract: A new hybrid Path Relinking(PR) algorithm is presented. The algorithm combining the solution construction mechanism of Greedy Randomized Adaptive Search Procedure(GRASP) into PR is designed. It considers both solution quality and diversification. The process of the path relinking phase is to introduce progressively attributes of the guiding solution into the initial solution to obtain the high quality solution as quickly as possible. Moreover, the algorithm adopts the dynamic updating strategy of the reference set to accelerate the convergence towards high-quality regions of the search space. Experimental results show that the method is very efficient and competitive compared with the best existing methods in terms of solution quality.

Key words: Traveling Salesman Problem(TSP), Greedy Randomized Adaptive Search Procedure(GRASP), Path Relinking(PR), local search, Restricted Candidate List(RCL), reference set

中图分类号: