基于混合单亲遗传算法的车辆运输问题求解

本文运用混合单亲遗传算法(Hybrid Partheno Genetic Algorithm,)求解车辆运输问题.我们用罚函数法将约束优化问题转化为无约束优化问题,HPGA采用序号编码的方式进行运算.生成初始种群时,在拟染色体中插入车辆序号,尽可能生成符合约束的子路径,由子路径拼接成完整的运输路径,降低罚函数的计算量;选择操作中内嵌最优保存策略,保证算法全局收敛;取消双亲交叉操作,每条染色体上独立改变基因产生新的个体,避免发生早熟早收敛现象;提出邻域搜索,使得GA能对某些指定区域进行重点搜索,加快算法在最优解附近的寻优速度;以CVRP作为HPGA的测试模型,采用Christofides和Eilon提出的标准VRP测试算例进行数值实验,和其他算法进行对比分析,验证了HPGA计算量少、收敛速度快和不会产生早熟早收敛现象.