一种结合局部搜索策略的求解TSP的演化算法  

A Solution to Traveling Salesman Problem by Using Local Evolutionary Algorithm

作　　者：王轩[1] 李元香[1] 

机构地区：[1]武汉大学计算机学院,武汉430079

出　　处：《计算机工程》2006年第9期16-18,共3页Computer Engineering

基　　金：国家自然科学基金重点资助项目(60473014);湖北省高等学校博士学科点专项科研基金资助项目(20030486049)

摘　　要：介绍了一种结合局部搜索策略的求解流动旅行商问题(TSP)的演化算法。该算法的主要思想是将局部搜索策略在邻域内搜索的快速性与演化方法在全局搜索上的鲁棒性结合起来,从而跳离局部最优。将该算法用于TSPLIB中部分TSP实例上的试验结果表明:与传统的各种求解TSP的演化方法相比,该算法在获得全局最优解的精确度上有了一定的改善。This paper introduces a new local evolutionary algorithm （LEA） and uses it to solve the traveling salesman problem. The algorithm incorporates speediness of local search algorithm in neighborhood search with robust quality of evolutionary algorithm in global search in order to obtain global optinmm. The experimental results show that the algorithm is of potential to obtain global optimum and it is more accurate than other evolutionary methods for the TSP.

关 键 词：演化算法 局部搜索 流动旅行商问题 

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