決策空間定向搜索的高維多目標優(yōu)化策略*

鄭金華,董南江,阮 干,鄒 娟,楊圣祥,3

1(智能計算與信息處理教育部重點實驗室(湘潭大學(xué)),湖南 湘潭 411105)

2(智能信息處理與應(yīng)用湖南省重點實驗室(衡陽師范學(xué)院),湖南 衡陽 421002)

3(School of Computer Science and Informatics,De Montfort University,Leicester LE19BH,UK)

通訊作者:董南江,E-mail:643260047@qq.com;鄒娟,E-mail:zoujuan@xtu.edu.cn

現(xiàn)實世界中存在多目標優(yōu)化問題(multi-objective optimization problem,簡稱MOP)[1,2],這些多目標優(yōu)化問題中不同目標之間的優(yōu)化存在著相互沖突的關(guān)系,不同于單目標優(yōu)化問題的最優(yōu)解只有一個,多目標優(yōu)化問題的最優(yōu)解是一組均衡解.多進目標化算法(multi-objective evolutionary algorithm,簡稱MOEA)[1,2]是一類基于群體智能的迭代優(yōu)化算法,因其能夠在單次運行中找到一組解,被廣泛地應(yīng)用于求解多目標優(yōu)化問題,受到越來越多研究者的關(guān)注.MOEA 的目標是尋找盡可能接近最優(yōu)均衡解集的一組均衡解集,這組決策向量解集稱為帕瑞托解集(Pareto set,簡稱PS),PS 對應(yīng)的在目標空間的目標向量集稱為帕瑞托前沿(Pareto front,簡稱PF).

現(xiàn)有的MOEA 在求解多目標優(yōu)化問題時有兩個關(guān)鍵的部分,一是如何生成解,二是如何保留解.

· 如何生成解主要與交叉及變異算子相關(guān),對于連續(xù)多目標優(yōu)化問題經(jīng)常使用的交叉及變異算子有模擬二進制交叉[3,4]、差分變異[5]、多項式變異[6]等;

· 對于如何保留解可以根據(jù)保留解的方式把現(xiàn)有算法大致分為:基于支配關(guān)系的算法,如NSGA-II[7],SPEA2[8]等;基于分解和參考點的方法,如MOEA/D[9]及其衍生算法、NSGA-III[10]等;基于指標的算法,如HypE[11]等.保留解通常選擇適應(yīng)度值高的個體保留下來,將適應(yīng)度值低的個體刪除掉.適應(yīng)度的計算通常會考慮解的收斂性和分布性,常用的分布性保持機制有聚集距離方法[7]、修剪的方法[8]、小生境技術(shù)[1]、均勻生成權(quán)重向量[9]或參考點方法[10]等,常用的收斂性保持機制有 Pareto 支配[1,7]及MOEAD 中用到的聚集函數(shù)[8]等.

傳統(tǒng)的基于支配關(guān)系的算法,如NSGA-II 和SPEA2,在求解低維的多目標優(yōu)化問題時已具有較好的效果,但是隨著目標維數(shù)的增加,當目標數(shù)大于3 時,問題的優(yōu)化難度將顯著增加.主要原因有:(1)算法本身的搜索能力不足;(2)選擇壓力不足.目標維數(shù)增加后,不同目標間優(yōu)化沖突加劇,收斂性和分布性難以平衡[12-15].當優(yōu)化問題的最優(yōu)PF 比較復(fù)雜和目標維數(shù)較大時,基于分解的算法就很難恰當?shù)貙栴}進行分解[16].基于指標的算法對于高維多目標優(yōu)化則隨著目標維數(shù)增加,算法的時間復(fù)雜度呈指數(shù)增加;同時,由于指標的特性,會使得算法偏好于PF 中的某些特殊點[16].

現(xiàn)有MOEA 的普遍做法是:在一次種群迭代優(yōu)化過程中同時保持種群的多樣性和收斂性,計算資源分配均勻,試圖在每次迭代中覆蓋整個PF,相應(yīng)的計算資源也總是均勻地分配在整個PF 上,導(dǎo)致具體分配到每個PF 的子部分計算資源匱乏.對高維MOP 來說,算法本身搜索能力已經(jīng)不足,這時再將計算資源均勻分配,則會導(dǎo)致每一子部分的搜索能力更加不足,從而進一步降低算法的搜索能力.

另一方面,現(xiàn)有MOEA 對優(yōu)化問題的特性利用并不是很充足.根據(jù)庫恩塔克定理,連續(xù)多目標優(yōu)化問題的特性[17,18]是PS,是m-1(m為MOP 的目標維數(shù))維的流體,同時,交叉變異算子的共性是子代個體與父代個體成一定關(guān)系,以更高的概率分布在父代個體周圍[3-6],因此,在PF 附近的父代個體更容易生成好的子代個體.

本文主要是對基于支配關(guān)系這一類算法進行研究.根據(jù)以上兩點,在如何生成解方面做了進一步的工作,利用多目標優(yōu)化問題的特性,為克服多目標優(yōu)化算法在高維問題中遇到的困難,提出了基于決策空間的定向搜索策略(decision space,簡稱DS),通過影響子代個體的生成區(qū)域來影響算法的收斂性和分布性.基本思想是,將算法的整個優(yōu)化過程分為3 個階段:第1 階段,針對問題進行采樣分析,判斷出問題決策空間的收斂性控制向量和分布性控制向量,并在之后的搜索過程中,基于采樣分析結(jié)果確定收斂性子空間和分布性子空間;第2 階段,算法沿著收斂性子空間搜索,使少數(shù)解先到達真實PF 附近;第3 階段,算法沿著分布性子空間搜索,使種群盡可能接近且廣泛地覆蓋真實PF.基于問題采樣的分析結(jié)果,先在收斂性子空間中搜索,不僅局部集中了計算資源,同時也克服了高維問題中選擇壓力不足的問題,當少數(shù)個體逼近真實PF 后,再通過在分布性子空間的搜索,使種群均勻廣泛地覆蓋整個PF.

近年來,也有關(guān)于目標空間收斂性和分布性的研究,主要代表有大規(guī)模多目標進化算法LMEA[19].LMEA主要是通過對決策變量分類,然后對分類后的決策變量進行分別優(yōu)化的算法.本文是提出一種有方向性地搜索的策略,可以與其他基于支配關(guān)系的算法相結(jié)合.本文中,DS 策略的采樣分析方法確定搜索方向與決策變量分類有一定的相似性,但是整體的搜索策略是完全不同的:LMEA 算法中,依然把收斂性和分布性在一次迭代優(yōu)化中同時考慮;而DS 策略則是將收斂性和分布性按階段分開考慮,收斂性相同的個體間比較分布性,分布性相同的個體間比較收斂性,增加了算法的搜索能力.

本文的主要貢獻如下:

(1)對解決高維連續(xù)多目標優(yōu)化問題提供了新的視角.由于連續(xù)多目標優(yōu)化問題的特性及優(yōu)化過程中收斂性和分布性難以平衡,而直接將收斂性和分布性分開在算法的不同階段進行搜索;

(2)新個體的產(chǎn)生不再是獨立于優(yōu)化問題.以往算子在生成個體時是獨立于目標空間的,目標空間不會對其產(chǎn)生影響;DS 通過優(yōu)化問題的采樣分析,判斷問題在決策空間以及目標空間的變化趨勢,分析結(jié)果將對算法搜索過程中子代個體的生成進行宏觀的影響,一定程度增強了算法的搜索能力;

(3)將DS 策略結(jié)合到NSGA-II,SPEA2 中,通過DTLZ,WFG 測試問題對DS-NSGA-II 進行了測試.并與一些比較經(jīng)典和流行的算法進行了對比實驗.

本文第1 節(jié)主要介紹動機及給出的相關(guān)定義.第2 節(jié)詳細介紹基于決策空間的定向搜索策略.第3 節(jié)進行實驗對比并對實驗結(jié)果進行分析.第4 節(jié)對本文進行總結(jié)及展望下一步研究工作.

1 動機及相關(guān)定義給出

1.1 連續(xù)多目標優(yōu)化問題的特性

根據(jù)庫恩塔克條件(KKT)可以得出:對于連續(xù)的多目標優(yōu)化問題,PS 是分段連續(xù)的m-1 維流體,m為目標空間的維數(shù).這種性質(zhì)稱為多目標優(yōu)化問題的特性[17,18].

定理1.假設(shè)當x*∈Ω(Ω的維數(shù)為n)時,目標函數(shù)fi(x),i=1,…,m是連續(xù)可微的,如果x*是一個Pareto 解,則存在一個向量α≥0,滿足:

滿足公式(1)的點稱為KKT 點.公式(1)有n+1 個等式約束和n+m變量x1,…,xn,α1,…,αm,因此在連續(xù)可微的情況下,多目標優(yōu)化問題的PS 是分段連續(xù)的m-1 維的流體.具體地說,對于二維的優(yōu)化問題,其PS 是一條曲線;對于三維的優(yōu)化問題,其PS 是一個曲面.

由于PS 是m-1 維的流體,為簡化理解,我們將個體在決策空間中距真實PS 上某一點的距離視為搜索到該點所需的計算資源,則可以得出這樣的結(jié)論:在真實PS 附近的父代個體,更容易生成位于PS 附近其他位置上的子代個體.如圖1 所示,曲線為真實PS,A,B個體是已知的父代個體,C為想要搜索得到的子代個體,由于A個體相對于B個體更靠近C,則相較于B個體,通過A個體進行基因重組更容易搜索得到C個體.

Fig.1 Schematic map of search difficulty圖1 搜索難易程度示意圖

1.2 計算資源分配

現(xiàn)有多目標優(yōu)化算法的普遍做法是:在一次迭代過程中試圖保證整個種群在目標空間的收斂性和分布性,算法的收斂性保持機制和分布性保持機制在同時發(fā)揮著作用.因此,整個種群是在不斷地迭代優(yōu)化過程中整體去逼近整個真實PF.

MOEA 每一次迭代優(yōu)化得出的解集中,個體的收斂程度和分布均勻性是不盡相同的.不過,為了方便理解,暫且將其理解為大致相同.如圖2 所示,F1,F2視為目標空間中平行于真實PF 的一層子空間,將F2附近的個體作為一個種群P2,種群大小為n,經(jīng)過m次迭代進化后得到F1附近的種群P1.由于算法在每次迭代中同時保證種群的分布性和收斂性,因此可以近似理解為種群P2是沿著虛線方向同步搜索至種群P1.如果將每個個體看做計算資源的單元,則P2搜索至P1消耗計算資源m×n,每一條虛線方向分配計算資源m個.因此可以理解為傳統(tǒng)的MOEA 是將計算資源盡量均勻分配,求得最優(yōu)PF 的各個子部分,各子部分之間通過遺傳算子存在一定的聯(lián)系.

