李文樺 張 濤 王 銳 王 凌

(1.國防科技大學系統(tǒng)工程學院,湖南長沙 410073;2.多能源系統(tǒng)智慧互聯(lián)技術(shù)湖南省重點實驗室,湖南長沙 410073;3.清華大學自動化系,北京 100084)

1 引言

大規(guī)模復雜系統(tǒng)、工程設計中的很多決策問題都需要同時考慮多個優(yōu)化目標,且優(yōu)化目標之間往往存在互斥關(guān)系,即提高某個目標函數(shù)值的性能時會引起其他一個或多個目標函數(shù)值的衰退,也就是說不存在一個使得所有優(yōu)化目標都達到最優(yōu)的解.不失一般性,研究者一般將多目標優(yōu)化問題(multi-objective optimization problem,MOP)表示為以下形式:

其中:?為問題的可行域,fm(x)為決策向量x對應的第m個目標函數(shù)的函數(shù)值.

與具有單個全局最優(yōu)值的單目標優(yōu)化問題不同,在MOP中,存在多個非劣解或稱非支配解(non-dominated solution),稱為Pareto最優(yōu)解集.解xA支配xB當且僅當

經(jīng)過多年的發(fā)展,進化多目標優(yōu)化(evolutionary multi-objective optimization,EMO)算法得到了極大的改進,在待優(yōu)化問題的目標函數(shù)個數(shù)較少時,EMO算法表現(xiàn)出了優(yōu)異的性能,所求解得到的Pareto最優(yōu)解集合能夠兼顧收斂性和分布的均勻性.一般來說,EMO算法大體可以分為以下幾類:

1) 基于Pareto支配關(guān)系的算法.該類算法利用種群中個體之間的Pareto支配關(guān)系,在進化計算的每一次迭代中,首先對所有個體進行Pareto排序,然后算法挑選具有較好支配序的個體組成下一代,以此來推動種群不斷向真實的Pareto前沿逼近.代表算法包括NSGA-II[1]和SPEA2[2].

2) 基于分解策略的算法.該類算法通過引入標量函數(shù)將多目標問題轉(zhuǎn)化為單目標優(yōu)化問題.由于不基于Pareto支配關(guān)系進行個體優(yōu)劣排序,該類算法在高維多目標優(yōu)化問題上較之于NSGA-II等算法具有更好的收斂性.但是算法的性能與所使用的標量函數(shù)有很大的關(guān)系,而其標量函數(shù)的選擇依賴于問題本身,即面對不同問題,需選擇不同的標量函數(shù)來取得滿意的結(jié)果.代表算法包括MOEA/D[3]和NSGA-III[4].

3) 基于評價指標的算法.該類算法基于某個評價指標,如超體積(hypervolume)、反世代距離(IGD)等,計算種群中個體對解集整體性能的貢獻,并將此作為評價個體優(yōu)劣的指標,進而選擇下一代個體繼續(xù)參與進化.代表算法包括IBEA[5],SMS-EMOA[6],HypE[7]等.

還有一些不屬于這3類的MOEA,如第3代差分算法(GDE3)[8]、M-PAES[9]和基于二元存檔的MOEA(Two-Arc)[10]等.

實驗顯示當優(yōu)化目標個數(shù)較少時,基于Pareto支配關(guān)系的進化多目標優(yōu)化算法能夠找到令人滿意的解.然而隨著待優(yōu)化目標個數(shù)的增加,個體之間的支配關(guān)系逐漸消失,即種群中絕大多數(shù)個體在進化的早期就變得彼此互不支配.這意味著基于Pareto支配關(guān)系的選擇壓力變得非常小,無法引導種群趨向于最優(yōu)前沿.因此目標數(shù)量的增加將嚴重降低基于Pareto支配關(guān)系的EMO算法的收斂能力.

針對該問題,學者們提出了很多改進的方法,例如修改Pareto支配關(guān)系的定義,如α-dominance[11],?-dominance[12],cone-dominance[13]等,使得個體在高維空間中仍然具備一定的支配關(guān)系.另外,研究表明,基于分解思想和基于評價指標的多目標優(yōu)化算法在高維多目標優(yōu)化問題中表現(xiàn)較好,在多達50個優(yōu)化目標的問題上仍能夠獲得令人較為滿意的解[7].

