Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (11): 11-15.DOI: 10.3778/j.issn.1002-8331.2009.11.004

• 博士论坛 • Previous Articles     Next Articles

Comparison on solving TSP via intelligent algorithm

ZHANG Yu-dong,WU Le-nan,WEI Geng   

  1. School of Information Science & Engineering,Southeast University,Nanjing 210096,China
  • Received:2008-11-18 Revised:2008-12-30 Online:2009-04-11 Published:2009-04-11
  • Contact: ZHANG Yu-dong

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

张煜东,吴乐南,韦 耿   

  1. 东南大学 信息科学与工程学院,南京 210096
  • 通讯作者: 张煜东

Abstract: 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.

Key words: Traveling Salesman Problem(TSP), evolutionary algorithm, ant colony algorithm, Hopfield network, self-organizing map

摘要: 目前TSP问题的求解方法不仅种类繁多,而且模型迥异。集中讨论求解TSP问题的智能算法,将其分为进化算法、Hopfield神经网络和自组织映射3类,对每类方法进行了原理研究、性能分析和优缺点比较。最后通过不同规模的实验进行验证,发现进化算法与局部搜索的组合求解TSP性能最好。今后的研究将集中在如何寻找更优的局部搜索。

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