基于信息素更新和挥发因子调整的改进蚁群算法

Improved Ant Colony Optimization Algorithm Based on Pheromone Updating and Evaporation Factor Adjusting

为了改进基本蚁群算法容易导致算法停滞、陷入局部最优解和收敛速度较慢的问题,提出一种改进的蚁群算法,主要是将信息素局部更新和全局更新结合,增加各路径的被选择机会,避免算法停滞;另外,由于信息素挥发因子ρ的大小直接关系到算法的全局搜索能力和收敛速度,提出在算法的初期、中期和后期分别设置不同的ρ,以此增加算法的全局搜索能力,又能在一定程度上加快算法的收敛.改进算法的性能在Oliver 30和att 48问题上得到验证,本方法与基本蚁群算法相比要更优,收敛速度更快,体现了此种改进的有效性.

For overcoming the algorithm stagnation,local optimal solution and slow rate of convergence,this paper presents an improved ant colony optimization algorithm. The principal means is combining local and global dynamic pheromone and increasing the chance of be selected for each path to avoid algorithm stagnation. Besides,the pheromone evaporation factor plays a significant role in the capability of global searching and speed of convergence. The different value for this factor is set in early,middle and late stage so as to increase the search capability and accelerate the convergence. The experimental results for solving Oliver30 and att48 are proved to be effective. We conclude that the new algorithm has better result and faster convergence compared with the basic ant colony algorithm,which reflects the effectiveness of such improvements.