基于外部存档更新及截断的NSGA-Ⅱ改进算法

An Improved NSGA-ⅡAlgorithm Based on External Archive Updating and Truncation

传统的NSGA-Ⅱ(Non-dominated Sorting Genetic AlgorithmⅡ)算法使用拥挤度作为精英选择的第二指标,该方法在处理高维多目标优化问题时,常常由于选择压力不足,以及不同目标间优化冲突加剧等原因,很难维持种群收敛性和多样性的平衡。针对上述问题,提出一种基于外部存档更新及截断机制的NSGA-Ⅱ改进算法NSGA-Ⅱ-UTEA(NSGA-Ⅱalgorithm based on Update and Truncation of External Archive)。该算法首先在精英选择中引入基于权重向量分解的外部存档机制,然后根据个体与所在权重向量及超平面距离之和更新外部存档,并基于个体间角度计算实现外部存档截断,进一步提升了算法在高维多目标优化问题中种群的收敛性和多样性。与NSGA-Ⅱ、NSGA-Ⅲ、MOEA/D(Multi-Objective Evolutionary Algorithm based on Decomposition)、NSGA-Ⅱ-ARSBX(NSGA-Ⅱwith Adaptive Rotation based Simulated Binary crossover)和RPD-NSGA-Ⅱ(Reference Point Dominance-based NSGA-Ⅱ)这5种先进的进化算法的对比实验结果表明,NSGA-Ⅱ-UTEA算法在10目标以上的高维DTLZ(Deb Thiele Laumanns Zitzler)和WFG(Walking Fish Group)系列测试函数上,各项性能指标整体优于其他算法,在解集的分布性和多样性方面具有显著优势。特别是在大部分高维WFG4~WFG7凹问题上都能取得最佳的性能指标值。与传统的NSGA-Ⅱ算法相比,NSGA-Ⅱ-UTEA算法在10目标以上的高维DTLZ系列测试函数上,反世代距离(IGD)性能平均提升了50.6%;在15目标以上的高维WFG系列测试函数上,超体积(HV)性能平均提升了60.7%。实验结果验证了NSGA-Ⅱ-UTEA算法改进的有效性。

The traditional NSGA-Ⅱalgorithm uses the crowding degree as the second index of elite selection,which is difficult to maintain the balance of population convergence and diversity when dealing with high-dimensional multi-objective optimization problems due to insufficient selection pressure and intensified optimization conflicts between different objectives.To solve these problems,an improved NSGA-Ⅱalgorithm based on external archive updating and truncation mechanism was proposed:NSGA-Ⅱ-UTEA.The algorithm firstly introduces the external archiving mechanism based on decision variable decomposition into elite selection,then updates the external archiving according to the sum of the weight vector and hyperplane distance between individuals,and realizes the truncation of external archiving based on the Angle calculation between individuals,which further improves the convergence and diversity of the algorithm in the high-dimensional multi-objective optimization problem.Compared with the five classical evolutionary algorithms,NSGA-Ⅱ,NSGA-Ⅲ,MOEA/D,NSGA-Ⅱ-ARSBX and RPD-NSGA-Ⅱ.The experimental results show that NSGA-Ⅱ-UTEA algorithm is superior to other algorithms in the performance indexes of high-dimensional DTLZ and WFG series test functions with more than 10 targets,and has significant advantages in the distribution and diversity of solution sets.In particular,the best performance index values can be obtained for most high-dimensional WFG4-7 concave problems.Compared with the traditional NSGA-Ⅱalgorithm,the IGD performance of NSGA-Ⅱ-UTEA algorithm is improved by 50.6%on average on the high-dimensional DTLZ series test functions with more than 10 targets.In the high-dimensional WFG series test functions with 15 targets and above,the HV performance is improved by 60.7%on average.Experimental results verify the effectiveness of the improved NSGA-Ⅱ-UTEA algorithm.