采用放松支配关系的高维多目标微分进化算法

为了提高进化算法在求解高维多目标优化问题时的收敛性和多样性,提出了采用放松支配关系的高维多目标微分进化算法。该算法采用放松的Pareto支配关系,以增加个体的选择压力;采用群体和外部存储器协同进化的方案,并通过混合微分变异算子,生成子代群体;采用基于指标的方法计算个体的适应度并对群体进行更新;采用基于Lp范数（0相似文献   

A many-objective evolutionary algorithm based on hyperplane projection and penalty distance selection

For many-objective optimization problems, due to the low selection pressure of the Pareto-dominance relation and the ineffectivity of diversity maintenance scheme in the environmental selection, the current Pareto-dominance based multi-objective evolutionary algorithms (MOEAs) fail to balance between convergence and diversity. This paper proposes a many-objective evolutionary algorithm based on hyperplane projection and penalty distance selection (we call it MaOEA-HP). Firstly, the normalization method is used to construct an unit hyperplane and the population is projected onto the unit hyperplane. Then, a harmonic average distance is applied to calculate the crowding density of the projected points on the unit hyperplane. Finally, the perpendicular distance from the individual to the hyperplane as convergence information is added into the diversity maintenance phase, and a penalty distance selection scheme is designed to balance between convergence and diversity of solutions. Compared with six state-of-the-art many-objective evolutionary algorithms, the experimental results on two well-known many-objective optimization test suites show that MaOEA-HP has more advantage than the other algorithms, could improve the convergence and ensure the uniform distribution.     

An angle based evolutionary algorithm with infeasibility information for constrained many-objective optimization

Recently, angle-based approaches have shown promising for unconstrained many-objective optimization problems (MaOPs), but few of them are extended to solve constrained MaOPs (CMaOPs). Moreover, due to the difficulty in searching for feasible solutions in high-dimensional objective space, the use of infeasible solutions comes to be more important in solving CMaOPs. In this paper, an angle based evolutionary algorithm with infeasibility information is proposed for constrained many-objective optimization, where different kinds of infeasible solutions are utilized in environmental selection and mating selection. To be specific, an angle-based constrained dominance relation is proposed for non-dominated sorting, which gives infeasible solutions with good diversity the same priority to feasible solutions for escaping from the locally feasible regions. As for diversity maintenance, an angle-based density estimation is developed to give the infeasible solutions with good convergence a chance to survive for next generation, which is helpful to get across the large infeasible barrier. In addition, in order to utilize the potential of infeasible solutions in creating high-quality offspring, a modified mating selection is designed by considering the convergence, diversity and feasibility of solutions simultaneously. Experimental results on two constrained many-objective optimization test suites demonstrate the competitiveness of the proposed algorithm in comparison with five existing constrained many-objective evolutionary algorithms for CMaOPs. Moreover, the effectiveness of the proposed algorithm on a real-world problem is showcased.     

MaOEA/d2:一种基于双距离构造的高维多目标进化算法

传统的基于Pareto支配关系的多目标进化算法(MOEA)难以有效求解高维多目标优化问题(MaOP). 提出一种利用PBI效用函数的双距离构造的支配关系, 且无需引入额外的参数. 其次, 利用双距离定义了一种多样性保持方法, 该方法不仅考虑了解个体的双距离, 而且还可以根据优化问题的目标数目自适应地调整多样性占比, 以较好地平衡高维目标解群的收敛性和多样性. 最后, 将基于双距离构造的支配关系和多样性保持方法嵌入到NSGA-II算法框架中, 设计了一种基于双距离的高维多目标进化算法MaOEA/d². 该算法与其他5种代表性的高维多目标进化算法一同在5-、10-、15-和20-目标的DTLZ和WFG基准测试问题上进行了IGD和HV性能测试, 结果表明, MaOEA/d²算法具有较好的收敛性和多样性. 由此表明, MaOEA/d²算法是一种颇具前景的高维多目标进化算法.     

A novel two-archive strategy for evolutionary many-objective optimization algorithm based on reference points

Current evolutionary many-objective optimization algorithms face two challenges: one is to ensure population diversity for searching the entire solution space. The other is to ensure quick convergence to the optimal solution set. In this paper, we propose a novel two-archive strategy for evolutionary many-objective optimization algorithm. The uniform archive strategy, based on reference points, is used to keep population diversity in the evolutionary process, and to ensure that an evolutionary algorithm is able to search the entire solution space. The single elite archive strategy is used to ensure that individuals with the best single objective value are able to evolve into the next generation and have more opportunities to generate offspring. This strategy aims to improve the convergence rate. Then this novel two-archive strategy is applied to improving the Non-dominated Sorting Genetic Algorithm (NSGA-III). Simulation experiments are conducted on benchmark test sets and experimental results show that our proposed algorithm with the two-archive strategy has a better performance than other state-of-art algorithms.     

