求解大規(guī)模多目標(biāo)問題的改進粒子群算法

蘭麗爾，孫超利，何小娟，譚 瑛

(1.太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院，太原 030024;2.太原科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，太原 030024 )

實際的工程應(yīng)用領(lǐng)域[1]通常存在大量多目標(biāo)優(yōu)化問題，即優(yōu)化問題需要同時考慮多個優(yōu)化目標(biāo)，而這些優(yōu)化目標(biāo)往往互相沖突。不失一般性，多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型如下所示：

(1)

(2)

其中m表示優(yōu)化目標(biāo)個數(shù)，RD表示D維決策空間。通常，由于優(yōu)化目標(biāo)之間的沖突性，因此找不到一個最優(yōu)解使得滿足所有的目標(biāo)函數(shù)達到最優(yōu)，而找到的最優(yōu)解通常不唯一且互相之間無優(yōu)劣之分，故稱為Pareto最優(yōu)解集(Pareto-optimal set)或非支配解集(nondominated set)[2].

近年來，多目標(biāo)進化優(yōu)化算法，如多目標(biāo)遺傳算法[3]、多目標(biāo)差分進化算法[4]以及多目標(biāo)粒子群算法[5]等，由于能對整個搜索空間的大量可行解同時并行搜索，且對目標(biāo)函數(shù)無連續(xù)可微要求等優(yōu)點在求解多目標(biāo)優(yōu)化問題上獲得了越來越多的應(yīng)用。常見的多目標(biāo)優(yōu)化問題求解方法有基于支配關(guān)系的多目標(biāo)優(yōu)化方法、基于分解策略的多目標(biāo)優(yōu)化方法[6]以及基于指標(biāo)的多目標(biāo)優(yōu)化方法[7]三大類。隨著優(yōu)化問題的復(fù)雜化，問題所需要優(yōu)化的目標(biāo)越來越多，計算也越耗時，因此近幾年來，學(xué)者們專注于研究求解許多目標(biāo)優(yōu)化問題(Many Objective Problems，MaOP)的不同方法，如Wang等[8]提出了用于求解許多目標(biāo)優(yōu)化問題的偏好協(xié)同進化算法，Jain和 Deb[9]基于NSGA-II框架提出了NSGA-III算法，使用快速排序法進行分層并使用參考向量實現(xiàn)對下一代個體的選擇，Li等[10]將支配和分解的方法結(jié)合，提出了一種基于分配和分解的多目標(biāo)優(yōu)化進化算法。Cheng等[11]提出了基于參考向量的進化算法，Zhang等[12]提出了基于拐點的進化算法，通過拐點增強多目標(biāo)進化算法在求解許多目標(biāo)優(yōu)化問題的搜索性能。為了有效利用取樣點的準(zhǔn)確性用于計算IGD(Inverted Generational Distance)指標(biāo)，Sun等[13]提出了一種有效的基于分解的最差點估計方法用于構(gòu)建理想的Pareto前沿。

縱觀現(xiàn)有的方法，大部分算法都是針對求解目標(biāo)空間高維的問題而提出的。實際工程問題中，還存在決策空間高維的多目標(biāo)優(yōu)化問題。查閱以往文獻，2017年由Zhang等[14]提出的基于決策變量聚類的進化算法用于求解大規(guī)模許多目標(biāo)優(yōu)化問題，2018年由Zille等人[15]提出的基于問題轉(zhuǎn)化的大規(guī)模多目標(biāo)優(yōu)化。盡管這兩種算法都取得了較好的優(yōu)化效果，但是文獻[14]中提出的方法運行時間較長，而文獻[15]提出的方法中其分組機制以及轉(zhuǎn)換函數(shù)會對結(jié)果產(chǎn)生影響。因此，急需新的求解大規(guī)模多目標(biāo)優(yōu)化問題的有效方法。

基于社會學(xué)習(xí)的粒子群優(yōu)化算法是Cheng等[16]提出的用于求解大規(guī)模單目標(biāo)優(yōu)化問題的改進粒子群優(yōu)化算法。在該方法中，每個粒子在每一維上向某一個比其好的個體的對應(yīng)維以及種群的平均位置進行學(xué)習(xí)，在種群多樣性和收斂性上取得平衡，從而獲得大規(guī)模優(yōu)化問題的最優(yōu)解。2015年Cheng等[17]又提出了求解大規(guī)模單目標(biāo)優(yōu)化的粒子群算法，該算法采用一種競爭機制，在產(chǎn)生子代過程中失敗者向成功者進行學(xué)習(xí)來更新粒子的位置和速度。之后2018年Zhang等[18]將該競爭機制引入大規(guī)模多目標(biāo)優(yōu)化問題中并取得了很好的成果。受此啟發(fā)，本文基于分解策略的框架下將社會學(xué)習(xí)粒子群優(yōu)化算法進行改進用于求解大規(guī)模多目標(biāo)優(yōu)化問題。在個體進化過程中，通過選擇向沿當(dāng)前權(quán)重向量更靠近參考點的個體學(xué)習(xí)，同時向更靠近權(quán)重向量的個體平均位置學(xué)習(xí)，以期能夠為大規(guī)模多目標(biāo)優(yōu)化問題找到分布均勻的最優(yōu)解集。

1 相關(guān)概念

1.1 基于社會學(xué)習(xí)的粒子群優(yōu)化算法(SLPSO)

粒子群算法(PSO)[19]是Kenney和Eberhart為求解單目標(biāo)優(yōu)化問題而提出的，但是隨著問題維度的提高，該算法在搜索過程中對于算法收斂性以及種群多樣性很難平衡，而且在粒子搜索過程中容易早熟收斂，陷入局部最優(yōu)。2015年，Cheng和Jin針對大規(guī)模優(yōu)化問題提出了一種改進的粒子群算法，稱為基于社會學(xué)習(xí)的粒子群優(yōu)化算法(SLPSO)[16].在該算法中，對種群中的粒子根據(jù)適應(yīng)值進行排序，除最優(yōu)粒子之外，每個粒子的每一維向比其好的任一粒子以及種群的平均位置的相應(yīng)維進行學(xué)習(xí)。圖1給出了作為粒子i示范粒子的確定過程，N表示種群大小，式(3)和式(4)給出了粒子i在其j維上的更新公式。

圖1 示范粒子的確定Fig.1 Determination of demonstration particles

vi,j(t+1)=r1,j(t)*vi,j(t)+r2,j(t)*Ii,j(t)+r3,j(t)*ε*Ci,j(t)

(3)

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

(4)

其中

Ii,j(t)=xk,j-xi,j(t)

(5)

(6)

1.2 切比雪夫加權(quán)法(Tchebycheff Approach)

2 求解大規(guī)模的改進粒子群算法(MPSO)

(7)

(8)

圖2 基于懲罰的邊界交叉法示例Fig.2 Illustration of the penalty-based boundary intersection approach

圖3 個體沿權(quán)重向量方向與參考點的距離排序Fig.3 The distance between individuals along the weight vector direction and the reference point

圖4 個體與權(quán)重向量之間的距離排序Fig.4 Distance ranking between individuals and weight vectors

本文提出的算法具體步驟如下：

步驟1：

參數(shù)設(shè)定，包括種群大小，最大迭代次數(shù)，參考向量個數(shù)，鄰域大小T；

步驟2：

初始化種群，包括初始化速度和位置；

步驟3：

步驟4：

產(chǎn)生權(quán)重向量，對每個權(quán)重向量分配種群個體；

步驟5：

確定每個個體i的鄰域個體為B(i)={i1,…,iT}；

步驟6：

對每個個體i，執(zhí)行以下操作：

(1)對個體i及其鄰域個體分別根據(jù)和d2進行排序，根據(jù)式(3)和式(4)對個體i使用本文所提方法進行速度和位置的更新；

(2)計算個體i的適應(yīng)值和切比雪夫加權(quán)值，若比之前位置的切比雪夫加權(quán)值好，則保留現(xiàn)在的新位置，否則保留原有位置；

步驟7：

將當(dāng)前種群個體和外部Archive中存儲的非支配解集合并，重新更新Archive中的非支配解集；

步驟8：

