摘要
针对遗传算法在求解最大值最小化着色旅行商问题(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.
作者
王东明
代星
孟祥虎
徐向平
李俊
WANG Dongming;DAI Xing;MENG Xianghu;XU Xiangping;LI Jun(Key Lab Measurement & Control of Complex System of Engineering, China Education Ministry, Southeast University, Nanjing 210096, China)
出处
《扬州大学学报(自然科学版)》
CAS
北大核心
2019年第2期56-60,共5页
Journal of Yangzhou University:Natural Science Edition
基金
国家自然科学基金资助项目(61773115)
江苏省"六大人才高峰"高层次人才选拔资助项目(DZXX-005)
江苏省基础研究计划资助项目(BK20161427)