多目标优化Knee前沿搜索方法研究进展

李文桦 张 涛 王 锐 王 凌

(1.国防科技大学系统工程学院,湖南长沙 410073;2.多能源系统智慧互联技术湖南省重点实验室,湖南长沙 410073;3.清华大学自动化系,北京 100084)

1 引言

大规模复杂系统、工程设计中的很多决策问题都需要同时考虑多个优化目标,且优化目标之间往往存在互斥关系,即提高某个目标函数值的性能时会引起其他一个或多个目标函数值的衰退,也就是说不存在一个使得所有优化目标都达到最优的解.不失一般性,研究者一般将多目标优化问题(multi-objective optimization problem,MOP)表示为以下形式:

其中:Ω为问题的可行域,fm(x)为决策向量x对应的第m个目标函数的函数值.

与具有单个全局最优值的单目标优化问题不同,在MOP中,存在多个非劣解或称非支配解(non-dominated solution),称为Pareto最优解集.解xA支配xB当且仅当

经过多年的发展,进化多目标优化(evolutionary multi-objective optimization,EMO)算法得到了极大的改进,在待优化问题的目标函数个数较少时,EMO算法表现出了优异的性能,所求解得到的Pareto最优解集合能够兼顾收敛性和分布的均匀性.一般来说,EMO算法大体可以分为以下几类:

1) 基于Pareto支配关系的算法.该类算法利用种群中个体之间的Pareto支配关系,在进化计算的每一次迭代中,首先对所有个体进行Pareto排序,然后算法挑选具有较好支配序的个体组成下一代,以此来推动种群不断向真实的Pareto前沿逼近.代表算法包括NSGA-II[1]和SPEA2[2].

2) 基于分解策略的算法.该类算法通过引入标量函数将多目标问题转化为单目标优化问题.由于不基于Pareto支配关系进行个体优劣排序,该类算法在高维多目标优化问题上较之于NSGA-II等算法具有更好的收敛性.但是算法的性能与所使用的标量函数有很大的关系,而其标量函数的选择依赖于问题本身,即面对不同问题,需选择不同的标量函数来取得满意的结果.代表算法包括MOEA/D[3]和NSGA-III[4].

3) 基于评价指标的算法.该类算法基于某个评价指标,如超体积(hypervolume)、反世代距离(IGD)等,计算种群中个体对解集整体性能的贡献,并将此作为评价个体优劣的指标,进而选择下一代个体继续参与进化.代表算法包括IBEA[5],SMS-EMOA[6],HypE[7]等.

还有一些不属于这3类的MOEA,如第3代差分算法(GDE3)[8]、M-PAES[9]和基于二元存档的MOEA(Two-Arc)[10]等.

实验显示当优化目标个数较少时,基于Pareto支配关系的进化多目标优化算法能够找到令人满意的解.然而随着待优化目标个数的增加,个体之间的支配关系逐渐消失,即种群中绝大多数个体在进化的早期就变得彼此互不支配.这意味着基于Pareto支配关系的选择压力变得非常小,无法引导种群趋向于最优前沿.因此目标数量的增加将严重降低基于Pareto支配关系的EMO算法的收敛能力.

针对该问题,学者们提出了很多改进的方法,例如修改Pareto支配关系的定义,如α-dominance[11],ϵ-dominance[12],cone-dominance[13]等,使得个体在高维空间中仍然具备一定的支配关系.另外,研究表明,基于分解思想和基于评价指标的多目标优化算法在高维多目标优化问题中表现较好,在多达50个优化目标的问题上仍能够获得令人较为满意的解[7].

值得关注的是,一方面,随着目标函数个数的增加,用来描述整个Pareto前沿的个体数量也随之增大.在仅有2-3个目标函数时,通常使用较小的种群就能够完整的描绘出整个Pareto前沿(几何形状);然而当目标个数逐渐增加时,用来准确描述Pareto前沿所需的个体数呈现出指数增长.因此在高维情况下,追求获得完整的Pareto前沿需要设置较大的种群规模,这也意味着求解高维多目标优化问题需要更强大的算力支持,而目前算力仍然是制约优化算法发展的瓶颈[14].

尽管EMO算法能够给出Pareto解集,决策者还需要在众多的Pareto最优解中挑选出一个来应用[15].在目标个数为2或者3时,算法能够给出直观的Pareto前沿,在这种情况下,可以使用后验的方法先获取问题的Pareto前沿,再由决策者挑选出最适合其偏好的解;对于超多目标优化问题,如果决策者能给出其偏好信息,那么利用基于偏好的多目标优化算法也能获得让决策者满意的解.然而,对于决策者无法给出偏好信息的情况,由于目前还没有一种公认的方法能够很好地展示出其Pareto前沿,因此决策者难以做出直观的判断.对许多实际问题(如消费者行为)的实证研究已经明确证实,当候选解决方案的目标数量大于5个时,决策者的决策能力将明显退化[16].

考虑到在高维多目标优化问题中,获得整个Pareto前沿计算复杂度高且无益于决策者做选择,目前一些能够反映决策者偏好的算法得到了极大发展.一方面,研究指出,给定特定的用户偏好信息,并利用偏好信息指导算法的搜索,能够使算法获得更好的性能.Wang等人[17]提出偏好启发式协同进化系列算法PICEAs,在高维多目标优化、交互式决策优化等方面性能突出;Zhang等人[18]提出KnEA,在种群进化过程中寻找Pareto前沿上的Knee,并通过该信息引导种群进化,实验结果表明该算法在测试问题上也具有良好的性能.另一方面,根据用户的偏好,着重搜索Pareto前沿的特定区域,并且忽略用户不感兴趣的区域,可以大大减少种群规模,这样不仅大大提高了计算效率,而且算法更加关注特定的搜索区域也使得解的质量更好.

Knee指的是Pareto前沿中具有局部最大边际效用的点[19].图1为两目标优化问题中Knee的示意图,直观上来看,Knee是Pareto前沿面上的向理想点方向的一个“凸起”,相较于它的相邻解,Knee更加靠近坐标原点.因此,在超体积(hypervolume)指标上,Knee比其他的Pareto解表现更好[18].因此通常来说,在没有决策者的偏好信息的情况下,Knee被认为是决策者更感兴趣的解.

图1 Knee示意图Fig.1 Illustration of Knee

不同的研究者对Knee的定义有所不同,具体来说,可以分别从Pareto的数值特征和几何特征对Knee进行定义:

定义1Knee对应于Pareto前沿上具有极大边际效用的点.换言之,在Knee附近,一个目标函数值的提升会导致至少另一个目标函数值的巨大衰退.

定义2连接Pareto前沿的边界点形成直线或者超平面L,Pareto前沿上到L的距离的极大值点对应的解为Knee.

上述两个Knee的定义,在不同的Pareto前沿形状上对Knee的精确定位存在着差异,但总体对应Pareto前沿上的同一块区域,这将在文章后续进行进一步探讨.另外,从定义中可以看到,Knee是在与它的相邻解的比较基础上定义的,因此相邻解的判定方法也是Knee检测过程中一个非常重要的概念.以两目标优化问题为例,对于每一个Pareto解S,它的相邻解可以定义为:与解S的距离(欧氏距离、曼哈顿距离等)小于d的解.在另一些文献中,也将该距离描述为半径[20].算法中通过设置不同的d,获得的Knee集合也会出现差异.如果设置过小的d值,则算法在搜索过程中极易检测到假的Knee点;相反如果设置较大的d值,则一些局部Knee会被另一些Knee合并.由于需要在算法搜索过程中动态确定所有的Knee,而在未收敛之前,Pareto前沿在集合上具有不均匀、非连续性等特点,因此Knee的检测方法必须具备一定的鲁棒性.

在算法研究方面,一方面许多基于Knee的EMO算法提出在进化搜索过程中寻找Knee,并基于获取到的信息指导进化过程[18].由于Knee本身在HyperVolume等指标上的优势,基于Knee的多目标优化算法在高维多目标问题上表现良好.另一方面,还有一些算法专注于搜索并获得Pareto前沿上的Knee区域.该类算法不关注Pareto前沿的其他部分,最终将获得一部分Pareto解集.

本文主要对Knee的优势进行探讨,并综述了近年来围绕Knee的相关研究.Knee的提出是为了解决高维多目标优化问题的解的选择问题,然而,由于目前还没有公认的较为合适的方式用来描述高维多目标优化问题的Pareto前沿,因此本文在后续的分析中大多使用目标个数为2或者3的多目标问题.本文后续结构为:第2节回顾了Knee的不同检测方法,第3节总结了Knee 的保留策略,第4 节和第5 节则分别介绍了Knee相关的测试问题和性能评价指标.最后,总结了现有的研究并对未来可能的研究方向进行了探讨.

2 Knee的检测方法

Knee的重要性在多篇文献中都有强调[21-22].目前,基于Knee的算法已经在实际工程问题中取得了较好的效果,如网络系统优化设计[23-24]、时间序列预测[25-26]、任务规划[13,27]、聚类问题[28]、车间调度[29]、复杂网络[30]、特征选择[31]等.早在2004年,Jugen等人[19]就指出,Pareto前沿上的Knee区域更受决策者的欢迎.遗憾的是,虽然Knee对于对多准则决策(multicriteria decision making,MCDM)领域具有显著的重要性,但相较于其他EMO算法,Knee的研究受到的关注较小.近年来,根据Knee的定义与特性,学者们提出了许多有效检测Knee的方法,大体上可以分为两类:一是根据Knee在Pareto前沿上的几何特征进行检测.与Pareto前沿的其他部分不同,Knee区域具有明显的几何特征,即Knee区域Pareto前沿的曲率发生突变.二是利用Pareto前沿上评价解之间权衡的指标.在Knee区域,目标函数值之间的影响增大,通过计算此类影响来检测Knee区域.

2.1 基于反射角度的方法

Branke等人[19]提出了基于反射角度的Knee检测方法,如图2所示.在迭代的每一代中,对每一个解,计算它与相邻节点形成的角度.在全部获得角度之后,拥有局部最大角度的点既为Knee.将计算得到的角度替换NSGA-II中的拥挤距离(crowding distance),从而提高Knee的竞争优势,使其在迭代优化的过程中得到保留.文中还指出仅使用角度α作为唯一指标,算法稳定性较差.因此,作者将α,β,γ,δ的最大值作为检测Knee的指标,并开发了基于NSGA-II的Knee算法,取得了一定的效果.然而反射角只考虑到Pareto前沿的局部信息,因此其检测Knee 的鲁棒性不强.Deb 和Gupta[32]提出了一种基于弯曲角的选择机制来弥补这个问题.基于反射角度的方法在二维情况下计算十分简单,但是也存在许多问题.一方面,角度在很大程度上依赖于解之间的位置关系,选择相邻点计算夹角导致误差较大.在点比较密集的情况下,相邻解之间的夹角存在一定的随机性,对于检测Knee带来一定干扰.另一方面,基于角度的方法只能运用在二维情况下,在高维情况下扩展性较差,综合而言,该类方法不适合作为一种通用的Knee检测方法.

图2 基于角度的Knee检测方法示意图Fig.2 Illustration of reflex angle

2.2 基于期望边际效用的方法

在文献[19],Branke等人还提出了利用期望边际效 用(expected marginal utility,EMU)来 确 定Knee的方法.一个解决方案的效用指的是这个解对于决策者而言的性能好坏.在MCDM领域中,已经广泛使用效用函数(或称为标量生成函数)来将MOP组合成一个单目标优化问题,从而使用单目标优化算法求解.线性效用函数可以定义为U(x,λ)==1.其中λi表示每个目标函数的权值.如果决策者给定一组权重向量λ=(λ1··· λm),则可以给出Pareto解集中最满足决策者的解,此时可将多目标优化问题退化为单目标优化问题.然而实际上,决策者往往很难给出这样一组权值向量.

