进化高维多目标优化研究进展

高维多目标优化问题是目标个数多于3的多目标优化问题.尽管进化优化方法在多目标优化问题求解中显示了卓越的性能,但是,对于高维多目标优化问题,已有方法存在目标维数难以扩展、Pareto占优关系无法区分进化个体,以及多样性维护策略失效等困难.因此,高维多目标优化问题的高效求解引起进化优化界的高度关注.本文将分别从新型占优关系、多样性维护策略、目标缩减、目标聚合、基于性能指标的选择、融入偏好、集合进化、变化算子、可视化技术,以及应用等10个方面分类总结近年来进化高维多目标优化的研究成果,通过分析已有研究存在的问题,指出今后可能的研究方向.     

进化高维多目标优化研究综述

高维多目标优化问题(many-objective optimization problems, MaOPs)已经普遍存在于工业和科学领域中,这类问题的目标数一般超过3个且目标之间存在冲突性。进化算法作为一种基于种群的元启发式搜索方法已经被证实能够有效求解MaOPs。近二十年来,高维多目标进化算法(many-objective evolutionary algorithms, MaOEAs)研究已取得了长足发展。现对进化高维多目标优化(evolutionary many-objective optimization, EMaO)的研究进展进行全面的综述,具体包括：(1)描述了EMaO的相关理论背景;(2)分析了EMaO面临的挑战;(3)详细讨论了Ma OEAs的发展概况;(4)归纳了Ma OPs以及性能指标;(5)介绍了面对高维目标空间的可视化工具;(6)总结了Ma OEAs在一些领域的应用;(7)剖析了进化算法在解决MaOPs时所面临的问题和挑战,并给出未来研究方向的建议。     

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

现实中大量存在的高维多目标优化问题对以往高效的多目标进化算法提出了严峻的挑战.通过将分解策略和协同策略相结合提出一种高维多目标进化算法MaOEA/DCE.该算法利用混合水平正交实验方法在聚合系数空间产生一组均匀分布的权重向量以改善初始种群的分布性;其次,算法将差分进化算子和自适应SBX算子进行协同进化,以产生高质量的子代个体,并改善算法的收敛性.该算法与另外5种高性能的多目标进化算法在基准测试函数集DTLZ{1,2,4,5}上进行对比实验,利用改进的反转世代距离指标IGD+评估各算法的性能.实验结果表明,Ma OEA/DCE算法与其他对比算法相比,在总体上具有较为显著的收敛性和分布性优势.     

区间参数高维多目标集合进化优化方法

区间参数高维多目标优化问题是现实生活中常见的一类优化问题,但其有效的求解方法并不是很多.对此,利用集合的概念,提出一种求解此类问题的新方法.首先,利用衡量解集收敛性、分布性、多样性的3种性能指标将原优化问题降为3目标优化问题;其次,采用集合Pareto占优关系和不确定测度来区分转化后优化问题解的优劣;再次,设计自适应变化的交叉、变异概率以提高种群的全局和局部搜索能力;最后,利用4种基准函数优化问题,对所提出方法和对比方法进行测试.测试结果显示,除了收敛性,所提出方法得到的Pareto解集的不确定性、多样性、分布性均优于对比方法.     

进化高维多目标优化算法研究综述

首先针对常规多目标优化算法求解高维多目标优化时面临的选择压力衰减问题进行论述;然后针对该问题,按照选择机制的不同详细介绍基于Pareto支配、基于分解策略和基于性能评价指标的典型高维多目标优化算法,并分析各自的优缺点;接着立足于一种全新的性能评价指标-----R2指标,给出R2指标的具体定义,介绍基于R2指标的高维多目标优化算法,分析此类算法的本质,并按照R2指标的4个关键组成部分进行综述;最后,发掘其存在的潜在问题以及未来发展空间.     

融入偏好的区间高维多目标集合进化优化方法

尽管区间参数高维多目标优化问题普遍存在且非常重要, 但是, 目前求解该问题的方法却很少. 本文提出一种有效解决该问题的集合进化优化方法, 通过在进化过程中融入决策者的偏好, 以得到符合决策者偏好的Pareto解集. 该方法将原优化问题转化为以超体积、不确定度、决策者满意度为新目标的确定型3目标优化问题; 为了求解转化后的优化问题, 采用集合Pareto占优关系比较个体, 并设计融入决策者偏好的延展性测度, 以进一步区分具有相同序值的个体; 此外, 还提出集合变异与重组策略, 以生成高性能的子代种群. 采用4个基准高维多目标优化问题和1个汽车驾驶室设计问题测试所提方法的性能, 并将其与另外3种方法进行对比. 实验结果验证, 该方法能得到收敛性、延展性、不确定度, 以及决策者满意度均衡的Pareto解集.     

基于角分解辅助的多阶段高维多目标进化算法

针对大多数现存高维多目标进化算法仍无法在高维空间中有效平衡种群收敛性与多样性的问题,提出一种基于角分解辅助的多阶段高维多目标进化算法(AMEA).该算法协作角分解机制与多阶段自适应删除策略逐一淘汰种群中性能较差的个体,进而平衡种群的收敛性和多样性.前者选取一对夹角最小的个体,其意味着它们最为相似;后者根据种群的进化状态自适应地淘汰这对个体中性能较差的个体.当种群处于未收敛于Pareto前沿状态时,删除策略淘汰收敛性较差的个体,以加速种群收敛.如果这对个体具有相同的收敛性,删除策略则淘汰多样性较差的个体.反之,删除策略利用所设计的综合性能指标来淘汰收敛性和多样性都较差的个体,以提升种群的综合性能.此外,所提出算法设计了基于径向空间投影的匹配选择策略来选取收敛性和多样性都良好的父代个体进入匹配池,进而提高算法探索高维空间的能力.实验结果表明,AMEA在处理高维多目标优化问题时具有较强的竞争力,能有效地平衡种群的收敛性与多样性.     

基于弱关联的自适应高维多目标进化算法

对现有的分解方法进行改进,提出一种基于弱关联的自适应高维多目标进化算法(WAEA).首先,提出一种基于夹角子空间的关联策略,使得一个解能与多个参考向量相关联;其次,提出弱关联概念,并基于此概念设计双模态标量函数,使算法能够更好地处理复杂PF问题,此外,算法通过检测参考向量子空间内解的数量,自适应调整惩罚参数大小,使其能...     

基于全局排序的高维多目标优化研究

目标数超过4的高维多目标优化是目前进化多目标优化领域求解难度最大的问题之一,现有的多目标进化算法求解该类问题时,存在收敛性和解集分布性上的缺陷,难以满足实际工程优化需求.提出一种基于全局排序的高维多目标进化算法GR-MODE,首先,采用一种新的全局排序策略增强选择压力,无需用户偏好及目标主次信息,且避免宽松Pareto支配在排序结果合理性与可信性上的损失;其次,采用Harmonic平均拥挤距离对个体进行全局密度估计,提高现有局部密度估计方法的精确性;最后,针对高维多目标复杂空间搜索需求,设计新的精英选择策略及适应度值评价函数.将该算法与国内外现有的5种高性能多目标进化算法在标准测试函数集DTLZ{1,2, 4,5}上进行对比实验,结果表明,该算法具有明显的性能优势,大幅提升了4~30维高维多目标优化的收敛性和分布性.     

基于向量角分解的高维多目标进化算法

选择是进化的主要驱动力,也是多目标进化算法的关键特征,然而,在处理高维多目标问题时,随着目标维数的增加种群的收敛性和分布性的冲突加剧,传统多目标进化算法中的选择算子已难以有效地维持种群的收敛性与分布性之间的平衡.针对该问题,提出一种基于向量角分解的高维多目标进化算法.首先,将个体本身作为参考向量,利用目标向量之间的夹角...     

基于双极偏好占优的高维目标进化算法

高维目标优化是目前多目标优化领域的研究热点和难点.提出一种占优机制,即双极偏好占优用于处理高维目标优化问题.该占优机制同时考虑决策者的正偏好和负偏好信息,在非支配解之间建立了更加严格的占优关系,能够有效减少种群中非支配解的比例,引导算法向靠近正偏好同时远离负偏好的Pareto最优区域收敛.为检验该方法的有效性,将双极偏好占优融入NSGA-Ⅱ中,形成算法2p-NSGA-Ⅱ,并在2到15目标标准测试函数上进行测试,得到了良好的实验结果.同时,将所提出的占优机制与目前该领域的两种占优机制g占优和r占优进行性能对比,实验结果表明,2p-NSGA-Ⅱ算法无论是在求解精度还是运行效率上,整体上均优于g-NSGA-Ⅱ和r-NSGA-Ⅱ.     

