一种动态挥发率和启发式修正的蚁群优化算法

An Ant Colony Optimization Algorithm Based on Dynamic Evaporation Rate and Amended Heuristic

群体智能的研究为分布式控制和优化提供了更好的方法,以蚁群算法为代表的群体智能已经得到了大量的研究,并广泛应用于组合优化领域.但是在求解组合优化问题特别是在求解规模较大的问题时,收敛速度慢、易于停滞等现象仍然制约算法的广泛应用.为此,提出了DEAHACO算法,该算法提出动态挥发率机制,用以更好地平衡求解效率和求解质量之间的矛盾,避免算法陷入局部最优;同时,为了加快算法的收敛速度,对启发式信息进行了重新定义,以指导算法快速收敛;最后,引入了边界对称变异策略对迭代结果进行对称变异,既提高了变异效率,也改进了变异质量.实验表明,该算法与其他算法相比,其收敛速度提高了20%以上,同时算法在其他一些经典的TSP问题上也表现出很好的性能.

Research on swarm intelligence provides a better way for distributed control and optimization.Much study has been done on swarm intelligence such as ACO（ant colony optimization）,and many applications also have been made in the field of combinatorial optimization.However,when solving combinatorial optimization problems,especially those problems with large scale,slow convergence and easy stagnation still restrain the algorithms being much more widely used.The DEAHACO algorithm is presented,in which a mechanism of dynamic evaporation rate is used to achieve better balance between solution efficiency and solution quality,avoiding algorithm falling into local optimum.To speed up the convergence of the algorithm,we redefine the heuristic information to guide the algorithm converge fast.A boundary symmetric mutation strategy is introduced to get variation of iteration results symmetrically,which not only enhances the mutation efficiency,but also improves the mutation quality.Experimental results show that the DEAHACO algorithm has better performance than other algorithm,and its convergence rate increases by 20% or more.Furthermore,the DEAHACO algorithm in other classic TSP instances also showes good performance.