EMU利用一组权重向量来计算的单个效用函数的积分.对于一个解决方案,其EMU定义为该解决方案被次优解决方案替代后产生的额外成本.EMU反映的是一个目标值的改变对另一个目标值的影响,EMU值越大,表示该影响越大.Branke等人给出了两目标下EMU的计算方法:

其中:t表示i=argminU(xj,λ),λ ∈[0,1]是一个由决策者给出的权重向量.

EMU方法虽然原则上可以扩展到高维,然而随着目标函数数量的增加,EMU对于Pareto前沿上不同的解的区别性降低.因此,Bhattacharjee等人[33]提出了改进的EMU方法,称为EMUr,不仅能够识别Knee,还能确定Knee的位置,无论它们位于Pareto前沿的内部还是外部.

此外,类似于EMU衡量一个解决方案目标值之间的影响,其他MCDM领域中用来评价解收敛到理想点的指标也可以用作Knee的检测方法,比如灰色关联分析(grey relation analysis,GRA)[34],以及逼近理想解排序法(technique for order preference by similarity to an ideal solution,TOPSIS)[35]等.

2.3 基于距离的方法

Das等人[36]在1999年提出了一种基于法向边界交点(normal boundary intersection,NBI)的Knee定位方法.Das为两目标问题定义了一条极端线,称为个体极小凸包(convex hull of individual minima,CHIM),该线穿过PF的两个边界点(也称为边缘点edge points).以二维情况来说,将边界点相连得到一条直线L:ax+by+c=0,其中a,b,c可由边界点计算得出.然后分别计算Pareto前沿上各点到直线L的距离.拥有局部最大距离的点即为Knee.如图3所示,Pareto前沿面上的点P(xp,yp)到L的距离可以表示为

图3 基于距离的Knee检测方法示意图Fig.3 Illustration of distance-based method for Knee detection

值得注意的是,该方法可以容易地扩展到高维的情况下,在3维时,直线L变成穿过3个边界点的平面,4维以上则变成超平面.由于该方法计算复杂度低,对于Knee的检测具有较强的鲁棒性,成为当前Knee算法的主流检测方法,在许多算法中得到了应用.

但是,基于距离的方法存在Knee定位不准的问题.由于该方法需要确定边界点,因此一旦边界点无法有效确定,那么Knee的检测也会产生偏差,如图3所示.一般来说,不同类型的算法在保留边界点的策略上会存在明显差异,因此在不同的算法基础上应用基于距离的Knee探测方法会导致结果存在细微的差异.

2.4 基于Trade-off的方法

Trade-off是一对非支配目标向量的特征,可以定义为某些目标的改进的净收益,由于将一个目标向量替换为另一个非支配目标向量而导致的其他目标的恶化,抵消了这些收益[37],通常对每对目标函数都给出折衷的数学定义.

Deb和Gupta[32]提出了两个目标的情况下Tradeoff的计算方法.该方法依赖于用户指定的权衡信息,该信息以一对值(α ＜1,β ＜1)的形式提供.首先将所有目标函数值进行归一化,对于Pareto前沿上的Knee来说,f1中的单位增益至少应在f2中引起α的牺牲,并且类似地,f2中的单位增益至少应在f1中引起β牺牲.

在文献[37]中,Rachmawati和Srinivasan提出了指标用来评价解的Trade-off性能,其计算公式可以表示如下:

其中:n是目标数,fk(xi)表示解xi的第k个目标值,fmax(k)和fmin(k)分别对应总体中第k个目标的最大值和最小值.µ(xi,S)表示通过用xi替换任何解决方案xj从S到每单位劣化的最小改善量.

在文献[38]中,Bechikh在环境选择中利用Tradeoff信息来保留Knee.Li等人[39]在此基础上,提出了Trade-off效用的方法,并且通过实验证明了提出的方法具有良好的效果.