Fig.2 Schematic diagram of resource allocation model圖2 資源分配模型示意圖

1.3 收斂性與分布性

多目標優(yōu)化算法追求的目標是求得的最終解集盡可能地靠近真實的PF,同時盡可能均勻和廣泛地覆蓋真實PF,前者是收斂性,后者是分布性.在多目標優(yōu)化過程中,尤其是高維多目標優(yōu)化問題,生成的解絕大部分個體是互不支配的,且收斂程度是不一樣的.下面將給出一些名詞的含義.

· 收斂度:如果我們把目標空間進行分層,真實PF 為最里層,每一層與真實PF 結(jié)構(gòu)平行相似,個體所在層的位置代表其收斂程度,越接近真實PF 層,則收斂程度越高;

· 同收斂性個體:將收斂程度相同(位于同一層)但在不同位置的個體稱為同收斂性個體;

· 同分布性個體:將在每一層中相對位置相同但收斂程度不同的個體稱為同分布性個體.

如圖3 中,F1為目標空間中真實PF,則3 條曲線的收斂程度是:F1>F2>F3;A點和B點都位于F2層附近的不同位置,所以A,B為同收斂性個體;同理,B點和C點位于不同層的附近,但在各自層的相對位置相同,所以B,C為同分布性個體;而A點和C點則是收斂性和分布性都不相同的個體.在高維多目標問題優(yōu)化時,種群中個體間的關(guān)系絕大部分是A點和C點的關(guān)系.

· 收斂性子空間:在決策空間中存在這樣一個子空間Ω:在Ω中,絕大部分個體之間是支配與被支配的關(guān)系,則稱Ω空間為收斂性方向子空間;

· 分布性子空間:在決策空間中存在這樣一個子空間Ω:在Ω中,絕大部分個體之間是互不支配的關(guān)系,則稱Ω空間為分布性方向子空間;

· 子空間的確定:先確定一個點R,以R點為基點,結(jié)合子空間控制向量V[n],確定子空間Ω.

子空間控制向量V[n],n為決策空間變量的維數(shù),V[i]值為0 或1:V[i]為1,則表示子空間Ω在Xi變量上的范圍是變量Xi的上下界;V[i]為0,則表示子空間Ω在Xi變量上為固定值,其值的大小由點R在Xi變量上的值確定.

以圖3、圖4 為例,將圖4 中的個體與圖3 中的個體相對應(yīng),圖4 為個體在決策空間的位置,圖3 為個體在目標空間的位置.圖4 的決策變量是2 維的,則其子空間是一維的.從圖3 可以看出,A,B為收斂程度相同分布位置不同的個體,所以A,B在決策空間中同一個分布性子空間;而B,C在同一收斂性子空間,為分布性相同收斂性不同的個體.收斂性子空間Ω1由C(或B)和收斂性控制向量V-con={1,0}確定:V-con[0]=1,表示Ω1子空間在X1變量上的范圍是X1的定義區(qū)間;V-con[0]=0,表示子空間Ω1中X2變量的值與個體C(或B)的X2相同.同理,分布性子空間Ω2由個體A(或B)和分布性控制向量V-div[2]確定,V-div[0]={0,1}:V-div[0]=0,表示子空間Ω2中X1變量的值與個體A(或B)的X1相同;V-div[1]=1,表示子空間Ω2在X2變量上的范圍是X2的定義區(qū)間.

Fig.3 Convergence and distribution圖3 收斂性和分布性

Fig.4 Subspace model圖4 子空間模型

在本文中,點和控制向量確定子空間的方法只能確定與某一軸垂直或平行的子空間.對于ZDT,DTLZ,WFG等一系列問題,使用該方法已經(jīng)可以較準確地確定收斂性和分布性子空間.在本文中,我們也只考慮了這種情況.而當PS 比較復(fù)雜時,通過這種方法去確定子空間的準確性會降低,這時會導(dǎo)致算法的搜索效率不高.在實際應(yīng)用中也有許多問題PS 是相對復(fù)雜的,對于復(fù)雜PS 多目標優(yōu)化問題對應(yīng)的子空間的確定,將是我下一步研究的重點內(nèi)容.

現(xiàn)有的MOEA 在對收斂性不同且互不支配的個體進行選擇時,根據(jù)算法偏好對收斂性和分布性進行量化,然后擇優(yōu)選擇或隨機選擇[20-23].圖3 中,A點和C點的收斂性和分布性均不同,這時對A和C做出選擇必然對種群的收斂性或分布性一方造成損失:選擇A點損失種群的收斂性,選擇C點損失種群的分布性.正確的做法是在相同分布性的個體之間比較收斂性,然后擇優(yōu)保留;在相同收斂性的個體之間比較分布性,然后擇優(yōu)保留.

本文的出發(fā)點就是摒棄之前MOEA 在每一次迭代中同時保證種群的分布性和收斂性的做法,在搜索過程中,宏觀影響子代個體的生成區(qū)域,集中計算資源先保證種群的收斂性,使少數(shù)解快速搜索到真實PS 附近,然后根據(jù)多目標優(yōu)化問題的特性進行分布性搜索,使整個種群均勻覆蓋PF.這樣,在具體到一個子部分時,相當于增加了算法的搜索能力.而將算法的收斂性和分布性分開,也增加了環(huán)境選擇時的選擇壓力.以圖2 為例,先集中整個種群的計算資源,從A點開始沿著AB虛線方向搜索,使得少數(shù)解快速搜索至B點;然后改變搜索方向,利用算法分布性保持機制使種群較好地覆蓋整個PF.

