一种改进的蚁群算法及其在TSP中的应用

蚁群算法是一种求解复杂组合优化问题的新的拟生态算法,也是一种基于种群的启发式仿生进化算法,属于随机搜索算法的一种,并用于较好地解决TSP问题.然而此算法也有它自己的缺陷,如易于陷入局部优化、搜索时间长等.通过对基本蚁群算法的介绍及相关因素的分析,提出了一种改进的蚁群算法,用于解决TSPLAB问题的10个问题,并与参考文献中的F-W、NCSOM、ASOM算法进行比较,计算机仿真结果表明了改进算法的有效性.如利用改进的蚁群算法解决lin105问题,其最优解为14382.995933(已知最优解为14379),相对误差是0.0209%,计算出的最小值几乎接近于已知最优解.

A Improved Ant Colony Alogorithm and Its Application in TSP

Ant colony algorithm is a kind of new ecological system algorithm used to solve complicated combinatorial optimizational problems,and it is a kind of heuristic evolutionary algorithm based on population,which belongs to the random search algorithm 'and is used to solve TSP problems.However,this algorithm also has its own defects,such as it is easy to fall into local optimization and searchs for a long time.Based on the basic ant colony algorithm introduced and the factors related to analyzed,this paper proposes an improved ant colony algorithm for solvling 10 questions from TSPLIB,and it is compared with the F-W,NCSOM and ASOM algorithms form references,the results of computer simulation show the validity of the improved algorithm.For example,in the linl05 problem,the optimal solution is 14382.995933,which is calculated by the improved algorithm(the known optimal solution is 14379),the relative error is 0.0209%,the calculated minimum value is almost close to the known optimal solution.