基于自适应更新策略的蚁群算法在TSP上的应用

Application of Ant Colony Algorithm Based on Adaptive Update Strategy in TSP

针对传统蚁群算法收敛性不好、易陷入局部最优的问题,提出了自适应更新策略的蚁群算法(A-daptive Update-Ant Colony System,AU-ACS),有效地平衡了种群多样性和算法收敛速度。算法前期通过自适应地改变信息素挥发值,由信息素挥发值动态约束信息素值,从而提高了种群多样性;运行后期奖励当前迭代最优路径的信息素,通过加大最优路径的相对引导作用,从而加快收敛速度;最后加入改进的子路径贡献度,根据阈值因子自适应调整局部最优路径的信息素,达到平衡种群多样性和收敛速度的目的。在与传统蚁群算法在旅行商问题(Travelling Salesman Problem,TSP)中对比表明,改进后算法求解的精度更高、稳定性增强。

The traditional ant colony algorithm has poor convergence and is easy to fall into local optimum.An adaptive update-ant colony system(AU-ACS)is proposed to effectively balance the population diversity and the algorithm convergence speed.In the early stage,the algorithm adaptively changes the pheromone volatility value and dynamically restricts the pheromone value by the pheromone volatility value.Therefore,the diversity of the population is improved.In the later stage of the operation,the pheromone of the optimal path is rewarded,the convergence speed is accelerated by increasing the relative guidance of the optimal path.Finally,the improved sub-path contribution is added,and the pheromone of the local optimal path is adaptively adjusted according to the threshold factor so as to achieve the purpose of balancing population diversity and convergence speed.Compared with the algorithm and traditional ant colony algorithm in traveling salesman problem(TSP),the improved algorithm has higher accuracy and stability.