基于参考点的高维多目标粒子群算法

高维多目标优化问题一般指目标个数为4个 或以上时的多目标优化问题.由于种群中非支配解数量随着目标数量的增加而急剧增多,导致进化算法的进化压力严重降低,求解效率低.针对该问题,提出一种基于粒子群的高维多目标问题求解方法,在目标空间中引入一系列的参考点,根据参考点筛选出能兼顾多样性和收敛性的非支配解作为粒子的全局最优,以增大选择压力.同时,提出了基于参考点的外部档案维护策略,以保持最后所得解集的多样性.在标准测试函数DTLZ2上的仿真结果表明,所提方法在求解高维多目标问题时能够得到收敛性和分布性都较好的解集.     

基于径向空间划分的昂贵多目标进化算法

为了解决难以建立精确数学模型或者真实评估实验成本高昂的多目标优化问题,提出了一种基于径向空间划分的昂贵多目标进化算法.首先算法使用高斯回归作为代理模型逼近目标函数;然后将目标空间的个体投影到径向空间,结合目标空间和径向空间信息保留对种群贡献更高的个体;之后由径向空间中个体的位置分布决定下一步应该选择哪些个体进行真实评估;最后,采用一种双档案管理策略维护代理模型的质量.数值实验和现实问题上的结果表明,与5种先进算法相比,该算法在解决昂贵多目标优化问题时能够提供更高质量的解.     

一种基于分解和协同的高维多目标进化算法

现实中高维多目标优化问题普遍存在，而且其巨大的目标空间使得经典的多目标进化算法面临严峻挑战，提出一种基于分解和协同策略的高维多目标进化算法MaOEA/DCE.该算法利用混合水平正交实验设计方法产生接近于指定规模且均匀分布于聚合系数空间的权重向量，提高种群的分布性；其次，算法将差分进化算子和自适应SBX算子进行协同进化以产生高质量的子代个体，改善算法的收敛性.该算法与另外五种高性能的多目标进化算法在基准测试函数集DTLZ{1，2，4，5}上进行IGD⁺性能指标实验，结果表明MaOEA/DCE在收敛性、多样性和稳定性方面总体具有显著的性能优势.     

融合张角拥挤控制策略的高维多目标优化

对于高维多目标优化问题,随着目标维数的增加,种群中非被支配解的比例剧增, 严重降低了种群的进化压力.为了对数量众多的非被支配解进行有效的拥挤控制并提升种群的多样性, 本文在提出张角概念的基础上设计了一种新的拥挤控制策略(Congestion control strategy based on open angle, CCSOA),它的时间复杂度并不会随着目标维数的增加而增大. 与目前优秀的进化多目标优化(Evolutionary multiobjective optimization, EMO)算法IBEA (Indicator-based evolutionary algorithm)、NSGAIII (Nondominated sorting genetic algorithm III)和GrEA (Grid-based evolutionary algorithm)的比较结果表明, 融合了CCSOA的高维多目标优化算法在收敛效果和解集分布的均匀性两个方面均有较大的优势.     

MCEDA: A novel many-objective optimization approach based on model and clustering

To solve many-objective optimization problems (MaOPs) by evolutionary algorithms (EAs), the maintenance of convergence and diversity is essential and difficult. Improved multi-objective optimization evolutionary algorithms (MOEAs), usually based on the genetic algorithm (GA), have been applied to MaOPs, which use the crossover and mutation operators of GAs to generate new solutions. In this paper, a new approach, based on decomposition and the MOEA/D framework, is proposed: model and clustering based estimation of distribution algorithm (MCEDA). MOEA/D means the multi-objective evolutionary algorithm based on decomposition. The proposed MCEDA is a new estimation of distribution algorithm (EDA) framework, which is intended to extend the application of estimation of distribution algorithm to MaOPs. MCEDA was implemented by two similar algorithm, MCEDA/B (based on bits model) and MCEDA/RM (based on regular model) to deal with MaOPs. In MCEDA, the problem is decomposed into several subproblems. For each subproblem, clustering algorithm is applied to divide the population into several subgroups. On each subgroup, an estimation model is created to generate the new population. In this work, two kinds of models are adopted, the new proposed bits model and the regular model used in RM-MEDA (a regularity model based multi-objective estimation of distribution algorithm). The non-dominated selection operator is applied to improve convergence. The proposed algorithms have been tested on the benchmark test suite for evolutionary algorithms (DTLZ). The comparison with several state-of-the-art algorithms indicates that the proposed MCEDA is a competitive and promising approach.     

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

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

