Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (5): 166-174.DOI: 10.3778/j.issn.1002-8331.1711-0358

Previous Articles     Next Articles

Improved NSGA-II Algorithm Based on Individual Neighborhood

DONG Junfeng, WANG Xiang, LIANG Changyong   

  1. School of Management, Hefei University of Technology, Hefei 230009, China
  • Online:2019-03-01 Published:2019-03-06


董骏峰,王  祥,梁昌勇   

  1. 合肥工业大学 管理学院,合肥 230009

Abstract: The Non-dominated Sorting Genetic Algorithm with elite strategy(NSGA-II) based on NSGA is one of the classical algorithms to solve multi-objective optimization problems. Congestion and congestion comparison operator are proposed by NSGA-II, which replace the fitness sharing strategy which needs to specify the shared radius. However, the exclusion mechanism based on crowding distance in NSGA-II to maintain population diversity has a defect in the front of the pareto frontier. Therefore, an improved algorithm named SN-NSGA2 which considers individual neighborhood is proposed. The idea of neighborhood in the density clustering algorithm DBSCAN is applied to new exclusion mechanism, and simultaneously a method of constructing individual neighborhood with corresponding elimination strategy is put forward. Experimental results show that the new algorithm has better distribution and good convergence.

Key words: Non-dominated Sorting Genetic Algorithm with elite strategy(NSGA2), multiobjective optimization, neighborhood, diversity, crowding distance

摘要: 带有精英策略的非支配排序遗传算法(NSGA-II)是在NSGA的基础之上,提出拥挤度和拥挤度比较算子,代替了需要指定共享半径的适应度共享策略,是解决多目标优化问题的经典算法之一。但是NSGA-II算法在保持种群多样性时采取的拥挤距离排挤机制有着pareto前沿分布不均匀的缺陷,因此,提出一种基于个体邻域的改进NSGA-II算法SN-NSGA2。SN-NSGA2将密度聚类算法DBSCAN中邻域的思想应用到排挤机制中去,提出一种个体邻域的构建方法,采用相应的淘汰策略去除个体邻域中的其他邻居个体。实验结果表明相对于NSGA-II算法来说,新算法求出的pareto解集有着更好的分布性以及良好的收敛性。

关键词: 带有精英策略的非支配排序遗传算法(NSGA2), 多目标优化, 邻域, 分布性, 拥挤距离