基于NSGA-II的偏好分解的多目標(biāo)優(yōu)化算法研究

謝倩文， 何利力

( 浙江理工大學(xué) 信息學(xué)院， 杭州 310018)

0 引 言

涉及兩個或者多個要優(yōu)化的沖突目標(biāo)的問題稱為多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem，MOP)。由于各個目標(biāo)之間相互排斥，無法取得在各個目標(biāo)上的最優(yōu)解。如何取得最優(yōu)解或者逐漸靠近最優(yōu)解的近似解，成為研究多目標(biāo)進(jìn)化算法(MOEA)的重點(diǎn)。目前的研究主要從兩個方面著手，一種是通過加權(quán)的方式，將多目標(biāo)優(yōu)化問題轉(zhuǎn)化成單目標(biāo)優(yōu)化問題；另外一種就是基于Pareto支配關(guān)系得到非支配解。Deb K提出使用帶有精英策略的、非支配的排序算法NSGA-II，能夠在真正的Pareto前沿附近找到最優(yōu)的解I[1]，但NSGA-II算法對于高維多目標(biāo)優(yōu)化問題，Pareto非支配解會越來越多，維度越大，擁擠距離在高維空間的計算也會更加復(fù)雜。張青富、李輝提出的MOEA/D對于低維簡單PF的多目標(biāo)優(yōu)化問題效果很好，根據(jù)分解方法能生成一組均勻分布的解，可擴(kuò)展性高、收斂快、計算復(fù)雜度低[2]。但當(dāng)有復(fù)雜的Pareto前沿時，MOEA/D的均勻分布就會被破壞。而偏好優(yōu)化算法通過建立偏好的初始條件，在進(jìn)化迭代的過程中不斷朝著偏好方向去搜索，減小搜索范圍，找到離偏好信息最接近的解。為了求解基于偏好關(guān)系的多目標(biāo)問題，Molina在參考點(diǎn)附近估計有效設(shè)置，提出了適用于MO進(jìn)化算法和MO元啟發(fā)算法的g-Dominance[3]；王麗萍等通過將偏好信息和分解的多目標(biāo)算法相結(jié)合，消除參考點(diǎn)的不同區(qū)域?qū)λ惴ㄊ諗啃缘挠绊慬4]。針對高維的多目標(biāo)問題，Deb, K提出了基于參考點(diǎn)的非支配排序方法的進(jìn)化多目標(biāo)優(yōu)化算法NSGA-III[5]；Yuan等人提出的θ-DEA，利用基于分解的MOEA中的適應(yīng)性評估方案，來增強(qiáng)最近提出的非支配排序遺傳算法III的收斂性[6]；Shouyong Jiang提出的SPEA/R基于參考方向的密度估計器，在多目標(biāo)問題上顯示出非常好的競爭性能[7]；Ke Li等人提出的MOEA/DD結(jié)合了基于優(yōu)勢和分解的方法，使用權(quán)重向量指定和評估子區(qū)域，得到收斂良好和分布良好的點(diǎn)集[8]。

在許多應(yīng)用領(lǐng)域中，多目標(biāo)矛盾的協(xié)調(diào)也是研究的重點(diǎn)。Li 等提出了基于分解的多目標(biāo)離散人工蟻群算法，對考慮工序啟動時間的置換流水車間調(diào)度問題求解[9]；李明峰研究了一種加權(quán)懲罰適應(yīng)度的多目標(biāo)氣象航線模型，得到了航行的最有航線[10]；王原針對群體智能機(jī)器人泛用性，提出了基于可變參數(shù)的多目標(biāo)控制模型優(yōu)化算法[11]。

1 多維偏好多目標(biāo)分解算法NSGA-RPIPBI

1.1 改進(jìn)的PBI Approach (IPBI) 方法

基于分解的多目標(biāo)進(jìn)化算法的代表MOEA/D的算法思想是通過聚合函數(shù)，將多目標(biāo)問題分解成多個單目標(biāo)優(yōu)化的子問題，同時對每個子問題進(jìn)行優(yōu)化。而每個子問題得到的最優(yōu)解對于討論的MOP都是最優(yōu)的。MOEA/D的每一個子問題由一個均勻分布的權(quán)重向量構(gòu)成，每生成一個新解，則基于聚合函數(shù)對該子問題附近的解進(jìn)行替換。

邊界交叉聚合方法(Penalty-Based Boundary Intersection, PBI)是使F(x)盡可能的逼近Pareto前沿，通過采用懲罰的方法來處理約束，式(1)。

minimize gbip(x|λ,z*)=d1+θ·d2,

subject tox∈Ω.

(1)

(2)

(3)

對于一些比較復(fù)雜PF問題，傳統(tǒng)的PBI Approach方法會丟失一些平緩解，導(dǎo)致解的分布不均勻，本文針對這個不足提出了改進(jìn)的PBI Approach (Improvement PBI Approach)。在種群迭代過程中，為了讓個體和參照點(diǎn)的距離越來越小，個體逼近參照點(diǎn)形成的超平面即可達(dá)到效果。w=(1,1,…,1)T表示該超平面的法向量。d1表示目標(biāo)點(diǎn)F(x)投影在從Pareto前沿出發(fā)的沿w方向的投影點(diǎn)到參考點(diǎn)的距離，式(4)；d2表示目標(biāo)點(diǎn)f(x)到w的距離，式(5)。

(4)

(5)

如果參照點(diǎn)邊界點(diǎn)沿著法向量穿過POF，落在POF上的交點(diǎn)就會變成POF的邊界點(diǎn)，那么交點(diǎn)以上的部分就會被舍棄，破壞了解的整體分布效果。為了使得到的解有較好的分布，就需要讓POF上的點(diǎn)落在超平面上的投影點(diǎn)都分布在第一象限，所以超平面和目標(biāo)都需要改動。對于每一個目標(biāo)，其落在超平面的投影點(diǎn)為f(x)=(f1(x),f2(x),…,fm(x))，而補(bǔ)足位移d=(d1,d2,…,dm)就是每個投影點(diǎn)在每一個目標(biāo)分量上的最小值，式(6)。

(6)

根據(jù)補(bǔ)足位移來移動超平面就會達(dá)到實(shí)驗(yàn)效果，使得轉(zhuǎn)換后的目標(biāo)解的邊界值也能落在超平面上。

1.2 NSGA-II算法

NSGA-II是一種非支配排序算法。對于大多數(shù)問題，提出一個選擇算子，該算子通過組合父代和后代種群，選擇最佳的N個解決方案(根據(jù)適應(yīng)度和分布)來創(chuàng)建新的種群空間。董駿峰研究的一種個體領(lǐng)域的構(gòu)建方法，采用相應(yīng)的淘汰策略，使得求出的解集有更好的分布性和良好的收斂性[12]；Elarbi, M.提出了新的基于分解優(yōu)勢關(guān)系來處理多目標(biāo)優(yōu)化問題，將RP支配地位替換為Pareto支配地位[13]；Zhichao Lu提出的NSGA-Net，以貝葉斯網(wǎng)絡(luò)的形式找到具有競爭力的神經(jīng)體系結(jié)構(gòu)，探索潛在的神經(jīng)網(wǎng)絡(luò)體系結(jié)構(gòu)的空間[14]。

NSGA-II的快速非支配排序?qū)⒎N群按照支配等級全部劃分，在同一等級的非支配解中，利用擁擠度使得解在目標(biāo)空間中分布均勻，式(7)。

(7)

在種群中先按照Pareto等級由低到高排列。在同一Pareto等級的個體按照擁擠度大小從大到小依次放入父代種群，直到父代種群個體數(shù)量飽和為止，至此新一代的父代種群生成。新的父代種群生成后，開始新一輪的選擇交叉和變異，生成子代種群，父子代種群合并，進(jìn)行快速非支配排序，根據(jù)排序結(jié)果計算擁擠度，選擇合適個體組成新父代種群，一直迭代到滿足最大迭代種群數(shù)時停止迭代。

NSGA-III算法是在NSGA-II的基礎(chǔ)上的改進(jìn)，NSGA-II算法的選擇策略主要根據(jù)擁擠度，在高維目標(biāo)中效果不明顯。NSGA-III加入了一組預(yù)先定義的參考點(diǎn)，使用權(quán)重向量生成方法，針對超平面生成均勻分布的權(quán)重向量。M是優(yōu)化目標(biāo)的個數(shù)，對于每個優(yōu)化目標(biāo)，沿著維度方向劃分H份，那么參考點(diǎn)的數(shù)量為式(8)：

