基于投影面的多目标优化问题进化算法MOEA/P

2022-04-12陈未如

沈阳化工大学学报 2022年5期

杨爽, 陈未如

(沈阳化工大学计算机科学与技术学院, 辽宁沈阳 110142)

在实际工程应用中,存在很多目标优化问题(multi-objective optimization problems,MOP).这些目标通常都是相互矛盾、相互制约的,基本上不可能在所有目标上都求得最优解,但存在一个Pareto最优解集[1].Pareto最优解的含义是没有任何其他解在各个目标上都比这个最优解更好.多目标优化算法的目标就是求解Pareto最优解集.由于可能存在无穷解,保证求解完整的Pareto最优解集是费时且几乎不可能的,所以多目标优化算法都是求解Pareto最优解集的近似子集,即在已得到的所有可行解中求解非支配解集——不被已知其他解所支配的解的集合.

进化算法由于基于种群的特点而十分适合多目标优化问题的求解,在近几十年的时间里成为国内外学者研究的热点,尤其是在近20年的时间内有着突飞猛进的研究成果.在最初的多目标遗传算法研究基础上,学者们提出了许多典型的算法:以精英保护策略为主要特征的算法NSGAII[2],利用Pareto支配信息指导解集的选择;基于分解的多目标进化算法(MOEA/D)[3],将一个多目标优化问题分解为一组单目标的子问题进行求解;基于指标评价的算法IBEA[4],通过评价指标指引算法的搜索方向,指导进化过程中新种群的选择;还有一些研究专门研究如何确定多目标权重系数以达到更强寻优能力的目的[5].

近年来,面向超多目标优化问题的算法研究也取得了一定进展,在Google学术搜索上超多目标优化相关论文多达19 700条(2020年3月19日以“many objective optimization”为关键词进行搜索).与多目标优化算法分类相同,面向超多目标优化问题的算法包括:(1)基于Pareto支配关系的超多目标进化算法,如GFM-MOEA[6];(2)基于改进支配关系的超多目标进化算法,如GPO[7];(3)将目标空间划分为若干网格并利用网格坐标作为目标值来判断Pareto支配关系的算法,如grid支配[8];(4)利用模糊逻辑提升某个解支配其他解概率的算法,如fuzzy支配[9];(5)利用小生境技术来判断支配关系的算法,如SDR[10];(6)基于分解的超多目标进化算法,如MOEA/D-AWA[11];(7)基于性能指标的超多目标进化算法,如基于改进的IGD的AR-MOEA[12].

多目标优化所面临的最大问题是存在大量、分散的解,影响算法的求解效率和求解质量.大多数算法都是面向整个解空间研究如何提高求解效率和求解质量,如果能够在较小的范围内求解,如重点关注某几个目标,或选择某些目标值范围内的最优解等,将会大大提高求解效率和求解质量.当面向整个解空间求解时会得到大量的解,而过多的解会使用户无从抉择,因此有侧重地去求所需要的解集,会使决策者在较小的范围内得到自己所关心、期望的结果.这个问题在超多目标优化问题中也尤为突出.

笔者提出一种全新的求解多目标优化问题的思想——基于投影面的多目标优化问题进化算法(multi-objective optimization evolutionary algorithm based on projection plane,MOEA/P).借鉴基于分解的多目标进化算法思想,根据决策需求将目标空间分成投影面和自由维,再把投影面分割成多个投影格,由各个投影格决定求解方向,在各个投影格上求解自由维的最优值,从而得到多目标优化问题的最优解.在求解过程中,利用空间压缩的进化方法,选择适当的适应度函数,由大到小将种群个体压缩向投影目标空间,逐步得到最终解.

投影面的划分将高维多目标优化问题简化成求解低维多目标优化问题,即仅在投影面上求解自由维目标的优化;投影格的分割将求解确定在由决策者指定的目标值具体范围,提高了求解精度和效率.在本算法应用中,可以根据用户的决策方向,有指导地选择相应的投影格进行最优求解,既能够保证求解的精度,又能够保证所得解满足用户决策支持需求.

1 相关工作

以最小化问题为例,多目标优化问题可以描述为:

