基于改进蚁群算法的TSP问题研究
|
摘要
蚁群算法作为解决TSP中组合优化问题方案,其搜索路径能力较其它算法优异,但传统蚁群算法的选取策略较随机,导致进化速度慢。为了优化传统蚁群算法速度较慢、过早收敛以致停滞现象,针对概率选取公式随机搜索下一节点,以延缓其收敛速度。对信息素调节公式进行更新以提高蚁群的搜索能力。实验结果表明,改进算法在最短路径、平均路径和搜索最短路径时间上较蚁群算法提高很大,改进的蚁群算法能有效提高算法的收敛速度和搜索能力。
The ant colony algorithm in solving TSP as a combinatorial optimization problem,its ability to search path than other algorithms in terms of a better,but the traditional ant colony algorithm is a random selection of strategy,lead to evolution slower.In order to optimize the speed of the traditional ant colony algorithm,the speed of the algorithm has been slow to stop.According to the probability selection formula,we randomly searched the next city,so we reintroduced the formula to delay its convergence rate.Secondly,the adjustment formula of pheromone is updated to improve the search ability of ant colony.Experiments show that improved algorithm in the shortest path,the average shortest path and the search path time than ant colony algorithm is improved greatly,which confirmed that the proposed algorithm can effectively improve the convergence speed and search ability of the algorithm.
The ant colony algorithm in solving TSP as a combinatorial optimization problem,its ability to search path than other algorithms in terms of a better,but the traditional ant colony algorithm is a random selection of strategy,lead to evolution slower.In order to optimize the speed of the traditional ant colony algorithm,the speed of the algorithm has been slow to stop.According to the probability selection formula,we randomly searched the next city,so we reintroduced the formula to delay its convergence rate.Secondly,the adjustment formula of pheromone is updated to improve the search ability of ant colony.Experiments show that improved algorithm in the shortest path,the average shortest path and the search path time than ant colony algorithm is improved greatly,which confirmed that the proposed algorithm can effectively improve the convergence speed and search ability of the algorithm.
引文
[1]孙文彬,王江.一种基于遗传算法的TSP问题多策略优化求解方法[J].地理与地理信息科学,2016,32(4):1-4.
[2]林冬梅,王东,李娅.一种求解多旅行商问题双层降解混合算法[J].计算机应用研究,2011,28(8):2876-2879.
[3]DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems Man&Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man&Cybernetics Society,1996,26(1):29-41.
[4]徐精明,曹先彬,王煦法.多态蚁群算法[J].中国科学技术大学学报,2005,35(1):59-65.
[5]王启明,李玮瑶.基于改进量子蚁群算法的TSP求解问题研究[J].微处理机,2015(3):31-33.
[6]张开碧,张洋川,万素波,等.一种改进的竞争型蚁群算法在TSP问题中的应用[J].计算机与数字工程,2016,44(3):396-399.
[7]GAMBARDELLA L M,DORIGO M Q.A Reinforcement learning approach to the traveling salesman problem-machine learning proceedings 1995-ant[J].Machine Learning Proceedings,2000,170(3):252-260.
[8]ROSENKRANTZ D J,STEARNS R E,II P M L.An analysis of several heuristics for thetraveling salesman problem[J].Siam Journal on Computing,1977,6(3):563-581.
[9]冯月华.一种求解TSP问题的改进蚁群算法[J].电子测试,2014(8):38-40.
[10]YOSHIKAWA M,TERAI H.Architecture for high-speed ant colony optimization[C].IEEE International Conference on Information Reuse and Integration.IEEE,2007:1-5.
[2]林冬梅,王东,李娅.一种求解多旅行商问题双层降解混合算法[J].计算机应用研究,2011,28(8):2876-2879.
[3]DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems Man&Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man&Cybernetics Society,1996,26(1):29-41.
[4]徐精明,曹先彬,王煦法.多态蚁群算法[J].中国科学技术大学学报,2005,35(1):59-65.
[5]王启明,李玮瑶.基于改进量子蚁群算法的TSP求解问题研究[J].微处理机,2015(3):31-33.
[6]张开碧,张洋川,万素波,等.一种改进的竞争型蚁群算法在TSP问题中的应用[J].计算机与数字工程,2016,44(3):396-399.
[7]GAMBARDELLA L M,DORIGO M Q.A Reinforcement learning approach to the traveling salesman problem-machine learning proceedings 1995-ant[J].Machine Learning Proceedings,2000,170(3):252-260.
[8]ROSENKRANTZ D J,STEARNS R E,II P M L.An analysis of several heuristics for thetraveling salesman problem[J].Siam Journal on Computing,1977,6(3):563-581.
[9]冯月华.一种求解TSP问题的改进蚁群算法[J].电子测试,2014(8):38-40.
[10]YOSHIKAWA M,TERAI H.Architecture for high-speed ant colony optimization[C].IEEE International Conference on Information Reuse and Integration.IEEE,2007:1-5.