值得關(guān)注的是,一方面,隨著目標函數(shù)個數(shù)的增加,用來描述整個Pareto前沿的個體數(shù)量也隨之增大.在僅有2-3個目標函數(shù)時,通常使用較小的種群就能夠完整的描繪出整個Pareto前沿(幾何形狀);然而當目標個數(shù)逐漸增加時,用來準確描述Pareto前沿所需的個體數(shù)呈現(xiàn)出指數(shù)增長.因此在高維情況下,追求獲得完整的Pareto前沿需要設置較大的種群規(guī)模,這也意味著求解高維多目標優(yōu)化問題需要更強大的算力支持,而目前算力仍然是制約優(yōu)化算法發(fā)展的瓶頸[14].

盡管EMO算法能夠給出Pareto解集,決策者還需要在眾多的Pareto最優(yōu)解中挑選出一個來應用[15].在目標個數(shù)為2或者3時,算法能夠給出直觀的Pareto前沿,在這種情況下,可以使用后驗的方法先獲取問題的Pareto前沿,再由決策者挑選出最適合其偏好的解;對于超多目標優(yōu)化問題,如果決策者能給出其偏好信息,那么利用基于偏好的多目標優(yōu)化算法也能獲得讓決策者滿意的解.然而,對于決策者無法給出偏好信息的情況,由于目前還沒有一種公認的方法能夠很好地展示出其Pareto前沿,因此決策者難以做出直觀的判斷.對許多實際問題(如消費者行為)的實證研究已經(jīng)明確證實,當候選解決方案的目標數(shù)量大于5個時,決策者的決策能力將明顯退化[16].

考慮到在高維多目標優(yōu)化問題中,獲得整個Pareto前沿計算復雜度高且無益于決策者做選擇,目前一些能夠反映決策者偏好的算法得到了極大發(fā)展.一方面,研究指出,給定特定的用戶偏好信息,并利用偏好信息指導算法的搜索,能夠使算法獲得更好的性能.Wang等人[17]提出偏好啟發(fā)式協(xié)同進化系列算法PICEAs,在高維多目標優(yōu)化、交互式?jīng)Q策優(yōu)化等方面性能突出;Zhang等人[18]提出KnEA,在種群進化過程中尋找Pareto前沿上的Knee,并通過該信息引導種群進化,實驗結(jié)果表明該算法在測試問題上也具有良好的性能.另一方面,根據(jù)用戶的偏好,著重搜索Pareto前沿的特定區(qū)域,并且忽略用戶不感興趣的區(qū)域,可以大大減少種群規(guī)模,這樣不僅大大提高了計算效率,而且算法更加關(guān)注特定的搜索區(qū)域也使得解的質(zhì)量更好.

Knee指的是Pareto前沿中具有局部最大邊際效用的點[19].圖1為兩目標優(yōu)化問題中Knee的示意圖,直觀上來看,Knee是Pareto前沿面上的向理想點方向的一個“凸起”,相較于它的相鄰解,Knee更加靠近坐標原點.因此,在超體積(hypervolume)指標上,Knee比其他的Pareto解表現(xiàn)更好[18].因此通常來說,在沒有決策者的偏好信息的情況下,Knee被認為是決策者更感興趣的解.

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

不同的研究者對Knee的定義有所不同,具體來說,可以分別從Pareto的數(shù)值特征和幾何特征對Knee進行定義:

定義1Knee對應于Pareto前沿上具有極大邊際效用的點.換言之,在Knee附近,一個目標函數(shù)值的提升會導致至少另一個目標函數(shù)值的巨大衰退.

定義2連接Pareto前沿的邊界點形成直線或者超平面L,Pareto前沿上到L的距離的極大值點對應的解為Knee.

上述兩個Knee的定義,在不同的Pareto前沿形狀上對Knee的精確定位存在著差異,但總體對應Pareto前沿上的同一塊區(qū)域,這將在文章后續(xù)進行進一步探討.另外,從定義中可以看到,Knee是在與它的相鄰解的比較基礎(chǔ)上定義的,因此相鄰解的判定方法也是Knee檢測過程中一個非常重要的概念.以兩目標優(yōu)化問題為例,對于每一個Pareto解S,它的相鄰解可以定義為:與解S的距離(歐氏距離、曼哈頓距離等)小于d的解.在另一些文獻中,也將該距離描述為半徑[20].算法中通過設置不同的d,獲得的Knee集合也會出現(xiàn)差異.如果設置過小的d值,則算法在搜索過程中極易檢測到假的Knee點;相反如果設置較大的d值,則一些局部Knee會被另一些Knee合并.由于需要在算法搜索過程中動態(tài)確定所有的Knee,而在未收斂之前,Pareto前沿在集合上具有不均勻、非連續(xù)性等特點,因此Knee的檢測方法必須具備一定的魯棒性.

在算法研究方面,一方面許多基于Knee的EMO算法提出在進化搜索過程中尋找Knee,并基于獲取到的信息指導進化過程[18].由于Knee本身在HyperVolume等指標上的優(yōu)勢,基于Knee的多目標優(yōu)化算法在高維多目標問題上表現(xiàn)良好.另一方面,還有一些算法專注于搜索并獲得Pareto前沿上的Knee區(qū)域.該類算法不關(guān)注Pareto前沿的其他部分,最終將獲得一部分Pareto解集.

本文主要對Knee的優(yōu)勢進行探討,并綜述了近年來圍繞Knee的相關(guān)研究.Knee的提出是為了解決高維多目標優(yōu)化問題的解的選擇問題,然而,由于目前還沒有公認的較為合適的方式用來描述高維多目標優(yōu)化問題的Pareto前沿,因此本文在后續(xù)的分析中大多使用目標個數(shù)為2或者3的多目標問題.本文后續(xù)結(jié)構(gòu)為:第2節(jié)回顧了Knee的不同檢測方法,第3節(jié)總結(jié)了Knee 的保留策略,第4 節(jié)和第5 節(jié)則分別介紹了Knee相關(guān)的測試問題和性能評價指標.最后,總結(jié)了現(xiàn)有的研究并對未來可能的研究方向進行了探討.

2 Knee的檢測方法

Knee的重要性在多篇文獻中都有強調(diào)[21-22].目前,基于Knee的算法已經(jīng)在實際工程問題中取得了較好的效果,如網(wǎng)絡系統(tǒng)優(yōu)化設計[23-24]、時間序列預測[25-26]、任務規(guī)劃[13,27]、聚類問題[28]、車間調(diào)度[29]、復雜網(wǎng)絡[30]、特征選擇[31]等.早在2004年,Jugen等人[19]就指出,Pareto前沿上的Knee區(qū)域更受決策者的歡迎.遺憾的是,雖然Knee對于對多準則決策(multicriteria decision making,MCDM)領(lǐng)域具有顯著的重要性,但相較于其他EMO算法,Knee的研究受到的關(guān)注較小.近年來,根據(jù)Knee的定義與特性,學者們提出了許多有效檢測Knee的方法,大體上可以分為兩類:一是根據(jù)Knee在Pareto前沿上的幾何特征進行檢測.與Pareto前沿的其他部分不同,Knee區(qū)域具有明顯的幾何特征,即Knee區(qū)域Pareto前沿的曲率發(fā)生突變.二是利用Pareto前沿上評價解之間權(quán)衡的指標.在Knee區(qū)域,目標函數(shù)值之間的影響增大,通過計算此類影響來檢測Knee區(qū)域.

2.1 基于反射角度的方法

Branke等人[19]提出了基于反射角度的Knee檢測方法,如圖2所示.在迭代的每一代中,對每一個解,計算它與相鄰節(jié)點形成的角度.在全部獲得角度之后,擁有局部最大角度的點既為Knee.將計算得到的角度替換NSGA-II中的擁擠距離(crowding distance),從而提高Knee的競爭優(yōu)勢,使其在迭代優(yōu)化的過程中得到保留.文中還指出僅使用角度α作為唯一指標,算法穩(wěn)定性較差.因此,作者將α,β,γ,δ的最大值作為檢測Knee的指標,并開發(fā)了基于NSGA-II的Knee算法,取得了一定的效果.然而反射角只考慮到Pareto前沿的局部信息,因此其檢測Knee 的魯棒性不強.Deb 和Gupta[32]提出了一種基于彎曲角的選擇機制來彌補這個問題.基于反射角度的方法在二維情況下計算十分簡單,但是也存在許多問題.一方面,角度在很大程度上依賴于解之間的位置關(guān)系,選擇相鄰點計算夾角導致誤差較大.在點比較密集的情況下,相鄰解之間的夾角存在一定的隨機性,對于檢測Knee帶來一定干擾.另一方面,基于角度的方法只能運用在二維情況下,在高維情況下擴展性較差,綜合而言,該類方法不適合作為一種通用的Knee檢測方法.

