智能算法求解TSP问题的比较  

Comparison on solving TSP via intelligent algorithm

作　　者：张煜东[1] 吴乐南[1] 韦耿[1] 

机构地区：[1]东南大学信息科学与工程学院,南京210096

出　　处：《计算机工程与应用》2009年第11期11-15,共5页Computer Engineering and Applications

基　　金：国家自然科学基金No.60872075;国家高技术研究发展计划(863)No.2008AA01Z227;江苏省自然科学基金No.BK2007103;高等学校科技创新工程重大项目培育资金项目(No.706028)~~

摘　　要：目前TSP问题的求解方法不仅种类繁多,而且模型迥异。集中讨论求解TSP问题的智能算法,将其分为进化算法、Hopfield神经网络和自组织映射3类,对每类方法进行了原理研究、性能分析和优缺点比较。最后通过不同规模的实验进行验证,发现进化算法与局部搜索的组合求解TSP性能最好。今后的研究将集中在如何寻找更优的局部搜索。There are various kinds of methods with different corresponding models to solve the Traveling Salesman Problem （TSP）, among which this paper focuses on those intelligent algorithms and divides them into three types, namely evolutionary, algorithm,Hopfield network and self-organizing map.Their principles,performances,advantages and disadvantages are discussed respectively.Experiments with different scales demonstrate that the one combines evolutionary algorithm and local search outweighed others,which suggests that the future research should be concentrated on finding better local research methods.

关 键 词：旅行商问题 进化算法 蚁群算法 HOPFIELD网络 自组织映射 

分 类 号：TN911.73[电子电信—通信与信息系统]