求解旅行商问题的萤火虫遗传算法
|
摘要
为改善基本遗传算法陷入局部最优的问题,提出一种改进的遗传算法,即萤火虫遗传算法。根据萤火虫算法能够自动划分成子组的优点,将萤火虫个体引入遗传算法的变异算子,即萤火虫变异;为防止萤火虫难以跳出局部极值的缺陷,引入变邻域扰动机制,提出萤火虫遗传算法。运用旅行商问题对改进遗传算法进行计算机测试仿真,仿真结果表明,改进遗传算法在求解精度和收敛速度上优于基本遗传算法。
Aiming at the problem of local optimization of basic genetic algorithm,an improved genetic algorithm-firefly genetic algorithm was proposed.According to the advantage of firefly algorithm that subgroup can be automatically divided,the firefly individual was introduced into the mutation operator of the genetic algorithm,namely,the firefly mutation.To prevent the fireflies from jumping out of the local optimal,the variable neighborhood perturbation mechanism was introduced and the firefly genetic algorithm was proposed.The improved genetic algorithm was simulated by computer solving using traveling salesman problem.The results show that the improved genetic algorithm is better than the basic genetic algorithm in solving precision and convergence speed.
Aiming at the problem of local optimization of basic genetic algorithm,an improved genetic algorithm-firefly genetic algorithm was proposed.According to the advantage of firefly algorithm that subgroup can be automatically divided,the firefly individual was introduced into the mutation operator of the genetic algorithm,namely,the firefly mutation.To prevent the fireflies from jumping out of the local optimal,the variable neighborhood perturbation mechanism was introduced and the firefly genetic algorithm was proposed.The improved genetic algorithm was simulated by computer solving using traveling salesman problem.The results show that the improved genetic algorithm is better than the basic genetic algorithm in solving precision and convergence speed.
引文
[1]LIANG Xu,HUANG Ming.Modern intelligent optimization hybrid algorithm and its application[M].Beijing:Publishing House of Electronics Industry,2011:176-182(in Chinese)[梁旭,黄明.现代智能优化混合算法及其应用[M].北京:电子工业出版社,2011:176-182.]
[2]YI Yunfei,LIN Xiaodong,CAI Yongle.Improved particle swarm optimization algorithm for solving traving salesman problem[J].Computer Engineering and Design,2016,37(8):2195-2199(in Chinese).[易云飞,林晓东,蔡永乐.求解旅行商问题的改进粒子群算法[J].计算机工程与设计,2016,37(8):2195-2199.]
[3]WU Husheng,ZHANG Fengming,LI Hao,et al.Discrete wolf pack algorithm for traveling salesman problem[J].Control and Decision,2015,30(10):1861-1867(in Chinese).[吴虎胜,张凤鸣,李浩,等.求解TSP问题的离散狼群算法[J].控制与决策,2015,30(10):1861-1867.]
[4]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.]
[5]ZHANG Yong,CHEN Lin,XU Xiaolong,et al.Research on time optimal TSP based on hybrid PSO-GA[J].Application Research of Computers,2015,32(12):3613-3617(in Chinese).[张勇,陈玲,徐小龙,等.基于PSO-GA混合算法时间优化的旅行商问题研究[J].计算机应用研究,2015,32(12):3613-3617.]
[6]LI Zhiyong,MA Liang,ZHANG Huizhenl.Discrete bat algorithm for solving minimum ratio traveling salesman problem[J].Application Research of Computers,2015,32(2):356-359(in Chinese).[李枝勇,马良,张惠珍.求解最小比率旅行商问题的离散蝙蝠算法[J].计算机应用研究,2015,32(2):356-359.]
[7]Yang XS.Cuckoo search and firefly algorithm:Theory and applications[M].Berlin:Springer International Publishing,2014:1-26.
[8]Yang XS.Nature-inspired metaheuristic algorithms[M].Beckington:Luniver Press,2008:105-108.
[9]Vlachos M,Kollios G,Gunopulos D.Discovering similar multidimensional trajectories[C]//International Conference on Data Engineering.IEEE Computer Society,2002:673.
[10]DUAN Shaonan,DAI Shenghua.The application of discrete firefly algorithm the high-speed train operation adjustment[J].Computer Engineering and Applications,2018,54(15):209-213(in Chinese).[段少楠,戴胜华.离散萤火虫算法在高速列车运行调整中的应用[J].计算机工程与应用,2018,54(15):209-213.]
[11]ZHOU Peng.Heuristic ordered crossover operator for TSP[J].Computer Engineering and Design,2007,28(8):1896-1897(in Chinese).[周鹏.求解TSP的启发式顺序交叉算子[J].计算机工程与设计,2007,28(8):1896-1897.]
[12]标准TSP测试库[EB/OL].[2008-08-06].http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/(in Chinese).[TSPLIB[EB/OL].[2008-08-06].http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/.]
[13]WANG Ying,ZHANG Liyi,FEI Teng,et al.Chasoticsimulated annealing ant colony algorithm for TSP[J].Computer Engineering and Design,2016,37(4):1067-1070(in Chinese).[王迎,张立毅,费腾,等.求解TSP的带混沌扰动的模拟退火蚁群算法[J].计算机工程与设计,2016,37(4):1067-1070.]
[14]ZHENG Ming,ZHUO Mugui.Solution for traveling salesman problem with four vertices and three lines genetic algorithm[J].Computer Engineering and Applications,2017,53(14):148-154(in Chinese).[郑明,卓慕瑰.四点三线遗传算法求解旅行商问题[J].计算机工程与应用,2017,53(14):148-154.]
[2]YI Yunfei,LIN Xiaodong,CAI Yongle.Improved particle swarm optimization algorithm for solving traving salesman problem[J].Computer Engineering and Design,2016,37(8):2195-2199(in Chinese).[易云飞,林晓东,蔡永乐.求解旅行商问题的改进粒子群算法[J].计算机工程与设计,2016,37(8):2195-2199.]
[3]WU Husheng,ZHANG Fengming,LI Hao,et al.Discrete wolf pack algorithm for traveling salesman problem[J].Control and Decision,2015,30(10):1861-1867(in Chinese).[吴虎胜,张凤鸣,李浩,等.求解TSP问题的离散狼群算法[J].控制与决策,2015,30(10):1861-1867.]
[4]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.]
[5]ZHANG Yong,CHEN Lin,XU Xiaolong,et al.Research on time optimal TSP based on hybrid PSO-GA[J].Application Research of Computers,2015,32(12):3613-3617(in Chinese).[张勇,陈玲,徐小龙,等.基于PSO-GA混合算法时间优化的旅行商问题研究[J].计算机应用研究,2015,32(12):3613-3617.]
[6]LI Zhiyong,MA Liang,ZHANG Huizhenl.Discrete bat algorithm for solving minimum ratio traveling salesman problem[J].Application Research of Computers,2015,32(2):356-359(in Chinese).[李枝勇,马良,张惠珍.求解最小比率旅行商问题的离散蝙蝠算法[J].计算机应用研究,2015,32(2):356-359.]
[7]Yang XS.Cuckoo search and firefly algorithm:Theory and applications[M].Berlin:Springer International Publishing,2014:1-26.
[8]Yang XS.Nature-inspired metaheuristic algorithms[M].Beckington:Luniver Press,2008:105-108.
[9]Vlachos M,Kollios G,Gunopulos D.Discovering similar multidimensional trajectories[C]//International Conference on Data Engineering.IEEE Computer Society,2002:673.
[10]DUAN Shaonan,DAI Shenghua.The application of discrete firefly algorithm the high-speed train operation adjustment[J].Computer Engineering and Applications,2018,54(15):209-213(in Chinese).[段少楠,戴胜华.离散萤火虫算法在高速列车运行调整中的应用[J].计算机工程与应用,2018,54(15):209-213.]
[11]ZHOU Peng.Heuristic ordered crossover operator for TSP[J].Computer Engineering and Design,2007,28(8):1896-1897(in Chinese).[周鹏.求解TSP的启发式顺序交叉算子[J].计算机工程与设计,2007,28(8):1896-1897.]
[12]标准TSP测试库[EB/OL].[2008-08-06].http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/(in Chinese).[TSPLIB[EB/OL].[2008-08-06].http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/.]
[13]WANG Ying,ZHANG Liyi,FEI Teng,et al.Chasoticsimulated annealing ant colony algorithm for TSP[J].Computer Engineering and Design,2016,37(4):1067-1070(in Chinese).[王迎,张立毅,费腾,等.求解TSP的带混沌扰动的模拟退火蚁群算法[J].计算机工程与设计,2016,37(4):1067-1070.]
[14]ZHENG Ming,ZHUO Mugui.Solution for traveling salesman problem with four vertices and three lines genetic algorithm[J].Computer Engineering and Applications,2017,53(14):148-154(in Chinese).[郑明,卓慕瑰.四点三线遗传算法求解旅行商问题[J].计算机工程与应用,2017,53(14):148-154.]
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |