基于萤火虫算法的最大值最小化着色旅行商问题的求解
|
摘要
针对遗传算法在求解最大值最小化着色旅行商问题(min-max colored traveling salesman problem, MM-CTSP)中存在解质量欠佳、耗时多和收敛速度慢等问题,提出基于萤火虫算法的MM-CTSP求解方法,采用直接路径编码方式提高解码效率;采用翻转变异策略更新个体,提高算法的收敛速度.结果表明,该方法的解质量高,耗时少,收敛速度快,且城市规模越大其优势越明显.
A genetic algorithm(GA) has some problems in solving min-max colored traveling salesman problem(MM-CTSP), e.g. poor solution quality, time consuming and low convergence. To avoid the issues, a solution method using firefly algorithm(FA) is proposed. It utilizes direct-route encoding to improve the decoding efficiency and uses an inversion mutation strategy for the individual update to promote the algorithm convergence. Finally, FA is compared with GA with respect to solution quality, time consumption and convergence. The results show that FA outperforms GA, the larger the city size, the greater the advantages of FA.
A genetic algorithm(GA) has some problems in solving min-max colored traveling salesman problem(MM-CTSP), e.g. poor solution quality, time consuming and low convergence. To avoid the issues, a solution method using firefly algorithm(FA) is proposed. It utilizes direct-route encoding to improve the decoding efficiency and uses an inversion mutation strategy for the individual update to promote the algorithm convergence. Finally, FA is compared with GA with respect to solution quality, time consumption and convergence. The results show that FA outperforms GA, the larger the city size, the greater the advantages of FA.
引文
[1] LI Jun,ZHOU Mengchu,SUN Qirui,et al.Colored traveling salesman problem [J].IEEE Trans Cybern,2015,45(11):2390-2401.
[2] LI Jun,SUN Qirui,ZHOU Mengchu,et al.Colored traveling salesman problem and solution [J].IFAC Proceed Vol,2014,47(3):9575-9580.
[3] LI Jun,MENG Xianghu,ZHOU Mengchu,et al.A two-stage approach to path planning and collision avoidance of multibridge machining systems [J].IEEE Trans Syst Man & Cybern Syst,2017,47(7):1039-1049.
[4] MENG Xianghu,LI Jun,DAI Xing,et al.Variable neighborhood search for a colored traveling salesman problem [J].IEEE Trans Intell Transp Syst,2018,99:1-9.
[5] DONG Xueshi,CAI Yongle,WANG Yufeng,et al.Discrete IT? algorithm to the coloured travelling salesman problem [J].Int J Wirel & Mob Comput,2016,11(2):157-165.
[6] PANDIRI V,SINGH A.A swarm intelligence approach for the colored traveling salesman problem [J].Appl Intell,2018,48(11):4412-4428.
[7] 代星.最大值最小化着色旅行商问题的研究及应用 [D].南京:东南大学,2017.
[8] 王艳.改进的萤火虫算法及其应用研究 [D].西安:西安理工大学,2018.
[9] SAYADI M K,RAMEZANIAN R,GHAFFARINASAB N.A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems [J].Int J Indust Engin Comput,2010,1(1):1-10.
[10] 于宏涛,高立群,韩希昌.求解旅行商问题的离散人工萤火虫算法 [J].华南理工大学学报(自然科学版),2015,43(1):126-131.
[2] LI Jun,SUN Qirui,ZHOU Mengchu,et al.Colored traveling salesman problem and solution [J].IFAC Proceed Vol,2014,47(3):9575-9580.
[3] LI Jun,MENG Xianghu,ZHOU Mengchu,et al.A two-stage approach to path planning and collision avoidance of multibridge machining systems [J].IEEE Trans Syst Man & Cybern Syst,2017,47(7):1039-1049.
[4] MENG Xianghu,LI Jun,DAI Xing,et al.Variable neighborhood search for a colored traveling salesman problem [J].IEEE Trans Intell Transp Syst,2018,99:1-9.
[5] DONG Xueshi,CAI Yongle,WANG Yufeng,et al.Discrete IT? algorithm to the coloured travelling salesman problem [J].Int J Wirel & Mob Comput,2016,11(2):157-165.
[6] PANDIRI V,SINGH A.A swarm intelligence approach for the colored traveling salesman problem [J].Appl Intell,2018,48(11):4412-4428.
[7] 代星.最大值最小化着色旅行商问题的研究及应用 [D].南京:东南大学,2017.
[8] 王艳.改进的萤火虫算法及其应用研究 [D].西安:西安理工大学,2018.
[9] SAYADI M K,RAMEZANIAN R,GHAFFARINASAB N.A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems [J].Int J Indust Engin Comput,2010,1(1):1-10.
[10] 于宏涛,高立群,韩希昌.求解旅行商问题的离散人工萤火虫算法 [J].华南理工大学学报(自然科学版),2015,43(1):126-131.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |