兩層優(yōu)化輔助的大規(guī)模高維多目標(biāo)優(yōu)化算法

時(shí)振濤,常晨芳,李曉波,王 浩

(1.太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,太原 030024;2.太原科技大學(xué)電子信息工程學(xué)院,太原 030024)

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

(1)

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

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

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

1 相關(guān)概念

1.1 社會(huì)學(xué)習(xí)微粒群算法(SL-PSO)

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

Xi,j(t+1)=

(2)

式(2)表示如果個(gè)體i在第t代的學(xué)習(xí)概率pi(t)小于給定的學(xué)習(xí)概率,則個(gè)體i進(jìn)行學(xué)習(xí),否則不變。Δ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)表示個(gè)體i在t代第j維的速度;第二部分中Ii,j(t)表示個(gè)體i的第j維向比個(gè)體i適應(yīng)值好的任意個(gè)體k的第j維學(xué)習(xí);第三部分中Ci,j(t)表示個(gè)體i向所有個(gè)體第j維的均值學(xué)習(xí),r1(t),r2(t),r3(t),為3個(gè)隨機(jī)數(shù)。Ii,j(t)和Ci,j(t)具體式(4)所示:

(4)

1.2 遺傳算法

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

1.2.1 模擬二進(jìn)制交叉

(5)

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

(6)

1.2.2 多項(xiàng)式變異

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

(2)計(jì)算βi的值:

(7)

其中,ηu為實(shí)驗(yàn)中設(shè)置的非負(fù)實(shí)數(shù)。

(3)計(jì)算子代:

(8)

1.3 支配關(guān)系

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

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

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

(9)

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

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

算法的流程:

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

(1)在決策空間中隨機(jī)取N個(gè)點(diǎn),構(gòu)成初始種群P;

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

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

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

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

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

(7)若未達(dá)到最大評(píng)價(jià)次數(shù),則返回3,否則,進(jìn)入下一步;

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

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

采用基于個(gè)體適應(yīng)值差值[23]作為單一指標(biāo)用于對(duì)個(gè)體進(jìn)行排序,其計(jì)算方法如下:

(10)

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

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

在第一層優(yōu)化中,個(gè)體的速度學(xué)習(xí)如式(11),其中r1,r2為0～1之間的隨機(jī)數(shù),t表示代數(shù),Xi,j(t)表示個(gè)體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)選擇父代種群:當(dāng)非支配解集A中的解的個(gè)數(shù)小于等于N時(shí),A中的解全部作為父代種群。當(dāng)非支配解集A中的解的個(gè)數(shù)大于N時(shí),在目標(biāo)空間生成均勻分布的N個(gè)參考向量,依據(jù)式(13)計(jì)算個(gè)體和參考向量之間角度:

(13)

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

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

3 實(shí)驗(yàn)

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

3.1 實(shí)驗(yàn)設(shè)置

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

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

表2 算法相關(guān)參數(shù)設(shè)置

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

表3 500維MaF1不同策略對(duì)比分析

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

3.2 算法性能度量指標(biāo)

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

(14)

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

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

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

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

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

為了驗(yàn)證提出的算法中第一層搜索可以改善非支配解集的多樣性,進(jìn)行了對(duì)比實(shí)驗(yàn),如圖2所示。

圖2 MaF1和MaF6測(cè)試函數(shù)500維10個(gè)目標(biāo)上指標(biāo)分布圖

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

(15)

多樣性指標(biāo)的計(jì)算如式(16):

(16)

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

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

3.4 實(shí)驗(yàn)結(jié)果及分析

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

4 總結(jié)

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