圖2 基于角度的Knee檢測方法示意圖Fig.2 Illustration of reflex angle

2.2 基于期望邊際效用的方法

在文獻[19],Branke等人還提出了利用期望邊際效 用(expected marginal utility,EMU)來 確 定Knee的方法.一個解決方案的效用指的是這個解對于決策者而言的性能好壞.在MCDM領(lǐng)域中,已經(jīng)廣泛使用效用函數(shù)(或稱為標量生成函數(shù))來將MOP組合成一個單目標優(yōu)化問題,從而使用單目標優(yōu)化算法求解.線性效用函數(shù)可以定義為U(x,λ)==1.其中λi表示每個目標函數(shù)的權(quán)值.如果決策者給定一組權(quán)重向量λ=(λ1··· λm),則可以給出Pareto解集中最滿足決策者的解,此時可將多目標優(yōu)化問題退化為單目標優(yōu)化問題.然而實際上,決策者往往很難給出這樣一組權(quán)值向量.

EMU利用一組權(quán)重向量來計算的單個效用函數(shù)的積分.對于一個解決方案,其EMU定義為該解決方案被次優(yōu)解決方案替代后產(chǎn)生的額外成本.EMU反映的是一個目標值的改變對另一個目標值的影響,EMU值越大,表示該影響越大.Branke等人給出了兩目標下EMU的計算方法:

其中:t表示i=argminU(xj,λ),λ ∈[0,1]是一個由決策者給出的權(quán)重向量.

EMU方法雖然原則上可以擴展到高維,然而隨著目標函數(shù)數(shù)量的增加,EMU對于Pareto前沿上不同的解的區(qū)別性降低.因此,Bhattacharjee等人[33]提出了改進的EMU方法,稱為EMUr,不僅能夠識別Knee,還能確定Knee的位置,無論它們位于Pareto前沿的內(nèi)部還是外部.