最小化:F(X)={f1(X),…,fm(X)}T.

约束到:gj(X)≥0,j=1,…,J,

hk(X)=0,k=1,…,K,

X∈Ω.

(1)

{F(X)|X∈Ω,gj(X)≥0,hk(X)=0}.

其中:j=1,…,J;k=1,…,K.

对于任意两个决策向量u,v∈Ω,称u支配v(记作uv).当且仅当 ∀i∈{1,2,…,m}时有fi(u)≤fi(v);当∃i∈{1,2,…,m}时有fi(u)

MOEA/D[3]是基于分解的多目标进化算法的代表,这类算法的核心思想是将一个多目标优化问题按照目标空间个数分为若干个单目标优化问题,同时求解这些子问题并将它们进行组合.在MOEA/D的基础上改进的超多目标优化算法中,大多侧重研究聚集函数的设计、权值向量的分配方式以及自适应方法.基于分解的多目标进化算法基本上采用参考点、参考向量以及权重向量等分解目标空间.由于目标解集可能存在解量大且不均匀的情况,因此,为了减少所得解的数量,得到有一定代表性的较小的解集,Yang等[8]将目标空间划分为若干网格,并利用网格坐标作为目标值进行Pareto支配关系的判断,从而将相近的解归并成一个解.

2 投影面及投影支配

与其他基于分解的多目标进化算法不同,笔者将目标空间按目标维分解为两部分:投影面和自由维.

定义1. 投影面:根据目标决策需求选取部分主要目标维构成投影面(projection plane),投影面上的各目标维称为投影维(projection dimension).投影面P是多目标函数集F的纯子集,即P⊂F.不失一般性,选取前m-1维目标作为投影面进行算法实验分析.这样,对于二目标优化问题,投影面就是f1坐标轴;对于三目标优化问题,投影面是f1、f2构成的一个坐标面.

定义2. 自由维:除投影面外的目标空间其他维称为自由维(free dimension),由所有自由维所组成的集合称为自由维集(free dimension set).自由维集D=F-P.

对于给定目标解向量f在投影面上的投影记为fp,在自由维集上的投影记为fd.

实验中将最后一目标维fm作为自由维.图1给出的是一个三维目标的投影面划分.

图1 三维目标空间划分成投影面和自由维

定义3. 投影点和自由值:目标向量在投影面上的分量称为投影点,在自由维上的分量称为自由值.

定义4. 投影格:将投影面分割成一个个子面,称为投影格(projection grid,PG).用其核心点作为标识向量,该标识向量称为投影格向量(projection grid vector,Vg).Vg由组成投影面的各维度值构成.在不影响理解的情况下,以下简称投影格向量为投影格.

按照本文给出的算法求得落在指定投影面上的目标向量后,以该投影面所限定的子空间(投影格)为目标求解范围,进化求解自由维最优解.

定义5. Pareto投影支配:设多目标优化问题F的投影面P和自由维集D.对于任意两个决策向量u,v∈Ω,称uPareto投影支配v(记作u◁v).当且仅当∀fp∈P时有fp(u)≤fp(v);当∀fd∈D时有fd(u)≤fd(v);当∃fd∈P时有fd(u)

定义6. 非Pareto投影支配解:非Pareto投影支配解是不被任何其他解Pareto投影支配的解.相应地,非Pareto投影支配解集NDP为所有非Pareto投影支配解的集合.以下简称非Pareto投影支配解为非投影支配解.

3 MOEA/P算法

笔者提出基于投影面的多目标优化问题进化算法MOEA/P.它不是求解多目标优化问题的所有Pareto前沿,而是根据目标决策需要将目标空间划分成投影面P和自由维D,同时将投影面分割成投影格,求解非Pareto投影格支配解,进而得到Pareto投影前沿,并在此基础上得到其中的全局非支配目标解.

宏观上看,MOEA/P是一种基于分解的多目标进化算法.但与其他类MOEA/D算法不同,MOEA/P不是分解成若干个参考向量,而是将目标空间分解成两部分:投影面和自由维.MOEA/P也进行网格分割,但分割对象不是整个目标空间,而是投影面,其目的是求各投影格上的最优解.

