结合局部优化的蚁群优化算法的研究与实现

Research and Implementation of Ant Colony Optimization Algorithm Combining with Local Optimization

蚁群算法是一种成功的启发式算法,但在解决TSP问题时存在着收敛速度慢和易陷入局部最优解的问题。本文针对这两个问题,提出了定期交流和模范带头学习模型,前者是在蚂蚁每走过一定城市后,进行学习交流,选出所走路径相对较短的蚂蚁进行信息素影响,从而加快总体的收敛速度;后者是当所有蚂蚁都旅行一圈后,选出最优秀的蚂蚁,在其走过的路径上释放大量信息素,对下一周期蚂蚁的旅行进行引导,避免陷入局部最优解。实验结果表明新算法在求解质量上比传统蚁群算法有了明显提高。本文也通过实验分析了蚂蚁数量等参数对算法性能的影响。

Ant colony algorithm is a successful heuristic algorithm, but it has two disadvantages in solving Traveling Salesman Problem （TSP）, that is slow convergence and easy to fall into local optima ion. In this paper, the authors propose a regular exchange model and an exemplary model of learning. The former is that each ant walking in certain cities, learning exchanges, the path chosen by the relatively short walk pheromone ant influence, thus speeding up the overall speed of convergence; the latter is that when all the ants are traveling around after selection of the most outstanding ants, release large amounts of pheromone on its path traversed for the next cycle of ants traveling to boot, to avoid falling into local optima. After comparison with the conventional ant colony algorithm found that the new algorithm has been significantly improved in the solution quality. The paper analyzes the influence of the parameters, such as ant population, on the algorithm performance.