Computer Engineering and Applications ›› 2023, Vol. 59 ›› Issue (1): 126-139.DOI: 10.3778/j.issn.1002-8331.2207-0006

• Theory, Research and Development • Previous Articles     Next Articles

Evolutionary Algorithm Based on Niche for Multi-Objective Optimization

GU Qinghua, LUO Jiale, LI Xuexian   

  1. 1.School of Management, Xi'an University of Architecture and Technology, Xi'an 710055, China
    2.Xi'an Key Laboratory for Intelligent Industrial Perception, Calculation and Decision, Xi'an University of Architecture and Technology, Xi'an 710055, China
    3.School of Resources Engineering, Xi'an University of Architecture and Technology, Xi'an 710055, China
  • Online:2023-01-01 Published:2023-01-01

基于小生境的多目标进化算法

顾清华,骆家乐,李学现   

  1. 1.西安建筑科技大学 管理学院,西安 710055
    2.西安建筑科技大学 西安市智慧工业感知、计算与决策重点实验室,西安 710055
    3.西安建筑科技大学 资源工程学院,西安 710055

Abstract: The main challenges for evolutionary algorithms to balance convergence and diversity in solving many-objective optimization problems are in two aspects:strengthening selection pressure towards the Pareto optimal front and achieving a good diversity of the obtained solution set. However, the Pareto dominance-based selection criteria cannot effectively solve the above problems with the increase of the objective number. Therefore, an evolutionary algorithm based on niche is designed. Firstly, based on the niche, a new dominance relation is proposed, where an aggregation function and an objective vector angle-based density estimation method are used to measure the convergence and distribution of candidate solutions respectively. Then, in the same niche, only the solution with the best convergence degree is identified as the non-dominated solution to ensure the convergence of a solution set. At the same time, to improve the diversity of a solution set, in any two different niches, the solution with good convergence and distribution in one niche will dominate the solution with poor convergence and distribution in the other niche. Finally, the proposed dominance relation is embedded into VaEA instead of Pareto dominance relation to design an improved many-objective evolutionary algorithm(VaEA-SDN). VaEA-SDN and six state-of-the-art algorithms NSGA-III, VaEA, MSEA, NSGAII-CSDR, RPS-NSGAII and CDR-MOEA are conducted in simulation experiments on the DTLZ(Deb-Thiele-Laumanns-Zitzler) and MaF(many-objective function) benchmark suites. The results show that the ability of VaEA-SDN in keeping a balance between the convergence and diversity has an average improvement of 37.7%, 32.9%, 31.8%, 22.2%, 43.5%, 30.2% over the compared six algorithms in terms of the quality of obtained solutions.

Key words: evolutionary algorithms, multi-objective optimization, niche, objective vector angle

摘要: 进化算法求解多目标优化问题平衡收敛性和多样性面临的主要挑战在两个方面:增强对帕累托最优前沿的选择压力和获得多样性良好的解集。然而,随着目标维数的增加,基于帕累托支配关系的选择标准无法有效地解决以上问题。因此,设计了一种基于小生境的多目标进化算法。基于小生境,提出了一种新的支配关系,其中,设计了一个聚合函数和一种采用目标向量角的密度估计方法分别度量候选解的收敛度和分布性。为了保证解集的收敛性,在同一个小生境内,仅仅收敛度最好的解是非支配解。为了维护解集的多样性,在任何两个不同的小生境内,一个小生境内兼具收敛度和分布性良好的解支配另一个小生境内收敛性和分布性均差的解,将提出的支配关系嵌入VaEA取代帕累托支配关系,设计了一种多目标进化算法VaEA-SDN。VaEA-SDN与NSGA-III、VaEA、MSEA、NSGAII-CSDR、RPS-NSGAII以及CDR-MOEA等先进的算法在DTLZ(Deb-Thiele-Laumanns-Zitzler)和MaF(many-objective function)基准测试系列问题上进行了广泛的对比仿真实验。仿真结果表明,VaEA-SDN平衡收敛收敛性和多样性的能力分别比被比较的6个算法平均高37.7%、32.9%、31.8%、22.2%、43.5%、30.2%。

关键词: 进化算法, 多目标优化, 小生境, 目标向量角