计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (1): 221-223.DOI: 10.3778/j.issn.1002-8331.2010.01.066

• 工程与应用 • 上一篇    下一篇

车辆路径问题的自适应伪并行免疫遗传算法

余振华   

  1. 北京航空航天大学 电子信息工程学院 202教研室,北京 100083
  • 收稿日期:2008-07-22 修回日期:2008-10-10 出版日期:2010-01-01 发布日期:2010-01-01
  • 通讯作者: 余振华

Adaptive pseudo-parallel immune genetic algorithm on vehicle routing problem

YU Zhen-hua   

  1. School of Electronics and Information Engineering,Beihang University,Beijing 100083,China
  • Received:2008-07-22 Revised:2008-10-10 Online:2010-01-01 Published:2010-01-01
  • Contact: YU Zhen-hua

摘要: 物流配送车辆路径优化问题是在物流系统中受到普遍关注的问题,也是一个NP-Hard问题。针对物流配送车辆路径问题,提出并实现了一种自适应伪并行免疫遗传算法。利用多个子种群同时进化及小生境技术,给出了一种小生境伪并行协同进化策略,给出了编解码方式及免疫克隆、提取疫苗、接种疫苗、免疫选择等免疫算子以及选择、交叉、变异等遗传算子的具体设计,进化过程中克隆规模可依据抗体-抗原亲合度、抗体-抗体亲合力自适应调整,采取了最优保存策略从而保证了算法以概率1收敛。实例验证了该算法的可行性,有效性。通过仿真验证,该算法运算速度快、结果精度高,对物流配送车辆路径优化问题研究具有一定的参考价值。

关键词: 车辆路径问题, 小生境, 最优保存策略, 免疫克隆, 免疫遗传算法

Abstract: The optimization of VRP(Vehicle Routing Problem) in the logistics system is a widely concerned problem and is proved to be a NP-Hard problem.Faced with this problem,a new algorithm named APPIGA(Adaptive Pseudo-Parallel Immune Genetic Algorithm) is presented and realized.A niche pseudo-parallel cooperation evolution strategy is given based on evolution of several filial-population and niche technique.A symbol encoding and decoding style is presented.The immune clone,extracting vaccine,inoculating vaccine,immune selection of immune operator and the selection,crossover,mutation of genetic operator are given.The clone scale can be regulated automatically by affinity between antibody and antigen,and between antibodies during evolution.By use of elitist strategy,the algorithm can be convergent with probability one.The feasibility and validity of the algorithm are validated by the calculation instances.It is validated that the algorithm is a high speed and fidelity method,and can be served as a reference to VRP.

Key words: vehicle routing problem, niche, elitist strategy, immune clone, immune genetic algorithm

中图分类号: