TSP的改进蚁群算法求解及其仿真研究  

Solution of TSP based on improved ant colony algorithm and its simulation

作　　者：杨再甫[1] 黄友锐[1] 曲立国[1] 葛平平[1] 

机构地区：[1]安徽理工大学电气与信息工程学院,安徽淮南232001

出　　处：《合肥工业大学学报（自然科学版）》2014年第8期928-932,共5页Journal of Hefei University of Technology：Natural Science

基　　金：国家自然科学基金资助项目(61073101;51274011;61300001)

摘　　要：蚂蚁数目是影响蚁群算法性能的重要参数,常规蚁群算法在求解TSP时易于陷入局部最优解。文章针对该问题,提出了一种蚂蚁数目动态改变的蚁群算法,即每次周游时的蚂蚁数目是在一个范围内随机取值,该改进算法借用遗传算法中的排序选择策略对每次遍历时的蚂蚁位置进行初始化;分别对常规蚁群算法的TSP求解和改进蚁群算法的TSP求解进行了原理阐述,并对2种算法求解TSP的结果进行了Matlab仿真。对比仿真结果表明,改进的算法在求解TSP时,能够有效地跳出局部最优解,并能很好地收敛,它比常规蚁群算法的性能要优。T he number of ants is an important parameter that affects the performance of ant colony al-gorithm .As the conventional ant colony algorithm for solving travelling salesman problem （TSP） is easy to fall into a local optimal solution ,an ant colony algorithm based on dynamic changes of the number of ants is proposed ,in which each traveling is to be with random number of ants in a certain range .Besides ,the ranking selection policy of genetic algorithm is used to initialize the location of ants each time when traveling .The theories of the conventional ant colony algorithm and the improved ant colony algorithm for solving TSP are both expatiated ,and the results of the mentioned algorithms for solving TSP are simulated by Matlab .The simulation results show that the performance of the im-proved algorithm is better than that of the conventional algorithm since the improved algorithm can ef-fectively jump out of local optimal solution and has better convergence performance .

关 键 词：常规蚁群算法 改进蚁群算法 旅行商问题 局部最优解 动态蚂蚁数目 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]