此外,類似于EMU衡量一個解決方案目標值之間的影響,其他MCDM領(lǐng)域中用來評價解收斂到理想點的指標也可以用作Knee的檢測方法,比如灰色關(guān)聯(lián)分析(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的檢測也會產(chǎn)生偏差,如圖3所示.一般來說,不同類型的算法在保留邊界點的策略上會存在明顯差異,因此在不同的算法基礎(chǔ)上應用基于距離的Knee探測方法會導致結(jié)果存在細微的差異.

2.4 基于Trade-off的方法

Trade-off是一對非支配目標向量的特征,可以定義為某些目標的改進的凈收益,由于將一個目標向量替換為另一個非支配目標向量而導致的其他目標的惡化,抵消了這些收益[37],通常對每對目標函數(shù)都給出折衷的數(shù)學定義.

Deb和Gupta[32]提出了兩個目標的情況下Tradeoff的計算方法.該方法依賴于用戶指定的權(quán)衡信息,該信息以一對值(α ＜1,β ＜1)的形式提供.首先將所有目標函數(shù)值進行歸一化,對于Pareto前沿上的Knee來說,f1中的單位增益至少應在f2中引起α的犧牲,并且類似地,f2中的單位增益至少應在f1中引起β犧牲.

在文獻[37]中,Rachmawati和Srinivasan提出了指標用來評價解的Trade-off性能,其計算公式可以表示如下:

其中:n是目標數(shù),fk(xi)表示解xi的第k個目標值,fmax(k)和fmin(k)分別對應總體中第k個目標的最大值和最小值.μ(xi,S)表示通過用xi替換任何解決方案xj從S到每單位劣化的最小改善量.

在文獻[38]中,Bechikh在環(huán)境選擇中利用Tradeoff信息來保留Knee.Li等人[39]在此基礎(chǔ)上,提出了Trade-off效用的方法,并且通過實驗證明了提出的方法具有良好的效果.

Trade-off方法在尋找Knee的過程中,對于Pareto前沿面的光滑程度敏感度較小,因此也能較好地識別出Knee.但是由于該方法需要計算個體相對于其他所有個體的影響,因此計算復雜度較高.

2.5 基于最小曼哈頓距離的方法

最小曼哈頓距離(minimum manhattan distance,MMD)方法[40]結(jié)合了幾何信息分析和解性能評估.首先計算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支配關(guān)系是嚴格的偏序關(guān)系,這意味著所有目標都具有同等的重要性和相同的權(quán)重,因此在任何目標上都沒有偏好.換句話說,在Pareto前沿上,Knee與其他非Knee的點具有相同的選擇優(yōu)勢,算法不會將種群的搜索方向引導到Knee上.針對這個問題,Ramirez-Atencia等人[13]提出了錐支配(cone-domination)的概念,定義了一個權(quán)重函數(shù)對目標函數(shù)值進行轉(zhuǎn)換,可以表示為

其中aij為第j個目標函數(shù)中損失一個單元時對應的第i個目標函數(shù)的增益值.

通過此定義,對原來的目標函數(shù)增加了權(quán)重,因此具有Knee特性的解在Pareto支配關(guān)系上更具有優(yōu)勢.上述修改可以理解為一個擴展優(yōu)勢關(guān)系,提高Pareto前沿上具有特定角度的區(qū)域的競爭優(yōu)勢,該角度可以表示為φ并且滿足tan=aij,類似的策略也見于文獻[42-43].

3 Knee的保留策略

在算法執(zhí)行過程中,不同的Knee檢測方法需要不同的Knee保留方法.通常來說,Knee的保留策略可以分為強制保留和概率保留.

3.1 增加Knee的保留概率

通常而言,EMO算法的進化過程可以歸納為:挑選父代個體產(chǎn)生新解,從中挑選出具有更好性能的解組成新的父代.算法在迭代過程中,種群不斷向理想Pareto前沿逼近.NSGA-II采取兩個策略對新產(chǎn)生的解進行篩選.首先對新解和父代進行快速非支配排序,并挑選出非支配解,如果非支配解的個數(shù)大于設定的種群數(shù)量,則進行第2次篩選.在第2次篩選中,首先計算出個體的擁擠距離,并挑選擁擠距離較大的解,以此來維持解分布的均勻性.

在Knee算法中,首先運用Knee檢測方法尋找出當前的Knee,然后給Knee以及Knee在周圍的解增加優(yōu)勢,由此增大該區(qū)域的被選中概率.Branke等人[19]提出使用反射角度和EMU 進行Knee 的探測,并且在NSGA-II算法的基礎(chǔ)上,將擁擠距離用反射角度(或者EMU)替換,從而對Knee進行保留.實驗結(jié)果表明,這個方法在測試問題上具有較好效果.

Li等人[20]則提出使用激活函數(shù)給Knee周圍的解增加適應度.在Knee檢測之后,計算當前解與Knee之間的距離,當距離小于預先設定的閾值時,則對該解進行獎勵,以此對Knee進行保留.

3.2 強制保留Knee

與增加Knee的保留概率的方法不同,在特殊情況下,Knee被強制保留進入下一代參與進化,從而確保當前Knee得到保留.基于分解的多目標優(yōu)化算法使用標量函數(shù)將多目標優(yōu)化問題轉(zhuǎn)化為許多個單目標優(yōu)化問題,并在一次運行中對所有單目標優(yōu)化問題求解.Li 等人[20]在MOEA/D的基礎(chǔ)上提出了一種獲取Knee的算法.在檢測到Knee之后,對不在Knee周圍的個體的權(quán)重向量進行修改,使得個體不斷向著Knee靠近,其權(quán)重向量更新過程可以表示為

其中:Wi表示個體的權(quán)重向量,r ∈[0,2]是隨機值.

Sudeng等人[44]在MOEA/D-DE的基礎(chǔ)上,引入了參數(shù)r用來控制獲得的Knee區(qū)域的均勻性,并通過實驗證明了該方法能有效處理目標個數(shù)為2-5的Knee測試問題.

3.3 保留策略的執(zhí)行條件

算法在搜索過程中需要動態(tài)探測Knee,并通過采取特定的策略來保留Knee區(qū)域.而由于在算法的搜索過程中,Pareto前沿呈現(xiàn)出不規(guī)則性,因此在何種條件下應用Knee的探測方法和Knee的保留方法至關(guān)重要.如果過早的進行Knee的探測,則不規(guī)則的Pareto前沿將導致對于Knee的誤判.在這種情況下,算法可能出現(xiàn)在不同的Knee之間搖擺的情況,從而導致收斂性能變差.

另一方面,如果在算法的后期進行Knee的探測,則對于計算資源是一種浪費.值得注意的是,針對不同的問題,傳統(tǒng)的EMO算法收斂到Pareto前沿需要的迭代次數(shù)各有不同,因此不可能單獨定義一個閾值來作為是否檢測Knee的標志.好的策略應是針對不同的問題動態(tài)進行閾值調(diào)整.

Li等人[20]提出以迭代次數(shù)作為分界線,并通過實驗指出在30%～50%迭代次數(shù)時進行Knee的探測和保留能讓算法在給定的測試問題取得最佳效果.然而,由于不同的測試問題,搜索到真實Pareto前沿的難易程度是不同的.因此該方法在進行Knee檢測時很難保證當前的Pareto前沿具有顯著的幾何特征.

Rachmawati等人[37]則指出,可以根據(jù)當前非支配解占總體的比值來決定是否執(zhí)行Knee的保留策略,并通過實驗建議當該比值大于80%時采取Knee的保留策略.Zhang等人[14]使用MMD進行Knee的檢測并在算法運行的最開始便執(zhí)行Knee的保留策略.經(jīng)過試驗指出該方法對于特定的測試問題具有較好效果.但是,對于收斂難度較大的測試問題,由于算法運行的前幾代無法形成具有幾何特征的Pareto前沿,導致算法在收斂難度較大的測試問題上效果較差.

由于不同的問題收斂難易程度不一致,因此,如何確定合適的迭代次數(shù)來進行Knee檢測和保留,也不盡相同.目前就何時進行Knee的檢測與保留提出的方法均有缺陷,隨著機器學習等工具的發(fā)展,未來針對該問題引入自適應機制進行動態(tài)調(diào)整,或?qū)⒊蔀榻鉀Q方法之一.