步驟9：

是否滿足終止條件，若滿足，則輸出；否則返回步驟5.

3 實驗結(jié)果及分析

為了驗證方法在大規(guī)模多目標(biāo)優(yōu)化問題上的有效性，我們選用5個ZDT測試函數(shù)，在低維和高維(500維和1000維)上進行了測試，并與傳統(tǒng)的MOEA/D和NSGA-II進行了比較。MOEA/D和NSGA-II的測試結(jié)果在Tian等[21]提出的測試平臺上運行得到。本文方法MPSO與這兩種對比算法的種群大小均設(shè)置為100，MOEA/D與MPSO的鄰域大小為20，而MOEA/D中模擬二進制交叉的分布指數(shù)和多項式變異都為20，交叉率為1，變異率為1/N.本文提出的MPSO算法中ε=β*g/MAXG,其中g(shù)表示當(dāng)前代，MAXG表示最大迭代次數(shù)，在本文實驗中，β=0.002，當(dāng)維度低于100時，MAXG=250，維度大于100時，MAXG=500.β的取值由多次實驗獲得。每個算法在每個測試函數(shù)上獨立運行20次。

為了對比不同算法的性能，在本文中采用IGD(Inverted Generational Distance)作為指標(biāo)來評價不同算法的優(yōu)化結(jié)果。假設(shè)P*是目標(biāo)空間中最優(yōu) Pareto 面上均勻分布的點的集合，P是非支配解集，則IGD的定義為：

表1給出了本文算法以及MOEA/D和NSGA-II在低維上和高維(500維和1000維)上的統(tǒng)計結(jié)果，并給出了Wilcoxon秩和檢驗結(jié)果，“+”,“-”和“≈”分別表示MPSO算法的結(jié)果優(yōu)于、差于和相似于對比算法得到的結(jié)果。從表1可以看到在低維多目標(biāo)優(yōu)化問題上，MPSO并不占優(yōu)勢，其獲得的IGD結(jié)果均比不上MOEA/D和NSGA-II算法。而在500維和1000維上均獲得了比其它兩種方法更好的解，這說明本文算法在大規(guī)模優(yōu)化問題上是有效的，這和文獻中的結(jié)論也是相符的，也再一次驗證了基于社會學(xué)習(xí)的粒子群優(yōu)化算法在高維優(yōu)化問題上的有效性。

表1 不同算法在不同維度測試函數(shù)上的統(tǒng)計結(jié)果
Tab.1 Statistical results of different algorithms on different dimension test functions

問題維度MOEA/DAvg.(Std.)NSGA-II Avg.(Std.)MPSOAvg.(Std.)ZDT13050010005.88E-03(2.47E-03)-5.55E+02(5.23E+01)+2.43E+03(9.98E+01)+4.77E-03(1.90E-04)-3.77E+02(4.12E+01)+1.70E+03(1.13E+02)+9.45E-02(1.06E-02)1.47E+01(3.81E+00)2.97E+02(1.43E+01)ZDT23050010001.41E-02(2.39E-02)-5.03E+02(4.84E+01)+2.38E+03(9.68E+01)+4.79E-03(2.01E-04)-3.84E+02(2.58E+01)+1.76E+03(1.12E+02)+1.03E-01(2.38E-02)2.37E+01(2.33E+00)1.95E+02(4.55E+01)ZDT33050010002.19E-02(1.31E-02)-5.75E+02(4.59E+01)+2.45E+03(8.40E+01)+4.85E-02(5.84E-02)-4.06E+02(3.72E+01)+1.71E+03(9.14E+01)+1.17E-01(4.83E-02)9.70E+00(7.88E-02)2.96E+02(2.95E+01)ZDT41050010008.51E-03(2.37E-03)-2.05E+03(8.96E+01)+6.49E+03(1.99E+02)+6.79E-03(2.02E-03)-1.72E+03(8.71E+01)+5.53E+03(1.95E+02)+9.57E-01(3.09E-01)1.68E+03(8.33E+01)4.91E+03(2.79E+02)ZDT61050010003.29E-03(8.22E-05)-2.51E+01(6.80E-01)+3.68E+01(6.10E-01)+3.85E-03(2.33E-04)-2.50E+01(5.35E-01)+3.49E+01(5.13E-01)+5.47E-02(1.15E-02)1.34E+01(1.92E-01)2.40E+01(1.09E+00) +/-/ 10/5/0 10/5/0

