双编码改进遗传算法求解旅行商问题

摘要

遗传算法是求解旅行商问题(Traveling Salesman Problem,TSP)的有效算法。但是其交叉策略对基于路径节点序列的基因编码不易操作,往往需要设计修复策略,甚至放弃交叉操作。为此,提出双编码改进遗传算法(Double Coding Improved Genetic Algorithm,DCIGA),算法中同时采用路径节点序列编码和一种可重复自然数编码,两种编码具有一一映射关系。在交叉环节,基于可重复自然数编码轮流选择三种交叉算子进行交叉操作,使种群个体的交叉效果得到合理控制和不同程度的增强;在变异环节,基于路径节点序列编码轮流选择四种变异算子进行变异操作,以增强种群多样性,提高算法寻优能力;最后将父代种群、交叉子代和变异子代进行合并排序和精英优选,以加快收敛速度。实验仿真选取TSPLIB的七组算例,和现有文献相比,DCIGA算法的求解精度有较明显提高,收敛速度更快。