基于分解和聚类的昂贵高维多目标进化算法

使用进化算法解决昂贵高维多目标优化问题时,因目标维数较高,导致收敛性和多样性平衡困难,并且消耗成本过高,使得计算资源有限时难以收敛.为此,提出一种基于分解和聚类的昂贵高维多目标进化算法(DC-EMEA),使用克里金模型近似目标函数,减少昂贵函数的评价次数.在优化器对模型的最优解集搜索时,借助参考向量分解目标空间,有利于收敛性和多样性的平衡,同时采取两轮选择的方式,保证后代种群规模与父代相同,为填充准则选择真实评价的个体时,提供更多选择,提升搜索效率.同时,提出一种自适应填充准则,首先使用K均值算法将种群划分为k个子种群.通过划分邻域, 将子种群自适应地分成不同类型,根据子种群的类型选择个体,提升计算资源的利用率.在选择个体时,侧重于对收敛性压力的维持,提升收敛速度.将选出的个体用于更新模型和档案.实验结果表明,DC-EMEA能够很好地平衡收敛性和多样性,同时具有较强的收敛能力.     

基于新的适应度函数和多搜索策略的高维多目标进化算法

为提高高维多目标进化算法的性能,提出了一个基于新的适应度函数和多搜索策略的高维多目标进化算法。该算法提出了一个新的适应度函数来平衡多样性和收敛性,并且设计了一个多搜索策略来帮助交叉算子产生优秀的后代进而提高收敛性。该适应度函数首先从当前种群和新产生的后代中挑出收敛性较好的个体,然后计算这些个体的稀疏程度;该多搜索策略选择稀疏且收敛的解来执行全局和局部搜索。数值实验测试了CEC2018高维多目标竞赛的15个测试问题,每个测试问题的目标个数分别为5、10、15。实验结果表明,该算法能找到一组比四种代表性算法（如NSGAIII、MOEA/DD、KnEA、RVEA）具有更好的多样性和收敛性的解集。     

基于邻域竞赛的多目标优化算法

传统多目标优化算法（Multi-objective evolution algorithms,MOEAs）的基本框架大致分为两部分:首先是收敛性保持,采用Pareto支配方法将种群分成若干非支配层;其次是分布性保持,在临界层中,采用分布性保持机制维持种群的分布性.然而在处理高维优化问题（Many-objective optimization problems,MOPs）（目标维数大于3）时,随着目标维数的增加,种群的收敛性和分布性的冲突加剧,Pareto支配关系比较个体优劣的能力也迅速下降,此时传统的MOEA已不再适用于高维优化问题.鉴于此,本文提出了一种基于邻域竞赛的多目标优化算法（Evolutionary algorithm based on neighborhood competition for multi-objective optimization,NCEA）.NCEA首先将个体的各个目标之和作为个体的收敛性估计;然后,计算当前个体向量与收敛性最好的个体向量之间的夹角,并将其作为当前个体的邻域估计;最后,通过邻域竞赛方法将问题划分为若干个相互关联的子问题并逐步优化.为了验证NCEA的有效性,本文选取5个优秀的算法与NCEA进行对比实验.通过对比实验验证,NCEA具有较强的竞争力,能同时保持良好的收敛性和分布性.     

基于帕累托前沿面曲率预估的超多目标进化算法

基于分解的超多目标进化算法是求解各类超多目标优化问题的主流方法, 其性能在很大程度上依赖于所采用参考向量与真实帕累托前沿面(Pareto front, PF)的匹配程度. 现有基于分解的超多目标进化算法尚难以同时有效处理各类PF不同的优化问题. 为此, 提出了一种基于PF曲率预估的超多目标进化算法(MaOEA-CE). 所提算法的核心包括两个方面, 首先基于对PF曲率的预估, 在每次迭代过程中生成不同的参考向量, 以渐进匹配不同类型问题的真实PF; 其次在环境选择过程中, 再基于预估的曲率选择合适的聚合函数对精英解进行挑选, 并对参考向量进行动态调整, 在维护种群多样性的同时提升种群的收敛性. 为验证MaOEA-CE的有效性, 将其与7个先进的超多目标算法在3个主流测试问题集DTLZ、WFG和MaF上进行对比, 实验结果表明MaOEA-CE具有明显的竞争力.     

基于指标和自适应边界选择的高维多目标优化算法

