基于分層學(xué)習(xí)的改進PSO算法求解復(fù)雜優(yōu)化問題

白曉慧，何小娟，孫超利，張國晨

(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院，太原 030024)

粒子群算法(PSO)[1]作為最重要的進化算法之一，目前已被應(yīng)用于各種優(yōu)化問題的求解中，取得了較好的效果[2]，但是在求解大規(guī)模優(yōu)化問題中，PSO存在過早收斂、易陷于局部最優(yōu)及種群多樣性丟失等問題。為了提高PSO求解大規(guī)模優(yōu)化問題的效率，學(xué)者們在PSO中引入?yún)f(xié)同進化策略(CC)、局部搜索策略以及多種群策略等方法。

協(xié)同進化策略是由Potter在1997年提出的方法[3],該策略通過分而治之的方法解決大規(guī)模優(yōu)化問題。Li 等人在2009年提出了一種基于協(xié)同進化的粒子群優(yōu)化算法(CCPSO)[4]，該算法將決策變量隨機分組協(xié)同進化，但是隨機分組不能精確地將相關(guān)變量分到同一組導(dǎo)致算法的優(yōu)化性能較差。李曉東等人提出一種自動分組的法(DG)[5]，該方法根據(jù)決策變量的相關(guān)性將決策變量分組，但是在求解決策變量的相關(guān)性時會花費大量的評價次數(shù)。文獻[6]將鄰域策略引入PSO中，使得每個粒子都向鄰域最優(yōu)值學(xué)習(xí)而不是向全局最優(yōu)值學(xué)習(xí)。文獻[7-8]將多種群策略引入PSO中，該算法把種群分為多個子種群分別進行優(yōu)化，有效提高了PSO的搜索能力。2015年，程然和金耀初將社會學(xué)習(xí)機制引入PSO中，提出了社會學(xué)習(xí)粒子群算法(SLPSO)[9].雖然SLPSO提高了PSO的優(yōu)化性能，但在解決大規(guī)模優(yōu)化問題時仍然存在多樣性缺失、收斂速度慢等缺點。針對該不足，本文引入分層學(xué)習(xí)策略與貢獻值策略對SLPSO進行改進，進一步提高PSO求解大規(guī)模優(yōu)化問題的性能。

1 大規(guī)模優(yōu)化問題

一般來說，大規(guī)模優(yōu)化問題可以用式(1)表述：

min/maxF(x)=f(x1,x2,…,xn)

(1)

其中x?Rn表示可行解集；n表示搜索空間的維數(shù)(即決策變量的個數(shù))；xi表示決策變量；f表示目標(biāo)函數(shù)。在大規(guī)模優(yōu)化問題中，決策變量的個數(shù)n一般大于100，通常達到1 000維以上。

2 社會學(xué)習(xí)粒子群算法

程然和金耀初在2015年提出了SLPSO算法。該算法首先根據(jù)粒子的適應(yīng)度值對種群中的粒子進行排序，其次除最優(yōu)粒子外，每個粒子在每一維上隨機選取比它適應(yīng)度值好的粒子以及種群的平均位置進行學(xué)習(xí)。粒子的位置與速度更新公式如(2)所示：

Vi,j=

Xi,j=Xi,j+Vi,j

(2)

3 基于分層學(xué)習(xí)的改進社會學(xué)習(xí)粒子群算法

針對SLPSO存在的問題，本文提出了一種基于分層學(xué)習(xí)的改進社會學(xué)習(xí)粒子群算法(HSLPSO).一方面引入分層學(xué)習(xí)策略，差別對待不同狀態(tài)的粒子，充分發(fā)揮不同狀態(tài)的粒子在探索和開發(fā)搜索空間中的不同潛能。另一方面引入貢獻值策略，減少計算資源的浪費。

3.1 分層學(xué)習(xí)策略

在進化期間，粒子在開發(fā)和探索搜索空間表現(xiàn)出了不同的潛能。適應(yīng)度值好的粒子在開發(fā)搜索空間中表現(xiàn)出了較優(yōu)的潛能，它可以引導(dǎo)種群向全局最優(yōu)區(qū)域移動，從而實現(xiàn)快速收斂，而適應(yīng)度值差的粒子在探索搜索空間中表現(xiàn)出了較優(yōu)的潛能，它可以幫助種群跳出局部最優(yōu)。因此不同狀態(tài)的粒子應(yīng)該被差別對待。

為了區(qū)別對待不同狀態(tài)的粒子，引入分層學(xué)習(xí)策略。首先根據(jù)粒子的適應(yīng)度值把粒子分為三層，適應(yīng)度好的粒子放入第一層，適應(yīng)度值較好的粒子放入第二層，適應(yīng)度值較差的粒子放入第三層。因為適應(yīng)度值較差的粒子在探索搜索空間表現(xiàn)出了較優(yōu)的潛能，能幫助種群跳出局部最優(yōu)。因此，為了增加種群的多樣性，在第三層放入的粒子數(shù)量最多的，第一層放入的粒子最少。分層學(xué)習(xí)策略的框架如圖1所示。

圖1 分層學(xué)習(xí)策略框架Fig.1 Hierarchical learning strategy framework

圖1中，種群中的粒子根據(jù)粒子的適應(yīng)度值按照升序排序，并且把粒子分為三層，每一層用Hi(1≤i≤3)表示。H1是第一層，H2是第二層，H3是第三層。第三層的粒子向當(dāng)前層以及第二層的粒子學(xué)習(xí)，第二層的粒子向當(dāng)前層以及第一層的粒子學(xué)習(xí)，第一層的粒子僅僅向當(dāng)前層的粒子學(xué)習(xí)。從圖1(c)中可以看到，第三層和第二層的粒子從當(dāng)前層以及它的前一層隨機選取示范粒子對應(yīng)的維進行學(xué)習(xí)，第一層的粒子從當(dāng)前層隨機選取示范粒子對應(yīng)的維進行學(xué)習(xí)，種群中的最優(yōu)粒子不進行學(xué)習(xí)。第二層與第三層粒子的更新公式如(3)所示，第一層粒子的更新公式如(4)所示：

(3)

(4)

3.2 貢獻值策略

因為HSLPSO算法中粒子的更新是采用基于維的社會學(xué)習(xí)方式，因此在進化后期，大量相似粒子的出現(xiàn)會影響HSLPSO算法的性能，并且會造成計算資源的浪費。為了解決這一問題，設(shè)定貢獻值策略，度量全局最優(yōu)值在一個迭代周期的改進性能。貢獻值較大時表示全局最優(yōu)值在這一個迭代周期內(nèi)的改進性能較大，否則認(rèn)為全局最優(yōu)值的改進性能較小。貢獻值較小時，說明種群中出現(xiàn)了大量相似粒子，通過減少種群數(shù)量，刪除種群中大部分的相似粒子，有助于緩解由于大量相似粒子的出現(xiàn)對算法性能的影響，并且在每次迭代中減少了評價次數(shù)，從而減少了計算資源的浪費。初始化階段，貢獻值r0為1，然后每隔一個迭代周期計算貢獻值。貢獻值的計算公式如(5)所示：

(5)

其中ri表示第i個迭代周期的貢獻值，bestyi表示第i個迭代周期中最優(yōu)個體的適應(yīng)度值。

在種群進化期間，當(dāng)兩個相鄰的貢獻值ri-1與ri同時小于閾值ε，并且種群數(shù)量為N時，把第三層的粒子放入到第二層，并隨機刪除第二層一半的粒子。

偽代碼1 HSLPSO

1:初始化種群與參數(shù)

2：while不滿足終止條件 do

3:計算粒子的適應(yīng)度值,并且把粒子分為3層

4:每隔一個周期通過公式(5)計算ri

5:ifri<ε&&ri-1<ε&&N=350

6:把第三層的粒子合并入第二層，并在第二層中隨機刪除一半粒子

7:c1=1/2*c1

8:end if

9:ifri<ε&&ri-1<ε

10: if FEs>=0.3*MaxFEs

11:根據(jù)公式(3)與(4)對粒子進行更新

12: else

13:根據(jù)公式(3)對粒子進行更新

14: end if

15:else

16:根據(jù)公式(3)對粒子進行更新

