计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (29): 69-72.DOI: 10.3778/j.issn.1002-8331.2008.29.018

• 理论研究 • 上一篇    下一篇

NSGA-II中重复个体产生原因分析及影响研究

谢炯亮,郑金华   

  1. 湘潭大学 信息工程学院,湖南 湘潭 411105
  • 收稿日期:2007-11-22 修回日期:2008-03-03 出版日期:2008-10-11 发布日期:2008-10-11
  • 通讯作者: 谢炯亮

Research on cause for overlapping solutions and on their influence in NSGA-II algorithm

XIE Jiong-liang,ZHENG Jin-hua   

  1. Institute of Information Engineering,Xiangtan University,Xiangtan,Hunan 411105,China
  • Received:2007-11-22 Revised:2008-03-03 Online:2008-10-11 Published:2008-10-11
  • Contact: XIE Jiong-liang

摘要: 进化种群中出现重复个体意味着搜索区域的重叠,使得算法探索新可行区域的效率降低。另外个体重复浪费了解集中的个体名额,且造成信息冗余,使得解集的有效代表性变差。这在用NSGA-II处理低维问题时体现得较为严重。分析了NSGA-II中出现重复个体的原因,测试了编码方式和变量维数与重复个体数量的关系;通过实验检验了重复个体对于算法性能和解集质量的影响。实验结果表明,去除重复个体的算法能获得分布性更好的解集,且具有更强的稳定性。

关键词: NSGA-II, 重复个体, 编码方式, 进化操作, 拥挤距离, 变量维数, 分布度, ,

Abstract: The existence of overlapping individuals in the evolution populations means overlapping regions in the searching space,which makes the algorithm much less efficiently in exploiting new feasible region.Additionally,it wastes the positions in the population and leads to the information redundancy,which reduces the diversity of the obtained solution set.This phenomenon is quite obvious in the famous NSGA-II algorithm when applied to low-variable dimension problems.In this paper,the cause of the overlapping solutions in NSGA-II is analyzed and the relation between the number of them and the coding method is diseovered,as well as and the variable dimension;then overlapping solutions have influence on the performance of the NSGA-II algorithm and on the quality of the obtained solution set is illuminated.The experimental results demonstrate that eliminating overlapping solutions make the NSGA-II algorithm more steady and gain a solution set with better diversity.

Key words: NSGA-II, overlapping individuals, coding method, evolutionary operation, crowding distance, variable dimension, diversity