基于區域失衡子空間的領先NSGAII算法

甘翔宇， 周新志， 楊秀清， 向 勇， 葉 毅

(四川大學電子信息學院， 成都 610065)

1 引 言

現實生活中的很多工程和科學問題，在決策過程中都涉及到多目標優化問題(Multi objective Optimization Problem, MOP)，例如多機器人任務分配(Multi Robot Task Allocation, MRTA)問題[1]、資源受限的項目調度優化問題(Resource Constrained Project Scheduling Optimization Problem,RCPSP)、基于多目標路徑規劃的資源配置問題等. 在這些問題中，目標函數之間經常是沖突的、相互制約的. 傳統多目標優化問題求解方法有加權法[2]、約束法和目標規劃法等，這些方法的基本思想大多是把多目標問題中的子目標函數，經過處理轉換為單目標問題，通過對單目標問題求解達到對多目標函數的求解. 而現實中MOP的目標函數、約束函數大多是非線性、不連續的，傳統的優化方法效率低，因此對有效的進化優化算法的研究是十分必要的.

在眾多多目標優化算法中，Deb在2002年提出的NSGAII算法[3]是影響最大和應用范圍最廣的，該算法具有較低的計算復雜性且在相同時間內能獲得較優的求解性能. 但NSGAII算法作為一種類隨機搜索算法，存在收斂速度慢和解分布特性差的問題. 針對NSGAII算法收斂性不足的缺陷，陳輔斌等[4]引入了免疫平衡原理，改進NSGAII算法的選擇策略和精英保留策略，避免了局部收斂問題. Mithilesh等[5]將涉及最佳染色體組的初始隨機種群的改進庫納入多目標優化算法的框架，以最小的世代數提高了收斂到全局Pareto最優前沿的速度. Ahmadi等[6]研究了MAP在NSGAII算法中的集成，實現了收斂性的提高. 為解決NSGAII擁擠度距離機制無法有效區分多樣性個體的缺陷，崔志華等[7]提出了基于平均距離聚類的NSGAII. 文獻[8,9]將動態擁擠距離(DCD)和受控精英(CE)引入NSGAII，提出的算法在維持多樣性方面表現優于NSGAII. 王明昭等[10]基于均勻聚集區間和基尼權重構造了一種均勻聚集距離算子，使所求解集更好、更均勻地收斂于Pareto最優邊界. 為進一步提升算法的性能，還有許多研究者嘗試把局部搜索思想融入到NSGAII算法中. Lara等[11]提出一種用于多目標模因算法的新的局部搜索策略. Harada等[12]提出將梯度信息用于局部搜索過程，根據梯度信息找到向Pareto最優前沿收斂的方向，從而提高收斂速度和精度.

基于收斂性和多樣性這兩個多目標優化問題中的關鍵性能指標，本文提出一種基于區域失衡子空間的領先NSGAII算法(Leading NSGAII Algorithm based on Regional Unbalanced Subspace)，實現種群快速接近Pareto前沿并有良好分布性. 種群進化前期優先在領先解個體周圍搜索，可避免隨機搜索過程計算量大的問題，提高算法運行效率，使種群快速收斂；由于迭代過程中種群分布不均會導致多樣性變差，容易陷入局部最優，因此該算法提出區域失衡子空間概念，通過均勻劃分目標空間，改善失衡區域來減少局部搜索計算量，提高解的質量，使解的分布更符合真實前沿的形狀. 最后通過基準多目標優化實驗驗證算法的有效性.

2 基本定義

本文主要針對多目標優化問題，其中相關定義解釋如下.

定義1多目標優化問題MOP. 具有n個決策變量，m個目標函數的多目標優化問題通常可以描述為

minimizeF(x)={f1(x),f2(x),...,fm(x)}，

x=(x1,x2,...,xn)T∈D?Rn，

li≤xi≤ui,i=1,2,...,n

(1)

式中，x表示n維決策變量；F(x)?Rm為m維目標向量；D?Rn表示n維決策空間；fj(x)(j=1,2,...,m)為第j個目標函數；li和ui分別為第i個決策變量xi的下界和上界. 在不失一般性的前提下，假設f1(x),...,fm(x)將被最小化，因為最大化問題也可通過對偶原理轉化為最小化問題.

定義2Pareto支配. 對于任意決策向量，若滿足以下條件.

(2)

則稱xu支配xυ，或稱xu相較于xυ占優，記xuxυ.

定義3Pareto最優解. 多目標優化問題中優先考慮的一組折中解決方案，無法比較各個目標函數的優劣性，即不能保證在改進一個目標函數的同時不削弱至少一個其他的目標函數，即Pareto最優解.

定義4Pareto最優解集. 決策空間中Pareto最優解的集合構成了Pareto最優解集(PS).

PS={xu∈D|?xυ∈D,xυxu}

(3)

定義5Pareto最優前沿. Pareto最優解集對應于目標空間中的像集稱為Pareto最優前沿(PF).

PF={F(Xu)=f1(xu),...,fm(xu)|xu∈PS}

(4)

3 NSGAII-URS算法

NSGAII是一種帶有精英保留策略的快速非支配多目標優化算法. 該算法降低了非劣排序遺傳算法的復雜性，但NSGAII算法仍然存在搜索隨機性偏大、收斂速度慢和解分布均勻性較差的問題. 因此本文提出在NSGAII算法基礎上，在種群進化前期，根據解的優劣性求得當前非支配解中的領先解，并加入到領先解解集，通過在領先解周圍局部搜索來加快算法收斂速度. 同時為了避免算法陷入局部最優，本文提出將目標空間均勻劃分為一系列子空間，結合基于稀疏度的局部搜索策略來分別優化不同的失衡區域，從而改善種群分布不均現象. 下面對NSGAII-URS算法其中涉及的優化方法和策略進行詳細的描述.

3.1 算法框架

算法1描述了NSGAII-URS算法的主要框架，首先,初始化種群PI，種群數量為N，從中選擇優秀個體進入交配池;然后,采用模擬二進制交叉和多樣式變異產生子代PM; 再通過對領先解進行局部搜索得到領先局部解PL，再對失衡子空間進行優化獲得失衡局部解PB，將領先局部解和失衡局部解統稱為局部解PN，將子代和父代以及局部解合并得到新父代PO;最后,通過環境選擇機制從新父代中選擇最優N個個體進入下一代，重復以上步驟直到滿足終止條件.

在NSGAII-URS算法中最大進化代數的2/3被作為種群進化中使用兩種不同策略的分割點.這是因為整個進化過程共分為進化前期、中期和后期三段，每一個進化段長度為1/3總迭代數. 由于對領先解集進行局部搜索操作偏向于強調解的收斂性，容易忽略多樣性和分布均勻性，而且種群進化到后期收斂性已經基本得到優化，因此本算法在后期將不再對領先解集進行處理.

3.2 領先解集

NSAGII算法通過個體之間的支配關系對種群中的個體進行排序，下一代種群選擇時，先從最高級別的非支配解(FrontNo=1)中進行選擇，以此加快算法的快速收斂. 由于非支配解也會存在明顯Pareto前沿傾向的個體，因此本文在文獻[13]提出的超平面輔助思想的基礎上，定義了當前非支配解中的領先解集.該集合中的領先個體將作為每輪迭代過程中的重點搜索對象，引導種群更快收斂至Pareto真實前沿.

超平面輔助思想是用個體周圍的相鄰解構成的超平面，在非支配解中區分出對Pareto最優前沿有明顯傾向的個體. 對于具有m個目標的個體,其相鄰解決方案集定義為B(xi)={xi1,xi2,...,xim}，當fm(xi)

算法1 Framework of NSGAII-URS

InputN(種群規模),IMAX(最大進化代數)

OutputPOMAX(最終種群)

1) Initialize the populationPwithNrandom

individuals

2) while NotTerminate(Population) do

3) MatingPool= T-Select(PI)

4)PM=GA(Population(MatingPool))

5) ifi<(2/3)*evaluationthen

6)PN= LocalSelection1(PI(F=1))

7)PO=PI+PM+PN

8)PO+1= E-Select1(PO)

9)O= O+ 1

10) else

11)PU= LocalSelection2(PI(F=1))

12)PO=PI+PM+PU

13)PO+1= E-Select2(PO)

14)O=O+ 1

15) end

16) end

17) returnPO+1

3.3 區域失衡

雖然對領先解的操作可促進種群收斂，但只關注領先解可能會導致種群陷入局部最優，還需重點優化解的分布均勻問題. 傳統NSGAII算法提出的擁擠距離和擁擠度比較算子不能有效保持種群多樣性，因此有研究者提出將局部搜索策略與NSGAII算法結合，但局部搜索過程會產生大量局部解，使計算量成倍增加. 因此，本文提出基于每輪迭代非支配解區域失衡概念，在每次遺傳過程中對目標空間中的不均勻解進行局部搜索，從而有效減少遺傳過程中的計算量，保持種群多樣性和均勻性.

圖1 領先解示意圖

3.3.1 失衡子空間 文獻[14]將當前非支配解中稀疏度最小的作為稀疏解，通過在稀疏解周圍搜索以減少局部搜索過程的計算量. 該思想的優點在于當解分布不均勻時，在稀疏解周圍局部搜索，當解分布均勻時，最邊緣的解稀疏度最小，從邊緣開始向外搜索，可以增加解集的廣泛性. 但在一次迭代過程中僅對一個稀疏解進行局部搜索操作并不能有效改善解的均勻性.因此本文將重點關注目標空間中的非支配解所在區域，在每次求解過程中將目標空間均勻分區，在各子空間中劃分當前非支配解，當存在失衡子空間時，采用不同的策略來改善局部子空間失衡情況.

失衡子空間的優化過程如算法2所示，首先使用一組單位向量將目標空間劃分為一系列子空間，如下所示.

U=(u1,...ui,...,uk)

(5)

V={v1,v2,...,vk}

(6)

H={H1,H2,...,Hk}

(7)

Hj=(ue,...,uw)

(8)

其中，U為每輪迭代非支配解的集合；k為非支配解的個體數量；V為一組單位向量，將作為參考向量來劃分失衡區域；H為均勻劃分的子空間；Hj為第j個子空間內所包含的個體，ue、uw∈U. 判斷失衡子空間的方法如下.對于每個非支配解ui，首先需要將其與各子空間關聯，計算其與各參考向量vi之間的夾角余弦距離，通過排序比較，得到與之最近的參考向量的序號，即分別劃分給不同的子空間，依靠劃分結果可以判斷失衡子空間. 如圖2所示，虛線所對應的參考向量將目標空間均勻劃分，以此為基準可將這片區域抽象為子空間集{Hr1,…,Hr10}，如圖2箭頭所示，根據計算結果，每個解都求得與之對應的參考向量，即分別與子空間建立了聯絡. 通過區域劃分確定了失衡子空間，分為以下兩種情況.

情況1某些子空間可能沒有解，例如Hr2、Hr6，定義該類空間為空閑子空間.

情況2某些子空間可能有多個解，例如陰影區域所示的Hr3和Hr8. 其余子空間相較于Hr3和Hr8具有更少的解，定義該類空間為稀疏子空間.

根據以上劃分，判斷本次遺傳過程中種群分布并不均勻，子空間存在失衡現象. 根據子空間的狀況分別采取不同的處理方法. 對于稀疏子空間，可以在下一輪迭代中對該空間內的個體進行局部搜索；對于空閑子空間，可以分別選取離該區最近的個體通過極限變異策略得到非均勻解. 局部搜索策略將在下節中進行詳細的描述.

算法2 LocalSelect1

InputPI(F=1),I(進化代數)

OutputPN(局部解)

1) Initialize a set of unit vectorsV={v1,…,vk}

2) Normalize the current non-dominated solutionPI(FN=1), denote the normalized matrix as Objs