Trade-off方法在寻找Knee的过程中,对于Pareto前沿面的光滑程度敏感度较小,因此也能较好地识别出Knee.但是由于该方法需要计算个体相对于其他所有个体的影响,因此计算复杂度较高.

2.5 基于最小曼哈顿距离的方法

最小曼哈顿距离(minimum manhattan distance,MMD)方法[40]结合了几何信息分析和解性能评估.首先计算Pareto前沿上各个解的曼哈顿距离,具有最小曼哈顿距离的解既为当前的全局Knee点.此方法等效于通过分而治之的方法进行的Knee选择,下面给出该方法检测Knee的详细过程[14].

其中fm和分别是第m维的原始目标值和归一化目标值.由此,MMD可以表示为

由图4可以看出,此方法通过斜率为−1的直线从理想点开始逼近Pareto前沿,直线与Pareto前沿的交点既为当前的全局Knee,此时该直线的截距为v,即为该点的最小曼哈顿距离.在获得全局Knee之后,可以将Pareto前沿一分为二,并递归进行局部Knee的搜索,直到找到全部Knee[14].

图4 MMD方法示意图Fig.4 Illustration of MMD method

基于MMD的方法具备较强的鲁棒性能,并且由于其计算复杂度较低,近年来成为Knee检测算法的热门[41].

2.6 基于锥支配的方法

Pareto支配关系是严格的偏序关系,这意味着所有目标都具有同等的重要性和相同的权重,因此在任何目标上都没有偏好.换句话说,在Pareto前沿上,Knee与其他非Knee的点具有相同的选择优势,算法不会将种群的搜索方向引导到Knee上.针对这个问题,Ramirez-Atencia等人[13]提出了锥支配(cone-domination)的概念,定义了一个权重函数对目标函数值进行转换,可以表示为

其中aij为第j个目标函数中损失一个单元时对应的第i个目标函数的增益值.

通过此定义,对原来的目标函数增加了权重,因此具有Knee特性的解在Pareto支配关系上更具有优势.上述修改可以理解为一个扩展优势关系,提高Pareto前沿上具有特定角度的区域的竞争优势,该角度可以表示为φ并且满足tan=aij,类似的策略也见于文献[42-43].

3 Knee的保留策略

在算法执行过程中,不同的Knee检测方法需要不同的Knee保留方法.通常来说,Knee的保留策略可以分为强制保留和概率保留.

3.1 增加Knee的保留概率

通常而言,EMO算法的进化过程可以归纳为:挑选父代个体产生新解,从中挑选出具有更好性能的解组成新的父代.算法在迭代过程中,种群不断向理想Pareto前沿逼近.NSGA-II采取两个策略对新产生的解进行筛选.首先对新解和父代进行快速非支配排序,并挑选出非支配解,如果非支配解的个数大于设定的种群数量,则进行第2次筛选.在第2次筛选中,首先计算出个体的拥挤距离,并挑选拥挤距离较大的解,以此来维持解分布的均匀性.

在Knee算法中,首先运用Knee检测方法寻找出当前的Knee,然后给Knee以及Knee在周围的解增加优势,由此增大该区域的被选中概率.Branke等人[19]提出使用反射角度和EMU 进行Knee 的探测,并且在NSGA-II算法的基础上,将拥挤距离用反射角度(或者EMU)替换,从而对Knee进行保留.实验结果表明,这个方法在测试问题上具有较好效果.

Li等人[20]则提出使用激活函数给Knee周围的解增加适应度.在Knee检测之后,计算当前解与Knee之间的距离,当距离小于预先设定的阈值时,则对该解进行奖励,以此对Knee进行保留.

3.2 强制保留Knee

与增加Knee的保留概率的方法不同,在特殊情况下,Knee被强制保留进入下一代参与进化,从而确保当前Knee得到保留.基于分解的多目标优化算法使用标量函数将多目标优化问题转化为许多个单目标优化问题,并在一次运行中对所有单目标优化问题求解.Li 等人[20]在MOEA/D的基础上提出了一种获取Knee的算法.在检测到Knee之后,对不在Knee周围的个体的权重向量进行修改,使得个体不断向着Knee靠近,其权重向量更新过程可以表示为

