時振濤,常晨芳,李曉波,王 浩

(1.太原科技大學計算機科學與技術學院,太原 030024;2.太原科技大學電子信息工程學院,太原 030024)

多目標優(yōu)化問題[1]在工程和科學領域中廣泛存在,例如:車輛調度問題[2],森林規(guī)劃問題[3]等。其數(shù)學表達式如公式(1)所示:

(1)

其中,M為目標函數(shù)的個數(shù),Ωn為n維決策空間且X?Ωn,x=(x1,x2,…,xn)為n維決策向量,f1(x),f2(x),…fM(x)構成目標空間。在多目標優(yōu)化問題中,由于多個優(yōu)化目標彼此沖突,即某目標性能的提高可能引起其他目標性能的降低,所以在求解多目標優(yōu)化問題中往往需要獲得的是一組解,稱為帕累托最優(yōu)解[4,5](Pareto set,簡稱PS),該組解相應的在目標空間的解集稱為帕累托最優(yōu)面(Pareto optimal front,簡稱PF).由于進化算法單次運行可以得到一組解,所以其被廣泛用于解決多目標優(yōu)化問題,稱為進化多目標優(yōu)化(Evolutionary multi-objective optimization,簡稱EMO).

到目前為止,進化多目標優(yōu)化算法根據(jù)使用的環(huán)境選擇的策略不同可以分為四類:第一類是基于支配關系的方法,如NSGAII[6];第二類是基于分解的方法,如MOEAD[7],RVEA[8],MaOEA-ARV[9]等;第三類是基于指標的方法,如IBEA[10],HyPE[11],MaOE-CSS[12],NSPI-EMO[13],還有其它方法,如采用支配和分解相結合的方法MOEADD[14]和NSGA-III[15].目前求解大規(guī)模高維多目標優(yōu)化算法大致分為三類:第一類是基于決策變量分析。在MOEA/DVA[16]中,Ma和liu 等人將決策變量分成多樣性相關和收斂性相關兩類,然后采用不同的優(yōu)化方法對兩類子問題分別優(yōu)化;同樣,Zhang等人在LMEA[17]中提出采用聚類的方法將決策變量分為兩類,然后分別采用收斂性和多樣性兩種不同的策略對收斂性相關變量和多樣性相關變量進行優(yōu)化。但是基于決策變量分析的方法的缺點在于當決策變量維度增大的時候,計算量會增大。第二類是基于分解的策略并利用協(xié)同進化框架(Cooperative Co-evolution,簡稱 CC)來提高種群的搜索效率。在CCGDE3[18]中,Antonio和Coello將決策空間分組,對每個子問題分別進行優(yōu)化。在該類方法中,分組的策略對優(yōu)化的結果有很大的影響,常見的分組方式有:隨機分組、線性分組、有序分組和差分分組。但是它的缺點在于在不知道決策變量的相互作用和組的大小的時候,CC的算法效果依賴于選擇什么樣的分組策略。第三類是基于問題轉化,在WOF[19]中,Zille等人將決策變量分成若干組,每個組都對應一個權重向量。借助權重向量把決策空間維度較大的多目標優(yōu)化問題轉換為決策空間維度較小的多目標優(yōu)化問題,還有最近新提出的方法 LSMOF[20],與WOF不同,LSMOF采用雙向權重向量,加快了種群收斂速度。但是此類型方法缺點是不考慮不同權重變量之間的差異,影響種群收斂速度。

種群的多樣性和搜索的收斂能力在種群的搜索過程中起著十分重要的作用,本文提出一種兩層優(yōu)化輔助的大規(guī)模高維多目標優(yōu)化算法(TOS-assisted LSMOEA).在第一層優(yōu)化中,主要通過增加種群多樣性提高算法的探索能力,因此選用具有良好探索能力的社會學習微粒群算法(SL-PSO)[21]算法進化種群,并且通過非支配解集保存種群進化過程中產(chǎn)生的非支配解。隨后,在第二層優(yōu)化策略中,根據(jù)參考向量選擇若干非支配解進行遺傳操作以提高算法的開采能力,以獲得較好的非支配解集。

1 相關概念

1.1 社會學習微粒群算法(SL-PSO)

SL-PSO是針對于大規(guī)模單目標優(yōu)化問題提出的一種改進微粒群算法。與其他單目標微粒群優(yōu)化算法相比,由于它采用隨機選擇較好個體的對應維度學習,而并非最好個體,增強了算法的多樣性,提高了算法的全局搜索能力,因而在解決大規(guī)模優(yōu)化問題上獲得了較好的結果。在SL-PSO中,每個個體的學習如式(2)所示:

Xi,j(t+1)=

(2)

式(2)表示如果個體i在第t代的學習概率pi(t)小于給定的學習概率,則個體i進行學習,否則不變。Δxi,j(t+1)的更新如式(3)所示:

ΔXi,j(t+1)=r1(t)·ΔXi,j(t)+