Objs=(Objs-Zmin)/(Zmax-Zmin)

3) Ang=ACDis(Objs,V)

4)nn=unique(min(Ang))

5)l1=[1:len(PI(F=1))]

6) fori=1 len(nn) do

7) mm=(l1-nn(i))==0

8)l1(mm)=[]

9) end

10)l2=l1calculate the subspace that’s not allocated to the individual

11) fori=1-length(l2) do

12) execute extreme optimization mutation strategy

13) end

14) returnPN

圖2 失衡區域示意圖

3.3.2 基于稀疏度的局部搜索策略

(1) 稀疏子空間.對于該類子空間,選取該區域內稀疏度最大的個體，通過在該個體周圍局部搜索來增強該區域的多樣性.其中稀疏度的計算公式如下.

設第i個解的目標向量為(f1(Xi),…,fm(Xi))，對函數值進行歸一化處理.

(9)

其中，fjmax和fjmin分別是當前所有解對應的第j個目標函數值得最大和最小值. 歸一化后第i個解Xi的稀疏度計算公式為

(10)

其中，ni為目標空間中與目標向量F(Xi)歐氏距離小于r的其他目標向量的個數；r的取值范圍為0

(2) 空閑子空間.由于本次迭代中該區域內未分配到個體，因此對距離該區域最近的兩個個體采用極限優化變異策略[15]. 該方法在產生局部解時，每個局部解變動選中解的一個決策變量. 極限優化策略的公式為

(11)

(12)

(13)

βmax(xi)=max[xi-li,ui-xi],0

(14)

其中，xi為決策變量；h為0～1之間的隨機數；q為正實數，稱為形狀參數，根據文獻[15]將q設為11；βmax(xi)為當前決策變量xi可變動的最大值. 由于極限優化變異方法每次只改變一個決策變量，搜索范圍較小. 因此對兩個個體中的稀疏度較大的個體采用第2種變異策略[16]，擴大搜索范圍，該策略的計算公式如下.設當前稀疏解為x=(x1,x2,...,xn)，n為決策變量個數，若種群總數為N，設置產生局部解個數為0.2N.

(15)

k=1,2,...,[0.2N]

(16)

(17)

4 實驗仿真

4.1 實驗環境和參數設置

為進一步驗證NSGAII-URS的性能，選取NSGAII-DLS、GrEA[17]、MOEADD[18]、HypE[19]、RVEA[20]等5個典型的多目標優化算法進行對比實驗. 其中NSGAII-DLS是一種基于密度的局部搜索NSGAII算法，GrEA引入網格排序、網格擁擠度和網格坐標距離等機制，以此來維持解的均勻性.MOEADD是一種基于支配和分解的進化多目標優化算法，HypE是一種用于多目標優化的超量估計算法，RVEA是一種用于多目標優化的參考矢量制導進化算法. 對于每個算法，都設置相同的種群規模和存檔大小，重組、變異、采樣等運算符都保持相同. 在同一個運行環境、相同參數設置下將不同的算法運行多次獲得最終結果.

實驗環境為Intel(R)Core(TM)i7-8550U CPU，內存8 GB，Windows 10操作系統，MatlabR2016b版本. 實驗操作平臺為通用的基于Matlab的多目標優化工具PlatEMO[21]，版本v2.8.

4.2 實驗結果與分析

由于雙目標ZDT系列函數和三目標DTLZ系列函數被廣泛地用于驗證多目標優化算法，本實驗分別采用 (ZDT1～ZDT4，ZDT6) 函數和(DTLZ4～DTLZ7) 函數來驗證算法的性能.函數的特征、維度和種群規模如表1和表2所示.

表1 ZDT基準測試函數的特征、維度、種群模式

表2 DTLZ基準測試函數的特征、維度、種群模式

