求解旅行商问题的探索—开发—跳跃策略单亲遗传算法

作者：陈加俊; 谭代伦^*

来源：计算机应用研究, 2023, 40(05): 1375-1380.

DOI：10.19734/j.issn.1001-3695.2022.10.0483

• 旅行商问题
• 单亲遗传算法
• logistic混沌映射
• 改良圈操作
• 近邻变异

针对遗传算法求解旅行商问题(TSP)时容易早熟、收敛速度慢等问题，提出一种基于探索—开发—跳跃策略的单亲遗传算法(EDJS-PGA)。该算法将基因移位、倒序、交换三种算子组合构成探索策略，用于扩展解的搜索空间，增强算法全局搜索能力；再将logistic混沌映射和改良圈操作融合为一种混沌映射改良圈算子，用于增强算法的局部搜索能力，构成开发策略；最后针对种群中的同优个体设计了近邻变异算子，构成跳跃策略，增强了算法跳出局部最优解的能力，使其兼具个体变异、局部优化、防止早熟等多重作用。通过对18个TSP实例进行仿真实验，结果表明EDJS-PGA相较于传统单亲遗传算法具有更高的求解精度和收敛速度，且最优解偏差率和平均误差率均处于较低水平；与其他文献对比，EDJS-PGA具有更强的鲁棒性和求解效率。

• 单位
  西华师范大学