基于萤火虫算法的最大值最小化着色旅行商问题的求解

Firefly algorithm for min-max colored traveling salesman problem

针对遗传算法在求解最大值最小化着色旅行商问题(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.