计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (10): 32-34.

• 理论研究、研发设计 • 上一篇    下一篇

一种基于优质边求解TSP的蚁群算法

胡银厚,王世卿   

  1. 郑州大学 信息工程学院,郑州 450052
  • 出版日期:2013-05-15 发布日期:2013-05-14

Ant colony algorithm based on quality edge to solve TSP

HU Yinhou, WANG Shiqing   

  1. School of Information Engineering, Zhengzhou University, Zhengzhou 450052, China
  • Online:2013-05-15 Published:2013-05-14

摘要: 应用蚁群算法求解旅行商问题时发现,算法易陷入局部最优解而停滞,并导致其探索新解能力的降低。提出了一种基于优质边的求解方法,根据算法运行过程中的相关信息选取优质边,在停滞时调整优质边上的信息素;使用改进的选路规则将蚂蚁的路径选择尽可能限制在优质边中,从而改进蚂蚁构造解的质量以增强算法的探索能力。实验结果表明,改进的策略是合理有效的。

关键词: 蚁群优化, 旅行商问题, 最大-最小蚁群算法, 智能计算, 优质边

Abstract: On the research of ant colony algorithm to the Traveling Salesman Problem shows that it can easily fall into the local optimal solution, leading to lower ability to explore better solutions. This paper proposes a solving approach which based on the quality edge to solve this problem. Choose the quality edge according to the information from the algorithm. While the algorithm is in stagnation, adjust the pheromone on quality edge, it will enhance the ability of algorithm to explore better solutions. At the same time, improved routing rules will limit the ant to choose the quality edge as much as possible, thereby improving the quality of solution. The?experiment results show that?the?improved?solution strategy?is reasonable and effective.

Key words: Ant Colony Optimization(ACO), Traveling Salesman Problem(TSP), Max-Min Ant System(MMAS), intelligent computation, quality edge