多目標進化算法性能評價指標綜述

胡涵 李振宇

摘 要：多目標進化算法常用于解決較復雜的多目標優化問題，該類算法是基于種群的進化算法，通過產生一組近似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

記為[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.

（責任編輯：江 艷）

多目標進化算法性能評價指標綜述