2 DS:基于決策空間的定向搜索策略

2.1 基本思想

根據(jù)連續(xù)多目標優(yōu)化問題的特性,即多目標優(yōu)化問題的真實PS 是一個m-1 維的流體,可以得出:如果有一個解先到達真實PF 附近,可以通過這個解更快地找到其他好的解,然后通過分布性保持策略,最終使得整個種群較好地覆蓋整個PF 面.

與之對應(yīng),在算法的搜索過程中分為兩個階段——收斂性搜索階段和分布性搜索階段:收斂性搜索階段,算法側(cè)重于問題的收斂性,其目的是優(yōu)先使得少數(shù)解到達真實PF 附近;分布性階段,基于優(yōu)先到達PF 附近的少數(shù)幾個個體,確定分布性子空間,通過重組算子及分布性保持策略,將整個種群擴展開來覆蓋整個PF.

在第1.3 節(jié)中,通過對問題分布性和收斂性的分析得出:不同收斂性、不同分布性個體之間的比較優(yōu)劣進而選擇,必然導(dǎo)致收斂性或分布性其中一方受到損失,而相同收斂性個體之間比較分布性,相同分布性個體之間比較收斂性,這樣才更高效.所以在搜索過程的收斂性搜索階段,盡可能產(chǎn)生分布性相同的個體,比較其收斂性,使得少數(shù)個體快速抵達真實PF 附近;在分布性搜索階段,基于快速抵達真實PF 的少數(shù)解,通過重組算子生成收斂性相同但分布性不同的解,通過分布性保持策略,使整個種群更好地覆蓋整個PF.

從圖5 中可以了解到基于決策空間的定向搜索策略的整體框架:先對多目標優(yōu)化問題進行采樣分析,確定收斂性子空間和分布性子空間的控制向量,在不同搜索階段,根據(jù)子空間控制向量確定搜索子空間,通過子空間映射有效控制子代個體生成區(qū)域,這時,父代個體產(chǎn)生子代個體并不是獨立于優(yōu)化問題的,而是受到問題采樣分析結(jié)果的宏觀影響,同時也達到集中計算資源的效果.當結(jié)束條件滿足時,輸出最新優(yōu)化種群作為最優(yōu)解集.收斂性子空間搜索時,種群個體多為同分布性個體;分布性子空間搜索時,種群多為同收斂性個體.

Fig.5 Flow chart of the algorithm圖5 算法流程圖

整體思想雖然簡單,但有如下優(yōu)點:首先,優(yōu)化問題的特性及基因重組算子生成子代個體在父代個體周圍的特性,決定了先收斂性后分布性搜索策略的可行性,DS 策略充分利用了連續(xù)多目標問題的特性來增強算法的搜索效率;其次,將收斂性和分布性分開在不同階段搜索,化解了高維多目標優(yōu)化問題中收斂性和分布性難以平衡的難點,使得該策略在高維優(yōu)化問題中會有較好的表現(xiàn);最后,收斂性和分布性分開搜索可以使計算資源在具體時刻具體子部分更加集中,增強了算法的搜索能力.

2.2 算法流程

基于決策空間定向搜索策略可以與基于支配關(guān)系的算法相結(jié)合,解決高維的連續(xù)多目標優(yōu)化問題,而且對原有算法的改動較小,使得加入DS 策略比較簡單.圖5 中給出了結(jié)合DS 策略的算法流程.

問題采樣分析在一定程度上是對問題特性的一種解析,問題的采樣分析得出解空間中收斂性子空間和分布性子空間的方向趨勢特征,即子空間控制向量.需要注意的是:

· 在收斂性搜索階段,是要使少數(shù)解快速搜索到真實PF 上的任意一個位置,所以在種群初始之初隨機生成一個解,以該個體為中心,結(jié)合收斂性子空間控制向量確定收斂性子空間,在收斂性子空間中生成初始種群,然后不斷迭代,在收斂性子空間搜索優(yōu)化;

· 在分布性搜索階段,初始化與收斂性類似,不同的是以收斂性搜索階段所得的最優(yōu)的一個或少數(shù)幾個最優(yōu)解為中心,結(jié)合分布性子空間控制向量確定分布性子空間.

結(jié)合DS 策略的算法并沒有對原算法的收斂性和分布性保持機制進行改動,算法仍然使用原算法的環(huán)境選擇和匹配選擇機制.DS 策略主要是通過控制算法的搜索區(qū)域(即子代個體的產(chǎn)生區(qū)域)來影響算法的收斂性和分布性.在收斂性搜索階段,算法主要在收斂性子空間搜索,種群內(nèi)個體多為同分布性個體,此時,算法側(cè)重于種群的收斂性,這時主要是原算法的收斂性機制發(fā)揮作用,集中計算資源,使少數(shù)解快速優(yōu)化至真實PF 上或附近;在分布性搜索階段,算法主要在分布性子空間搜索,種群內(nèi)個體多為同收斂性個體,算法側(cè)重于種群的分布性,這時主要是原算法的分布性機制發(fā)揮作用,使種群可以很好地覆蓋整個PF.

2.3 問題采樣分析

問題采樣分析的準確程度很大程度決定了算法優(yōu)化的速率和準確度.通過問題采樣分析,我們得出分布性子空間和收斂性子空間的控制向量,進而確定收斂性子空間和分布性子空間,對迭代優(yōu)化過程中生成子代個體進行引導(dǎo),提高搜索效率.算法1 描述了問題采樣分析的流程.

算法1.優(yōu)化問題采樣分析.

輸入:決策變量維數(shù)n,優(yōu)化問題,對每一維決策變量采樣次數(shù)J;

輸出:收斂性子空間控制向量:V-con[n];分布性子空間控制向量:V-div[n].

這里,針對每一維的決策變量進行J次的個體采樣,決策變量維數(shù)是n,則總的采樣個體數(shù)為n×J.對于第i維決策變量采樣得到的J個個體,如果J個個體均為支配或被支配關(guān)系,則賦值V-con[i]=1,V-div[i]=0;反之,則賦值V-con[i]=0,V-div[i]=1.最終得出子空間控制向量V-con[n],V-div[n].關(guān)于如何通過子空間控制向量V-con[n],V-div[n]來確定子空間,已在第1.3 節(jié)中說明并舉例.

2.4 子空間映射

不同的搜索階段在相對應(yīng)的子空間進行搜索優(yōu)化.當子空間確定后,由于算法的搜索是集中計算資源對相應(yīng)子空間進行優(yōu)化搜索,而在以往的進化算法中采用的基因重組算子生成的解很有可能不在我們確定的目標子空間(收斂性子空間或分布性子空間)中,本文并沒有重新設(shè)計算子使得生成的解位于目標子空間內(nèi),而是采用原有的基因重組算子生成子代個體,然后通過一定的位置變換,使得新生成的個體位于目標子空間中.在本文中,我們具體采用的是映射的方法,將生成的子代個體映射到目標子空間中去,集中計算資源在相應(yīng)的子空間中搜索.算法2 具體描述了如何在目標子空間生成子代個體.

算法2.在目標子空間生成解.

輸入:種群P,種群大小N;

輸出:種群Q.

以圖6 為例,在二維的決策空間中,子空間為一維的流體,A′點為通過現(xiàn)有的交叉變異及變異算子生成的子代個體,將個體A′對子空間進行投影,得到個體A″,這時,用A″替代個體A′進行之后的個體評價及算法優(yōu)化.

Fig.6 Subspace mapping圖6 子空間映射

2.5 算法時間復(fù)雜分析

在算法中加入DS 策略,并不會增加原有算法的時間復(fù)雜度.DS 策略的加入,是對原有算法的搜索過程進行了宏觀的控制.相對于原算法,DS 策略的加入主要是增加了問題采樣和生成子代個體時的目標子空間映射.問題采樣分析的時間復(fù)雜度為n·J(n為決策空間維數(shù),J為針對每一維變量的采樣次數(shù));目標子空間映射在上一節(jié)詳細描述,并不會增加算法時間復(fù)雜度,因此,加入DS 策略并不會增加算法的時間復(fù)雜度.例如,NSGAII 的時間復(fù)雜度為O(rN2),則加入DS 策略的時間復(fù)雜度仍是O(rN2);SPEA2 的時間復(fù)雜度為O(rN3),則加入DS 策略的時間復(fù)雜度仍是O(rN3).其中,r為優(yōu)化問題的目標維數(shù).

3 實驗分析

DS 策略可以與基于支配關(guān)系的算法相結(jié)合,而與其他有強制性機制保證分布性和收斂性的算法則較難結(jié)合,比如MOEAD,NSGA-III,因為MOEAD 中均勻生成權(quán)重向量、NSGA-III 中的均勻生成參考點等這些機制導(dǎo)致DS 策略前期側(cè)重收斂性搜索優(yōu)化時效果不佳,因此本文選擇NSGA-II,SPEA2 算法與DS 策略結(jié)合進行實驗比較與分析.為了檢驗DS 策略的有效性,首先將結(jié)合了DS 策略的NSGA-II,SPEA2 算法(DS-NSGA-II,DSSPEA2)與原NSGA-II,SPEA2 算法進行實驗對比,來檢驗加入DS 策略之后對原有算法的影響;然后,基于DSNSGA-II 選取一些比較經(jīng)典主流的算法MOEAD-PBI,NSGA-III,Hype,MSOPS[24],LMEA 算法做對比實驗,來進行性能比較,檢驗DS-NSGAII 在高維多目標優(yōu)化問題中的性能.本文采用DTLZ 系列[25]、WFG 系列[26]測試問題,并分別采用IGD[27]和HV[28]指標對優(yōu)化結(jié)果進行評價.DTLZ,WFG 系列測試問題包含多種特性,包括線性問題、凸面問題、凹面問題、多峰問題、連續(xù)問題、非連續(xù)問題以及退化問題等[20,21].

3.1 實驗參數(shù)設(shè)置

為了公平地比較所有的優(yōu)化算法,本文采取推薦的參數(shù)值作為算法比較的參數(shù)值.本文涉及到的算法采用模擬二進制交叉和多項式變異的方法生成子代種群.正如在文獻[16]中推薦的,交叉的分配指標數(shù)(Nc)設(shè)為20,變異的分配指標數(shù)(Nm)設(shè)定為20,并且交叉的概率(Pc)設(shè)定為1.0,變異概率(Pm)設(shè)定為1/D,其中,D是決策變量的數(shù)量.為了避免生成的權(quán)重分布在Pareto 前沿的邊界上,采用NSGA-III 推薦的雙層參考點生成策略[10]去生成均勻分布的MOEA/D 權(quán)重向量和NSGA-III 的參考點.DS 策略中采樣分析部分取J值為8.J值越大,采樣分析結(jié)果越準確,對于絕大多數(shù)問題,J取8 已經(jīng)可以較準確地確定子空間的控制向量.本文其他算法對同一問題采用相同的種群大小,對于4 維～10 維的測試問題設(shè)置種群大小為120,對于15 維、20 維的測試問題設(shè)置種群大小為220.Hype,MSOPS,LMEA 均采用原文推薦的參數(shù)設(shè)置[11,19,24].每個算法針對所有測試問題都進行30 次獨立重復(fù)實驗.本文以個體的總評價次數(shù)作為算法的結(jié)束條件,表1 為所有的測試問題及其相對應(yīng)的結(jié)束條件.

Table 1 Terminate conditions表1 結(jié)束條件

在DS 策略中,兩個搜索階段間的轉(zhuǎn)換有一個條件,這里同樣把評價次數(shù)作為轉(zhuǎn)換的條件.將轉(zhuǎn)換搜索階段的評價次數(shù)設(shè)置為SUM×r,r為一個比值,取值范圍[0,1].當已評價的次數(shù)大于SUM*r時,將收斂性搜索階段轉(zhuǎn)變?yōu)榉植夹运阉麟A段.

r的取值范圍平均分成10 等分(參數(shù)變化梯度為0.1)進行實驗(r為0,即沒有收斂性搜索,顯然不利于問題的優(yōu)化,所以是以r取值0.1 為起始值進行的實驗),并統(tǒng)計DS-NSGA-II 算法在參數(shù)r不同取值下的IGD 值變化規(guī)律,獨立重復(fù)實驗30 次.如圖7 所示,給出了難收斂問題DTLZ3、退化問題DTLZ5、不連續(xù)PF 問題DTLZ7在8 維目標上的實驗結(jié)果.

r的值反映了在收斂性搜索階段分配的計算資源,從圖7 中可以看出,

· 當r=0.1 時,IGD 值很高;

· 隨著r值的增加,IGD 值顯著減少;

· 當r為0.5 時,IGD 值到達最小值;

· 之后,再隨著r值的增加,IGD 值并沒有再減少甚至有增大的趨勢.

這是因為當部分點已經(jīng)優(yōu)化至真實PF 附近時,再增加更多的計算資源也不會改善其收斂性,因為其收斂性已經(jīng)最優(yōu).因此,本文將r的值設(shè)為0.5,即收斂性搜索階段和分布性搜索階段獲得的計算資源基本相同.

Fig.7 IGD means with different values of r圖7 r 取不同值情況下的IGD 均值

3.2 評價指標

本節(jié)介紹兩個綜合性評價指標,分別是反轉(zhuǎn)世代距離IGD[27]和超體積指標HV[28].

· 反轉(zhuǎn)世代距離IGD 采用Pareto 最優(yōu)解集真實PF*中的個體到算法所求得的非支配解解集的平均距離來表示,其計算公式為

· 超體積指標HV 因其良好的理論支撐,已成為較流行的評價指標.通過計算非支配解集與參考點(最差點)圍成的空間的超體積的值,實現(xiàn)對MOEA 綜合性能的評價,計算公式為

其中,λ代表勒貝格測度;vi代表參考點和非支配個體pi構(gòu)成的超體積;S代表非支配解集,pi為S中的第i個個體.由于超體積指標HV的計算時間非常大,本文采用蒙特卡洛HV指標.

3.3 實驗結(jié)果分析

本節(jié)中將實驗結(jié)果以圖表的形式給出,表2 列出了所有實驗的均值和方差(括號內(nèi)是方差).其中表現(xiàn)最好的結(jié)果用灰色底紋標識.本文通過符號檢驗的方法對實驗數(shù)據(jù)進行顯著性分析,其中,顯著性水平閾值設(shè)置為0.05,signtest值越小,表明算法間的顯著性差異越大.?標識signtest值小于0.05 的情況.

1)DS-NSGA-II VS NSGA-II &DS-SPEA2 VS SPEA2

DS 策略可與基于支配關(guān)系的多目標進化算法相結(jié)合.本文將基于支配關(guān)系的經(jīng)典算法NSGA-II 和SPEA2與DS 策略相結(jié)合,分別得到算法DS-NSGA-II 和DS-SPEA2,采用DTLZ 系列測試問題進行測試,通過對比引入DS 策略前后算法的性能來驗證DS 的有效性.NSGA-II 和SPEA2 在低維多目標優(yōu)化問題中算法性能較好,且DS 主要是針對高維多目標優(yōu)化問題的一種策略,所以在該節(jié)中對DTLZ 系列測試問題在4 維～6 維、8 維這4個維度進行對比實驗.IGD 作為評價指標,實驗結(jié)果在表2 中給出,IGD 均值越小,表示算法性能越優(yōu)秀.

