基于Pareto支配的高维多目标优化算法的分析与研究

2023-03-30 08:52操心慧许丽娟
现代计算机 2023年2期
关键词:高维收敛性支配

操心慧,许丽娟

(广州华商学院数据科学学院,广州 511300)

0 引言

多目标优化问题(multi‑objective optimization problems,MOPs)是指具有多个目标且在本质上存在冲突,需要同时进行优化的问题。多目标优化的概念在实际应用中经常被研究,如软件工程、配电网络和工业调度[1]。多目标优化方案中各目标的冲突行为,导致获得一组非支配解,称为Pareto最优集,即目标空间[2]。多目标优化算法(MOEAs)在求解多目标优化问题时是有效的,因为它们能够在单次运行中获得Pareto 最优集。MOEAs 在求解MOPs 时的主要目的是在收敛性(得到的Pareto前沿与真实Pareto前沿的接近程度)和多样性[3](得到的Pareto前沿中种群的均匀分布)之间取得平衡。MOEAs能否在收敛性和多样性之间进行权衡,主要取决于所采用的选择策略。按照机制将其大致分为:Pareto支配型MOEAs(PD‑MOEAs)、分解型MOEAs、指标型MOEAs[4],而其中Pareto支配型MOEAs最为流行。

然而,大多数经典的基于Pareto 支配的MOEAs(PDMOEAs)在多目标优化问题上表现较好,但在处理超过三个目标的问题,也就是高维多目标优化问题(MaOPs)时,效果大大折扣。PDMOEAs 在解决多目标优化问题时,由于难以在收敛性和多样性之间取得平衡,其性能急剧下降。导致PDMOEAs 性能下降的主要原因是Pareto支配关系的失效,后续多样性的维护操作占据了主导位置,这种现象降低了选择压力,不能引导搜索过程向收敛方向发展。也可以理解为由于目标空间维度的增加,MOEAs 的行为采用了随机搜索,大多数个体变得无法比较,而解集无法收敛到Pareto最优前沿[5]。

此外,随着目标数量的增加,在多样性和收敛性之间取得平衡成为一项艰巨的任务。由于计算复杂度的问题,MOEAs 中使用的种群规模有限,个体最终会在高维空间中彼此远离,导致进化效率低下。因此,对于MaOPs 来说,设计一种算法使其稳定有效地找到收敛性和分布性都不错的Pareto最优解集仍有一定难度。目前进化计算的权威期刊《IEEE Transactions on Evolutionary Computation》和《Evolutionary Com⁃putation》每年都发表一系列关于高维多目标优化的研究成果,并呈逐年递增趋势。在国内,该领域的研究始于2010 年,迄今为止不仅论文发表数量不多而且研究成果远滞后于国外,属于起步阶段,亟待加大研究投入,所以在国内开展MaOEAs的研究具有十分迫切的需求。

1 高维多目标优化问题概述

1.1 高维多目标优化问题(MaOPs)

在解决多目标优化问题时,有些问题是难以解决的。这是因为多目标优化问题(MOPs)不同于单目标优化(SOPs),在最优解上多目标优化问题具有多个最优解,而高维多目标问题是普通多目标问题的复杂情况。

对于一个具有k个目标,n维决策变量的MOPs,其数学模型[6]为

其中,x=(x1,x2,…,xk)∈Ω 被称为k维决策向量,为一组个体。当k≥4 时为高维多目标优化问题,在目标进化中优化函数向量k是目标函数的个数。求解高维多目标优化问题的最终目的是得到一组无限收敛于真实Pareto前沿,并且均匀分布的Pareto解集。

1.2 解决高维多目标优化问题面临的问题

常规多目标优化算法能够有效解决两个或三个目标的多目标优化问题,但将算法拓展到MaOPs(高维多目标优化问题)时,其求解过程将主要面临以下三个问题:

(1)随着目标维数的增加,对于给定的种群,该种群中非支配解的数量占其种群规模的比例接近于1。因此,Pareto 支配关系不适合在这类问题的解之间进行区分。MaOPs 面临的另一个问题是,近似整个Pareto 前沿所需解的数量,正常情况下会随着目标函数的数量呈指数增长。因此,需要更大的种群规模来获得适当的Pareto集近似,这又需要更长的执行时间。

(2)随着目标维数的增加,如果MaOPs 的大多数目标高度相关,则其Pareto前沿不太可能在高维目标空间的广泛范围内扩散。此外,如果它们依赖于少数相互矛盾的目标,则目标空间中Pareto 沿的维数可能远远小于目标的数量。除了目标的数量及其相互关系之外,实验表明当每个目标的目标值范围不同时,一些专门设计用于处理MaOPs 的MOEAs 可能无法获得预期的性能。因此,需要进行目标归一化。然而,MaOPs 缺乏一种有效的、鲁棒的归一化方法。此外,观察表明,归一化在性能上的影响具有很强的问题依赖性。

