一种求解旅行商问题的改进蚁群算法  

An Improved Ant Colony Algorithm for Traveling Salesman Problems

作　　者：王沛栋[1,2] 唐功友[1] 杨熙鑫[1] 李扬[1] 

机构地区：[1]中国海洋大学信息科学与工程学院,山东青岛266100 [2]青岛市产品质量监督检验所,山东青岛266101

出　　处：《中国海洋大学学报（自然科学版）》2013年第1期93-97,共5页Periodical of Ocean University of China

基　　金：国家自然科学基金项目(61074092);山东省自然科学基金项目(ZR2010FM019);山东省科技发展计划项目(2008GGB01192)资助

摘　　要：提出一种求解旅行商问题的改进蚁群算法。该算法在信息素更新过程中,利用信息素局部更新和全局动态更新结合的方法,使得当前最优路径上的信息素值能够动态地调配,避免算法陷入停滞状态;在局部搜索过程中,仅对部分走出更优路径的售货员使用2-opt方法,加快了最优解的收敛速度。仿真实验验证了算法的有效性,与其它算法相比,本文算法在解的质量和收敛速度上都显示出了良好的性能。An improved ant colony system algorithm was proposed for traveling salesman problems （TSPs）. In the process of phenomenon update, by using a method of combination of local phenomenon update and global dynamic phenomenon update, the distribution of phenomenon was dynamicly adjusted on the current optimal route. In the process of local research, the method of 2-opt was only used for partial salesmen with shorter tours, enhancing the convergence speed. The simulation results demonstrate the proposed algorithm works well and efficient.

关 键 词：蚁群算法 路径规划 信息素动态更新 TSP中图法 

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