其中:Wi表示个体的权重向量,r ∈[0,2]是随机值.

Sudeng等人[44]在MOEA/D-DE的基础上,引入了参数r用来控制获得的Knee区域的均匀性,并通过实验证明了该方法能有效处理目标个数为2-5的Knee测试问题.

3.3 保留策略的执行条件

算法在搜索过程中需要动态探测Knee,并通过采取特定的策略来保留Knee区域.而由于在算法的搜索过程中,Pareto前沿呈现出不规则性,因此在何种条件下应用Knee的探测方法和Knee的保留方法至关重要.如果过早的进行Knee的探测,则不规则的Pareto前沿将导致对于Knee的误判.在这种情况下,算法可能出现在不同的Knee之间摇摆的情况,从而导致收敛性能变差.

另一方面,如果在算法的后期进行Knee的探测,则对于计算资源是一种浪费.值得注意的是,针对不同的问题,传统的EMO算法收敛到Pareto前沿需要的迭代次数各有不同,因此不可能单独定义一个阈值来作为是否检测Knee的标志.好的策略应是针对不同的问题动态进行阈值调整.

Li等人[20]提出以迭代次数作为分界线,并通过实验指出在30%～50%迭代次数时进行Knee的探测和保留能让算法在给定的测试问题取得最佳效果.然而,由于不同的测试问题,搜索到真实Pareto前沿的难易程度是不同的.因此该方法在进行Knee检测时很难保证当前的Pareto前沿具有显著的几何特征.

Rachmawati等人[37]则指出,可以根据当前非支配解占总体的比值来决定是否执行Knee的保留策略,并通过实验建议当该比值大于80%时采取Knee的保留策略.Zhang等人[14]使用MMD进行Knee的检测并在算法运行的最开始便执行Knee的保留策略.经过试验指出该方法对于特定的测试问题具有较好效果.但是,对于收敛难度较大的测试问题,由于算法运行的前几代无法形成具有几何特征的Pareto前沿,导致算法在收敛难度较大的测试问题上效果较差.

由于不同的问题收敛难易程度不一致,因此,如何确定合适的迭代次数来进行Knee检测和保留,也不尽相同.目前就何时进行Knee的检测与保留提出的方法均有缺陷,随着机器学习等工具的发展,未来针对该问题引入自适应机制进行动态调整,或将成为解决方法之一.

4 测试问题及评价指标

近年来,学者们也相继提出了针对Knee研究的测试问题集.Guo等人提出了二维的测试问题CKP[45];Branke等人[19]基于DTLZ问题提出了DO2DK、DEB-2DK、DEB3DK系列测试问题.该系列测试问题可以通过参数K控制Knee的个数.Tea等人[46]则在DEB-DK问题的基础上,将目标个数拓展到4,5的情况.为方便读者,下面具体给出DEB-DK以及DO2DK问题的表达式以及Pareto前沿.见图5-6所示.

图5 DEB-DK问题Pareto前沿(K=4),其中红点表示KneeFig.5 The Pareto front of DEB-DK (K=4),where the red points represent the Knee

图6 DO2DK问题Pareto前沿,其中红点表示KneeFig.6 The Pareto front of DO2DK,where the red points represent the Knee

由于DEB-DK问题设计相对简单,收敛速度极快,算法一般能在较短时间(如10-20代)内就可以收敛到Pareto前沿,而现实问题往往较为复杂,因此该类测试问题很难反映算法在复杂问题上的性能.Guo等人[47]针对Knee问题提出了的新的、较为全面的PMOP测试问题集,该测试集合考虑了问题是否线性、凸性、退化、规模等特性.其测试问题具体定义如下:

其中:g(X)是控制问题收敛性难易的函数;l(X)用于调整决策变量间的相关关系以及线性或非线性的链接函数;h(X)函数用来确定Pareto前沿的形状;Knee函数k(X)可用于确定Pareto前沿的对称性、Knee个数、位置、退化以及Knee区域的可区分性.