從表2 可以看出:由于DS 策略的引入,在DTLZ 系列測試問題中,DS-NSGA-II 和DS-SPEA2 在幾乎所有問題的不同維度上性能都優(yōu)于NSGA-II 和SPEA2,尤其對于比較難收斂的DTLZ1,DTLZ3 問題.從表中可以看出,NSGAII,SPEA2 算法的求解結(jié)果隨著目標維數(shù)的增加,IGD值也顯著增加;而結(jié)合DS 策略之后,求解結(jié)果的IGD值全部降低到1 以內(nèi).可見:隨著目標維數(shù)的增加,DS 策略對算法性能提高的程度也越高.NSGA-II 和SPEA2 在求解高維多目標優(yōu)化問題時能力匱乏,主要原因一是隨著目標維數(shù)的增加,非支配解集在種群中的占比顯著增加,導(dǎo)致算法的選擇壓力顯著下降;二是目標維數(shù)的增加一般伴隨著決策空間的增大,決策空間的增大導(dǎo)致算法的搜索能力不足.而DS 策略的引入,收斂性搜索階段在收斂性子空間產(chǎn)生解,減小了非支配解集的比例,增加了選擇壓力.不同階段在不同子空間搜索,避免了收斂性和分布性難以平衡的難點,集中了計算資源,增加了算法的搜索能力.因此,DS 策略的引入,加強了NSGA-II,SPEA2 在求解高維多目標優(yōu)化問題上的性能.

Table 2 Experimental results of DS-NSGA-II,NSGA-II,DS-SPEA2 and SPEA2 on DTLZ test problems表2 DS-NSGA-II,NSGA-II,DS-SPEA2,SPEA2 在DTLZ 測試問題上的實驗結(jié)果

圖8、圖9 是4 個算法對5 維的DTLZ1,DTLZ3 問題的優(yōu)化結(jié)果圖,圖中平行坐標中,橫坐標是目標空間不同的目標,縱坐標是目標值.從圖8、圖9 中可以看出,引入DS 策略后的算法在DTLZ1 問題上目標值可以很好地收斂到0～0.5 范圍內(nèi)且分布性良好;在DTLZ3 問題上,目標值可以很好地收斂到0～1 范圍內(nèi)且分布性良好;而原算法NSGA-II 和SPEA2 則不能收斂.同時我們也可以看到,DS-SPEA2 在DTLZ1,DTLZ3 上的分布性略好于DS-NSGA-II.這是由于SPEA2 的修剪策略比NSGA-II 的聚集距離在分布性保持上要好一些,但是修剪策略的時間復(fù)雜度相對較大.從圖中可以直觀地體會到:DS 策略的引入,使算法在高維多目標問題優(yōu)化上性能有了顯著的提升.

2)與其他算法比較

本節(jié)主要是進一步驗證DS 策略的有效性,證明將收斂性和分布性分開考慮的可行性,所以選取了不同類型的MOEAS 中比較有代表性的算法進行對比實驗.由于DS-SPEA2 的時間復(fù)雜度相比DS-NSGA-II 的時間復(fù)雜度要大,所以在本節(jié)中,我們采用DS-NSGA-II 與不同類型的算法進行進一步的比較,包括MOEAD-PBI,NSGA-III,Hype,MSOPS,LMEA.MOEAD 是基于分解的算法,NSGAII 是基于參考點,Hype 是基于指標的,MSOPS是基于新支配關(guān)系,LMEA 是一種決策變量分類的大規(guī)模多目標算法.測試問題采用DTLZ 系列和WFG 系列,分別在8 維、10 維、15 維、20 維這4 個維度上做對比實驗.DTLZ 問題采用IGD 評價指標,WFG 問題采用HV指標,IGD指標數(shù)值越小,表示算法性能越優(yōu)秀;HV指標數(shù)值越大,表示算法性能越優(yōu)秀.表3 是DTLZ 系列測試問題的IGD指標測試結(jié)果,表4 是WFG 系列測試問題的HV指標測試結(jié)果.

Fig.8 Experimental results of DS-NSGA-II,DS-SPEA2,NSGA-II and SPEA2 on DTLZ1 problem圖8 DS-NSGA-II,DS-SPEA2,NSGA-II,SPEA2 在DTLZ1 問題上的實驗結(jié)果圖

Fig.9 Experimental results of DS-NSGA-II,DS-SPEA2,NSGA-II and SPEA2 on DTLZ3 problem圖9 DS-NSGA-II,DS-SPEA2,NSGA-II,SPEA2 在DTLZ3 問題上的實驗結(jié)果圖

Table 3 Experimental results of DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS and LMEA on DTLZ series test problems表3 DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS,LMEA 在DTLZ 系列測試問題上的實驗結(jié)果

Table 4 Experimental results of DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS and LMEA on WFG series test problems表4 DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS,LMEA 在WFG 系列測試問題上的實驗結(jié)果

Table 4 Experimental results of DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS and LMEA on WFG series test problems (Continued)表4 DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS,LMEA 在WFG 系列測試問題上的實驗結(jié)果(續(xù))

從表3 和表4 中我們可以看到,DS-NSGA-II 不論在DTLZ 系列測試問題還是在WFG 系列測試問題上,對大部分的測試問題都具有良好的表現(xiàn).DTLZ1-3 測試問題中,DS-NSGA-II 大部分情況下不同程度地優(yōu)于其他算法,LMEA 的IGD值較接近于DS-NSGAII.但總體略差,而在DTLZ5-6 退化的測試問題上,LMEA 表現(xiàn)較好,但是DS-NSGA-II 在這類問題尤其是DTLZ5 上明顯優(yōu)于其他算法.在DTLZ7 不連續(xù)的測試問題中,DS-NSGA-II 則優(yōu)于其他算法.在WFG2,WFG5,WFG6 測試問題上,DS-NSGA-II 表現(xiàn)良好;對于WFG3 問題,LMEA 表現(xiàn)更好一些,但是DS-NSGA-II 與之相比非常接近且明顯好于其他算法.

