计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (26): 43-45.DOI: 10.3778/j.issn.1002-8331.2009.26.012

• 研究、探讨 • 上一篇    下一篇

最优路径问题的自适应伪并行免疫算法

余振华,张其善   

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

Adaptive pseudo-parallel immune algorithm on optimal path planning problem

YU Zhen-hua,ZHANG Qi-shan   

  1. School of Electronics and Information Engineering,Beihang University,Beijing 100083,China
  • Received:2008-10-23 Revised:2009-01-06 Online:2009-09-11 Published:2009-09-11
  • Contact: YU Zhen-hua

摘要: 针对标准遗传算法在解决路径规划问题中存在的不能以概率1收敛及进化时出现退化等情况,提出并实现了一种自适应伪并行免疫算法。利用多个子种群同时进化及小生境技术,给出了一种小生境伪并行协同进化策略。提出了一种新的编解码方式,给出了相关的免疫克隆、免疫优势等免疫算子的具体设计。进化过程中克隆规模可依据抗体-抗原亲合度、抗体-抗体亲合力自适应调整,采取了最优保存策略从而保证了算法以概率1收敛。实例验证了该算法的可行性、有效性,与标准遗传算法相比,增强了全局收敛,提高了收敛速度,通过仿真验证,该算法运算速度快、结果精度高,为路径规划问题研究提供了一种新方法。

关键词: 路径规划, 小生境, 免疫克隆, 最优保存策略, 免疫算法

Abstract: In solving path planning,standard genetic algorithm exists the problem of non-convergence with probability one and inevitable degeneration.Faced with this problem,a new algorithm named Adaptive Pseudo-Parallel Immune Algorithm(APPIA) is presented and realized.A niche pseudo-parallel cooperation evolution strategy is given based on evolution of several filial-population and niche technique.A new symbol encoding and decoding style is presented,the design of immune clone,immune dominance of immune 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 instance.Compared with standard genetic algorithm,the algorithm has improved the speed of convergence and has achieved higher capacity of global optimization.The instance shows that it is a high speed and fidelity method and provides a new approach for solving the problem of optimal path planning.

Key words: path planning, niche, immune clone, elitist strategy, immune algorithm

中图分类号: