基于區(qū)域失衡子空間的領(lǐng)先NSGAII算法

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

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

1 引 言

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

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

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

2 基本定義

本文主要針對多目標(biāo)優(yōu)化問題，其中相關(guān)定義解釋如下.

定義1多目標(biāo)優(yōu)化問題MOP. 具有n個決策變量，m個目標(biāo)函數(shù)的多目標(biāo)優(yōu)化問題通?？梢悦枋鰹?/p>

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維目標(biāo)向量；D?Rn表示n維決策空間；fj(x)(j=1,2,...,m)為第j個目標(biāo)函數(shù)；li和ui分別為第i個決策變量xi的下界和上界. 在不失一般性的前提下，假設(shè)f1(x),...,fm(x)將被最小化，因為最大化問題也可通過對偶原理轉(zhuǎn)化為最小化問題.

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

(2)

則稱xu支配xυ，或稱xu相較于xυ占優(yōu)，記xuxυ.

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

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

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

(3)

定義5Pareto最優(yōu)前沿. Pareto最優(yōu)解集對應(yīng)于目標(biāo)空間中的像集稱為Pareto最優(yōu)前沿(PF).

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

(4)

3 NSGAII-URS算法

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

3.1 算法框架

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

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

3.2 領(lǐng)先解集

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

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

算法1 Framework of NSGAII-URS

InputN(種群規(guī)模),IMAX(最大進(jìn)化代數(shù))

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 區(qū)域失衡

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

圖1 領(lǐng)先解示意圖

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

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

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

(5)

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

(6)

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

(7)

Hj=(ue,...,uw)

(8)

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

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

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

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

算法2 LocalSelect1

InputPI(F=1),I(進(jìn)化代數(shù))

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 失衡區(qū)域示意圖

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

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

設(shè)第i個解的目標(biāo)向量為(f1(Xi),…,fm(Xi))，對函數(shù)值進(jìn)行歸一化處理.

(9)

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

(10)

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

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

(11)

(12)

(13)

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

(14)

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

(15)

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

(16)

(17)

4 實驗仿真

4.1 實驗環(huán)境和參數(shù)設(shè)置

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

實驗環(huán)境為Intel(R)Core(TM)i7-8550U CPU，內(nèi)存8 GB，Windows 10操作系統(tǒng)，MatlabR2016b版本. 實驗操作平臺為通用的基于Matlab的多目標(biāo)優(yōu)化工具PlatEMO[21]，版本v2.8.

4.2 實驗結(jié)果與分析

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

表1 ZDT基準(zhǔn)測試函數(shù)的特征、維度、種群模式

表2 DTLZ基準(zhǔn)測試函數(shù)的特征、維度、種群模式

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

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

(a)

(b)

(c)

(d)

(e)

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

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

(18)

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

(a) DTLZ4優(yōu)化效果

(b) DTLZ5優(yōu)化效果

(c) DTLZ6優(yōu)化效果

(d) DTLZ7優(yōu)化效果

表3 ZDT系列測試函數(shù)上IGD的平均值和標(biāo)準(zhǔn)差

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

(19)

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

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

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

表4 DTLZ系列測試函數(shù)上IGD的平均值和標(biāo)準(zhǔn)差

表5 ZDT系列測試函數(shù)上HV的平均值和標(biāo)準(zhǔn)差

表6 DTLZ系列測試函數(shù)上IGD的平均值和標(biāo)準(zhǔn)差

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