基于多态变异的单亲遗传算法解CVRP问题  

Partheno-genetic Algorithm Based on Polymorphic Mutation for Solving CVRP

作　　者：陈肖莉 谭代伦[1,2] Chen Xiaoli;Tan Dailun(School of Mathematics and Information,China West Normal University,Nanchong 637009,China;Sichuan Provincial Key Laboratory of Optimization Theory and Application,Nanchong 637009,China)

机构地区：[1]西华师范大学数学与信息学院,四川南充637009 [2]西华师范大学最优化理论与应用四川省高校重点实验室,四川南充637009

出　　处：《洛阳师范学院学报》2024年第8期13-17,26,共6页Journal of Luoyang Normal University

基　　金：四川省科技计划项目(2019YFG0299);教育部产学合作协同育人项目(202102454008);四川省教育厅重点教改项目(JG2021-959)。

摘　　要：针对遗传算法求解带容量约束的车辆路径规划问题(CVRP)时存在收敛速度慢、易早熟等问题,提出一种基于多态变异的单亲遗传算法(PM-PGA).将多种算子分组构成局部搜索、整体搜索和随机移动三种策略,使种群发生多态变异,增强种群多样性,提高寻优能力;采用个体浓度控制和Metropolis准则相结合的混合跳跃策略,避免陷入局部最优;为提高解的质量,设计了基于迭代次数和车辆超载量的自适应罚函数.选取CVRP问题算例进行仿真实验,结果表明PM-PGA算法在收敛速度和求解精度方面得到明显改善和增强.Researchers proposed a partheno-genetic algorithm based on polymorphic mutation(PM-PGA)to solve the problems such as slow convergence and precocity when genetic algorithm was used to solve capacitated vehicle routing problem(CVRP).During the research process,the researchers grouped a variety of operators into local search,global search and random movement for population polymorphism,so as to enhance the population diversity and improve the optimization ability.Meanwhile,the researchers adopted a hybrid jump strategy combining individual concentration control and Metropolis criterion so as to avoid falling into local optimality.Furthermore,the researchers designed an adaptive penalty function based on the number of iterations and vehicle overload so as to improve the quality of the solution.The result of simulation experiments on CVRP examples shows that the PM-PGA algorithm can significantly improve and enhance the convergence speed and solution accuracy.

关 键 词：CVRP问题 单亲遗传算法 多态变异 个体浓度 METROPOLIS准则 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]