求解TSP问题的拟人算法  

Personification Algorithm for Traveling Salesman Problem

作　　者：吴军[1] 李建[1] 胡永泉[1] 

机构地区：[1]西南石油大学计算机科学学院,成都610500

出　　处：《计算机系统应用》2011年第4期248-250,244,共4页Computer Systems & Applications

摘　　要：基于贪心算法提出了一种改进的求解旅行商问题(TSP)的拟人算法。该算法采用邻域定义,主要思想是:给定一个所有城市的全排列,依此全排列的指挥用贪心算法生成一个回路。通过城市交换和城市序列平移,在当前的邻域中搜索比它更好的解,如能找到如此的解,则使之成为新的当前解,然后重复上述过程。在搜索的过程中,采取跳坑策略以跳出局部最优解,始终向目标最接近的方向搜索。算法结果与Rego提出的完全子路径搜索算法(F-SEC)做比较。In this paper,a personification algorithm for solving the Traveling Salesman Problem（TSP） is proposed,which is based on original greedy algorithm.The algorithm adopts neighborhood definition,the main idea is that to give a full array of all cities,and so full array of command to generate a loop with a greedy algorithm.Through the city exchange and Sub-sequence migration,it generates a better solution in the current neighborhood search.If the solution is found,it becomes the new current solution.Then,repeat the process.In the search process,Off-trap strategies are used to jump from local optimal solution and guide the search in promising directions.The results of the algorithm are compared to the Full Sub-path Ejection Algorithm（F-SEC） proposed by Rego.

关 键 词：旅行商问题 拟人算法 邻域搜索 子序列平移 跳坑策略 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]