(8)

選定參考點(diǎn)，借助參考點(diǎn)找到其對應(yīng)的近似Pareto最優(yōu)解。

1.3 偏好向量的參考機(jī)制

基于參考點(diǎn)的多目標(biāo)進(jìn)化算法MOEAs大都通過參考點(diǎn)來測量群體質(zhì)量的好壞。在基于參考方向的強(qiáng)度 Pareto進(jìn)化算法中，基于參考向量的局部適應(yīng)度分配方案保留了該子區(qū)域中最有希望的個體。最近，田調(diào)整參考點(diǎn)的位置，以保持極端點(diǎn)和解決方案，以實(shí)現(xiàn)更好的多樣性[16]；金飛飛在決策過程盡可能多地保留決策者的偏好信息，基于得分函數(shù)定義由于偏好關(guān)系，在有序一致性的情況下，選擇最優(yōu)的決策方案[17]。在設(shè)計偏好多目標(biāo)優(yōu)化算法時，應(yīng)該考慮的重點(diǎn)包括如何保證偏好區(qū)域的可控性以及分布性。

本文提出的算法在種群初始化之前，根據(jù)目標(biāo)維度的大小生成了均勻分布的權(quán)重向量，第一層的偏好向量和偏好范圍由決策者規(guī)定，通過與偏好向量相互作用，使得權(quán)重向量分布在偏好向量的交互半徑內(nèi)。第一次的偏好向量在一定的迭代次數(shù)內(nèi)保持不變，當(dāng)達(dá)到改變條件后，選取當(dāng)前迭代種群的最優(yōu)解作為第二次的偏好，再次將更新后的權(quán)重向量向偏好方向轉(zhuǎn)移。

(9)

在迭代次數(shù)滿足一定條件后，選擇當(dāng)前種群中最符合偏好的解作為再次進(jìn)化的新的偏好方向。在更新后的偏好向量的指導(dǎo)下，利用偏好向量和新的權(quán)重向量的夾角，權(quán)重向量越靠近偏好方向，兩者之間的夾角就越小，權(quán)重向量會被選擇再次進(jìn)入進(jìn)化部分的幾率越高，式(10)。

(10)

得到的值越大，說明距離偏好向量越近，越有機(jī)會被選取。

1.4 RP策略

為了產(chǎn)生更加有效的參照點(diǎn)，覆蓋率更大，參照點(diǎn)在生成時需要進(jìn)行動態(tài)調(diào)整。需要把一些無效的參照點(diǎn)舍去，在參照點(diǎn)密度高的區(qū)域重新生成參考點(diǎn)，新生成的參考點(diǎn)根據(jù)第一次交互產(chǎn)生的最優(yōu)解作為偏好參考，再次進(jìn)行偏好調(diào)整。

重新生成的參照點(diǎn)數(shù)量，式(11)[18]：

(11)

再次生成新的H值，式(12)：

(12)

其中，N代表種群大小,RP表示附近有解的參照點(diǎn)個數(shù)。H值如果滿足公式(12)，H即可確定下來，新生成的參照點(diǎn)數(shù)量也可確定。

2 算法設(shè)計

在該算法中，初始化種群數(shù)量N以及初始的權(quán)重向量和理想點(diǎn)位置、移動位移。在迭代次數(shù)未達(dá)到的情況下，每次迭代生成的新個體，通過個體選擇，將一部分子代種群和父代種群統(tǒng)一起來，形成新種群。根據(jù)新種群中經(jīng)過環(huán)境選擇之后的個體動態(tài)調(diào)整參考點(diǎn)得到均勻分布的解。算法描述如下：

算法NSGA-RPIPBI: Framework of the NSGA-RPIPBI procedure

輸入：種群迭代大小，優(yōu)化問題MOP

輸出：Pareto非支配解

1: 初始化：初始化權(quán)重向量W，初始化種群N，得到初始理想點(diǎn)z*和移動位移d

2:whileItrCounter

3:Individual=Recombination+Mutation(交叉變異進(jìn)化生成新個體)

4:RItrCounter=N∪Individual(合并子代種群和父代種群)

5:PItrCounter=EnviromentSelection(RItrCounter) (進(jìn)行環(huán)境選擇)

