Abstract: In ant colony algorithm, how to effectively deal with the contradiction between the convergence speed and the precocity and stagnation has been a difficult problem. A parameter adaptive ant colony system is proposed by introducing the crowding degree to strengthen the coordination and cooperation between ants in the search process. In the presented ant colony algorithm, it adopts the proactive strategies to avert the precocity and stagnation in advance, and embeds the crowding degree into the state transition and the pheromone update. The parameter in the local pheromone update adaptively changes with the local search state, and the parameter in the global pheromone update adaptively changes with the global search state. These make its global searching ability enhance remarkably. At the same time a simple and efficient mutation algorithm is adopted to accelerate convergence. Experimental results show that the presented algorithm has much higher quality and stability and convergence speed than that of classical ant colony algorithm

Key words: ant colony system, parameter adaptive, mutation algorithm, traveling salesman problem

摘要： 在蚁群算法中，如何有效处理加速收敛和出现早熟、停滞现象的矛盾一直是一个困难的问题。通过引入拥挤度来加强搜索过程中蚂蚁之间的协调和配合，提出了一种基于拥挤度的参数自适应蚁群算法。该算法采用提前主动预防早熟的策略，将拥挤度嵌入到蚁群算法的状态转移和信息素更新过程中，让局部信息素更新参数随局部搜索状态自适应地调整，全局信息素更新参数随全局搜索状态自适应地调整，大大提高了算法全局搜索能力和自适应能力，同时采用了一种简单有效的变异算法来加快收敛速度。用多个TSPLIB范例进行比较实验，结果表明，改进算法无论是求解质量、稳定性以及收敛速度都有显著提高。

关键词: 蚁群系统, 参数自适应, 变异算法, 旅行商问题