多目标优化算法的主要目标是实现好的多样性和收敛性.传统的高维多目标优化算法,当目标维数增加时,选择方式难以平衡种群的收敛性与多样性.对此,提出一个基于指标和自适应边界选择的高维多目标优化算法.在环境选择中,首先计算种群中两两个体的指标Iε(x,y)作为第一选择标准;其次,提出一种自适应边界选择策略,利用种群进化信息对超...     

A many-objective evolutionary algorithm based on a projection-assisted intra-family election

In recent years, many researchers have put emphasis on the study of how to keep a good balance between convergence and diversity in many-objective optimization. This paper proposes a new many-objective evolutionary algorithm based on a projection-assisted intra-family election. In the proposed algorithm, basic evolution directions are adaptively generated according to the current population and potential evolution directions are excavated in each individual's family. Based on these evolution directions, a strategy of intra-family election is performed in every family and elite individuals are elected as representatives of the specific family to join the next stage, which can enhance the convergence of the algorithm. Moreover, a selection procedure based on angles is used to maintain the diversity. The performance of the proposed algorithm is verified and compared with several state-of-the-art many-objective evolutionary algorithms on a variety of well-known benchmark problems ranging from 5 to 20 objectives. Empirical results demonstrate that the proposed algorithm outperforms other peer algorithms in terms of both the diversity and the convergence of the final solutions set on most of the test instances. In particular, our proposed algorithm shows obvious superiority when handling the problems with larger number of objectives.     

一种基于参考点约束支配的NSGA-III算法

针对带约束的高维多目标优化问题,设计一种基于参考点的约束支配关系(RPCDP),将可行解与不可行解作为一个整体看待,进而综合考虑它们的收敛性、多样性和可行性,并基于此提出用于解决约束高维多目标优化问题的NSGA-III算法.将所提出算法与著名的3种约束高维多目标进化算法进行对比,实验结果表明在标准测试函数集CDTLZ上,相对于其他算法,所提出算法的解集具有更好的收敛性和分布性.     

Handling many-objective optimisation problems with R2 indicator and decomposition-based particle swarm optimiser

An R2 indicator-based multi-objective particle swarm optimiser (R2-MOPSO) can obtain well-convergence and well-distributed solutions while solving two and three objectives optimisation problems. However, R2-MOPSO faces difficulty to tackle many-objective optimisation problems because balancing convergence and diversity is a key issue in high-dimensional objective space. In order to address this issue, this paper proposes a novel algorithm, named R2-MaPSO, which combines the R2 indicator and decomposition-based archiving pruning strategy into particle swarm optimiser for many-objective optimisation problems. The innovations of the proposed algorithm mainly contains three crucial factors: (1) A bi-level archiving maintenance approach based on the R2 indicator and objective space decomposition strategy is designed to balance convergence and diversity. (2) The global-best leader selection is based on the R2 indicator and the personal-best leader selection is based on the Pareto dominance. Meanwhile, the objective space decomposition leader selection adopts the feedback information from the bi-level archive. (3) A new velocity updated method is modified to enhance the exploration and exploitation ability. In addition, an elitist learning strategy and a smart Gaussian learning strategy are embedded into R2-MaPSO to help the algorithm jump out of the local optimal front. The performance of the proposed algorithm is validated and compared with some algorithms on a number of unconstraint benchmark problems, i.e. DTLZ1-DTLZ4, WFG test suites from 3 to 15 objectives. Experimental results have demonstrated a better performance of the proposed algorithm compared with several multi-objective particle swarm optimisers and multi-objective evolutionary algorithms for many-objective optimisation problems.     

基于最小距离和聚合策略的分解多目标进化算法

针对基于帕累托（Pareto）支配的多目标进化算法在解决高维问题时选择压力降低,以及基于分解的多目标进化算法在提高收敛性和分布性的同时降低了种群多样性的问题,提出了一种基于最小距离和聚合策略的分解多目标进化算法。首先,使用基于角度分解的技术将目标空间分解为指定个数的子空间来提高种群的多样性;然后,在生成新解的过程中加入基于聚合的交叉邻域方法,使生成的新解更接近于父代解;最后,分两阶段在每个子空间内基于最小距离和聚合策略来选择解以提高收敛性和分布性。为了验证所提算法的可行性,采用标准测试函数ZDT和DTLZ进行仿真实验,结果表明所提算法的总体性能均优于经典的基于分解的多目标进化算法（MOEA/D）、MOEA/D-DE、NSGA-Ⅲ和GrEA。可见,所提算法在提高多样性的同时可以有效平衡收敛性和多样性。