17:end if

18:end while

19:輸出最優(yōu)值

3.3 算法流程

HSLPSO的偽代碼見偽代碼1，首先初始化種群，其次根據(jù)分層學(xué)習(xí)策略對種群進行分層并更新粒子，在種群進化期間計算貢獻值，當(dāng)貢獻值滿足一定條件時，減少種群數(shù)量。最后，當(dāng)評價次數(shù)達到最大評價次數(shù)時，輸出最優(yōu)值。

4 仿真實驗及結(jié)果分析

為了驗證本文所提算法的有效性，在CEC2010測試函數(shù)集上進行仿真實驗[10]。并與5種典型算法(DLLSO[11]、SLPSO 、CSO[12]、DECC-DG以及DECC-G[13])的測試結(jié)果進行對比。在實驗中，HSLPSO的參數(shù)設(shè)定如表1.每個算法分別獨立運行20次，最大評價次數(shù)設(shè)置為3 000*n，其中n是大規(guī)模優(yōu)化問題的維數(shù)。

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

在初始化階段種群的數(shù)量被設(shè)置為350.第一層的粒子數(shù)量M為50，當(dāng)種群被分為三層時，第二層和第三層的粒子數(shù)量分別為2M與4M.當(dāng)種群被分為兩層時，第二層的粒子數(shù)量為3M.

表2給出了6種算法的測試結(jié)果。均值和方差取20次運行結(jié)果的平均值。當(dāng)HSLPSO與CSO、SLPSO、 DECC-DG對比時，使用威爾克遜秩和檢驗來進行顯著性檢驗(α=0.05).P-value上角標(biāo)的“+”“-”與“=”分別表示HSLPSO算法的性能比其他算法的性能“顯著好”“顯著差”“幾乎等同”。

從測試結(jié)果看出HSLPSO在解決大規(guī)模優(yōu)化問題時的有效性，其中HSLPSO在13個函數(shù)的測試結(jié)果明顯好于其他5種算法。對于測試函數(shù)F20，HSLPSO的測試結(jié)果與SLPSO、CSO的測試結(jié)果相同，并且好于其余3種算法的測試結(jié)果。本文在CECC2010測試函數(shù)集中選擇了4個典型的函數(shù)(F1：完全可分的單模態(tài)函數(shù)，F(xiàn)3：完全可分的多模態(tài)函數(shù)，F(xiàn)7：部分可分的單模態(tài)函數(shù)以及F8：部分可分的多模態(tài)函數(shù))對HSLPSO、SLPSO與CSO進行收斂性對比，對比結(jié)果如圖2-圖5所示。對于完全可分函數(shù)，從圖2與圖3中可以看出HSLPSO的收斂速度明顯比其他兩種算法的收斂速度快；對于部分可分函數(shù)，從圖4中可以看出在進化前期HSLPSO的收斂速度比SLPSO的收斂速度快，和CSO的收斂速度一樣，但在進化后期HSLPSO的收斂速度明顯比其他兩種算法的收斂速度快，從圖5中看出，HSLPSO在進化前期的收斂速度和其他兩種算法的收斂速度一樣，但在進化后期HSLPSO收斂速度比其他兩種算法的收斂速度快。

表2 6種算法測試結(jié)果

圖2 測試函數(shù)F1的收斂圖Fig.2 Convergence graph of test function F1

圖3 測試函數(shù)F3的收斂圖Fig.3 Convergence graph of test function F3

圖4 測試函數(shù)F7的收斂圖Fig.4 Convergence graph of test function F7

圖5 測試函數(shù)F8的收斂圖Fig.5 Convergence graph of test function F8

5 結(jié)束語

為了解決大規(guī)模優(yōu)化問題，提出一種改進的SLPSO算法——HSLPSO.針對SLPSO存在的收斂速度慢以及進化后期多樣性缺失等問題。本文引入分層學(xué)習(xí)策略以及貢獻值策略，改善了SLPSO在進化后期多樣性缺失的問題，提高了SLPSO的收斂速度。通過仿真實驗，測試結(jié)果表明在解決大規(guī)模優(yōu)化問題時HSLPSO的有效性。