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

传统的多目标进化算法能够有效地解决2个或3个目标的优化问题,但当优化目标超过4维即具有高维目标时,其优化效果将大大下降,因此高维多目标进化算法的研究得到了较多的关注.鉴于此,对高维多目标进化算法的研究进展进行系统地分类综述,分析了高维目标对优化算法造成的困难以及改进的可视化技术;总结了各类算法的特点与缺陷,并给出进一步可能的研究方向.     

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

高维多目标优化问题(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支配、基于分解策略和基于性能评价指标的典型高维多目标优化算法,并分析各自的优缺点;接着立足于一种全新的性能评价指标-----R2指标,给出R2指标的具体定义,介绍基于R2指标的高维多目标优化算法,分析此类算法的本质,并按照R2指标的4个关键组成部分进行综述;最后,发掘其存在的潜在问题以及未来发展空间.     

高维目标减少算法

在多目标优化中,许多实际问题都是由很多目标（超过三个）所组成,但是目前提出的大多数算法却只有在三维以下时高效。由于超过三维的情况无法用欧式空间来表示,而且在处理高维问题时,算法的时间复杂度通常很高,因此人们开始考虑将高维目标转化为低维目标后再处理。首先介绍了目前已经存在的将高维目标转化为低维目标的算法,提出了一种新的算法,该方法通过数据拟合,将各目标函数拟合为一条直线,比较相互之间的斜率之差来确定目标是否存在冗余,以期减少冗余目标。     

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

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

改进聚合树的高维多目标降维优化算法

对于高维多目标优化问题,降维优化算法通过去除或融合冗余目标的方法解决算法耗时过多的问题,但同时也会导致算法分布性能下降。聚合树算法定义非参数秩冲突从而可以快速计算出各目标间冲突度,但聚合树算法鲁棒性有待提高,且需要用户自行决策去除冗余目标。针对这些问题,提出数组叠加机制并定义冲突趋势和冲突度误差,以提高算法鲁棒性;通过合并冲突度较低的冗余目标的方法来进行目标降维,并定义降维截止冲突度;与NSGA-III算法结合,以达到对高维多目标问题进行完整降维优化的目的。为检验该算法性能,与其他经典高维算法进行对DTLZ测试函数集的优化对比,实验结果表明,该算法在耗时更少的同时,也具有较为优秀的分布性能和收敛性能。     

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

传统多目标优化算法（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具有较强的竞争力,能同时保持良好的收敛性和分布性.     

高维多目标头脑风暴优化算法

多目标优化的两个核心指标是收敛性和多样性,而对二者加以优化和权衡是多目标进化算法的关键.头脑风暴优化算法作为一种新型的群体智能优化算法,一经提出便引起了众多研究者的关注.本文在对现有的多目标头脑风暴优化算法研究的基础上,通过对决策变量进行分析,围绕收敛性和多样性分别进行优化,在对收敛性优化时通过分解策略增加选择压力,而在对多样性优化时以参考点更新种群增加多样性,最终扩展并提出了高维多目标头脑风暴优化算法.此外,本文提出一种以角点为聚类中心的自适应聚类方式,明确个体的导向,提高种群的扩展性.与现有的几种效果较好的多目标进化算法进行比较,大量的仿真结果表明了本文的算法具有优秀的性能.     

求解高维多目标调度的新型人工蜂群算法

高维多目标连续优化问题已得到广泛研究,而高维多目标组合优化问题的进展相对较小,虽然人工蜂群(Artificial Bee Colony,ABC)算法已成功应用于多种生产调度问题,但很少被用来求解高维多目标调度问题,而且高维多目标调度自身的研究进展也非常小。针对高维多目标柔性作业车间调度问题,文中提出了一种新型ABC算法以同时优化最大完成时间、总延迟时间、总能耗和机器总负荷。与常规柔性作业车间调度问题不同,上述问题考虑了总能耗,使其成为绿色调度问题。新型ABC具有明显不同于现有ABC算法的新特点,其跟随蜂(onlooker bee)的数量小于引领蜂(employed bee),引领蜂侧重于全局搜索,而跟随蜂只进行局部搜索,通过两类蜜蜂彼此各异的搜索方式来避免算法陷入局部最优。同时,该算法将跟随对象限定为质量较好的部分引领蜂和外部档案成员,其他引领蜂无法成为跟随对象,以避免计算资源浪费在较差解的搜索上,并给出了侦查蜂(scout)新的处理策略。测试实例的仿真实验表明,高维多目标调度问题中非劣解数量占种群规模的比例明显低于高维连续优化问题。将新型ABC与多目标遗传算法和变邻域搜索进行比较,实...     

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

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

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

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

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

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

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

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

基于高维多目标优化的多无人机协同航迹规划

随着无人机应用领域的增多,多无人机协同航迹规划问题变得愈发重要.然而,现存的多无人机协同航迹规划问题大多将多个目标加权转换为单目标问题进行优化,为减少多目标加权的主观性,本文提出一种基于高维多目标优化的多无人机协同航迹规划模型,此模型可以同时优化多无人机航迹距离代价、多无人机航迹威胁代价、多无人机航迹能耗代价,以及多无...     

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

对于高维多目标优化问题,随着目标维数的增加,种群中非被支配解的比例剧增, 严重降低了种群的进化压力.为了对数量众多的非被支配解进行有效的拥挤控制并提升种群的多样性, 本文在提出张角概念的基础上设计了一种新的拥挤控制策略(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的高维多目标优化算法在收敛效果和解集分布的均匀性两个方面均有较大的优势.     

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

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

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

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

基于改进K 支配排序的高维多目标进化算法

为提高4目标以上高维多目标优化问题的求解性能,提出一种基于改进K支配排序的高维多目标进化算法(KS-MODE).该算法针对K支配的支配关系和排序方法进行改进,避免循环支配并增强选择压力;设计新的全局密度估计方法提高局部密度估计精确性;设计新的精英选择策略和适应度值评价函数;采用CAO局部搜索算子加速收敛.在4～30个目标标准测试函数上的实验结果表明,KS-MODE能够在保证解集分布性的同时大幅提升收敛性和稳定性,能够有效求解高维多目标优化问题.     

多目标优化的粒子群算法研究

本文介绍了粒子群优化算法PSO中的多目标优化的粒子群算法及其应用,并将其运用在防守对方多个前锋球员的进攻威胁,以粒子群算法随机性来适应不断变化的形势。     

基于R2指标和目标空间分解的高维多目标粒子群优化算法

基于R2指标和分解策略的多目标粒子群优化算法(R2-MOPSO)在求解2、3个目标优化问题时具有较好的收敛性和多样性,但在求解高维多目标优化问题时难度较大.对此,提出一种基于R2指标和目标空间分解的高维多目标粒子群优化算法(R2-MOPSO-II).首先借鉴R2指标和目标空间分解策略综合权衡选择过程的收敛性和多样性,设...