计算机与现代化 ›› 2012, Vol. 203 ›› Issue (7): 14-16,2.doi: 10.3969/j.issn.1006-2475.2012.07.004

• 算法设计与分析 • 上一篇    下一篇

求解旅行商问题的自适应蚁群算法

梁德赛1,梁高业2,韦思庆3   

  1. 1.钦州学院数学与计算机科学学院,广西钦州535000;2.武利中学,广西钦州535427;3.钦州学院海洋学院,广西钦州535000
  • 收稿日期:2012-06-19 修回日期:1900-01-01 出版日期:2012-08-10 发布日期:2012-08-10

Solving Traveling Salesman Problem by an Adaptive Ant Colony Algorithm

LIANG De-sai1, LIANG Gao-ye2, WEI Si-qing3

  

  1. 1.School of Mathematics and Computer Science, Qinzhou University, Qinzhou 535000, China; 2.Wuli Middle School, Qinzhou 535427, China; 3.School of Ocean, Qinzhou University, Qinzhou 535000, China
  • Received:2012-06-19 Revised:1900-01-01 Online:2012-08-10 Published:2012-08-10

摘要: 传统蚁群算法求解TSP问题,收敛速度慢,容易陷入局部最优。针对蚁群算法的不足,对算法加以改进,本文提出一种自适蚁群算法,在搜索初期,信息素挥发系数较大,使搜索速度加快;在迭代后期,信息素系数减小到一个恒定值,使算法转向精细寻优。仿真结果表明,改进的算法有较快的收敛速度和较高的精度。

关键词: 旅行商问题, 自适应蚁群算法, 搜索, 收敛速度, 精度

Abstract: The traditional ant colony algorithm for TSP problem, convergence speed is slower and is easy to fall into local optimum. Aiming at the deficiency of traditional ant colony algorithm, the algorithm is improved, a kind of new self adaptive ant colony algorithm is put forward. Early in the search, pheromone volatilization coefficient is bigger then decreases to a constant value, ensure to search quickly at the early iteration stage and to search accurately at the late stage. The simulation results show that, the improved algorithm has faster convergence speed and higher precision.

Key words: traveling salesman problem, adaptive ant colony algorithm, search, rate of convergence, precision

中图分类号: