胡涵 李振宇
摘 要:多目標(biāo)進(jìn)化算法常用于解決較復(fù)雜的多目標(biāo)優(yōu)化問題,該類算法是基于種群的進(jìn)化算法,通過產(chǎn)生一組近似Pareto最優(yōu)解集滿足決策者偏好。介紹了多目標(biāo)優(yōu)化問題背景知識(shí)及相關(guān)定義,根據(jù)評(píng)價(jià)指標(biāo)衡量解集特性,將現(xiàn)有算法性能評(píng)價(jià)指標(biāo)分為3類并分別進(jìn)行闡述,分析、比較其特點(diǎn)與區(qū)別。
關(guān)鍵詞:多目標(biāo)優(yōu)化;進(jìn)化算法;評(píng)價(jià)指標(biāo);最優(yōu)解集
DOI:10. 11907/rjdk. 191024 開放科學(xué)(資源服務(wù))標(biāo)識(shí)碼(OSID):
中圖分類號(hào):TP312 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):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 引言
多目標(biāo)優(yōu)化問題在日常生活中較為常見,無論是在科學(xué)研究還是實(shí)際工程應(yīng)用中,多目標(biāo)優(yōu)化都是非常重要的課題。不僅因?yàn)槎嗄繕?biāo)優(yōu)化問題往往伴隨多個(gè)目標(biāo)需要同時(shí)進(jìn)行優(yōu)化,而且多目標(biāo)優(yōu)化的最優(yōu)解往往是一組解集,如何選出符合決策者偏好的解也是亟需解決的問題。
單目標(biāo)優(yōu)化問題優(yōu)化的只有一個(gè)目標(biāo)并且最終得到一個(gè)單獨(dú)的最優(yōu)解。但多目標(biāo)優(yōu)化問題中目標(biāo)之間往往相互沖突,一個(gè)目標(biāo)性能提升往往伴隨其它一個(gè)或多個(gè)目標(biāo)性能下降。多目標(biāo)優(yōu)化問題中存在一組表示各個(gè)目標(biāo)間權(quán)衡和折中關(guān)系的解集,通常稱為Pareto最優(yōu)解集。Pareto最優(yōu)解集在目標(biāo)域的投影被稱為Pareto前沿[1]。
為了更好地解決多目標(biāo)優(yōu)化問題,研究人員提出了多種用于求解多目標(biāo)的進(jìn)化算法,諸如NSGA-II[2]、MOEA/D[3]、HypE[4]等。隨著多種多目標(biāo)進(jìn)化算法的出現(xiàn),如何比較和衡量這些算法性能成為一大熱門課題。對(duì)一個(gè)多目標(biāo)進(jìn)化算法進(jìn)行評(píng)價(jià)時(shí),一方面需有一套能夠客觀反映多目標(biāo)進(jìn)化算法優(yōu)劣的評(píng)價(jià)工具或方法;另一方面需選取一組有代表性的測(cè)試集。效果、效率、魯棒性、問題求解范圍,以及是否方便使用等是考察多目標(biāo)進(jìn)化算法的重要指標(biāo)。
1 多目標(biāo)優(yōu)化問題概述
通常一個(gè)求解最小化目標(biāo)值的多目標(biāo)優(yōu)化問題可以被定義為:
[minF(x)=(f1(x),?,fm(x))Tsubject to x∈Ω] ? ? ? ? ? ? ? (1)
其中,[x=(x1,x2,?,xn)T]為決策變量,[Ω]被稱為決策空間,[F:Ω→θ?Rm]包含由[n]維決策空間[Ω]映射到[m]維目標(biāo)空間[θ]的[m]個(gè)實(shí)值目標(biāo)函數(shù),[Rm]被稱為目標(biāo)空間,[F(x)|x∈Ω]表示為該問題的可行目標(biāo)解。當(dāng)目標(biāo)數(shù)[m]<3時(shí),式(1)被稱為多目標(biāo)優(yōu)化問題;當(dāng)目標(biāo)數(shù)[m]≥4時(shí),則稱式(1)為超多目標(biāo)優(yōu)化問題。
多目標(biāo)優(yōu)化問題的重要概念及定義如下文所示。
定義1(Pareto支配):設(shè)[u=(u1,u2,?,um)]和[v=(v1,v2,][?,vm)]是目標(biāo)空間[Rm]中的兩個(gè)向量,稱[u]Pareto支配[v],當(dāng)且僅當(dāng)
[?i∈1,?,m, ui≤vi ∧ ?j∈1,?,m, ui 記為[u?v]。 定義2(非支配解集):對(duì)于解集[P]中的每個(gè)解[x]而言,若[x]不被[P]中任何解所Pareto支配,則由[x]組成的解集被稱為[P]的非支配解集。 定義3(Pareto最優(yōu)解):對(duì)于式(1)中任意可行解[x*∈Ω],則稱[x*]是Pareto最優(yōu)解,當(dāng)且僅當(dāng): [??x∈Ω, x?x*] ? ? ? ? ? ? (3) 定義4(Pareto最優(yōu)解集):一個(gè)多目標(biāo)優(yōu)化問題中所有Pareto最優(yōu)解構(gòu)成的集合稱為Pareto最優(yōu)解集(Pareto Set,PS)。 定義5(Pareto前沿):Pareto最優(yōu)解集中的解在其目標(biāo)空間中對(duì)應(yīng)目標(biāo)向量組成的集合稱Pareto前沿(Pareto Front,PF),即: [PF=F(x)∈Rm|x∈PS] ? ? ? ?(4) 定義6(理想點(diǎn)):在最小化多目標(biāo)優(yōu)化問題目標(biāo)空間中,由在各個(gè)目標(biāo)上有最小值的可行解組成的向量稱為理想點(diǎn),記為[z*] ,即: [z*j=minfj(x), j∈1,?,m] ? ? ?(5) 定義7(極值點(diǎn)):在最小化多目標(biāo)優(yōu)化問題目標(biāo)空間中,由在各個(gè)目標(biāo)上有最大值的Pareto最優(yōu)解集中的解組成的向量稱為極值點(diǎn),記為[znad],即: [znadj=maxx∈PSfj(x), j∈1,?,m] ? ? ? ? ? ? (6) 2 多目標(biāo)進(jìn)化算法性能評(píng)價(jià)角度分類 對(duì)多目標(biāo)進(jìn)化算法的性能評(píng)價(jià)主要考慮3個(gè)方面:所求解集的質(zhì)量、計(jì)算效率與魯棒性。對(duì)于每一類性能評(píng)價(jià),均有相應(yīng)的評(píng)價(jià)工具。 2.1 解集質(zhì)量 每運(yùn)行一個(gè)多目標(biāo)進(jìn)化算法后,會(huì)得到一組近似解集,只有獲得的近似解集有較高的質(zhì)量,該多目標(biāo)進(jìn)化算法才有意義。因?yàn)槎嗄繕?biāo)優(yōu)化問題往往具有較復(fù)雜的目標(biāo)函數(shù)等特點(diǎn),通過多目標(biāo)進(jìn)化算法得到目標(biāo)空間上完整的Pareto最優(yōu)解集是不現(xiàn)實(shí)的。一般而言,只需得到一組包含有限個(gè)解并且非常逼近帕里托前沿的PF近似解集,幫助決策者根據(jù)偏好選擇合適的解,從而幫助其決策。 在評(píng)價(jià)解集質(zhì)量時(shí),對(duì)于已知最優(yōu)解的測(cè)試問題,如DTLZ[5]、WFG[6]測(cè)試問題集等,常要求解集滿足以下兩點(diǎn):①收斂性,其衡量對(duì)象是近似解集趨近于Pareto前沿程度,旨在解決如何指引種群朝著Pareto前沿進(jìn)行搜索。PF近似解集應(yīng)盡可能逼近真實(shí)Pareto前沿;②多樣性,其衡量近似解集中解的多樣化程度。一個(gè)良好的保持種群多樣性的方法可以在整個(gè)Pareto前沿上提供分布均勻的解決方案。衡量解集的多樣性可以進(jìn)一步分為衡量解集分布的均勻性與延展性[7]。均勻性衡量近似解集中解與解之間距離相等程度,延展性衡量近似解集中解在目標(biāo)空間中能擴(kuò)展的范圍程度。 2.2 效率 在確保所求解質(zhì)量的前提下,多目標(biāo)進(jìn)化算法運(yùn)行效率也是一項(xiàng)重要的考察指標(biāo)??梢酝ㄟ^多目標(biāo)進(jìn)化算法運(yùn)行的CPU時(shí)間或達(dá)到某種效果所需迭代次數(shù),衡量多目標(biāo)進(jìn)化算法時(shí)間效率。在多目標(biāo)進(jìn)化算法收斂過程中,其求解集質(zhì)量往往隨時(shí)間而變化。一般情況下,解集質(zhì)量會(huì)隨時(shí)間增加而改進(jìn),該規(guī)律可以通過“質(zhì)量—時(shí)間”曲線描述。因?yàn)椴煌亩嗄繕?biāo)進(jìn)化算法采用進(jìn)化策略、非支配解集的構(gòu)造方法不盡相同,對(duì)不同階段的時(shí)間分析有利于深入研究多目標(biāo)進(jìn)化算法的進(jìn)化特性。 2.3 魯棒性 如果一個(gè)多目標(biāo)進(jìn)化算法只有在特定問題特性上才能有較好的求解能力與表現(xiàn),則該多目標(biāo)進(jìn)化算法不是魯棒的。一個(gè)魯棒的多目標(biāo)進(jìn)化算法應(yīng)能解決特點(diǎn)各異的不同問題,并且在求解問題時(shí)表現(xiàn)出較好的穩(wěn)定性能。一個(gè)多目標(biāo)進(jìn)化算法對(duì)所求解問題特征的敏感性、對(duì)待處理數(shù)據(jù)質(zhì)量的敏感性及對(duì)不同參數(shù)設(shè)置敏感性等均為衡量其魯棒性的重要指標(biāo)。 3 多目標(biāo)進(jìn)化算法性能評(píng)價(jià)指標(biāo) 已有研究者提出多種多目標(biāo)進(jìn)化算法評(píng)價(jià)指標(biāo),按照前文所述可以分為3大類:①評(píng)價(jià)所求解集與真正PF的趨近程度,即收斂性;②評(píng)價(jià)解集在整個(gè)PF上的分布情況,即多樣性(多樣性細(xì)分為延展性和均勻性);③綜合考慮解集的收斂性與多樣性。各大類中一些具有代表性的算法評(píng)價(jià)指標(biāo)如下。 3.1 僅衡量收斂性指標(biāo) Set Coverage[8](C-metric):通過兩組PF近似解集衡量收斂性能。設(shè)[A]和[B]為兩組PF近似解集[C(A,B)]的定義,如式(7)所示,其表示[B]中個(gè)體至少被[A]中一個(gè)個(gè)體支配的占比。 [CA,B=u∈B|?v∈A:v?uB] ? ? ? ? ? (7) [C(A,B)=1]表示[B]中所有個(gè)體都被[A]中一些個(gè)體支配,即[B]的收斂性比[A]差。相反,若[C(A,B)=0],表示[B]中沒有個(gè)體被[A]中個(gè)體支配,即[B]的收斂性優(yōu)于[A]。因?yàn)镃-metric的計(jì)算是基于支配關(guān)系,所以其最大缺點(diǎn)是隨著目標(biāo)數(shù)的增多,PF 近似解集中的解均彼此互為非支配解,C-metric無法度量收斂性。 迭代距離[9](Generational Distance,GD):衡量真實(shí)PF上與近似解集之間的間隔距離。需要預(yù)先獲得一組在真實(shí)PF上均勻采樣的解集。設(shè)[P*]為一組在真實(shí)PF上均勻采樣的解集,[S]是多目標(biāo)進(jìn)化算法求得的PF近似解集,則GD定義如式(8)所示。 [GD(S,P*)=x∈Sdist(x,P*)2S] ? ? ? ? ? ? (8) 其中,[dist(x,S)]表示個(gè)體[x∈S]到[P*]上離其最近個(gè)體之間的歐氏距離,[S]是集合[S]的基數(shù)。GD值越小,表示[S]具有越好的收斂性,越能逼近整個(gè)PF。 錯(cuò)誤率[10](Error Ratio,ER):描述的是不屬于真實(shí)PF的解向量占種群規(guī)模的比率。經(jīng)多目標(biāo)進(jìn)化算法得到的PF近似解中很可能存在某些解向量不在真實(shí)PF中。令[S=x1,x2,?,xn]為含有[n]個(gè)解向量的PF近似解集。[ei=][0],當(dāng)且僅當(dāng)解向量[xi]屬于真實(shí)PF,否則[ei=1]。錯(cuò)誤率需要一組真實(shí)PF作為參考解集,其數(shù)學(xué)表達(dá)式如式(9)所示。 [ER(S)=i=1nein] ? ? ? ? ? ?(9) [ER(S)]越小表示近似解集有更好的非支配解集。 3.2 僅衡量多樣性指標(biāo) 空間評(píng)價(jià)方法[11](Spacing Metric)可衡量PF近似解集中個(gè)體在目標(biāo)空間的分布情況。其數(shù)學(xué)表達(dá)式如式(10)所示。 [Spacing=i=1|PF|di-d|PF|] ? ? ? ? (10) 其中,[PF]代表已知的真實(shí)PF,[di]指解集中非支配邊界上兩個(gè)連續(xù)向量的歐氏距離,[d]是距離平均值。但該評(píng)價(jià)方法比較適用于兩維目標(biāo)空間,而在超多目標(biāo)情況下效果不理想。 Maximum Spread[12]可通過計(jì)算PF近似解集覆蓋真實(shí)PF的程度,衡量該近似解集的延展性能。設(shè)[P]為一組在真實(shí)PF采樣上均勻的解集,[S]是多目標(biāo)進(jìn)化算法求得的PF近似解集,其數(shù)學(xué)表達(dá)式如式(11)所示。 [MS=1mi=1m|min(Smaxi-Pmaxi)-max(Smini-Pmini)Pmaxi-Pmini|] (11) 其中,[Smaxi]和[Smini]表示近似解集[S]在第[i]個(gè)目標(biāo)上的最大值與最小值,[Pmaxi]和[Pmini]表示真實(shí)PF[P]在第[i]個(gè)目標(biāo)上的最大值與最小值。[MS]值越高表示近似解集[S]覆蓋在真實(shí)PF上的區(qū)域越大,多樣性越好。 [Δ]Metric可通過獲得解集延展程度衡量解集多樣性[13]。計(jì)算所獲得非支配解集中連續(xù)解之間歐氏距離的平均值,然后通過擬合平行于真實(shí)PF的曲線計(jì)算該解集在目標(biāo)空間中的極值解。其數(shù)學(xué)表達(dá)式如式(12)所示。 [Δ=df+dl+i=1N-1|di-d|df+dl+(N-1)d] ? ? ? ? (12) 式中,[df]和[dl]分別為PF近似解集上極值解之間的距離及每個(gè)目標(biāo)之間邊界解之間的距離。[N]為PF近似解集中個(gè)體數(shù)目。[di]表示解集中連續(xù)兩個(gè)個(gè)體之間的距離,[d]為所有[di,i=1,2,?,N-1]距離的平均值。當(dāng)所有距離[di]等于[d]且[df=dl=0]時(shí),使得[Δ=0]時(shí)有最佳多樣性。 3.3 綜合衡量收斂性與多樣性指標(biāo) 反向迭代距離[14](Inverted Generational Distance,IGD)衡量的是真實(shí)PF的個(gè)體到算法求得的近似解集之間最小距離的平均值,因此計(jì)算IGD需要預(yù)先獲得一組在真實(shí)PF上均勻采樣的解集。設(shè)[P*]為一組在真實(shí)PF上均勻采樣的解集,[S]是多目標(biāo)進(jìn)化算法求得的PF近似解集,則IGD定義如式(13)所示。 [IGD(S,P*)=x∈P*dist(x,S)|P*|] ? ? ? ? (13) 其中,[dist(x,S)]表示個(gè)體[x∈P*]到[S]上離其最近個(gè)體之間的歐氏距離,[|P*|]是集合[P*]的基數(shù)。IGD值越小,表示[S]具有越好的收斂與多樣性能,越能逼近整個(gè)PF。另外,當(dāng)[IGD(S,P*)=0]時(shí),表示[S]是[P*]的子集。 超體積指標(biāo)[8](Hypervolume,HV)指給定一組預(yù)先設(shè)置分布在目標(biāo)空間的參考點(diǎn)[r*=(r*1,r*2,?,r*m)]與一組由算法得到的PF近似解集[S],滿足[r*]被[S]中所有解支配。HV衡量的是以[r*]為邊界、被[S]支配目標(biāo)空間的體積大小,其定義如式(14)所示。 [HV(S)=VOL(x∈S[f1(x),r*1]×?fm(x),r*m)] ? (14) 式中[VOL(?)]表示勒貝格測(cè)度。HV值越大,表示[S]越近似于整個(gè)PF。但HV有兩個(gè)明顯缺陷:①HV計(jì)算復(fù)雜度隨目標(biāo)數(shù)呈指數(shù)級(jí)增長(zhǎng);②參考點(diǎn)選取一定程度決定HV值的準(zhǔn)確性。 [p-metric][15]是最近提出的用于度量超多目標(biāo)PF近似解集的性能指標(biāo)。通過預(yù)設(shè)的參考向量將目標(biāo)空間分割成若干個(gè)子空間。如果滿足[i=argmaxλi∈V(λi)T?F(s)||λi|||?|F(s)||],其中[λi]表示第[i]個(gè)參考向量,[F(s)]表示個(gè)體[s]的解向量,則稱個(gè)體[s]屬于第[i]個(gè)子空間[?i]。 在每個(gè)子空間[?i]中離初始解[s]最近的距離[ri]定義[p-metric],其數(shù)學(xué)表達(dá)式如式(15)所示。 [p-metric =i=1M1ri] ? ? ? ? ? ? ? ? (15) 其中[M]表示子空間數(shù)目,[1r=0]表示該子空間內(nèi)不存在個(gè)體。從式(15)中可以看出PF近似解集的多樣性與子空間相關(guān)個(gè)體數(shù)目有關(guān)。值得注意的是,一個(gè)個(gè)體只能處于一個(gè)子空間內(nèi),但一個(gè)子空間可以包含若干個(gè)個(gè)體。[p-metric]的精度并不能通過增加參考向量的方式得到改進(jìn),因?yàn)閇N]個(gè)個(gè)體最多處于[N]個(gè)子空間內(nèi)。 R2被首次提出時(shí)被用于評(píng)估兩組PF近似解集之間相對(duì)性能[16]。假定一組理想點(diǎn)[z*]和標(biāo)準(zhǔn)加權(quán)的切比雪夫聚合函數(shù),該指標(biāo)可用于評(píng)估單個(gè)PF近似解集的性能。 給定一組近似解集[S],一組在目標(biāo)空間均勻分布的權(quán)重向量[W=(w1,?,wm)]以及標(biāo)準(zhǔn)切比雪夫聚合函數(shù),則R2定義如式(16)所示,R2值越小表示近似解集越接近于理想點(diǎn)。 [R2(S,W,z*)=1Wx∈Wminx∈Smaxwi(fi(x)-z*i)] (16) 超體積比率(Hypervolume Ratio,HVR)指計(jì)算近似解集非支配解集[D]的超體積值占真實(shí)帕里托前沿[P*]的超體積值比率[17],如式(17)所示。 [HVR=HV(D)HV(P*)] ? ? ? ? ? ? (17) HV為非支配解集以參考點(diǎn)為邊界構(gòu)建的超立方體空間量。HVR值越高表示非支配解集越接近真實(shí)PF,且在目標(biāo)空間中多樣性越好。 4 結(jié)語 隨著多目標(biāo)進(jìn)化算法的不斷進(jìn)化,如何比較、衡量算法性能成為熱門課題。本文首先分析多目標(biāo)進(jìn)化算法相關(guān)概念及定義,從評(píng)價(jià)多目標(biāo)進(jìn)化算法的不同角度進(jìn)行分類,并著重闡述衡量算法種群質(zhì)量的多目標(biāo)進(jìn)化算法性能評(píng)價(jià)指標(biāo),將目前主流評(píng)價(jià)指標(biāo)分為3大類,介紹其基本思想及優(yōu)缺點(diǎn),以期為在不同應(yīng)用場(chǎng)景中選擇合適的評(píng)價(jià)指標(biāo)提供參考。 參考文獻(xiàn): [1] 梅志偉.多目標(biāo)進(jìn)化算法綜述[J]. 軟件導(dǎo)刊,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. (責(zé)任編輯:江 艷) 多目標(biāo)進(jìn)化算法性能評(píng)價(jià)指標(biāo)綜述