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

高维多目标优化问题(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支配关系,以增加个体的选择压力;采用群体和外部存储器协同进化的方案,并通过混合微分变异算子,生成子代群体;采用基于指标的方法计算个体的适应度并对群体进行更新;采用基于Lp范数（0相似文献   

基于IGD+S指标的高维多目标进化算法

如何有效评价个体是处理高维多目标优化问题的关键.文中提出改进的反世代距离(IGD⁺S)指标,以反世代距离(IGD)指标为原型,融合修改的反世代距离(IGD⁺)指标的弱支配性,增加无贡献个体概念,可综合评价解集收敛性和多样性.将IGD⁺S指标嵌入进化算法框架中,提出基于IGD⁺S指标的高维多目标进化算法.在环境选择过程中,根据IGD⁺S选择优良个体.实验表明,文中算法在处理DTLZ问题和WFG问题上具有良好的竞争力.     

一种基于自适应模糊支配的高维多目标粒子群算法

高维多目标优化问题由于具有巨大的目标空间使得一些经典的多目标优化算法面临挑战.提出一种基于自适应模糊支配的高维多目标粒子群算法MAPSOAF,该算法定义了一种自适应的模糊支配关系,通过对模糊支配的阈值自适应变化若干步长,在加强个体间支配能力的同时实现对种群选择压力的精细化控制,以改善算法的收敛性;其次,通过从外部档案集中选取扰动粒子,并在粒子速度更新公式中新增一扰动项以克服粒子群早熟收敛并改善个体分布的均匀性;另外,算法利用简化的Harmonic归一化距离评估个体的密度,在改善种群分布性的同时降低算法的计算代价.该算法与另外五种高性能的多目标进化算法在标准测试函数集DTLZ{1,2,4,5}上进行对比实验,结果表明该算法在收敛性和多样性方面总体上具有较显著的性能优势.     

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

高维多目标优化是指对目标维数大于三维的多目标问题(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在处理高维多目标优化问题时具有良好的收敛性和分布性.     

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

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

高维多目标多方向协同进化算法

提出一种高维多目标多方向协同进化算法(HMMCA).该算法利用目标空间内的一组方向向量将多目标优化问题分解成多个方向进行寻优,并提出一种混合变异策略以加强算法在每个方向上的收敛能力;同时,该算法采用改进的交互式模糊支配和拥挤度估计因子来维护外部归档集的规模,增强种群的收敛性和分布性.将该算法与目前性能最好的3种多目标进化算法在标准测试函数集上进行对比实验,所得结果表明HMMCA与其他算法相比具有更好的收敛性和分布性.     

基于线性权重最优支配的高维多目标优化算法

在高维多目标优化问题中,Pareto支配关系存在非支配解随优化目标数增加呈指数级增长和种群选择压力下降等问题。针对这些问题,基于线性权重聚合函数和支配关系两种比较多目标解方法的思想,提出一种线性权重最优支配关系（LWM-dominance）,并理论证明了LWM非支配解集是Pareto非支配解集的子集,同时保留了种群中重要的角解。进一步地,基于LWM支配关系,实现了一个高维多目标进化优化算法,基于该算法的实验验证了LWM支配关系的性质。在随机解空间中的实验结果表明LWM支配关系适用于5~15个目标的高维多目标优化问题,通过DTLZ1~DTLZ7高维多目标优化问题进化过程中LWM非支配解集与Pareto非支配解集规模的对比实验,结果表明优化目标数为10和15时非支配解的比例平均下降了约17%。     

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

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

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

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

基于空间网格划分的多目标进化算法

为了有效求解多目标优化问题,找到分布宽广、均匀的Pareto解集,提出了一个基于空间网格划分的进化算法。将目标空间网格化,利用网格的位置,删除大量被支配个体。在杂交算子中利用了单个目标最优的个体信息,以增加非劣解的宽广性。利用一种新设计的基于最大距离排序的方法删除非劣解集中多余个体。数值实验表明提出的算法是可行有效的。     

一种基于邻域的多目标进化算法

种群维护是多目标进化算法的重要组成部分。针对维护方法和运行效率的矛盾,提出一种基于邻域的多目标进化算法（NMOEA）。定义了一个反映个体之间邻近程度的指标--邻域包含关系,利用此关系对个体进行分布适应度分级的赋值,并用动态方法快速地对种群进行维护。通过7个测试问题和3个方面的测试标准,结果表明新算法在较快速地接近真实的最优面的同时,拥有良好的分布性。     

基于空间距离的多目标差分进化算法*

在经典差分进化的基础上,提出了一种基于空间距离的多目标差分进化算法(SD-MODE),与目前经典算法NSGA-Ⅱ和ε-MOEA 进行比较,结果表明该算法拥有良好的分布性,同时也较好地改善了收敛性。     

一种基于个体密度估算的多目标优化演化算法

通过在目标空间中利用目标本身信息估算个体k最近邻距离之和,作为个体的密度信息,根据个体的密度信息对群体中过剩的非劣解进行逐个去除,以便更好地维护解的多样性,由此给出了一种基于个体密度估算的多目标优化演化算法IDEMOEA。用这个算法对几个典型的多目标优化函数进行测试。测试结果表明,算法IDEMOEA求解多目标优化问题是行之有效的。     

一种基于相似个体的多目标进化算法

分布性保持是多目标进化算法研究的一个重要方面,一个好的分布性能给决策者提供更多合理有效的选择。Pareto最优解的分布性主要体现在分布广度与均匀性两个方面。提出一种基于相似个体的多目标进化算法（SMOEA）。在种群维护中删除相似程度最大的个体;在进化操作中,选取了相似程度最大的个体进行进化。与目前经典算法NSGA-II和ε-MOEA进行比较,结果表明新算法拥有良好的分布性,同时也较好的改善了收敛性。     

基于模糊决策与进化算法的生产设备布局优化

为解决复杂情况下制造系统的生产设备布局优化问题,提出了一种将模糊决策与进化算法相结合的设备布局优化方法。进一步完善了优化模型,优化目标包括总成本最小、设备相邻要求最大化和面积利用率最大化等优化目标;其中总成本最小目标考虑了物料搬运成本,设备重置导致的设备拆装、移动成本,生产停工造成的产能损失成本。该方法考虑了用户对于成本、利用率及相邻性要求等存在的满意度、优先度等模糊情况,基于模糊决策理论,对多目标优化模型进行了模糊化处理,设计了模糊适应度函数,用以根据用户的优先关系评价pareto解集。基于求解模型的特点,对多目标进化算法的染色体编码方式与交叉、变异等遗传操作方式进行改进,以提高求解该模型的实用性与效率。最后以实际案例的优化结果证明了该方法的有效性。     

基于密集度的搅动多目标演化算法

多目标演化算法的研究目标是使算法种群快速收敛并均匀分布于问题的非劣最优域.定义和使用密集度来保持群体中个体的均匀分布,将个体的Pareto强度值和密集度合并到个体的适应值定义中.提出搅动策略,以提高算法对解空间的遍历性,从而较大程度上避免算法的早熟,对每次搅动得到的部分非劣解个体进行邻域搜索以加快非劣解前沿的进化.最后,测试函数的实验结果表明了算法的可行性和有效性.     

一种新型的多目标优化混合量子进化算法

针对复杂多目标优化问题,提出一种混合量子进化算法,并利用它求解多目标函数优化问题。该算法根据多目标优化的特点,创建外部集合保存历代搜索到的非支配解,利用其中的精英个体设计了一种旋转角自适应调整的量子门更新策略,并对量子比特表示的概率幅设置最大和最小阈值,以防止量子群体早熟收敛。借鉴量子门引入了专门针对量子个体的旋转交叉算子,同时小概率地对量子比特进行取反变异操作。对所提算法的计算复杂度进行了理论分析。与另一种已有的多目标量子进化算法的比较结果表明,所提算法具有更好的收敛性能、分布特性及求解效率。     

基于半监督的多目标进化模糊聚类算法

为了解决传统聚类由于缺少有效指导而导致图像分割结果不理想的问题,将半监督方法引入到多目标进化模糊聚类算法中,提出了一种基于半监督的多目标进化模糊聚类。图像分割算法通过构造基于半监督的类内紧致性函数和类间分离度函数,利用监督信息指导聚类过程获得非支配解集。为了从非支配解集中选择一个最优解,利用监督信息构造了基于相似性度量的有效性指标。实验结果表明,提出的方法在分割准确率和视觉效果上明显优于无监督的聚类方法。     

基于多目标进化算法的手机概念设计优化

针对手机设计领域应用计算机辅助设计存在的一些问题,以及如何处理相互冲突的多目标间的优化问题,深入地分析了概念设计过程中的创新思维和多目标优化的基本理论.在手机概念设计阶段同时考虑了用户要求.构件设计属性.设计成本和综合评价值等多种因素,将分布估计算法应该于求解手机集成的多目标优化问题,给出了具体的方法和步骤.实验结果表明,该方法可以提高设计的创新性,给设计人员提供有益的借鉴.