4 測試問題及評價指標

近年來,學者們也相繼提出了針對Knee研究的測試問題集.Guo等人提出了二維的測試問題CKP[45];Branke等人[19]基于DTLZ問題提出了DO2DK、DEB-2DK、DEB3DK系列測試問題.該系列測試問題可以通過參數(shù)K控制Knee的個數(shù).Tea等人[46]則在DEB-DK問題的基礎(chǔ)上,將目標個數(shù)拓展到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代)內(nèi)就可以收斂到Pareto前沿,而現(xiàn)實問題往往較為復雜,因此該類測試問題很難反映算法在復雜問題上的性能.Guo等人[47]針對Knee問題提出了的新的、較為全面的PMOP測試問題集,該測試集合考慮了問題是否線性、凸性、退化、規(guī)模等特性.其測試問題具體定義如下:

其中:g(X)是控制問題收斂性難易的函數(shù);l(X)用于調(diào)整決策變量間的相關(guān)關(guān)系以及線性或非線性的鏈接函數(shù);h(X)函數(shù)用來確定Pareto前沿的形狀;Knee函數(shù)k(X)可用于確定Pareto前沿的對稱性、Knee個數(shù)、位置、退化以及Knee區(qū)域的可區(qū)分性.

根據(jù)問題的定義,原文作者具體提出了PMOP1-14等測試問題,并且該測試問題能夠方便的擴展到任意目標維度.圖7為PMOP1-14測試問題在三目標情況下的Pareto前沿和Knee分布情況,更多詳細信息,請參考原文獻.Tea等人[46]在對Knee問題進行研究時,將DEB-DK系列測試問題拓展到4維和5維的情況,并提出了prosection方法用于展示4維和5維情況下測試問題的Pareto前沿.簡單來說,prosection方法的想法是使用映射函數(shù)一次只顯示空間的一部分,如式(14)所示.在4個目標的情況下,該方法定義了兩個參數(shù),即角度φ和截面寬度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個目標函數(shù)值.在本文中,為了更好地顯示效果,設置φ=?=45°,d=e=3.