3.1 MOEA/P算法框架

MOEA/P算法框架

输入:

多目标问题MOP;

结束条件;

DS:目标决策空间(投影面)设定;

ω:投影格边长;

S:初始种群大小.

输出:最优解集PS

过程:

步骤(1) 目标空间划分

根据DS确定MOP投影面及投影范围,并将之分割成边长为ω的多个投影格PGs;

设目标解集PS为空.

步骤(2) 在每个投影格上求非投影支配解

对于PGs的每一个投影格,执行步骤①～③.

步骤① 初始化种群

初始化长度为S的种群G,构造种群中个体并初始个体基因序列,保证所有个体满足MOP约束条件;

对种群G每个个体进行初始计算,得到相应的目标函数值;

设置投影格内个体非支配解个体列表GridList.

步骤② 种群进化

如果满足结束条件,转步骤③;

设置新一代个体池GenPOOL;

分别对种群G中的个体进化操作;

计算每一个新生成个体并根据适应度优先关系将之按序加入GenPOOL中,并将落入到相应投影格内的个体按支配关系插入到GridList;

令G=GenPOOL,并将GridList中的个体插入到G的前端;

对G进行截断操作;

重复本步骤.

步骤③ 提交进化结果

将GridList中所有非投影支配个体提交到PS,并保证不与PS中任何现有个体相互Pareto支配.若存在Pareto支配关系对,则从PS中删去被支配的个体.

步骤(3) 输出PS

3.2 投影面分割

在MOEA/P算法中,目标空间划分是求解的第一步,也是最重要的一步,它包括目标决策空间设定和投影面划分两部分.

目标决策空间设定是要选定投影面及相应决策范围.投影面由用户重点关注和设定的目标维组成.投影维的决策范围即各投影维的决策上下界,它可以采用参考文献[13]的方法设置缺省值,也可以由用户设定所关注的区间.投影维决策范围设定后通过归一化方法,将整个目标空间变换为归一化空间.目标决策空间的设定将最优化求解空间设定到一个较小的范围内,可以大大缩小计算时间并提高计算精度.

投影面选定之后,需要根据投影格边长将投影面分割成投影格,并将各投影格按邻接关系排序,以便进一步求解.投影格由相应的投影格标识向量所标定,对投影面进行分割就是要生成相应的投影格向量.

3.3 适应度函数及投影盒

在MOEA/P算法中,适应度包括两部分:投影格适应度δ和自由维适应度λ.

投影格适应度又称空间适应度,是目标向量f距离指定投影格Vg的距离.

(2)

自由维适应度λ是自由维向量各维同理想值偏差平方和的开方.

(3)

在δ和λ的基础上,MOEA/P算法采用空间压缩思想,设置一个投影盒box,其计算公式为

box=α·λ+β·δ.

(4)

其中:box表示了一个目标向量与投影格Vg在目标空间的距离,其值越小,表明目标向量距Vg越近,就越接近最优值;α、β是适应度强度,反映了自由维和投影面的权重组合.通过进化计算,MOEA/P算法将所有种群个体向投影格向量压缩,使box值在最小范围内的非Pareto投影支配解被最后选中.

4 实验及讨论

4.1 算法性能

由于公式(4)的引入,算法大部分过程通过box向投影格进行压缩,实际上是将多目标问题简化为单目标问题.在将各目标个体向量压入投影格后再进行Pareto投影支配比较,而此时各目标向量已经很接近最终值了.所以算法每次进化迭代的效率可以表示为O(N·LOGN·S),其中:N是种群大小;S是投影格数量.S根据用户需要进行选择设定,而由于投影格的划分,N可以设置得很小.

算法是在将目标向量压入投影格的同时使自由值最优,单目标化的过程保证了算法的收敛性.

算法的多样性通过两种途径实现:一是投影格的划分,保证有解的情况下各个投影格都会求得相应的较优解;二是算法设置的目标间距ε,保证目标个体间不会因为局部太近而使整个区间分布不均.

