基于DACS3的改进蚁群算法求解TSP问题

蚁群算法是优化领域中新出现的一种仿生进化算法。该算法采用分布式并行计算机制,具有较强的鲁棒性,易与其他算法结合,但存在运行时间长,容易陷入局部最优解,导致出现停滞现象等缺点。针对蚁群算法,首先介绍其基本原理及不足之处。随后提出了一种改进算法,该算法在选择路径时仅考虑信息素强度,在信息素强度更新时采用基于3层动态信息素更新(Dynamic Ant Colony System with 3 level updates,DACS3)机制,更好地模仿了自然蚂蚁。最后通过仿真验证该算法,结果表明该算法可以取得较好的搜索效果。

An Analysis and Simulation of TSP with Improved Ant Colony Algorithm Based on DACS3

Ant colony algorithm is a new category of bionic algorithm in optimization field. Adopting parallel computation mechanism, ant colony algorithm has strong robustness and is easy to combine with other methods in optimization. But it has the shortcoming of long nmning time and easily getting into local best solution, and falling into stagnating state. Firstly, the basic principle and shortcoming of ant colony algorithm is introduced. Then, the paper proposes a new ant colony algorithm which only depends on the intensity of pheromone when selecting the path, adopts the system based on Dynamic Ant Colony System with 3 level updates when updating the pheromone, and better simulates the natural ants. Finally, the proposed algorithm is verified by simulation. The experiments demonstrate that the proposed algorithm can obtain good searching results.