Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (20): 28-34.DOI: 10.3778/j.issn.1002-8331.1808-0384

Previous Articles     Next Articles

Improved NSGA-II algorithm based on synchronous update of external archive

GU Chunhua, LIU Xinping, LUO Fei, DING Weichao   

  1. School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China
  • Online:2018-10-15 Published:2018-10-19


顾春华,刘鑫平,罗  飞,丁炜超   

  1. 华东理工大学 信息科学与工程学院,上海 200237

Abstract: When calculating the crowding coefficient, NSGA-II does not consider the individual distribution of the parent population and offspring population, so that some individuals with excellent distribution in the global space are eliminated. Aiming at the poor distribution of NSGA-II convergence results, an improved algorithm(UAA-NSGA-II) is proposed. In the iterative process, the non-dominated individuals of a certain quantum generation are randomly filled into the external archive, and the crowding coefficient operator is used to prune the archive. At the same time, to solve the problem that binary encoding is trapped in local optimum, the search speed and width in solution space are enhanced by Gray code and dynamic mutation operator. Tests are performed on ZDT series problems and compared with two typical algorithms and three improved NSGA-II algorithms. The results show that UEA-NSGA-II algorithm is superior to the contrast algorithm in terms of stability and optimization effect.

Key words: multi-objective evolutionary algorithm, NSGA-II, external archive, archiving strategy

摘要: NSGA-II在执行拥挤系数计算时不考虑父子代种群各自独立的个体分布情况,使某些在全局空间中分布优秀的个体被淘汰。针对NSGA-II收敛结果的较差分布性,提出了改进算法(UEA-NSGA-II),在迭代过程中随机填充一定量子代种群的非支配个体到外部归档集内,使用拥挤系数算子用于归档集的剪枝操作。同时,针对二进制编码存在陷入局部最优的问题,采用格雷码和动态变异算子增强算法在解空间上搜索速度与宽度。在ZDT系列问题上执行测试,并与两种典型算法和三种NSGA-II改进算法对比,结果表明UEA-NSGA-II在算法的稳定性与优化效果方面均优于所对比的算法。

关键词: 多目标进化算法, NSGA-II, 外部归档集, 归档策略