由于本文研究的是基于投影面的多目标优化问题的求解,并不追求整个目标空间的求解,所以一般用于评价算法性能的方法并不适用于本算法.设ND为算法得到的非Pareto支配解集,以下为算法性能指标相关概念.

(1)目标间距ε:为保证目标个体间不会因为局部太近而使整个区间分布不均,设置目标间距ε,其含义是任何两个目标个体之间至少在一个目标维度上的值不小于ε,否则将被认为是相同的目标.

(2)自由维误差δd:在某指定投影格上,如果有解,算法所求的解与理想解越近越好.自由维误差表示的是所有ND对应非支配解的自由值与理想值距离的算术平均值.

(5)

(3) 投影误差δp:目标个体与其投影点附近所有理想值之间的平均距离.

(6)

其中Dp是投影维个数.投影误差δd可以同时反映算法的多样性指标和收敛性.

4.2 与NSGA-II和MOEA/D算法的对比实验

由于NSGA-II和MOEA/D是两种影响非常广的多目标优化问题进化算法,因此选择与它们进行对比.参照参考文献[3]的相关实验,选择双目标测试用例ZDT1、ZDT2、ZDT3、ZDT4和ZDT6和三目标测试用例DTLZ1-DTLZ2进行对比实验.原文采用种群大小N=100用于二目标测试,N=300用于三目标测试,进化250代.MOEA/P算法对二目标测试划分4个投影格,对三目标测试划分25个投影格,所有测试种群大小都设置为70,同样进化250代.由于MOEA/P划分了投影格,为公平起见,对MOEA/P算法在满足足够进化精度的种群大小情况下,通过调整目标间距ε使所得目标解个数分别在100和300左右.选择相同环境(Intel CPU @3.2GHz)下运行,每组测试独立运行30次.表1与表2中有关NSGA-II和MOEA/D的数据均来自参考文献[3].

表1为算法NSGA-II、MOEA/D和MOEA/P求解部分多目标优化问题时相应的平均运行时间.表1结果显示:MOEA/P算法除了在ZDT6用例上较MOEA/D相当之外,在其他用例上都有很大的优势.

表1 NSGA-II、MOEA/D和MOEA/P平均运行时间

为了测试算法的收敛性和多样性,参考文献[3]使用了D-matric指标.设P*是一组在真实Pareto前沿上均匀采样的解集,A为多目标进化算法求得的近似解集,d(v,A)是v与A中各点的最小欧式距离,则从P*到A的平均距离[3]定义为

(7)

与参考文献[3]相同,选用均匀分布的500点和990点的P*进行D-matric计算.表2为算法NSGA-II、MOEA/D和MOEA/P求解部分多目标优化问题时相应的D-matric值(括号内为标准差).表2结果显示:MOEA/P算法除了在ZDT3用例上较NSGA-II相当之外,在其他用例上都有明显优势,且具有更好的稳定性.

表2 NSGA-II、MOEA/D和MOEA/P D-matirc值

表3是MOEA/P算法求解部分问题所得解的投影误差δp与D-matric计算结果(括号内为标准差).由表3可知:除在ZDT6上因个别点抖动(标准差增大)影响外,其他结果显示投影误差δp与D-matric基本在同一量级,可以用于MOEA/P算法在不同测试用例中进行收敛性和多样性的评价.

表3 投影误差δp与D-matirc值

4.3 超多目标优化实验

对于4个目标以上的超多目标优化问题,往往很难用P*进行D-matric计算,大多数采用超体积指标进行算法的收敛性和多样性测试.笔者利用投影误差δp的概念对算法求解超多目标优化问题的性能进行评价.

选用DTLZ系列测试案例[14]进行超多目标测试.整体采用N=80大小的种群,进化200代.目标间距ε=0.05,分别对 3、4、5、6、7个目标的问题进行求解,每组实验独立运行10次,表4是相关测试结果(括号内为标准差).表4测试结果表明MOEA/P算法在求解超多目标问题时有较好的收敛性、多样性和稳定性.

图2是MOEA/P算法求解部分超多目标问题相应的运行时间与投影格个数的关系.图2表明算法的运行时间与目标个数关联不大,每次迭代运行时间基本上与投影格数目成正比关系.