圖3和圖4分別是NSGAII-URS在ZDT系列和DTLZ系列函數上的優化效果圖，可以看出對于凹、凸和非連續的多目標函數，該算法都能很好地逼近Pareto前端且分布比較均勻. 其中，對于ZDT系列的雙目標問題和DTLZ系列中的真實Pareto連續問題取得了相對顯著的優化效果，對于DTLZ系列中的多峰且非連續問題也達到了良好的快速收斂和均勻分布效果.

在實驗對比部分，函數調用次數均為10 000次、指標結果分別是算法獨立運行30次得到的平均值和標準差，表格中加粗部分為同一測試函數中獲得的最優值. 在結果比較中，采用了Wilcoxon秩和檢驗比較算法性能差異性，置信度為95%，其中“+”、“-”、“=”分別表示顯著優、顯著劣、無差異于NSGAII-URS算法.

(a)

(b)

(c)

(d)

(e)

為了比較不同算法性能，采用以下兩個廣泛使用的綜合性能評價指標對算法進行驗證.

(1) 反世代距離(IGD).IGD通過度量真實Pareto前沿和算法所獲得的Pareto前沿之間的接近程度來評價算法的收斂性和多樣性，IGD的定義如下.

(18)

表3是6個算法分別在ZDT系列測試函數上關于IGD指標的運行結果，可見 NSGAII-URS算法得到的IGD值的平均值和標準差均小于對比算法，且平均IGD值比對比算法的結果都要小1到2個數量級. 表4是在DTLZ系列測試函數上關于IGD指標的運行結果，可見本文算法在DTLZ6、DTLZ7上得到的IGD值是優異于其他5種算法的，在DTLZ4和DTLZ5上略差于NSGAII-DLS,但總體上還是比另外4種算法運行效果好.

(a) DTLZ4優化效果

(b) DTLZ5優化效果

(c) DTLZ6優化效果

(d) DTLZ7優化效果

表3 ZDT系列測試函數上IGD的平均值和標準差

(2) 超體積(HV).HV衡量算法所獲得的Pareto最優解集在目標空間所覆蓋的范圍大小，該指標可以同時衡量收斂性和多樣性，計算公式如下.

(19)

式中，PFt是t時刻算法所獲得的Pareto前沿，是由參考點和個體形成的超體積. HV越大說明算法所得到的 Pareto前沿收斂性越好，分布越均勻.

表5是6個算法分別在ZDT系列測試函數上關于HV指標的運行結果，可見 NSGAII-URS算法在ZDT1～ZDT2、ZDT4、ZDT6上得到的HV值的平均值和標準差均小于對比算法，在ZDT3上略差于算法HypE，但相較于另外4種算法還是有明顯優勢的. 表6是在DTLZ系列測試函數上關于HV指標的運行結果，可見在DTLZ6～DTLZ7上本文算法得到的IGD值都是具有優勢的，在DTLZ4上略差于算法MOEADD，在DTLZ5上略差于算法NSGAII-DLS，在后續的工作中可就這些問題進行更深入的研究.

由以上實驗和分析可以得出，在實驗指標設置相同的情況下，針對雙目標和三目標優化問題，本文提出的NSGAII-URS算法可以獲得更明顯的優化效果.

表4 DTLZ系列測試函數上IGD的平均值和標準差

表5 ZDT系列測試函數上HV的平均值和標準差

表6 DTLZ系列測試函數上IGD的平均值和標準差

在多目標優化問題中，進化算法的環境選擇上，在收斂性和均勻性中形成合理的平衡是一項艱巨的任務. NSGAII-URS算法在尋找最優解時，以NSGAII為搜索引擎，以領先解解集中的個體為基礎進行局部搜索，為下一代優選解，增強了種群向Pareto最優前沿的選擇壓力.由于均勻性也是考核算法優越性的重要標準之一，本文提出在每次遺傳過程中面向非支配解劃分區域、定位失衡子空間，調整獲得的Pareto前沿，使其在保持快速收斂的同時也具有良好分布性. 綜合分析本文提出的算法與其他多目標算法在ZDT和DTLZ系列基準測試函數上的結果，顯示NSGAII-URS在保持收斂和分布均勻之間的良好平衡方面是有效且具有競爭力的.