基于二分法和控制信息素量的改进蚁群算法

Improved ant colony optimization based on dichotomy and pheromone control

为弥补蚁群算法易陷入局部最优、收敛速度较慢等不足,提出一种基于二分法和控制信息素量的改进蚁群算法。在每次迭代结束时,利用二分法放弃行走路程较远的半数蚁群的信息素,使收敛速度得到提高;利用3-opt局部优化方法提高解的精度;通过控制信息素量动态调整蚁群选择路径的概率,避免算法早熟;将改进的算法应用于旅行商问题。实验结果表明,该算法在寻优能力、可靠性、收敛速度以及稳定性方面均表现出明显的优越性。

With the purpose of improving the insufficient ant colony optimization algorithm,including easiness to sink into local optimization and low convergence speed,an improved algorithm based on dichotomy and controlling the amount of pheromone was proposed.The dichotomy was introduced into the iterative process,and the ant pheromone on the inferior path in the last half of each iteration was discarded to accelerate the convergence speed of the algorithm.The 3-opt local optimization was used to improve the accuracy of the solution.The path selection probability of ants was dynamically adjusted by controlling pheromone quantity to avoid premature algorithm.The improved method was applied to the traveling salesman problem.Experimental results show that the proposed method has significant superiorities in optimization ability,reliability,convergence speed and stability.