多目标进化算法性能评价指标综述

来源:用户上传      作者:

　　摘 要：多目标进化算法常用于解决较复杂的多目标优化问题，该类算法是基于种群的进化算法，通过产生一组近似Pareto最优解集满足决策者偏好。介绍了多目标优化问题背景知识及相关定义，根据评价指标衡量解集特性，将现有算法性能评价指标分为3类并分别进行阐述，分析、比较其特点与区别。
　　关键词：多目标优化;进化算法;评价指标;最优解集
　　DOI：10. 11907/rjdk. 191024 开放科学（资源服务）标识码（OSID）：
　　中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2019）009-0001-04
　　A Survey of Performance Indicators for Multi-objective Evolutionary Algorithms
　　HU Han， LI Zhen-yu
　　（School of Computer Science and Technology， Nanjing University of Aeronautics and Astronautics， Nanjing 210016， China）
　　Abstract： Multi-objective evolutionary algorithms are often used to solve complex multi-objective optimization problems. The algorithms are population-based evolutionary algorithms that satisfy decision makers' preferences by generating a set of approximate Pareto optimal solution sets. This paper introduces the background knowledge and related definitions in multi-objective optimization problems. According to the characteristics of the solution set measured by the evaluation indicators， the existing algorithm performance indicators are divided into three categories and elaborated separately， and their specifics are analyzed and some differences between them are compared.
　　Key Words： multi-objective optimization; evolutionary algorithms; performance indicator; optimal solution set
　　0 引言
　　多目标优化问题在日常生活中较为常见，无论是在科学研究还是实际工程应用中，多目标优化都是非常重要的课题。不仅因为多目标优化问题往往伴随多个目标需要同时进行优化，而且多目标优化的最优解往往是一组解集，如何选出符合决策者偏好的解也是亟需解决的问题。
　　单目标优化问题优化的只有一个目标并且最终得到一个单独的最优解。但多目标优化问题中目标之间往往相互冲突，一个目标性能提升往往伴随其它一个或多个目标性能下降。多目标优化问题中存在一组表示各个目标间权衡和折中关系的解集，通常称为Pareto最优解集。Pareto最优解集在目标域的投影被称为Pareto前沿[1]。
　　为了更好地解决多目标优化问题，研究人员提出了多种用于求解多目标的进化算法，诸如NSGA-II[2]、MOEA/D[3]、HypE[4]等。随着多种多目标进化算法的出现，如何比较和衡量这些算法性能成为一大热门课题。对一个多目标进化算法进行评价时，一方面需有一套能够客观反映多目标进化算法优劣的评价工具或方法;另一方面需选取一组有代表性的测试集。效果、效率、鲁棒性、问题求解范围，以及是否方便使用等是考察多目标进化算法的重要指标。
　　1 多目标优化问题概述
　　通常一个求解最小化目标值的多目标优化问题可以被定义为：
　　[minF（x）=（f1（x），？，fm（x））Tsubject to x∈Ω]               （1）
　　其中，[x=（x1，x2，？，xn）T]为决策变量，[Ω]被称为决策空间，[F：Ω→θ？Rm]包含由[n]维决策空间[Ω]映射到[m]维目标空间[θ]的[m]个实值目标函数，[Rm]被称为目标空间，[F（x）|x∈Ω]表示为该问题的可行目标解。当目标数[m]<3时，式（1）被称为多目标优化问题;当目标数[m]≥4时，则称式（1）为超多目标优化问题。
　　多目标优化问题的重要概念及定义如下文所示。
　　定义1（Pareto支配）：设[u=（u1，u2，？，um）]和[v=（v1，v2，][？，vm）]是目標空间[Rm]中的两个向量，称[u]Pareto支配[v]，当且仅当
　　[？i∈1，？，m， ui≤vi ∧ ？j∈1，？，m， ui<vi]  （2）
　　记为[u？v]。
　　定义2（非支配解集）：对于解集[P]中的每个解[x]而言，若[x]不被[P]中任何解所Pareto支配，则由[x]组成的解集被称为[P]的非支配解集。
　　定义3（Pareto最优解）：对于式（1）中任意可行解[x*∈Ω]，则称[x*]是Pareto最优解，当且仅当： 　　[？？x∈Ω， x？x*]             （3）
　　定义4（Pareto最优解集）：一个多目标优化问题中所有Pareto最优解构成的集合称为Pareto最优解集（Pareto Set，PS）。
　　定义5（Pareto前沿）：Pareto最优解集中的解在其目标空间中对应目标向量组成的集合称Pareto前沿（Pareto Front，PF），即：
　　[PF=F（x）∈Rm|x∈PS]        （4）
　　定义6（理想点）：在最小化多目标优化问题目标空间中，由在各个目标上有最小值的可行解组成的向量称为理想点，记为[z*] ，即：
　　[z*j=minfj（x）， j∈1，？，m]      （5）
　　定义7（极值点）：在最小化多目标优化问题目标空间中，由在各个目标上有最大值的Pareto最优解集中的解组成的向量称为极值点，记为[znad]，即：
　　[znadj=maxx∈PSfj（x）， j∈1，？，m]             （6）
　　2 多目标进化算法性能评价角度分类
　　对多目标进化算法的性能评价主要考虑3个方面：所求解集的质量、计算效率与鲁棒性。对于每一类性能评价，均有相应的评价工具。
　　2.1 解集质量
　　每运行一个多目标进化算法后，会得到一组近似解集，只有获得的近似解集有较高的质量，该多目标进化算法才有意义。因为多目标优化问题往往具有较复杂的目标函数等特点，通过多目标进化算法得到目标空间上完整的Pareto最优解集是不现实的。一般而言，只需得到一组包含有限个解并且非常逼近帕里托前沿的PF近似解集，帮助决策者根据偏好选择合适的解，从而帮助其决策。
　　在评价解集质量时，对于已知最优解的测试问题，如DTLZ[5]、WFG[6]测试问题集等，常要求解集满足以下两点：①收敛性，其衡量对象是近似解集趋近于Pareto前沿程度，旨在解决如何指引种群朝着Pareto前沿进行搜索。PF近似解集应尽可能逼近真实Pareto前沿;②多样性，其衡量近似解集中解的多样化程度。一个良好的保持种群多样性的方法可以在整个Pareto前沿上提供分布均匀的解决方案。衡量解集的多样性可以进一步分为衡量解集分布的均匀性与延展性[7]。均匀性衡量近似解集中解与解之间距离相等程度，延展性衡量近似解集中解在目标空间中能扩展的范围程度。
　　2.2 效率
　　在确保所求解质量的前提下，多目标进化算法运行效率也是一项重要的考察指标。可以通过多目标进化算法运行的CPU时间或达到某种效果所需迭代次数，衡量多目标进化算法时间效率。在多目标进化算法收敛过程中，其求解集质量往往随时间而变化。一般情况下，解集质量会随时间增加而改进，该规律可以通过“质量—时间”曲线描述。因为不同的多目标进化算法采用进化策略、非支配解集的构造方法不尽相同，对不同阶段的时间分析有利于深入研究多目标进化算法的进化特性。
　　2.3 鲁棒性
　　如果一个多目标进化算法只有在特定问题特性上才能有较好的求解能力与表现，则该多目标进化算法不是鲁棒的。一个鲁棒的多目标进化算法应能解决特点各异的不同问题，并且在求解问题时表现出较好的稳定性能。一个多目标进化算法对所求解问题特征的敏感性、对待处理数据质量的敏感性及对不同参数设置敏感性等均为衡量其鲁棒性的重要指标。
　　3 多目标进化算法性能评价指标
　　已有研究者提出多种多目标进化算法评价指标，按照前文所述可以分为3大类：①评价所求解集与真正PF的趋近程度，即收敛性;②评价解集在整个PF上的分布情况，即多样性（多样性细分为延展性和均匀性）;③综合考虑解集的收敛性与多样性。各大类中一些具有代表性的算法评价指标如下。
　　3.1 仅衡量收敛性指标
　　Set Coverage[8]（C-metric）：通过两组PF近似解集衡量收敛性能。设[A]和[B]为两组PF近似解集[C（A，B）]的定义，如式（7）所示，其表示[B]中个体至少被[A]中一个个体支配的占比。
　　[CA，B=u∈B|？v∈A：v？uB]           （7）
　　[C（A，B）=1]表示[B]中所有个体都被[A]中一些个体支配，即[B]的收敛性比[A]差。相反，若[C（A，B）=0]，表示[B]中没有个体被[A]中个体支配，即[B]的收敛性优于[A]。因为C-metric的计算是基于支配关系，所以其最大缺点是随着目标数的增多，PF 近似解集中的解均彼此互为非支配解，C-metric无法度量收敛性。
　　迭代距离[9]（Generational Distance，GD）：衡量真实PF上与近似解集之间的间隔距离。需要预先获得一组在真实PF上均匀采样的解集。设[P*]为一组在真实PF上均匀采样的解集，[S]是多目标进化算法求得的PF近似解集，则GD定义如式（8）所示。
　　[GD（S，P*）=x∈Sdist（x，P*）2S]             （8）
　　其中，[dist（x，S）]表示個体[x∈S]到[P*]上离其最近个体之间的欧氏距离，[S]是集合[S]的基数。GD值越小，表示[S]具有越好的收敛性，越能逼近整个PF。
　　错误率[10]（Error Ratio，ER）：描述的是不属于真实PF的解向量占种群规模的比率。经多目标进化算法得到的PF近似解中很可能存在某些解向量不在真实PF中。令[S=x1，x2，？，xn]为含有[n]个解向量的PF近似解集。[ei=][0]，当且仅当解向量[xi]属于真实PF，否则[ei=1]。错误率需要一组真实PF作为参考解集，其数学表达式如式（9）所示。 　　[ER（S）=i=1nein]            （9）
　　[ER（S）]越小表示近似解集有更好的非支配解集。
　　3.2 仅衡量多样性指标
　　空間评价方法[11]（Spacing Metric）可衡量PF近似解集中个体在目标空间的分布情况。其数学表达式如式（10）所示。
　　[Spacing=i=1|PF|di-d|PF|]         （10）
　　其中，[PF]代表已知的真实PF，[di]指解集中非支配边界上两个连续向量的欧氏距离，[d]是距离平均值。但该评价方法比较适用于两维目标空间，而在超多目标情况下效果不理想。
　　Maximum Spread[12]可通过计算PF近似解集覆盖真实PF的程度，衡量该近似解集的延展性能。设[P]为一组在真实PF采样上均匀的解集，[S]是多目标进化算法求得的PF近似解集，其数学表达式如式（11）所示。
　　[MS=1mi=1m|min（Smaxi-Pmaxi）-max（Smini-Pmini）Pmaxi-Pmini|] （11）
　　其中，[Smaxi]和[Smini]表示近似解集[S]在第[i]个目标上的最大值与最小值，[Pmaxi]和[Pmini]表示真实PF[P]在第[i]个目标上的最大值与最小值。[MS]值越高表示近似解集[S]覆盖在真实PF上的区域越大，多样性越好。
　　[Δ]Metric可通过获得解集延展程度衡量解集多样性[13]。计算所获得非支配解集中连续解之间欧氏距离的平均值，然后通过拟合平行于真实PF的曲线计算该解集在目标空间中的极值解。其数学表达式如式（12）所示。
　　[Δ=df+dl+i=1N-1|di-d|df+dl+（N-1）d]         （12）
　　式中，[df]和[dl]分别为PF近似解集上极值解之间的距离及每个目标之间边界解之间的距离。[N]为PF近似解集中个体数目。[di]表示解集中连续两个个体之间的距离，[d]为所有[di，i=1，2，？，N-1]距离的平均值。当所有距离[di]等于[d]且[df=dl=0]时，使得[Δ=0]时有最佳多样性。
　　3.3 综合衡量收敛性与多样性指标
　　反向迭代距离[14]（Inverted Generational Distance，IGD）衡量的是真实PF的个体到算法求得的近似解集之间最小距离的平均值，因此计算IGD需要预先获得一组在真实PF上均匀采样的解集。设[P*]为一组在真实PF上均匀采样的解集，[S]是多目标进化算法求得的PF近似解集，则IGD定义如式（13）所示。
　　[IGD（S，P*）=x∈P*dist（x，S）|P*|]         （13）
　　其中，[dist（x，S）]表示个体[x∈P*]到[S]上离其最近个体之间的欧氏距离，[|P*|]是集合[P*]的基数。IGD值越小，表示[S]具有越好的收敛与多样性能，越能逼近整个PF。另外，当[IGD（S，P*）=0]时，表示[S]是[P*]的子集。
　　超体积指标[8]（Hypervolume，HV）指给定一组预先设置分布在目标空间的参考点[r*=（r*1，r*2，？，r*m）]与一组由算法得到的PF近似解集[S]，满足[r*]被[S]中所有解支配。HV衡量的是以[r*]为边界、被[S]支配目标空间的体积大小，其定义如式（14）所示。
　　[HV（S）=VOL（x∈S[f1（x），r*1]×？fm（x），r*m）]   （14）
　　式中[VOL（？）]表示勒贝格测度。HV值越大，表示[S]越近似于整个PF。但HV有两个明显缺陷：①HV计算复杂度随目标数呈指数级增长;②参考点选取一定程度决定HV值的准确性。
　　[p-metric][15]是最近提出的用于度量超多目标PF近似解集的性能指标。通过预设的参考向量将目标空间分割成若干个子空间。如果满足[i=argmaxλi∈V（λi）T？F（s）||λi|||？|F（s）||]，其中[λi]表示第[i]个参考向量，[F（s）]表示个体[s]的解向量，则称个体[s]属于第[i]个子空间[？i]。 在每个子空间[？i]中离初始解[s]最近的距离[ri]定义[p-metric]，其数学表达式如式（15）所示。
　　[p-metric =i=1M1ri]                 （15）
　　其中[M]表示子空间数目，[1r=0]表示该子空间内不存在个体。从式（15）中可以看出PF近似解集的多样性与子空间相关个体数目有关。值得注意的是，一个个体只能处于一个子空间内，但一个子空间可以包含若干个个体。[p-metric]的精度并不能通过增加参考向量的方式得到改进，因为[N]个个体最多处于[N]个子空间内。
　　R2被首次提出时被用于评估两组PF近似解集之间相对性能[16]。假定一组理想点[z*]和标准加权的切比雪夫聚合函数，该指标可用于评估单个PF近似解集的性能。 给定一组近似解集[S]，一组在目标空间均匀分布的权重向量[W=（w1，？，wm）]以及标准切比雪夫聚合函数，则R2定义如式（16）所示，R2值越小表示近似解集越接近于理想点。
　　[R2（S，W，z*）=1Wx∈Wminx∈Smaxwi（fi（x）-z*i）] （16）
　　超体积比率（Hypervolume Ratio，HVR）指计算近似解集非支配解集[D]的超体积值占真实帕里托前沿[P*]的超体积值比率[17]，如式（17）所示。 　　[HVR=HV（D）HV（P*）]             （17）
　　HV为非支配解集以参考点为边界构建的超立方体空间量。HVR值越高表示非支配解集越接近真实PF，且在目标空间中多样性越好。
　　4 结语
　　隨着多目标进化算法的不断进化，如何比较、衡量算法性能成为热门课题。本文首先分析多目标进化算法相关概念及定义，从评价多目标进化算法的不同角度进行分类，并着重阐述衡量算法种群质量的多目标进化算法性能评价指标，将目前主流评价指标分为3大类，介绍其基本思想及优缺点，以期为在不同应用场景中选择合适的评价指标提供参考。
　　参考文献：
　　[1] 梅志伟.多目标进化算法综述[J]. 软件导刊，2017，16（6）：204-207.
　　[2] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multi-objective genetic algorithm： NSGA-II[J]. IEEE Transactions on Evolutionary Computation， 2002， 6（2）：182-197.
　　[3] ZHANG Q，LI H. MOEA/D： A multi-objective evolutionary algorithm based on decomposition[M]. New York： IEEE Press， 2007.
　　[4] BADER J，ZITZLER E. HypE： an algorithm for fast hyper volume-based many-objective optimization[J]. Evolutionary Computation，2011，19（1）： 45-76.
　　[5] DEB K，THIELE L，LAUMANNS M，et al. Scalable test problems for evolutionary multi-objective optimization[M]. London：Springer， 2005.
　　[6] HUBAND S， BARONE L， WHILE L， et al. A scalable multi-objective test problem toolkit[C].  International Conference on Evolutionary Multi-Criterion Optimization，2005： 280-295.
　　[7] LI M， YANG S， LIU X. Diversity comparison of Pareto front approximations in many-objective optimization[J]. IEEE Transactions on Cybernetics， 2014， 44（12）： 2568-2584.
　　[8] ZITZLER E， THIELE L. Multi-objective evolutionary algorithms： a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation， 1999， 3（4）：257-271.
　　[9] SCHUTZE O，ESQUIVEL X，LARA A，et al. Using the averaged Hausdorff distance as a performance measure in evolutionary multi-objective optimization[J]. IEEE Transactions on Evolutionary Computation， 2012， 16（4）： 504-522.
　　[10] VELDHUIZEN D A V. Multi-objective evolutionary algorithms： classifications， analyses， and new innovations[J]. Evolutionary Computation， 1999， 8（2）：125-147.
　　[11] BANDYOPADHYAY S，PAL S K，ARUNA B. Multi-objective GAs， quantitative indices， and pattern classification[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B（Cybernetics）， 2004， 34（5）：2088-2099.
　　[12] ZITZLER E，DEB K，THIELE L. Comparison of multi-objective evolutionary algorithms： empirical results[J]. Evolutionary computation， 2000， 8（2）： 173-195.
　　[13] DEB K，PRATAP A，AGARWAL S，et al. A fast and elitist multi-objective genetic algorithm： NSGA-II[J]. IEEE transactions on evolutionary computation， 2002， 6（2）： 182-197.
　　[14] BOSMAN P A N， THIERENS D. The balance between proximity and diversity in multi-objective evolutionary algorithms[J]. IEEE transactions on evolutionary computation， 2003， 7（2）： 174-188.
　　[15] HE Z， YEN G G. Visualization and performance metric in many-objective optimization[J]. IEEE Transactions on Evolutionary Computation， 2016， 20（3）： 386-402.
　　[16] HANSEN M P， JASZKIEWICZ A. Evaluating the quality of approximations to the non-dominated set[R]. Denmark： Department of Mathematical Modelling，Technical University of Denmark，IMM-REP-1998-7，1994.
　　[17] VAN VELDHUIZEN D A，LAMONT G B. Multi-objective evolutionary algorithm test suites[C]. 1999 ACM symposium on Applied computing，1999： 351-357.
　　（责任编辑：江 艳）
　　多目标进化算法性能评价指标综述
转载注明来源:https://www.xzbu.com/8/view-15019890.htm