根据问题的定义,原文作者具体提出了PMOP1-14等测试问题,并且该测试问题能够方便的扩展到任意目标维度.图7为PMOP1-14测试问题在三目标情况下的Pareto前沿和Knee分布情况,更多详细信息,请参考原文献.Tea等人[46]在对Knee问题进行研究时,将DEB-DK系列测试问题拓展到4维和5维的情况,并提出了prosection方法用于展示4维和5维情况下测试问题的Pareto前沿.简单来说,prosection方法的想法是使用映射函数一次只显示空间的一部分,如式(14)所示.在4个目标的情况下,该方法定义了两个参数,即角度φ和截面宽度d,并满足|f1sinφ−f2cosφ|≤d.在5个目标的情况下,则需要进行两次变换,如式(15)所示:

图7 PMOP1-14测试问题的Pareto的前沿,其中红点表示KneeFig.7 The pareto front of PMOP1-14,where the red points represent the Knee

其中fi是问题的第i个目标函数值.在本文中,为了更好地显示效果,设置φ=ϕ=45°,d=e=3.

在本文中,展示了具有5个目标函数的PMOP1-9经过prosection变换之后的Pareto前沿及其Knee分布情况,如图8所示.从图8中可以看出,经过投影变换之后的三维图像,仍然具有一定的关于Knee的几何特征,其展示的Pareto前沿具有明显的分层现象.由此可以看出,prosection变换方法能够在一定程度上用于展示具有Knee的问题的Pareto前沿.然而,随着目标函数个数的增多,其Knee特征在转换后的Pareto前沿上越来越不明显.因此,针对高维多目标Knee测试问题的可视化方法仍然是目前的研究重点之一.

图8 5目标PMOP1-9测试问题经过prosection变换之后的Pareto的前沿,其中红点表示KneeFig.8 The pareto front of PMOP1-9 with 5 objectives after prosection,where the red points represent the Knee

对于Knee 问题,由于算法只关注于获得特定的Knee区域,因此针对传统EMO算法的评价指标不太适用于评价Knee算法的优劣.由于缺少相关的评价指标,早期的Knee算法没有使用定量的评价指标对算法进行评价,而是通过给出算法运行的Pareto前沿进行直观判断,其中一个原因是DO2DK、DEB-DK问题具有直观的2-3维的几何特征.随着算法的发展,一些学者提出使用世代距离(GD)作为算法的评价指标.GD[48]代表解与真实Pareto前沿的距离,只反应解逼近真实最优解的距离,因此可以用来衡量Knee算法的性能,其定义如下:

其中n代表解的数量,di是每个解与真实Pareto前沿中最近点之间的欧几里得距离.GD只反应获得的解与真实解的差距,不能反应找到的解是否是Knee,以及距离真实Knee之间的差距.

Guo等人[47]针对Knee问题提出了KGD、KIGD以及KD评价指标,其中KGD评估获得的解到Knee区域参考点的收敛性能,KIGD评估了在Knee区域获得的解决方案的多样性,KD评估算法查找所有Knee的搜索能力.给定在Knee区域中获取的一组均匀分布的参考点Q(包括真实的Knee(K)),G表示获得的Pareto解集,则KGD、KIGD以及KD的计算方式可以表示为

KGD衡量所获得的解与Knee区域的接近程度.它主要评估MOEA的搜索能力,也可以评估其识别Knee区域内解的能力,因为Knee区域以外的解决方案会降低KGD值.而KIGD值指示所获得的解覆盖Knee区域的程度,这主要评估了分布在Knee区域的解的多样性.如果决策者仅对Knee附近而非Knee区域的解感兴趣,KD可以表示解集中是否至少有一个解靠近Knee,并且该解集是否可以找到全部Knee.仅当解集完全覆盖所有Knee时,KD值为零.因此,KD可有效评估算法识别Knee附近个体的能力.

5 总结展望

随着问题复杂度的增加,需要考虑的目标函数也越来越多,因此高维多目标优化开始进入EMO领域.针对高维多目标优化提出的算法,需要使用数量较大的种群参与进化,以描述整个Pareto前沿.由于最终需要从得到的Pareto解集中挑选出一个解作为最终方案,因此花费大量资源去搜寻Pareto前沿上决策者不感兴趣的解是一种浪费.同时,决策者在面对数量巨大、目标函数众多的Pareto解集时,往往很难给出最终方案.多目标优化中,Knee作为在没有特定决策偏好下的更好选择,能够反映出不同目标函数之间互相影响的程度,在近些年得到越来越多学者的关注,特别是在高维多目标优化领域.针对如何检测、获取Knee,大量学者做了相关研究并取得了效果.研究指出,专注于Pareto前沿上的Knee区域能够显著降低问题求解的种群规模,并且有效提高解集的性能.基于此动机,本文对Knee的检测方法、保留策略、测试问题以及算法评价指标等作了较为全面的回顾,以帮助读者快速了解本领域的基本知识和研究现状.

目前针对低维多目标优化问题,全局和局部的Knee均能够被很好的找到并保留,因此Knee算法在一些实际问题上取得了较好效果,例如车间调度、任务规划等.但是针对低维情况,笔者认为可以首先获取整个Pareto前沿,然后采用一些后验的方法来找出Knee区域,因此更多关于Knee搜索的研究应该着眼于高维多目标优化问题.笔者认为,至少可以从以下几个方面对Knee进行研究和开发:

一是结合强化学习[49]等机器学习方法,提高Knee检测的效率和效果.在前面的回顾中可以发现,Knee的检测和保留策略的执行都需要手动设置参数值.然而,类似的最佳参数跟要求解的具体问题息息相关.因此,目前还没有一个公认的较为稳定的参数设置方法.基于强化学习等机器学习技术,在参数的设置上进行优化,或者将此类技术与Knee的检测和保留相结合,从而进一步提高方法的鲁棒性,将是未来可行的研究方向.

二是开发用于展示高维Pareto前沿Knee特征的可视化方法.目前来说,针对高维的Pareto前沿的展示方法有常用的线性图、雷达图等[50].然而,类似的方法只能将多目标优化问题的各个目标函数值进行展示,考虑到Knee问题在2-3维的情况下具有非常明显的几何特征,因此,开发面向任意维度的Knee问题可视化方法,对于Knee算法性能的检测以及检测效果都具有重要意义.Tea等人[46]使用projection技术将4-5维的Pareto前沿投影到3维空间,能大致看出其Knee的几何特征,然而,随着目标个数的增加,其投影之后的图像会变得十分混乱,难以分辨.

三是将基于Knee的EMO算法应用到需要动态决策的问题中.多目标优化算法大多是一种离线的应用,因为其最终要选择一个最优解作为方案去应用.为实现多目标优化算法的在线、动态应用,在缺乏决策偏好信息的情况下,往往很难挑选出最合适的解.由于Knee算法能自动给出当前Pareto前沿上的最佳解,因此结合Knee方法对此类问题进行优化将减少用户输入参数、提升最终解的质量.选择基于Knee的多目标优化算法,即找到Pareto前沿的Knee点(区域),并将之作为最优解进行下一步的动态搜索.目前该理念已被成功应用到自步学习(self-paced learning)中[51-52],并通过实验证明该方法具有良好的效果.在自步学习中,需要不断确定下一步使用哪些数据集参与训练,而Knee算法很好的满足了该需求.另外,在微电网能量管理优化问题中,为了降低用户负荷、可再生能源发电等随机性带来的影响,需要引入模型预测控制方法[53].该方法可以根据预测数据和实时数据动态调整微电网的运行策略,从而降低微电网的运行费用.通过将Knee算法与模型预测控制框架相结合,从而在每个时间节点自动选择最佳解来应用,可以提高EMO算法的适用性以及准确性.