改进的蚁群算法及其在Eil50问题上的检验  

Approach of Improving Ant Colony Algorithm and experimentation in the Eil50 of TSP

作　　者：李扬[1] 

机构地区：[1]沈阳化工大学数理系,辽宁沈阳110142

出　　处：《辽宁工程技术大学学报（自然科学版）》2010年第5期956-958,共3页Journal of Liaoning Technical University (Natural Science)

基　　金：国家自然科学基金资助项目(60674113)

摘　　要：针对蚁群算法在开始的时候由于信息素较少导致收敛速度慢的问题,提出了一种基于图形的加权蚁群算法,它利用蚁群算法最优路径的特点,对每个城市分别加权,然后从比较离散的点开始进行寻优。节省了在不可能构成最优路径上的计算时间,提高了运算速度。用TSP问题的Eil50检验的结果表明新算法提高了标准蚁群算法的效率和计算结果的质量。Aiming at solve the problems of ant colony algorithm that short of pheromone in the beginning and need longer computer time,this paper proposed a weighted ant colony algorithm based on graph. Using the character of the best route,it weighted for every cities and then from the discrete cities search for best route. New algorithm improved the searching strategy and consequently saved the computational time on the paths that can not be on the best route. It significantly improved the basic ant colony algorithm by accelerating the convergence speed and improved the precision. Simulation on its test in the Eil50 of TSP proved that the new algorithm improves both the efficiency and the quality of results of the standard ant colony algorithm.

关 键 词：蚁群算法 权 信息素 旅行商问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]