在本文中,展示了具有5個目標函數(shù)的PMOP1-9經(jīng)過prosection變換之后的Pareto前沿及其Knee分布情況,如圖8所示.從圖8中可以看出,經(jīng)過投影變換之后的三維圖像,仍然具有一定的關(guān)于Knee的幾何特征,其展示的Pareto前沿具有明顯的分層現(xiàn)象.由此可以看出,prosection變換方法能夠在一定程度上用于展示具有Knee的問題的Pareto前沿.然而,隨著目標函數(shù)個數(shù)的增多,其Knee特征在轉(zhuǎn)換后的Pareto前沿上越來越不明顯.因此,針對高維多目標Knee測試問題的可視化方法仍然是目前的研究重點之一.

圖8 5目標PMOP1-9測試問題經(jīng)過prosection變換之后的Pareto的前沿,其中紅點表示KneeFig.8 The pareto front of PMOP1-9 with 5 objectives after prosection,where the red points represent the Knee

對于Knee 問題,由于算法只關(guān)注于獲得特定的Knee區(qū)域,因此針對傳統(tǒng)EMO算法的評價指標不太適用于評價Knee算法的優(yōu)劣.由于缺少相關(guān)的評價指標,早期的Knee算法沒有使用定量的評價指標對算法進行評價,而是通過給出算法運行的Pareto前沿進行直觀判斷,其中一個原因是DO2DK、DEB-DK問題具有直觀的2-3維的幾何特征.隨著算法的發(fā)展,一些學者提出使用世代距離(GD)作為算法的評價指標.GD[48]代表解與真實Pareto前沿的距離,只反應解逼近真實最優(yōu)解的距離,因此可以用來衡量Knee算法的性能,其定義如下:

其中n代表解的數(shù)量,di是每個解與真實Pareto前沿中最近點之間的歐幾里得距離.GD只反應獲得的解與真實解的差距,不能反應找到的解是否是Knee,以及距離真實Knee之間的差距.

Guo等人[47]針對Knee問題提出了KGD、KIGD以及KD評價指標,其中KGD評估獲得的解到Knee區(qū)域參考點的收斂性能,KIGD評估了在Knee區(qū)域獲得的解決方案的多樣性,KD評估算法查找所有Knee的搜索能力.給定在Knee區(qū)域中獲取的一組均勻分布的參考點Q(包括真實的Knee(K)),G表示獲得的Pareto解集,則KGD、KIGD以及KD的計算方式可以表示為

KGD衡量所獲得的解與Knee區(qū)域的接近程度.它主要評估MOEA的搜索能力,也可以評估其識別Knee區(qū)域內(nèi)解的能力,因為Knee區(qū)域以外的解決方案會降低KGD值.而KIGD值指示所獲得的解覆蓋Knee區(qū)域的程度,這主要評估了分布在Knee區(qū)域的解的多樣性.如果決策者僅對Knee附近而非Knee區(qū)域的解感興趣,KD可以表示解集中是否至少有一個解靠近Knee,并且該解集是否可以找到全部Knee.僅當解集完全覆蓋所有Knee時,KD值為零.因此,KD可有效評估算法識別Knee附近個體的能力.

5 總結(jié)展望

隨著問題復雜度的增加,需要考慮的目標函數(shù)也越來越多,因此高維多目標優(yōu)化開始進入EMO領(lǐng)域.針對高維多目標優(yōu)化提出的算法,需要使用數(shù)量較大的種群參與進化,以描述整個Pareto前沿.由于最終需要從得到的Pareto解集中挑選出一個解作為最終方案,因此花費大量資源去搜尋Pareto前沿上決策者不感興趣的解是一種浪費.同時,決策者在面對數(shù)量巨大、目標函數(shù)眾多的Pareto解集時,往往很難給出最終方案.多目標優(yōu)化中,Knee作為在沒有特定決策偏好下的更好選擇,能夠反映出不同目標函數(shù)之間互相影響的程度,在近些年得到越來越多學者的關(guān)注,特別是在高維多目標優(yōu)化領(lǐng)域.針對如何檢測、獲取Knee,大量學者做了相關(guān)研究并取得了效果.研究指出,專注于Pareto前沿上的Knee區(qū)域能夠顯著降低問題求解的種群規(guī)模,并且有效提高解集的性能.基于此動機,本文對Knee的檢測方法、保留策略、測試問題以及算法評價指標等作了較為全面的回顧,以幫助讀者快速了解本領(lǐng)域的基本知識和研究現(xiàn)狀.

