计算机应用 ›› 2016, Vol. 36 ›› Issue (5): 1319-1324.DOI: 10.11772/j.issn.1001-9081.2016.05.1319

• 人工智能 • 上一篇    下一篇

基于自适应混合非支配个体排序策略的改进型NSGA-Ⅱ算法

耿焕同1,2, 李辉健2, 赵亚光2, 陈正鹏2   

  1. 1. 南京信息工程大学 江苏省网络监控中心, 南京 210044;
    2. 南京信息工程大学 计算机与软件学院, 南京 210044
  • 收稿日期:2015-10-21 修回日期:2015-12-06 出版日期:2016-05-10 发布日期:2016-05-09
  • 通讯作者: 耿焕同
  • 作者简介:耿焕同(1973-),男,安徽宣城人,教授,博士生导师,博士,CCF高级会员,主要研究方向:计算智能与约束多目标优化;李辉健(1989-),男,山东临沂人,硕士研究生,主要研究方向:进化计算;赵亚光(1990-),女,江苏扬州人,硕士研究生,主要研究方向:进化计算;陈正鹏(1990-),男,江苏南京人,硕士研究生,主要研究方向:进化计算。
  • 基金资助:
    国家自然科学基金资助项目(61403206);江苏省自然科学基金资助项目(BK20151458);"青蓝工程"资助项目(2016)。

Improved NSGA-Ⅱ algorithm based on adaptive hybrid non-dominated individual sorting strategy

GENG Huantong1,2, LI Huijian2, ZHAO Yaguang2, CHEN Zhengpeng2   

  1. 1. Jiangsu Engineering Center of Network Monitoring, Nanjing University of Information Science and Technology, Nanjing Jiangsu 210044, China;
    2. College of Computer and Software, Nanjing University of Information Science and Technology, Nanjing Jiangsu 210044, China
  • Received:2015-10-21 Revised:2015-12-06 Online:2016-05-10 Published:2016-05-09
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61403206), the Natural Science Foundation of Jiangsu Province (BK20151458), Sponsored by Qing Lan Project(2016).

摘要: 针对经典快速非支配排序遗传算法(NSGA-Ⅱ)中基于拥挤距离的种群多样性保持策略不能客观反映个体间真实拥挤程度的问题,提出了一种基于自适应混合非支配个体排序策略的改进型NSGA-Ⅱ算法(NSGA-Ⅱh)。首先,设计一种新的循环聚类个体排序策略;然后,根据Pareto分层信息来对基于经典拥挤距离和循环聚类的两种个体排序策略进行自适应的选择;最终,实现对进化后期的种群多样性保持机制的改进。通过5个标准测试函数进行算法验证,并与经典的NSGA-Ⅱ、多目标粒子群优化算法(MOPSO)和GDE3等算法进行对比分析,NSGA-Ⅱh算法获得了80%的最优反向世代距离(IGD)值,且显著性水平为5%的双尾t检验结果表明,新算法具有明显统计意义上的性能优势。改进算法不仅能提高进化种群的分布性,而且能增强算法的收敛性,有效提高了优化效果。

关键词: 快速非支配排序遗传算法, 非支配个体排序, 拥挤距离, 循环聚类, 自适应

Abstract: In order to solve the problem that the population diversity preservation strategy only based on crowding distance of Non-dominated Sorting Genetic Algorithm-Ⅱ (NSGA-Ⅱ) cannot reflect the real crowding degree of individuals, an improved NSGA-Ⅱ algorithm based on the adaptive hybrid non-dominated individual sorting strategy (NSGA-Ⅱh) was proposed. First, a novel loop-clustering individual sorting strategy was designed. Second, according to the Pareto layer-sorting information the NSGA-Ⅱh algorithm adaptively chose one from the two individual sorting strategies based on classical crowding distance and loop-clustering. Finally, the diversity maintain mechanism could be improved especially during the late period of evolutionary optimization. The NSGA-Ⅱh algorithm was compared with three classical algorithms including NSGA-Ⅱ, Multi-Objective Particle Swarm Optimization (MOPSO) and GDE3. The experiments on five multi-objective benchmark functions show that the NSGA-Ⅱh algorithm can acquire 80% of optimal Inverted Generational Distance (IGD) values, and the corresponding two-tailed t-test results at a 0.05 level of significance are remarkable. The proposed algorithm can not only improve convergence of the original algorithm, but also enhance the distribution of Pareto optimal set.

Key words: Non-dominated Sorting Genetic Algorithm-Ⅱ (NSGA-Ⅱ), non-dominated individual sorting, crowding distance, loop-clustering, adaptive

中图分类号: