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

高维多目标优化问题(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时所面临的问题和挑战,并给出未来研究方向的建议。     

基于目标分解的高维多目标并行进化优化方法

高维多目标优化问题普遍存在且难以解决, 到目前为止, 尚缺乏有效解决该问题的进化优化方法. 本文提出一种基于目标分解的高维多目标并行进化优化方法, 首先, 将高维多目标优化问题分解为若干子优化问题, 每一子优化问题除了包含原优化问题的少数目标函数之外, 还具有由其他目标函数聚合成的一个目标函数, 以降低问题求解的难度; 其次, 采用多种群并行进化算法, 求解分解后的每一子优化问题, 并在求解过程中, 充分利用其他子种群的信息, 以提高Pareto非被占优解的选择压力; 最后, 基于各子种群的非被占优解形成外部保存集, 从而得到高维多目标优化问题的Pareto 最优解集. 性能分析表明, 本文提出的方法具有较小的计算复杂度. 将所提方法应用于多个基准优化问题, 并与NSGA-II、PPD-MOEA、ε-MOEA、HypE和MSOPS等方法比较, 实验结果表明, 所提方法能够产生收敛性、分布性, 以及延展性优越的Pareto最优解集.     

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

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

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

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

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

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

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

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

基于目标迁移和条件替代的高维多目标进化算法

尽管许多高维多目标进化算法已被提出,但大多仍无法有效处理具有不规则Pareto前沿的高维多目标优化问题.鉴于此,提出基于目标迁移和条件替代的高维多目标进化算法(MaOEA-OTCR),在环境选择过程中利用目标迁移策略和条件替代准则协作逐一选择收敛性和多样性好的个体进入下一代.前者首先选择位于Pareto前沿边界的极值解进入下一代,以确定Pareto前沿的范围,同时选择收敛性最好的若干个体进入下一代,以加速种群收敛;然后迁移已选解集且利用迁移解集和未迁移解集的最大距离来选择收敛性和多样性好的个体进入下一代.后者利用基于角度和收敛性评估的条件取代准则来防止前者过度强调多样性.此外,提出一个多标准决策的匹配选择策略,旨在增加具有良好收敛性和多样性种群个体结合的概率,进一步提升算法的搜索效率.为了验证MaOEA-OTCR的有效性,在3个测试集上与8个先进的高维多目标进化算法进行对比实验.实验结果表明, MaOEA-OTCR在处理高维多目标优化问题时不仅能够获得较强的竞争性能,而且有能力处理具有不规则Pareto前沿的高维多目标优化问题.     

改进的r支配高维多目标粒子群优化算法

高维多目标优化问题是广泛存在于实际应用中的复杂优化问题,目前的研究方法大都限于进化算法.本文利用粒子群优化算法求解高维多目标优化问题,提出了一种基于r支配的多目标粒子群优化算法.采用r支配关系进行粒子的比较与选择,并结合粒子群优化算法收敛速度快的优势,使得算法在目标个数增加时仍保持较强的搜索能力;为了弥补由此造成的群体多样性的丢失,优化非r支配阈值的取值策略;此外,引入决策空间的拥挤距离测度,并给出新的外部存储器更新方法,从而进一步防止算法陷入局部最优.对多个基准测试函数的仿真结果表明所得解集在收敛性、多样性以及围绕参考点的分布性上均优于其他两种算法.     

一种基于信息分离的高维多目标进化算法

高维多目标优化是指对目标维数大于三维的多目标问题(multi-objective optimization problem,简称MOP)进行优化.大多数传统的多目标进化算法采用Pareto支配关系指导搜索,很难在高维多目标优化问题上得到较为理想的结果.为此,提出了一种基于信息分离的高维多目标进化算法(multi-objective evolutionary algorithm based on information separation,简称ISEA).该算法在目标空间中将原坐标系进行旋转,使第1条坐标轴与向量(1,1,…,1)^T平行.ISEA定义转换坐标的第1个坐标值为收敛信息(convergence information,简称CI),剩余的坐标代表个体分布信息(diversity information,简称DI).同时,采用一种基于分层选择的邻域惩罚机制,利用一种由两个超圆锥组成的邻域形状保持种群的分布性,当个体被选入归档集后,其邻域内的个体将被惩罚进入下一层选择,防止邻近的个体同时被选入归档集.邻域形状的第1部分利用分布信息覆盖邻近的个体,第2部分覆盖边界上的差个体.与NNIA,e-MOEA, MSOPS,AR+DMO以及IBEA这5种经典算法进行了比较.实验结果表明,ISEA在处理高维多目标优化问题时具有良好的收敛性和分布性.     

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

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

改进聚类排序的多目标优化算法

针对高维多目标优化问题提出一种改进型的聚类排序算法,旨在提升原算法所得解的多样性。对该算法的改进,主要集中在两方面。首先,引入了一种双层权值向量系统。相对于原始权值向量方法,该方法可以建立目标空间当中的内部权值向量。内部向量与边缘权值向量的合并,可以促进整体权值向量的多样性。此外,引入一种新的聚类算子,可避免特定权值向量中附着过多的解。实验结果表明,相对比于原始的聚类排序算法和其他两种对比算法,所提出的算法在不同特性的测试问题上具有较好的性能。     

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.     

Reference direction based immune clone algorithm for many-objective optimization

In this paper, a new preference multi-objective optimization algorithm called immune clone algorithm based on reference direction method （RD-ICA） is proposed for solving many-objective optimization problems. First, an intelligent recombination operator, which performs well on the functions comprising many parameters, is introduced into an immune clone algorithm so as to explore the potentially excellent gene segments of all individuals in the antibody pop- ulation. Second, a reference direction method, a very strict ranking based on the desire of decision makers （DMs）, is used to guide selection and clone of the active population. Then a light beam search （LBS） is borrowed to pick out a small set of individuals filling the external population. The proposed method has been extensively compared with other recently proposed evolutionary multi-objective optimization （EMO） approaches over DTLZ problems with from 4 to 100 objectives. Experimental results indicate RD-ICA can achieve competitive results.     

Reference direction based immune clone algorithm for many-objective optimization

In this paper, a new preference multi-objective optimization algorithm called immune clone algorithm based on reference direction method (RD-ICA) is proposed for solving many-objective optimization problems. First, an intelligent recombination operator, which performs well on the functions comprising many parameters, is introduced into an immune clone algorithm so as to explore the potentially excellent gene segments of all individuals in the antibody population. Second, a reference direction method, a very strict ranking based on the desire of decision makers (DMs), is used to guide selection and clone of the active population. Then a light beam search (LBS) is borrowed to pick out a small set of individuals filling the external population. The proposed method has been extensively compared with other recently proposed evolutionary multi-objective optimization (EMO) approaches over DTLZ problems with from 4 to 100 objectives. Experimental results indicate RD-ICA can achieve competitive results.     

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

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

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

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

基于IGD+指标的两阶段选择高维多目标进化算法

针对在高维空间下多目标进化算法难以维持种群收敛性和多样性平衡的问题, 本文提出一个基于IGD+指标的两阶段选择高维多目标进化算法(MaOEA–ITS). 在第1阶段, 算法基于IGD+指标选择收敛性良好的精英个体, 其所需的参考点通过引入切割平面截距法构建. 在第2阶段, MaOEA–ITS使用模糊c均值算法对参考向量进行聚类, 聚类后的参考向量引导种群分解策略对剩余个体进行环境选择, 从而维持种群的多样性. 另外, 为了保护能够提高种群多样性的极值解, 本文提出一个参考点分布自适应策略. 最后, 通过仿真实验来验证MaOEA–ITS的有效性和优越性.     

多因子进化算法研究进展

多因子优化是一类新的优化问题。多因子进化算法受到多因子遗传模型的启发,利用进化个体的单一种群,能够同时求解跨域的多个优化问题。它属于一种文化基因算法,是智能计算领域新近涌现的研究热点。介绍了多因子进化算法的生物学基础、算法流程,以及文化基因算法的基本概念。然后从工作机理、算法改进、典型应用领域等角度,系统总结了前人的理论和应用成果。最后,指出了将来研究所面临的若干挑战和机遇,以推动学科发展。     

基于新型双目标模型的约束优化进化算法

利用双目标模型求解约束优化问题时,由于它们的最优解集并不相等,因此需要增加特殊机制确保求解双目标问题的算法收敛到原问题的最优解.为克服这一缺点,本文首先将约束优化问题转化为新的双目标优化模型,并证明了新模型的最优解集与原问题的最优解集相等.其次,以简单的差分进化为搜索算法,基于多目标Pareto支配关系的非支配排序为选择准则,提出了求解新模型的差分进化算法.最后,用10个标准测试函数的数值试验说明了新模型及求解算法的有效性.