基于自然选择策略的蚁群算法求解TSP问题  

Improved ant colony algorithm based on natural selection strategy for solving TSP problem

作　　者：吴华锋[1] 陈信强[1] 毛奇凰[1] 张倩楠[1] 张寿春[2] 

机构地区：[1]上海海事大学商船学院,上海201306 [2]上海海事大学信息工程学院,上海201306

出　　处：《通信学报》2013年第4期165-170,共6页Journal on Communications

基　　金：国家自然科学基金资助项目(51279099);上海市科学技术委员会基金资助项目(12ZR1412500);上海市教委科研创新基金资助项目(13ZZ124);上海市教育委员会和上海市教育发展基金会"曙光计划"基金资助项目(12SG40)~~

摘　　要：针对蚁群算法收敛速度慢,容易陷入局部最优解的缺陷,提出了一种基于自然选择策略的改进型蚁群算法,改进后的算法利用自然选择中"优胜劣汰"的进化策略,对每次迭代的随机进化因子大于进化漂变阈值的路径信息素进行二次更新,增强满足进化策略路径上的信息素浓度,以加快算法的收敛速度;而随机进化因子的随机性增强了算法跳出局部最优解的概率。将提出的改进型蚁群算法求解经典的TSP问题,并通过实验证明了改进后的蚁群算法在最优解精度和收敛速度等方面均有所提高。To solve basic ant colony algorithm＇s drawbacks of low convergence rate, easiness of trapping in local optimal solution, an improved ant colony algorithm based on natural selection was proposed. The improved algorithm employed evolution strategy of survival the fittest in natural selection to enhance pheromones in paths whose random evolution factor was bigger than threshold of evolution drift factor in each process of iteration. It could accelerate convergence rate effectively. Besides the introduction of random evolution factor reduced probability of trapping local optimal solution notably. The proposed algorithm was applied to classic TSP problem to find better solution for TSP. Simulation results depict the improved algorithm has better optimal solution and higher convergence rate.

关 键 词：蚁群算法 自然选择 TSP 随机进化因子 进化漂变阈值 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]