圖5-9給出了不同算法在低維多目標(biāo)優(yōu)化問題上的IGD趨勢圖，從圖中可以看出，在低維問題上，所提的MPSO算法在多樣性和收斂性方面并不占特別的優(yōu)勢，但是在算法前期，除了ZDT4，本文所提出的MPSO算法相比于其它兩種算法，具有較好的IGD值，說明通過本文方法在前期找到的最優(yōu)解集具有較好的多樣性和收斂性。

圖10-14給出了不同算法在500維不同多目標(biāo)優(yōu)化問題上的IGD趨勢圖，從圖中可以看出，本文所提的MPSO算法在相同評價次數(shù)下其IGD的值要遠遠好于其它兩種算法。盡管在ZDT4上沒有超過NSGA-II算法，但是相比于相應(yīng)低維問題上的結(jié)果我們可以發(fā)現(xiàn)MPSO和NSGA-II之間的差距在逐步減少。

圖5 不同算法在30維ZDT1上的IGD變化圖Fig.5 IGD variation chart of different algorithms on 30 dimensional ZDT1圖6 不同算法在30維ZDT2上的IGD變化圖Fig.6 IGD variation chart of different algorithms on 30 dimensional ZDT2

圖9 不同算法在10維ZDT6上的IGD變化圖Fig.9 IGD variation chart of different algorithms on 30 dimensional ZDT6圖10 不同算法在500維ZDT1上的IGD變化圖Fig.10 IGD variation chart of different algorithms on 500 dimensional ZDT1

圖15-19給出了不同算法在1000維不同多目標(biāo)優(yōu)化問題上的IGD趨勢圖，從圖中我們清晰地看到MPSO算法在每一次評價次數(shù)下其IGD的值均比其它算法好，特別是ZDT4上，我們很容易就發(fā)現(xiàn)本文所提出的MPSO在1000維ZDT4多目標(biāo)優(yōu)化問題上已獲得了比其他算法更好的IGD值，再一次驗證了本文算法在大規(guī)模多目標(biāo)優(yōu)化問題上的優(yōu)勢。

圖11 不同算法在500維ZDT2上的IGD變化圖Fig.11 IGD variation chart of different algorithms on 500 dimensional ZDT2圖12 不同算法在500維ZDT3上的IGD變化圖Fig.12 IGD variation chart of different algorithms on 500 dimensional ZDT3

圖15 不同算法在1000維ZDT1上的IGD變化圖Fig.15 IGD variation chart of different algorithms on 1000 dimensional ZDT1圖16 不同算法在1000維ZDT2上的IGD變化圖Fig.16 IGD variation chart of different algorithms on 1000 dimensional ZDT2

圖17 不同算法在1000維ZDT3上的IGD變化圖Fig.17 IGD variation chart of different algorithms on 1000 dimensional ZDT3圖18 不同算法在1000維ZDT4上的IGD變化圖Fig.18 IGD variation chart of different algorithms on 1000 dimensional ZDT4

圖19 不同算法在1000維ZDT6上的IGD變化圖Fig.19 IGD variation chart of different algorithms on 1000 dimensional ZDT6

4 結(jié)論

針對大規(guī)模多目標(biāo)優(yōu)化問題,本文基于社會學(xué)習(xí)粒子群優(yōu)化算法的思想，將多目標(biāo)分解策略與之相結(jié)合提出了一種改進的粒子群算法(MPSO)，并分別進行了低維和高維ZDT函數(shù)的測試，結(jié)果表明本文算法在求解大規(guī)模多目標(biāo)優(yōu)化問題上有明顯的優(yōu)勢，但是在低維問題上并不理想。因此，今后將進一步改進算法，一方面保證在在低維問題上取得更好的結(jié)果，另一方面將其擴展到大規(guī)模許多目標(biāo)問題中，以獲得較好的最優(yōu)效果。