Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (28): 67-68.DOI: 10.3778/j.issn.1002-8331.2009.28.019

• 研究、探讨 • Previous Articles     Next Articles

Solving travelling salesman problem based on nearest neighbor strategy

WANG Tong,LI Yun-qiang   

  1. Department of Applied Mathematics,Electronic Technique Institute,PLA Information Engineering University,Zhengzhou 450004,China
  • Received:2008-05-26 Revised:2008-09-15 Online:2009-10-01 Published:2009-10-01
  • Contact: WANG Tong


汪 彤,李云强   

  1. 解放军信息工程大学 电子技术学院 应用数学系,郑州 450004
  • 通讯作者: 汪 彤

Abstract: According to the specific properties of TSP and the spirit of neighborhood search,the paper presents a new genetic algorithm based on the nearest neighbor strategy to solve TSP.First,calculate the nearest neighbor schemas according to the TSP and use the schemas to generate the initial population.Then introduce one of the schemas randomly into every generation.Simulation tests show that the new algorithm increases the convergence speed heavily and has better effect on the process of GAs.As the city number increases,its superiority appears more obviously.

Key words: nearest neighbor strategy, Genetic Algorithm(GA), Travelling Salesman Problem(TSP)

摘要: 根据TSP问题的特征信息并借鉴邻域搜索算法的有关思想,提出了一种基于近邻策略的TSP问题求解算法,该算法首先依据TSP问题的特殊性求出相应的近邻模式,再将近邻模式用于初始种群的生成,而后在进化过程中随机引入这类模式。该算法可以大大缩短遗传进程,提高进化效率。通过仿真实验,验证了该算法的有效性,并且随着城市数目的增加其优越性更为明显。

关键词: 近邻策略, 遗传算法, 旅行商问题

CLC Number: