基于莱维飞行的改进蚁群算法求解TSP问题
|
摘要
蚁群算法存在易于限于局部最优解、迭代易停滞、计算量大以及搜索时间较长等缺陷。针对此问题,提出一种莱维飞行模式与蚁群算法的信息素更新方式相结合的算法。利用莱维飞行的随机搜索模式寻找全局最优解,即小步长和偶尔的大步长搜索相结合的搜索模式,大步长搜索可以提高蚁群算法的收敛速度,小步长搜索有利于提高解的质量,寻到全局最优解。对TSP问题的仿真结果表明,所提算法有效地提高了解的精度并加快了收敛速度,寻优效果更优。
Ant colony algorithm(ACA)has some demerits,such as relapsing into local extremum,slow convergence velocity and low convergence precision.The Levy flight mode and the pheromone updating method of ant colony algorithm were combined to solve the problems raised above.The occasional large-stride search of Levy flight,that was the combination of small-step search and occasional large-step search,was used to find the best solution to obtain the global optimum.The occasional large-step search of Levy flight improved the convergence speed of the algorithm,while the small-step search helped to improve the quality of the solution.The simulations for TSP problem show that the Levy ACA has better optimization effect at higher convergence speed.
Ant colony algorithm(ACA)has some demerits,such as relapsing into local extremum,slow convergence velocity and low convergence precision.The Levy flight mode and the pheromone updating method of ant colony algorithm were combined to solve the problems raised above.The occasional large-stride search of Levy flight,that was the combination of small-step search and occasional large-step search,was used to find the best solution to obtain the global optimum.The occasional large-step search of Levy flight improved the convergence speed of the algorithm,while the small-step search helped to improve the quality of the solution.The simulations for TSP problem show that the Levy ACA has better optimization effect at higher convergence speed.
引文
[1]YU Yingying,CHEN Yan,LI Taoying.Improved genetic algorithm for solving TSP[J].Control and Decision,2014,29(8):1483-1488(in Chinese).[于莹莹,陈燕,李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策,2014,29(8):1483-1488.]
[2]YAO Minghai,WANG Na,ZHAO Lianpeng.Improved simulated annealing algorithm and genetic algorithm for TSP[J].Computer Engineering and Applications,2013,49(14):60-65(in Chinese).[姚明海,王娜,赵连朋.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用,2013,49(14):60-65.]
[3]Kan JM,Zhang Y.Application of an improved ant colony optimization on generalized traveling salesman problem[J].Energy Procedia,2012,17(2):319-325.
[4]Mavrovouniotis M,Muller FM,Yang S.Ant colony optimization with local search for dynamic traveling salesman problems[J].IEEE Transactions on Cybernetics,2016,47(7):1743-1756.
[5]ZHANG Peng,XU Xiaoxu.Simulation research on global path planning based on improved ant colony algorithm[J].Aeronautical Computing Technique,2013,43(6):1-5(in Chinese).[张鹏,徐晓旭.改进型蚁群算法的全局路径规划仿真研究[J].航空计算技术,2013,43(6):1-5.]
[6]WANG Min.Solving travelling salesman problem by adaptive ant colony optimization method based on information weight factor[J].China Science Paper,2015,10(5):573-576(in Chinese).[王敏.基于信息权重自适应蚁群算法求解TSP问题[J].中国科技论文,2015,10(5):573-576.]
[7]LI Qing,ZHANG Chao,CHEN Peng,et al.Improved ant colony optimization algorithm based on particle swarm optimization[J].Control and Decision,2013,28(6):873-878(in Chinese).[李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(6):873-878.]
[8]GE Bin,HAN Jianghong,WEI Zhen,et al.Dynamic adaptive ant colony optimization algorithm for min-max vehicle routing problem[J].Pattern Recognition and Artificial Intelligence,2015,28(10):930-938(in Chinese).[葛斌,韩江洪,魏臻,等.最小最大车辆路径问题的动态自适应蚁群优化算法[J].模式识别与人工智能,2015,28(10):930-938.]
[9]HUANG Yongqing,YANG Fan,ZHANG Junling,et al.An interactive max-min ant algorithm[J].Computer Engineering,2012,38(20):128-131(in Chinese).[黄永青,杨凡,张俊岭,等.一种交互式最大最小蚂蚁算法[J].计算机工程,2012,38(20):128-131.]
[10]YU Jiapeng, WANG Cheng’en, WANG Jianxi.Assembly sequence planning based on max-min ant colony system[J].Journal of Mechanical Engineering,2012,48(23):152-166(in Chinese).[于嘉鹏,王成恩,王健熙.基于最大-最小蚁群系统的装配序列规划[J].机械工程学报,2012,48(23):152-166.]
[11]Zaw MM,Mon EE.Web document clustering using cuckoo search clustering algorithm based on levy flight[J].International Journal of Innovation&Applied Studies,2013,4(1):263-281.
[12]WANG Qingxi,GUO Xiaobo.Particle swarm optimization algorithm based on Levy flight[J].Application Research of Computers,2016,33(9):2588-2591(in Chinese).[王庆喜,郭晓波.基于莱维飞行的粒子群优化算法[J].计算机应用研究,2016,33(9):2588-2591.]
[13]LI Rongyu,WANG Ying.Improved particle swarm optimization based on Lévy flights[J].Journal of System Simulation,2017,29(8):1685-1691(in Chinese).[李荣雨,王颖.基于莱维飞行的改进粒子群算法[J].系统仿真学报,2017,29(8):1685-1691.]
[14]LIU Xiaolong,NING Qing,ZHAO Chengping,et al.Bird swarm algorithm based on levy flight[J].Computer Measurement&Control,2016,24(12):194-197(in Chinese).[刘晓龙,宁芊,赵成萍,等.基于莱维飞行的鸟群优化算法[J].计算机测量与控制,2016,24(12):194-197.]
[15]ZHU Xiao’en,HAO Xin,XIA Shunren,et al.Feature selection algorithm based on Levy Flight[J].Journal of Zhejiang University(Engineering Science),2013,47(4):638-643(in Chinese).[朱晓恩,郝欣,夏顺仁,等.基于Levy Flight的特征选择算法[J].浙江大学学报(工学版),2013,47(4):638-643.]
[2]YAO Minghai,WANG Na,ZHAO Lianpeng.Improved simulated annealing algorithm and genetic algorithm for TSP[J].Computer Engineering and Applications,2013,49(14):60-65(in Chinese).[姚明海,王娜,赵连朋.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用,2013,49(14):60-65.]
[3]Kan JM,Zhang Y.Application of an improved ant colony optimization on generalized traveling salesman problem[J].Energy Procedia,2012,17(2):319-325.
[4]Mavrovouniotis M,Muller FM,Yang S.Ant colony optimization with local search for dynamic traveling salesman problems[J].IEEE Transactions on Cybernetics,2016,47(7):1743-1756.
[5]ZHANG Peng,XU Xiaoxu.Simulation research on global path planning based on improved ant colony algorithm[J].Aeronautical Computing Technique,2013,43(6):1-5(in Chinese).[张鹏,徐晓旭.改进型蚁群算法的全局路径规划仿真研究[J].航空计算技术,2013,43(6):1-5.]
[6]WANG Min.Solving travelling salesman problem by adaptive ant colony optimization method based on information weight factor[J].China Science Paper,2015,10(5):573-576(in Chinese).[王敏.基于信息权重自适应蚁群算法求解TSP问题[J].中国科技论文,2015,10(5):573-576.]
[7]LI Qing,ZHANG Chao,CHEN Peng,et al.Improved ant colony optimization algorithm based on particle swarm optimization[J].Control and Decision,2013,28(6):873-878(in Chinese).[李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,28(6):873-878.]
[8]GE Bin,HAN Jianghong,WEI Zhen,et al.Dynamic adaptive ant colony optimization algorithm for min-max vehicle routing problem[J].Pattern Recognition and Artificial Intelligence,2015,28(10):930-938(in Chinese).[葛斌,韩江洪,魏臻,等.最小最大车辆路径问题的动态自适应蚁群优化算法[J].模式识别与人工智能,2015,28(10):930-938.]
[9]HUANG Yongqing,YANG Fan,ZHANG Junling,et al.An interactive max-min ant algorithm[J].Computer Engineering,2012,38(20):128-131(in Chinese).[黄永青,杨凡,张俊岭,等.一种交互式最大最小蚂蚁算法[J].计算机工程,2012,38(20):128-131.]
[10]YU Jiapeng, WANG Cheng’en, WANG Jianxi.Assembly sequence planning based on max-min ant colony system[J].Journal of Mechanical Engineering,2012,48(23):152-166(in Chinese).[于嘉鹏,王成恩,王健熙.基于最大-最小蚁群系统的装配序列规划[J].机械工程学报,2012,48(23):152-166.]
[11]Zaw MM,Mon EE.Web document clustering using cuckoo search clustering algorithm based on levy flight[J].International Journal of Innovation&Applied Studies,2013,4(1):263-281.
[12]WANG Qingxi,GUO Xiaobo.Particle swarm optimization algorithm based on Levy flight[J].Application Research of Computers,2016,33(9):2588-2591(in Chinese).[王庆喜,郭晓波.基于莱维飞行的粒子群优化算法[J].计算机应用研究,2016,33(9):2588-2591.]
[13]LI Rongyu,WANG Ying.Improved particle swarm optimization based on Lévy flights[J].Journal of System Simulation,2017,29(8):1685-1691(in Chinese).[李荣雨,王颖.基于莱维飞行的改进粒子群算法[J].系统仿真学报,2017,29(8):1685-1691.]
[14]LIU Xiaolong,NING Qing,ZHAO Chengping,et al.Bird swarm algorithm based on levy flight[J].Computer Measurement&Control,2016,24(12):194-197(in Chinese).[刘晓龙,宁芊,赵成萍,等.基于莱维飞行的鸟群优化算法[J].计算机测量与控制,2016,24(12):194-197.]
[15]ZHU Xiao’en,HAO Xin,XIA Shunren,et al.Feature selection algorithm based on Levy Flight[J].Journal of Zhejiang University(Engineering Science),2013,47(4):638-643(in Chinese).[朱晓恩,郝欣,夏顺仁,等.基于Levy Flight的特征选择算法[J].浙江大学学报(工学版),2013,47(4):638-643.]