新型蚁群算法在TSP问题中的应用  

Application of self-adaptive ant colony optimization in TSP

作　　者：张弛[1,2] 涂立[2] 王加阳[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083 [2]湖南城市学院信息科学与工程学院,湖南益阳413000

出　　处：《中南大学学报（自然科学版）》2015年第8期2944-2949,共6页Journal of Central South University:Science and Technology

基　　金：湖南省教育科学"十二五"规划课题(XJK014CGD013);益阳市科技计划项目(2014JZ52)~~

摘　　要：针对传统的蚂蚁算法容易出现早熟和停滞现象,提出一种新型蚂蚁算法(new ant colony algorithm,NACA),即将转移规则、全局信息素灾变规则和局部混合调整信息素规则。选择几个典型TSP问题进行实验。研究结果表明:新型蚂蚁算法一方面提高了算法种群的多样性,同时将轮盘赌算子利用到城市转移规则中,有利于提高算法的收敛速度;另一方面,将种群个体的差分信息应用于局部信息素更新规则中,有利于搜索全局解;最后灾变算子避免算法陷入局部最优,而达到全局最优。新型的蚁群算法具有更强的搜索全局最优解的能力以及更好的稳定性和收敛性,同时为解决其他优化问题提供新的思路。Considering that there exists precocious and stagnation behavior phenomenon about the traditional ant algorithm, a new ant colony algorithm（NACA） was proposed, i.e. the transition rule, convulsions rule of global pheromones and the mixing adjustment rule of local pheromones were mixed. The results show that on one hand, NACA enhances genetic algorithms population diversity and at the same time the roulette operator is used in translative rules, whch is beneficial to improving the convergence speed. On the other hand, the individual differential information is used in the updated rule of local pheromones, which is good for searching the global solution. Finally, the cataclysm operator avoids falling into local optimum, and leads to reach the global optimum. NACA has stronger ability to search the global optimal solution and better stability and astringency. It also provides a new idea for solving other combinational optimization problems.

关 键 词：蚁群算法(ACA) 轮盘赌 信息素 差分演化 灾变 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]