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

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

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

高维多目标优化问题(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/d2:一种基于双距离构造的高维多目标进化算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

DAV-MOEA:一种采用动态角度向量支配关系的高维多目标进化算法

现实中不断涌现的高维多目标优化问题对传统的基于Pareto支配的多目标进化算法构成巨大挑战.一些研究者提出了若干改进的支配关系,但仍难以有效地平衡高维多目标进化算法的收敛性和多样性.提出一种动态角度向量支配关系动态地刻画进化种群在高维目标空间的分布状况,以较好地在收敛性与多样性之间取得平衡;另外,提出一种改进的基于Lp...     

A Line Complex-Based Evolutionary Algorithm for Many-Objective Optimization

In solving many-objective optimization problems(MaO Ps), existing nondominated sorting-based multi-objective evolutionary algorithms suffer from the fast loss of selection pressure. Most candidate solutions become nondominated during the evolutionary process, thus leading to the failure of producing offspring toward Pareto-optimal front with diversity. Can we find a more effective way to select nondominated solutions and resolve this issue? To answer this critical question, this work proposes to...     

一种基于混合交叉策略的多目标演化算法

演化算法是求解多目标优化问题(MOP)重要而有效的方法,而应用演化策略、技巧是改善解性能的重要途径。论文叙述了多目标优化问题的有关概念,结合已有算法中的方法,设计了基于两种交叉操作相互结合的多目标演化算法(MOEAHC),该算法不仅具有较高的计算效率,而且能够保持解的多样性分布。测试结果表明该算法的良好性能。     

基于新模型的动态多目标优化进化算法

在动态多目标优化中,各目标通常相互冲突,其最优解往往有无穷多个,如何在时间连续发生变化的情况下依然能求出分布均匀且数量多的Pareto最优解供决策者选择十分重要.对动态多目标优化问题连续变化的时间变量区间进行了任意划分,在得到的每个时间子区间上把动态多目标优化问题近似为静态多目标优化问题,进而在每个子区间上定义了种群的静态序值方差和静态密度方差,然后把目标个数任意的动态多目标优化问题转化成一个双目标静态优化问题.在给出的一种能自动检测时间变化的自检算子下,提出一种新的动态多目标优化进化算法,并且证明了算法的收敛性.计算机仿真表明新算法对动态多目标优化问题求解十分有效.     

Pareto强度值演化算法求解约束优化问题

提出了一种求解约束函数优化问题的方法.它不使用传统的惩罚函数,也不区分可行解和不可行解.新的演化算法将约束优化问题转换成两个目标优化问题,其中一个为原问题的目标函数,另一个为违反约束条件的程度函数.利用多目标优化问题中的Pareto优于关系,定义个体Pareto强度值指标以便对个体进行排序选优,根据Pareto强度值排序和最小代数代沟模型设计出新的实数编码遗传算法.对常见测试函数的数值实验证实了新方法的有效性、通用性和稳健性,其性能优于现有的一些演化算法.特别是对于一些既有等式约束又有不等式约束的复杂非线性规划问题,该算法获得了更高精度的解.     

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

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

一种基于云模型的多目标进化算法

在多目标进化算法的基础上,提出了一种基于云模型的多目标进化算法(CMOEA).算法设计了一种新的变异算子来自适应地调整变异概率,使得算法具有良好的局部搜索能力.算法采用小生境技术,其半径按X条件云发生器非线性动态地调整以便于保持解的多样性,同时动态计算个体的拥挤距离并采用云模型参数来估计个体的拥挤度,逐个删除种群中超出的非劣解以保持解的分布性.将该算法用于多目标0/1背包问题来测试CMOEA的性能,并与目前最流行且有效的多目标进化算法NSGA-II及SPEA2进行了比较.结果表明,CMOEA具有良好的搜索性能,并能很好地维持种群的多样性,快速收敛到Pareto前沿,所获得的Pareto最优解集具有更好的收敛性与分布性.