目前針對低維多目標優(yōu)化問題,全局和局部的Knee均能夠被很好的找到并保留,因此Knee算法在一些實際問題上取得了較好效果,例如車間調(diào)度、任務規(guī)劃等.但是針對低維情況,筆者認為可以首先獲取整個Pareto前沿,然后采用一些后驗的方法來找出Knee區(qū)域,因此更多關(guān)于Knee搜索的研究應該著眼于高維多目標優(yōu)化問題.筆者認為,至少可以從以下幾個方面對Knee進行研究和開發(fā):

一是結(jié)合強化學習[49]等機器學習方法,提高Knee檢測的效率和效果.在前面的回顧中可以發(fā)現(xiàn),Knee的檢測和保留策略的執(zhí)行都需要手動設置參數(shù)值.然而,類似的最佳參數(shù)跟要求解的具體問題息息相關(guān).因此,目前還沒有一個公認的較為穩(wěn)定的參數(shù)設置方法.基于強化學習等機器學習技術(shù),在參數(shù)的設置上進行優(yōu)化,或者將此類技術(shù)與Knee的檢測和保留相結(jié)合,從而進一步提高方法的魯棒性,將是未來可行的研究方向.

二是開發(fā)用于展示高維Pareto前沿Knee特征的可視化方法.目前來說,針對高維的Pareto前沿的展示方法有常用的線性圖、雷達圖等[50].然而,類似的方法只能將多目標優(yōu)化問題的各個目標函數(shù)值進行展示,考慮到Knee問題在2-3維的情況下具有非常明顯的幾何特征,因此,開發(fā)面向任意維度的Knee問題可視化方法,對于Knee算法性能的檢測以及檢測效果都具有重要意義.Tea等人[46]使用projection技術(shù)將4-5維的Pareto前沿投影到3維空間,能大致看出其Knee的幾何特征,然而,隨著目標個數(shù)的增加,其投影之后的圖像會變得十分混亂,難以分辨.

三是將基于Knee的EMO算法應用到需要動態(tài)決策的問題中.多目標優(yōu)化算法大多是一種離線的應用,因為其最終要選擇一個最優(yōu)解作為方案去應用.為實現(xiàn)多目標優(yōu)化算法的在線、動態(tài)應用,在缺乏決策偏好信息的情況下,往往很難挑選出最合適的解.由于Knee算法能自動給出當前Pareto前沿上的最佳解,因此結(jié)合Knee方法對此類問題進行優(yōu)化將減少用戶輸入?yún)?shù)、提升最終解的質(zhì)量.選擇基于Knee的多目標優(yōu)化算法,即找到Pareto前沿的Knee點(區(qū)域),并將之作為最優(yōu)解進行下一步的動態(tài)搜索.目前該理念已被成功應用到自步學習(self-paced learning)中[51-52],并通過實驗證明該方法具有良好的效果.在自步學習中,需要不斷確定下一步使用哪些數(shù)據(jù)集參與訓練,而Knee算法很好的滿足了該需求.另外,在微電網(wǎng)能量管理優(yōu)化問題中,為了降低用戶負荷、可再生能源發(fā)電等隨機性帶來的影響,需要引入模型預測控制方法[53].該方法可以根據(jù)預測數(shù)據(jù)和實時數(shù)據(jù)動態(tài)調(diào)整微電網(wǎng)的運行策略,從而降低微電網(wǎng)的運行費用.通過將Knee算法與模型預測控制框架相結(jié)合,從而在每個時間節(jié)點自動選擇最佳解來應用,可以提高EMO算法的適用性以及準確性.