r2(t)·Ii,j(t)+r3(t)·Ci,j(t)

(3)

式中:ΔXi,j(t+1)由三部分組成,第一部分中ΔXi,j(t)表示個體i在t代第j維的速度;第二部分中Ii,j(t)表示個體i的第j維向比個體i適應值好的任意個體k的第j維學習;第三部分中Ci,j(t)表示個體i向所有個體第j維的均值學習,r1(t),r2(t),r3(t),為3個隨機數(shù)。Ii,j(t)和Ci,j(t)具體式(4)所示:

(4)

1.2 遺傳算法

遺傳算法(genetic algorithm,GA)是一種模擬自然界生物的物競天擇,適者生存和通過染色體產(chǎn)生子代的智能算法。該算法通過群體搜索技術和種群之間反復迭代逐步尋優(yōu)到全局最優(yōu)解,其中在產(chǎn)生子代時算法的交叉和變異算子起著十分重要作用,本文采用模擬二進制交叉策略和多項式變異策略來產(chǎn)生子代種群。

1.2.1 模擬二進制交叉

(5)

式(5)中,β是由分布因子η按照公式動態(tài)隨機決定,如式(6)所示:

(6)

1.2.2 多項式變異

(1)選擇隨機數(shù)ui∈[0,1);

(2)計算βi的值:

(7)

其中,ηu為實驗中設置的非負實數(shù)。

(3)計算子代:

(8)

1.3 支配關系

假設給定兩個個體x,y,如果同時滿足式(9),則稱x支配y,記為xy

?i∈(1,2,…,M)∶Fi(x)≤Fi(y)∧

?i∈(1,2,…,M)∶Fi(x)

(9)

式中:Fi(x)為個體x的第i個目標函數(shù)值,M為目標函數(shù)的個數(shù)且i∈(1,2,…,M).

2 兩層優(yōu)化策略的優(yōu)化算法(TOS-assisted LSMOEA)

算法的流程:

輸入:種群數(shù)量N,初始種群P,最大評價次數(shù)Fitmax;輸出:非支配解集A

(1)在決策空間中隨機取N個點,構成初始種群P;

(2)把初始種群中的非支配解保存于集合A中;

(3)使用SL-PSO更新個體位置的方法產(chǎn)生新的種群,并計算目標函數(shù)值。(詳見2.1節(jié));

(4)更新非支配解集A;

(5)從A中選擇若干個體進行遺傳操作,并計算目標函數(shù)值。(詳見2.2節(jié));

(6)更新非支配解集A;

(7)若未達到最大評價次數(shù),則返回3,否則,進入下一步;

(8)優(yōu)化結束,輸出集合A中的解。

2.1 第一層優(yōu)化策略

采用基于個體適應值差值[23]作為單一指標用于對個體進行排序,其計算方法如下:

(10)

式中,fp(i)表示個體p在第i個目標上的目標函數(shù)值。M表示待優(yōu)化問題目標個數(shù)。

然后利用SL-PSO的位置更新方式對個體進行位置更新。即每個個體的每一維度隨機選擇一個種群中比自己優(yōu)秀的個體進行學習,同時由于非支配解集A中保存著進化過程中產(chǎn)生的優(yōu)秀個體,因此種群中的個體還有一定的概率r(r=0.1)向集合A中的個體學習。為了避免種群陷入局部最優(yōu),所以種群中的個體不再向每一維度的均值學習。

在第一層優(yōu)化中,個體的速度學習如式(11),其中r1,r2為0～1之間的隨機數(shù),t表示代數(shù),Xi,j(t)表示個體i的第j維在第t代的值。k(i

vi,j(t+1)=(0.5*r1+0.1)*

vi,j(t)+r2*(Xk,j(t)-Xi,j(t))

(11)

Xi,j(t+1)=Xi,j(t)+vi,j(t+1)

(12)

2.2 第二層優(yōu)化策略

第二層優(yōu)化中主要考慮提高算法的收斂能力,主要分為兩步。

(1)選擇父代種群:當非支配解集A中的解的個數(shù)小于等于N時,A中的解全部作為父代種群。當非支配解集A中的解的個數(shù)大于N時,在目標空間生成均勻分布的N個參考向量,依據(jù)式(13)計算個體和參考向量之間角度:

(13)

其中λj表示參考向量,f(Xi)表示個體i的目標向量,θxi,λj表示個體i的目標向量和參考向量j之間的角度。每個參考向量選擇和自己目標向量角度最小的解,并把所有選出來的解作為父代種群。由于該部分種群是由非支配解集中的解組成,因此具有較好的收斂性。

(2)通過GA產(chǎn)生子代種群:當選出父代種群之后,該種群將通過遺傳算法產(chǎn)生子代種群,對其進行目標函數(shù)評價,并更新非支配解集。

3 實驗

為了驗證本文算法的有效性,本文選擇被廣泛采用的MaF[24]函數(shù)測試集上進行測試,MaF的決策空間維度為500,分別在3,5,8,10個目標上進行了測試。

3.1 實驗設置

為了說明本文提出算法的有效性,選NMPSO[25],MPSOD[26],RVEA[8],MaOEACSS[12]4個算法作為對比算法。最大評價次數(shù)為10 000.種群規(guī)模大小的設置見表1,其他參數(shù)設置見表2.其中w為權重系數(shù),c1,c2為學習公式系數(shù),pc,pm,ηc,ηm分別為交叉概率,變異概率,交叉分布指數(shù),變異分布指數(shù),CR為交叉率,F為差分進化算法中的收縮因子。

表1 TOS-assisted LSMOEA種群規(guī)模設置

表2 算法相關參數(shù)設置

本文實驗中的所有算法在每個測試函數(shù)上均獨立運行 20 次,IGD 的統(tǒng)計結果如表3,表4.其中最優(yōu)結果值用加粗字體表示。采用顯著水平為0.05的Wilcoxon 秩和檢驗,從統(tǒng)計學角度比較了算法之間差異的顯著性,表中“+”“-”和“≈”分別表示其他對比算法明顯優(yōu)于、明顯劣于和近似于本文提出的算法。

表3 500維MaF1不同策略對比分析

表4 TOS-assisted LSMOEA與MPSOD,NMPSO,RVEA,MaOEACSS在 500維MaF 函數(shù)上IGD 值比較結果

3.2 算法性能度量指標

本文選取反向世代距離[27](Inverted Generational Distance,IGD)作為性能度量指標來評價解集的收斂性和多樣性。P*為真實的PF面產(chǎn)生的解的集合,S為EMO產(chǎn)生的解的集合,S中IGD如式(14)所示:

(14)

式中,dist(X*,S)為P*中的點X*和鄰域S之間的歐氏距離。IGD越小表示S中的解越接近真實的PF面,解集S的質量越好。

3.3 算法參數(shù)及策略分析

為了提高算法搜索效率,本文中種群有一定的概率向非支配解集A中的個體學習。分別測試了當r為0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9時算法在MaF1測試函數(shù)500維時的表現(xiàn),實驗結果如圖1所示。可以看出,當r取0.1時算法在各個目標上的表現(xiàn)是最好的,因此本文r取0.1.

圖1 500維MaF1 參數(shù)r對比分析

本文采用兩層單獨優(yōu)化,說明提出的兩層優(yōu)化策略的有效性,策略1為算法僅進行第一層搜索,策略2為算法僅進行第二層搜索。在MaF1測試函數(shù)500維進行測試。

為了驗證提出的算法中第一層搜索可以改善非支配解集的多樣性,進行了對比實驗,如圖2所示。

圖2 MaF1和MaF6測試函數(shù)500維10個目標上指標分布圖

圖2展示了不同策略在MaF1以及MaF6測試函數(shù)500維10個目標上種群進化過程中非支配解集多樣性和收斂性指標的變化圖。為了便于觀察,在圖2中橫坐標上收斂性指標取了相反數(shù)。收斂性指標的計算如式(15):

(15)

多樣性指標的計算如式(16):

(16)

式中,dist(Xi,Xj)表示點Xi和點Xj之間的歐式距離。A為非支配解集。

多樣性指標值越大說明算法的多樣性越好,收斂性指標的值越小說明算法的收斂性越好。從圖2中可以看出,在收斂性相同的情況下,TOS-assisted LSMOEA算法的多樣性優(yōu)于TOS-assisted LSMOEA變種(即僅采用TOS-assisted LSMOEA算法中的第二層搜索)。因此,本算法中第一層搜索可以有效的提升算法的多樣性。

3.4 實驗結果及分析

表4展示了本文提出的算法和4種對比算法在MaF測試函數(shù)500維的IGD測試結果?？梢钥闯?本算法和其他4種對比,表現(xiàn)差,表現(xiàn)好和沒有顯著性差異的分別為12/37/3,12/36/4,13/36/3,14/34/4.可以發(fā)現(xiàn)本算法對于解決大規(guī)模高維多目標優(yōu)化問題是有效的。

4 總結

本文提出了一種兩層優(yōu)化策略用于求解大規(guī)模高維多目標優(yōu)化問題,在第一層優(yōu)化中,采用多樣性較好的SL-PSO位置更新方式引導種群進化,并用于更新非支配解集。隨后在第二層優(yōu)化中,依據(jù)個體和參考向量之間的角度選擇一部分個體組成父代種群,使用模擬二進制交叉和多項式變異策略產(chǎn)生子代種群以提高算法的開采能力,評價后的子代同樣用于更新非支配解集。MaF測試函數(shù)上的實驗結果表明本文提出的兩層優(yōu)化策略在解決大規(guī)模高維多目標優(yōu)化問題時是有效的。