(3)多样性是另一个需要考虑的方面。虽然非支配解会影响收敛性,但保留合理数量的解可能有利于种群多样性。目标数量不断增加所带来的巨大目标空间,为在MaOPs上保持解集均匀分布带来了几个挑战。在这些挑战和研究机会中,仍然需要开发适当的多样性保存机制、适当的拥挤距离机制和最优解集的最终评估方法。

2 PDMOEAs的改进方法

针对PDMOEAs 在处理高维多目标优化问题时所出现的性能缺陷,专家学者们对其进行改进,改进的方向大致分为以下三类。

2.1 优势关系的松弛

这一类思想侧重于放松支配关系,即通过引入新的支配关系来修改传统Pareto支配关系的定义。引入改良显性关系的主要目的是提高两个体在MaOPs上的可比性。

文献[7]提出了一种新的控制个体优势区域(CDAS)的方法,以提高MOEAs 的性能。CDAS算法通过控制优势区域,诱导出合适的个体排序,增强了选择过程。文献[10]提出了一种自适应外部参数S 和自控制个体优势区(S‑CDAS)的CDAS 方法来解决MaOPs 问题。在S‑CDAS 算法中提出的主要改进是,S‑CDAS 采用了细粒度排序,将极限解始终包含在队列的最前面。文献[8]提出了一个广义Pareto 最优(GPO)来处理PDMOEAs 的可扩展性问题。GPO 的主要思想是,随着问题维度的增加,解决方案的主导区域逐渐扩大。广义Pareto最优方法与控制优势区域扩张程度的扩展角参数相关联。文献[9]提出了Pareto支配关系的模糊化方法,并分析了该方法在MOEAs 设计中的适用性。同时,描述了一种通用排序方案,该方案以集合依赖、非对称和尺度无关的方式分配具有支配度的任意向量集。文献[10]引入了一种新的适应度评价机制,将解连续划分为不同程度的最优解。在适应度评价机制的基础上,基于模糊逻辑提出了一种模糊Pareto‑dominance(FD),并将其整合到流行的NSGA-II和SPEA2中,增加解决MaOPs上的性能。文献[11]提出了一种对传统Pareto‑dominance的修正,称为g‑dominance,可以被纳入到任何MOEA 的设计中。g‑dominance 利用了纳入参 考点的信息,没有任何缩放函数的帮助,逼近最优区域周围的有效集。文献[12]提出了ε-MOEA,该ε-MOEA 采用了一种新的Pareto 优势变体—ε-优势与存档和选择策略相结合,以提高对Pa‑reto最优集的搜索。文献[13]提出了强化优势关系(SDR),它是对Pareto 优势关系的一种新的加强方式。然而,改良优势度关系的PDMOEAs 处理MaOPs 的性能有所提高,但往往会出现局部最优情况。

2.2 使用附加指标结合Pareto优势

这类思想集中于将附加的指标与Pareto优势相结合,以促进PDMOEAs 的融合。许多工作集中在发展有效的额外指标,以提供适当的均衡之间的收敛性和多样性。

文献[14]提出了一种MOEA(NSGA-III),该MOEA 生成一组均匀分布的参考点,并优先考虑与参考点垂直距离最小的非支配解,以保持多样性。换句话说,在NSGA-III 中,多样性的保存机制借助于一组分布良好的参考点。在NSGA-III 的环境选择中,合并种群中的每个个体都与一个参考点关联,与参考点距离最小的解将被选择。文献[15]引入了一种多样性机制,基于移位的密度估计(SDE)指标,旨在保持多样性而不失去收敛性。SDE 的基本思想是通过相对于每个目标的收敛性比较,移动其他个体的位置来估计候选解的密度。因此,收敛性能较差的个体会有高密度值。文献[16]提出了基于Pareto‑dominance 和排序方法的MOEA,在总体中给每个候选解分配一个优先级排序。根据①非支配排序得到的解的Pareto 排序给每个候选解分配优先级排序;②归一化目标和;③改变生态位半径。优先级最低的个体在交配和环境选择中更受青睐,因为它们加速了向Pareto前沿的收敛,同时保持了多样性。文献[13]提出了一种基于矢量角度的MaOPs-EA,它采用了Pareto 优势与最大矢量角度优先原则相结合。除了这些指标,还采用了劣解消除原则。文献[17]基于有利收敛(FC)和方向多样性(DD)提出了一种多目标进化算法(MOEA-DDFC)。在MOEA‑DDFC 算法中,引入了良好的收敛性和方向多样性,使算法的收敛性和多样性同时提高。

2.3 以支配与分解相结合为基础

最后一类是将基于支配的方法与基于分解的算法相结合。文献[18]提出了一个统一的范式,采用基于优势的方法与基于分解的方法相结合来解决MaOPs(MOEA-DD)。在MOEA-DD中,利用一组权值将目标空间划分为不同的子区域,每个权值向量定义一个适合度评估子问题。文献[19]提出了一种双准则进化(BCE)框架,将Pareto 准则(PC)方法与非Pareto 准则(NPC)方法相结合,增强了收敛性和多样性。双标准方法试图通过充分交换信息的协作方式将PC 和NPC 方法的优势结合起来,以促进彼此的进化。另一方面,双标准进化试图弥补彼此的弱点。

