決策空間定向搜索的高維多目標優化策略*

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

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

2(智能信息處理與應用湖南省重點實驗室(衡陽師范學院),湖南 衡陽 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

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

現有的MOEA 在求解多目標優化問題時有兩個關鍵的部分,一是如何生成解,二是如何保留解.

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

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

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

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

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

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

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

本文的主要貢獻如下:

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

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

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

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

1 動機及相關定義給出

1.1 連續多目標優化問題的特性

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

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

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

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

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

1.2 計算資源分配

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

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

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

1.3 收斂性與分布性

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

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

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

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

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

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

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

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

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

以圖3、圖4 為例,將圖4 中的個體與圖3 中的個體相對應,圖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的定義區間;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的定義區間.

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

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

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

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

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

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

2.1 基本思想

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

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

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

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

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

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

2.2 算法流程

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

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

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

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

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

2.3 問題采樣分析

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

算法1.優化問題采樣分析.

輸入:決策變量維數n,優化問題,對每一維決策變量采樣次數J;

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

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

2.4 子空間映射

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

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

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

輸出:種群Q.

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

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

2.5 算法時間復雜分析

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

3 實驗分析

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

3.1 實驗參數設置

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

Table 1 Terminate conditions表1 結束條件

在DS 策略中,兩個搜索階段間的轉換有一個條件,這里同樣把評價次數作為轉換的條件.將轉換搜索階段的評價次數設置為SUM×r,r為一個比值,取值范圍[0,1].當已評價的次數大于SUM*r時,將收斂性搜索階段轉變為分布性搜索階段.

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

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

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

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

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

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

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

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

3.2 評價指標

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

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

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

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

3.3 實驗結果分析

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

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

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

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

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 測試問題上的實驗結果

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

2)與其他算法比較

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

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 問題上的實驗結果圖

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 問題上的實驗結果圖

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 系列測試問題上的實驗結果

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 系列測試問題上的實驗結果

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 系列測試問題上的實驗結果(續)

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

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

圖10 是6 個算法在15 維的DTLZ3 和WFG3 的實驗結果圖(左列為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 上的實驗結果圖

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 上的實驗結果圖(續)

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

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

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

4 總結與展望

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

本文具有以下創新性和優點.

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

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

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

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

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