基于进化算法的多目标优化方法

进化算法在解决多目标优化问题中有其特有的优势.首先对多目标优化问题进行了描述;然后结合研究现状讨论了目前几种主要的基于进化算法的多目标优化方法,以及它们的优缺点;最后给出了多目标进化优化算法的一些应用,以及进化多目标优化算法的未来发展方向.     

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

传统多目标优化算法（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核迁移估计模型。其次,当探测到问题环境发生改变时,算法利用以前环境搜索到的Pareto核的有效信息通过Pareto核迁移估计模型对新环境下的进化种群进行近似估计;当问题的环境未发生变化时,引入了带区间分割的变异算子和非劣解存档保优策略,以提高算法的搜索效率。最后计算机仿真表明新算法对动态多目标优化问题十分有效。     

面向复杂超多目标优化问题的自适应增强学习进化算法

在解决超多目标优化问题中,基于分解的进化算法是一种较为有效的方法.传统的分解方法依赖于一组均匀分布的参考向量,它借助聚合函数将多目标优化问题分解为一组单目标子问题,然后对这些子问题同时进行优化.然而,由于参考向量分布和Pareto前沿形状的不一致性,导致这些预定义的参考向量在解决复杂超多目标优化问题时表现较差.对此,提出一种基于自适应增强学习的超多目标进化算法(MaOEA-ABL).该算法主要分为两个阶段:第1阶段,采用一种自适应增强学习算法对预定义的参考向量进行调整,在学习过程中删除无用向量,增加新的向量;第2阶段,设计一种对Pareto形状无偏好的分解方法.为验证所提出算法的有效性,选取具有复杂Pareto前沿的MaF系列测试函数进行仿真研究,结果显示, MaOEA-ABL算法的IGD (inverted generational distance)均值在67%的测试函数上超过了对比算法,从而表明该算法在复杂超多目标优化问题中表现良好.     

混合分解和强度帕累托多目标进化算法

在多目标进化优化中,使用分解策略的基于分解的多目标进化算法(MOEA/D)时间复杂度低,使用〖BP(〗强度帕累托策略的〖BP)〗强度帕累托进化算法-2(SPEA2)能得到分布均匀的解集。结合这两种策略,提出一种新的多目标进化算法用于求解具有复杂、不连续的帕累托前沿的多目标优化问题(MOP)。首先,利用分解策略快速逼近帕累托前沿;然后,利用强度帕累托策略使解集均匀分布在帕累托前沿,利用解集重置分解策略中的权重向量集,使其适配于特定的帕累托前沿;最后,利用分解策略进一步逼近帕累托前沿。使用的反向世代距离(IGD)作为度量标准,将新算法与MOEA/D、SPEA2和paλ-MOEA/D在12个基准问题上进行性能对比。实验结果表明该算法性能在7个基准问题上最优,在5个基准问题上接近于最优,且无论MOP的帕累托前沿是简单或复杂、连续或不连续的,该算法均能生成分布均匀的解集。     

Convergence of multi-objective evolutionary algorithms to a uniformly distributed representation of the Pareto front

In evolutionary multi-objective optimization (EMO), the convergence to the Pareto set of a multi-objective optimization problem (MOP) and the diversity of the final approximation of the Pareto front are two important issues. In the existing definitions and analyses of convergence in multi-objective evolutionary algorithms (MOEAs), convergence with probability is easily obtained because diversity is not considered. However, diversity cannot be guaranteed. By combining the convergence with diversity, this paper presents a new definition for the finite representation of a Pareto set, the B-Pareto set, and a convergence metric for MOEAs. Based on a new archive-updating strategy, the convergence of one such MOEA to the B-Pareto sets of MOPs is proved. Numerical results show that the obtained B-Pareto front is uniformly distributed along the Pareto front when, according to the new definition of convergence, the algorithm is convergent.