3 ad⁃MOEA

上节提到对于PDMOEAs 算法的改进,最终的目的都是想要均衡算法的收敛性和多样性。基于此,本节详细介绍一种具有自适应交配和环境选择的多目标优化进化算法(ad‑MOEA),利用自适应交配和环境选择的策略自适应地平衡算法的收敛性和多样性。

3.1 ad⁃MOEA的总体框架

该算法的总体框架类似于经典的NSGA-II。在该方法中,随机生成一个大小为N 的初始种群,并对其初始化。初始化后,得到归一化目标(SoNB)和拥挤距离(CWD)的Pareto 最优解集。根据这些准则计算每个候选解的加权级,然后进行交配选择,随机选择两个亲本解,并根据权重进行比较,选择一个权重最小的解作为后代的亲本。在交配选择后,通过突变和重组操作生成大小为N的后代种群。

将子代种群与父代种群合并,对合并种群中的每个个体,得到每个候选解的Pareto 排序和归一化目标之和(SoNB)。环境选择过程中,在Pareto 优势之后,个体的选择一直持续到临界前沿。

在临界前沿,一定概率下基于目标之和选择候选解,根据拥挤距离选择剩余的候选解。选择候选解的概率由一个自适应参数w决定。最初,参数“w”的值设置为1,因为在初始代中需要收敛。然后根据问题的特点,自适应参数w的值。但随着进化到需要增强多样性的最后阶段,“w”的值预计会下降。图1 描述了所提方法的框架,在NSGA-II 框架的基础上结合归一化目标之和SoNB 以及拥挤距离CWD 得到ad‑MOEA算法的总体框架。

图1 ad⁃MOEA总体框架

3.2 交配选择

交配选择过程在MOEAs 的进化过程中起着重要作用。在产生过程中,筛选有前景子代进化的解决方案将提高算法的性能。该算法在交配选择中引入了加权的概念,为了得到加权排序,首先对个体进行Pareto排序和归一化目标之和的升序排序,并按照排序后的顺序给每个个体分配一个排序,根据排序结果,选择有前景的子代进化产生后代种群。算法1描述了交配选择的过程。

3.3 环境选择

环境选择的主要目的是为下一次迭代保留作为父种群的精英。在环境选择中,首先将交配选择后获得的子代种群与父种群进行组合。然后对合并后的种群采用Pareto优势法,将个体分配到不同的非优势Pareto 前沿。根据Pareto‑Dominance 算法,得到了每个候选解的归一化目标和拥挤距离之和。

首先,来自第一个非支配Pareto 前沿F1和判断 |F1|>N,F1中的个体是基于考虑标准化目标总和(SoNB)和拥挤距离(CWD)的自适应方法进行选择。如果前面个体解的大小(F1)小于N,则从第二个非支配Pareto 前沿F2中选择解;如果|F1∪F2|>N,就将Pareto前沿F2视为非支配Pareto前沿,并采用自适应方法选择第二非支配Pareto前沿的解。对于下一代而言,在获得具有精英解的N大小种群之前,遵循的相同过程选择非支配Pareto前沿的个体。本文采用了自适应参数w,为了调整参数,利用关于组合总体中非支配解数量的信息,自适应参数w采用如下公式计算。

其中:wt表示t代参数w的值;wt-1表示上一代中w的值;M为目标个数;NF表示总体中非支配解的数量,N表示个体总数量。首先,基于归一化目标与百分比(w× 100)所需的解决方案是根据归一化目标的总和来选择的。然后根据拥挤距离选择剩余解,因此参数w在环境选择中起着关键作用。

4 结语

本文对解决高维多目标优化问题的算法进行了研究与分析,重点介绍了一种具有自适应交配和环境选择的多目标进化算法(ad‑MOEA)以及处理多目标和多目标优化问题的过程。该方法将归一化目标之和的概念引入交配选择和环境选择中,用以均衡收敛性和多样性,从而得到最优结果。环境选择中,在临界前沿,首先根据目标之和选择方案,然后根据拥挤距离选择剩余方案。为了选择基于归一化目标和的解,本文采用了由自适应参数决定的一定概率,与现有的NSGA-II 算法相比,该算法的性能有所提高,与其他先进算法相比具有竞争力。尽管如此,还无法完全解决PDMOEA 在高维多目标优化上遇到的问题。

猜你喜欢
高维收敛性支配
被贫穷生活支配的恐惧
Lp-混合阵列的Lr收敛性
跟踪导练(四)4
一种改进的GP-CLIQUE自适应高维子空间聚类算法
END随机变量序列Sung型加权和的矩完全收敛性
基于加权自学习散列的高维数据最近邻查询算法
基于决策空间变换最近邻方法的Pareto支配性预测
随心支配的清迈美食探店记
一般非齐次非线性扩散方程的等价变换和高维不变子空间
行为ND随机变量阵列加权和的完全收敛性