同時,我們也能看到,DS-NSGA-II 在DTLZ 系列中的DTLZ4,DTLZ6 問題上,在WFG 系列中的WFG1,WFG7～WFG9 問題上的性能并不是很好.關(guān)于DS-NSGA-II 對大部分測試問題性能良好的原因,在前面小節(jié)中已有解釋,這里主要分析一下DS-NSGA-II 為何在DTLZ4,DTLZ6,WFG7～WFG9 這些測試問題上表現(xiàn)不佳,主要原因有兩個方面:一是本文中問題采樣分析的方法較為初始簡單,采樣分析結(jié)果與實際問題可能會有一定的偏差,導(dǎo)致在算法的搜索過程中產(chǎn)生一定偏差;二是NSGA-II 算法的分布性保持機制(聚集距離)本身存在一定的瓶頸.同時,DTLZ4,WFG 問題對算法的保持分布性的能力要求較高.

圖10 是6 個算法在15 維的DTLZ3 和WFG3 的實驗結(jié)果圖(左列為DTLZ3,右列為WFG3).

Fig.10 Experimental results of DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS and LMEA on DTLZ3 and WFG3圖10 DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS,LMEA 在DTLZ3 和WFG3 上的實驗結(jié)果圖

Fig.10 Experimental results of DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS and LMEA on DTLZ3 and WFG3 (Continued)圖10 DS-NSGA-II,MOEAD_PBI,NSGA-III,Hype,MSOPS,LMEA 在DTLZ3 和WFG3 上的實驗結(jié)果圖(續(xù))

從圖中我們可以看出,NSGA-III 和Hype 在DTLZ3 問題上都不能很好地收斂;DS-NSGA-II,MOEAD-PBI,MSOPS,LMEA 都可以收斂;DS-NSGA-II,LMEA 的分布性較優(yōu).

WFG3 是一個退化問題,從圖中我們可以看出,Hype 收斂于一點;其他算法甚至都不能收斂;DS-NSGA-II 與LMEA 不僅能很好地收斂到PF 上,而且分布性也較好.

總體而言,從實驗結(jié)果看,引入DS 策略的算法較之原算法對于連續(xù)高維多目標優(yōu)化問題在性能上有了明顯的提高.與當下比較流行經(jīng)典的一些其他算法相比較,雖然DS-NSGA-II 并不是在高維所有測試的問題上都優(yōu)于其他方法,但在絕大多數(shù)問題上優(yōu)于其他算法或性能接近.總之,由于DS 策略的引入,使得DS-NSGA-II 與當下較流行的高維多目進化算法相比有了較強的競爭力.

4 總結(jié)與展望

本文提出一種基于決策空間的定向搜索策略,通過對優(yōu)化問題的采樣分析,得出決策空間的收斂性控制向量和分布性控制向量,再通過一個或少數(shù)幾個解,確定收斂性子空間和分布性子空間,一改之前算法同時保持收斂性和分布性的機制,將算法搜索過程分為收斂性搜索階段和分布性搜索階段,分別對應(yīng)收斂性子空間和分布性子空間進行搜索優(yōu)化.在收斂性搜索階段,側(cè)重于種群的收斂性,使少數(shù)幾個解可以快速收斂至真實PF 附近;在分布性搜索階段,側(cè)重于種群的分布性,利用原算法的分布性保持機制,使種群較均勻廣泛地覆蓋整個PF,同時也會對算法的收斂性進行微小的優(yōu)化.

本文具有以下創(chuàng)新性和優(yōu)點.

(1)根據(jù)連續(xù)多目標優(yōu)化問題的特性,對多目標優(yōu)化提供了新的視角:對種群的收斂性和分布性進行分階段側(cè)重優(yōu)化.這樣可以很大程度弱化高維多目標問題優(yōu)化時收斂性和分布性之間的沖突;

(2)提出在種群中個體間的比較是:同分布性個體之間比較收斂性,或同收斂性個體之間比較分布性.這樣可以在高維多目標問題優(yōu)化環(huán)境選擇時,增加個體的選擇壓力;

(3)根據(jù)對優(yōu)化問題的采樣分析,在算法優(yōu)化過程中對子代個體的生成有一個宏觀的影響,使得搜索的目的性更強.對于高維多目標優(yōu)化問題搜索能力不足的問題,有目的性地搜索集中了計算資源,避免了在不必要區(qū)域進行搜索導(dǎo)致的計算資源浪費.

同時,DS 策略也面臨一些問題,如:針對優(yōu)化問題的采樣分析和子空間確定的準確性,很大程度會影響算法的效率和準確性,采用什么樣的數(shù)學(xué)方法進行采樣分析,以及是否在搜索過程中對問題進行多次有針對性的采樣分析;對于復(fù)雜PS 問題的優(yōu)化,如何準確地確定子空間,以及確定后如何高效恰當?shù)卦谧涌臻g中生成解等.

這些問題都需要花費時間和精力進一步研究,這也是本人下一步的研究內(nèi)容.