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

通信学报

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

吴华锋1，陈信强1，毛奇凰1，张倩楠1，张寿春2

1.上海海事大学商船学院，上海 201306；2. 上海海事大学信息工程学院，上海 201306

出版日期:2013-04-25 发布日期:2013-04-15
基金资助:
国家自然科学基金资助项目(51279099)；上海市科学技术委员会基金资助项目(12ZR1412500)；上海市教委科研创新基金资助项目(13ZZ124)；上海市教育委员会和上海市教育发展基金会“曙光计划”基金资助项目(12SG40)

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

Online:2013-04-25 Published:2013-04-15
Supported by:
The National Natural Science Foundation of China (51279099); The Science and Technology Committee Foundation of Shanghai Municipality (12ZR1412500); The Innovation Program of Shanghai Municipality Education Commission (13ZZ124); “Shu Guang”Project of Shanghai Municipal Education Commission and Shanghai Education Development Foundation (12SG40)

摘要/Abstract

摘要： 针对蚁群算法收敛速度慢，容易陷入局部最优解的缺陷，提出了一种基于自然选择策略的改进型蚁群算法，改进后的算法利用自然选择中“优胜劣汰”的进化策略，对每次迭代的随机进化因子大于进化漂变阈值的路径信息素进行二次更新，增强满足进化策略路径上的信息素浓度，以加快算法的收敛速度；而随机进化因子的随机性增强了算法跳出局部最优解的概率。将提出的改进型蚁群算法求解经典的TSP问题，并通过实验证明了改进后的蚁群算法在最优解精度和收敛速度等方面均有所提高。

Abstract: 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.

吴华锋1，陈信强1，毛奇凰1，张倩楠1，张寿春2. 基于自然选择策略的蚁群算法求解TSP问题[J]. 通信学报.