基于动态缩减机制的多策略单亲遗传算法求解CVRP问题

Multi-strategy Partheno-genetic Algorithm Based on Dynamic Reduction Mechanism for Solving CVRP Problem

针对传统遗传算法求解带容量约束的车辆路径问题(CVRP)时存在易早熟、收敛速度慢、精度低等问题,提出一种基于动态缩减机制的多策略单亲遗传算法。基于同类个体实现对寻优空间的划分,采用模拟退火准则对最低类别子空间进行淘汰或更新,构成寻优空间的缩减和移动机制;基于单亲遗传算法,综合设计了组内、组间、整体搜索,以及扰动与跳跃的多种遗传进化策略;为适应度函数设计了基于个体发展、种群进化、整体收敛3个罚因子的自适应罚函数分量,对不可行解作出更有效惩罚。通过对3组CVRP问题实例进行仿真实验分析,结果表明:该算法在种群质量、全局与局部寻优能力、求解精度和收敛速度等方面均得到改善和提升。

Aiming at the problems of premature,slow convergence and low accuracy of traditional genetic algorithm in solving capacitated vehicle routing problem,a multi-strategy partheno-genetic algorithm based on dynamic reduction mechanism is proposed.The algorithm divides the optimization space based on similar individuals,and uses simulated annealing criterion to eliminate or update the lowest category subspace,which constitutes the reduction and movement mechanism of the optimization space.Based on parthenogenetic algorithm,a variety of genetic evolution strategies including intra-group,inter-group,global search,disturbance and jump strategy are designed Based on the three penalty factors of individual development,population evolution and overall convergence,the adaptive penalty function component is designed for the fitness function,which is more effective to punish the infeasible solution.Through the simulation experiments on three groups of CVRP problems,the results show that DRM-MSPGA algorithm is improved in population quality,global and local optimization ability,solution accuracy and convergence speed.