6:AdjustingReferencePoints(根據(jù)新種群調(diào)整參考點(diǎn))

7:ItrCounter++

8:endwhile

9:returnPItrCounter

3 仿真實(shí)驗(yàn)及分析

3.1 參數(shù)設(shè)置

本實(shí)驗(yàn)研究的多目標(biāo)數(shù)量即目標(biāo)維度設(shè)定為基數(shù)3至5；同時初始化種群數(shù)量，種群規(guī)模設(shè)定為300至500；參數(shù)Mr用來控制迭代次數(shù)，得到相對精準(zhǔn)的超平面；參數(shù)fr表示動態(tài)參數(shù)調(diào)整的次數(shù)，需要適當(dāng)?shù)膮?shù)調(diào)整，得到更好的參照點(diǎn)；父代種群通過交叉變異操作形成子代種群。具體參數(shù)值設(shè)置見表1。

表1 參數(shù)設(shè)置

3.2 算法性能評價指標(biāo)

分布性(Distribution)：衡量算法得到的解在Pareto前沿上面的分布情況，是否能夠均勻分布，以及是否覆蓋到整個Pareto前沿。

收斂性(Convergence)：衡量算法得到的解與真實(shí)的Pareto前沿的距離[19]，距離越小，逼近程度越好。

反向代間距離IGD(Inverted Generational Distance)：表示真實(shí)Pareto前沿中每個解到近似解中所有解的歐氏距離的最小值。IGD越小，表示得到的解的收斂效果和分布效果更好。

3.3 算法性能測試對比

種群迭代次數(shù)= 500，目標(biāo)維數(shù)= 3

(1)NSGA-RPIPBI測試結(jié)果。隨著迭代次數(shù)的增加，目標(biāo)曲線越來越趨于穩(wěn)定，如圖1所示。

圖1 NSGA-RPIPBI測試結(jié)果

(2)NSGA-II測試結(jié)果。算法后期收斂效果不能一直保持，如圖2所示。

圖2 NSGA-II測試結(jié)果

(3)MOEA/DD算法測試結(jié)果。MOEA/DD在100代之后沒有明顯的優(yōu)化，如圖3所示。

圖3 MOEA/DD測試結(jié)果

種群迭代次數(shù)= 300，目標(biāo)維數(shù)= 5

(1)NSGA-RPIPBI測試結(jié)果。種群迭代結(jié)果越來越穩(wěn)定，并且收斂性一直保持良好，如圖4所示。

圖4 NSGA-RPIPBI測試結(jié)果

(2)NSGA-II測試結(jié)果。迭代達(dá)到一定次數(shù)后，收斂性不能得到保證，如圖5所示。

圖5 NSGA-II測試結(jié)果

(3)MOEA/DD測試結(jié)果。迭代達(dá)到一定次數(shù)后，收斂性不能得到保證，如圖6所示。

圖6 MOEA/DD測試結(jié)果

通過對比測試結(jié)果，NSGA-RPIPBI相比較NSGA-II和MOEA/DD來說，得到的解更加靠近真實(shí)的最優(yōu)解，同時NSGA-RPIPBI收斂效果更好，收斂速度更快。通過動態(tài)調(diào)整參照點(diǎn)，NSGA-RPIPBI的優(yōu)勢就是能夠保證全局的參照點(diǎn)是均勻分布的，通過這些參照點(diǎn)得到的解也是均勻分布的，所以對于真實(shí)的最優(yōu)解來說，會更加具有參考價值。

4 結(jié)束語

本文為了得到更加分布均勻的解和選擇帶有偏好機(jī)制的解集，提出了偏好分解的多目標(biāo)優(yōu)化算法NAGA-RPIPBI。該算法利用分解算法得到均勻分布的權(quán)重向量，同時加入決策者的偏好信息，引導(dǎo)得到的解向POF收斂，更好地體現(xiàn)解的收斂；同時針對NSGA-II在復(fù)雜前沿分布不均勻的問題也提出了改進(jìn)。通過移動超平面，增加了覆蓋最優(yōu)解的區(qū)域。最后，通過在測試函數(shù)上的對比實(shí)驗(yàn)，NAGA-RPIPBI比NSGA-II和MOEA/DD算法展示出了更好的收斂性和穩(wěn)定性。