摘要: 提出一种求解旅行商问题的新型混合路径重连算法,将贪婪随机自适应搜索方法的构建机制引入到路径重连算法中,从而在搜索过程中同时考虑解的质量及分散性。在重连过程中,将向导解的属性逐步引入到起始解属性中,以快速获得该线路上的最优解,并采用动态更新参考集策略加快收敛速度。实验结果表明,该算法的解质量优于其他算法。
关键词:
旅行商问题,
贪婪随机自适应搜索方法,
路径重连,
局部搜索,
限制候选列表,
参考集
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
中图分类号:
张晓霞, 童杰伟, 刘哲. 一种求解旅行商问题的混合路径重连算法[J]. 计算机工程, 2012, 38(12): 122-124.
ZHANG Xiao-Xia, TONG Jie-Wei, LIU Zhe. Hybrid Path Relinking Algorithm for Solving Traveling Salesman Problem[J]. Computer Engineering, 2012, 38(12): 122-124.