白曉慧，何小娟，孫超利，張國(guó)晨

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

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

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

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

一般來(lái)說(shuō)，大規(guī)模優(yōu)化問(wèn)題可以用式(1)表述：

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

(1)

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

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

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

Vi,j=

Xi,j=Xi,j+Vi,j

(2)

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

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

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

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

為了區(qū)別對(duì)待不同狀態(tài)的粒子，引入分層學(xué)習(xí)策略。首先根據(jù)粒子的適應(yīng)度值把粒子分為三層，適應(yīng)度好的粒子放入第一層，適應(yīng)度值較好的粒子放入第二層，適應(yīng)度值較差的粒子放入第三層。因?yàn)檫m應(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)前層以及它的前一層隨機(jī)選取示范粒子對(duì)應(yīng)的維進(jìn)行學(xué)習(xí)，第一層的粒子從當(dāng)前層隨機(jī)選取示范粒子對(duì)應(yīng)的維進(jìn)行學(xué)習(xí)，種群中的最優(yōu)粒子不進(jìn)行學(xué)習(xí)。第二層與第三層粒子的更新公式如(3)所示，第一層粒子的更新公式如(4)所示：

(3)

(4)

3.2 貢獻(xiàn)值策略

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

(5)

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

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

偽代碼1 HSLPSO

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

2：while不滿足終止條件 do

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

4:每隔一個(gè)周期通過(guò)公式(5)計(jì)算ri

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

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

7:c1=1/2*c1

8:end if

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

10: if FEs>=0.3*MaxFEs

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

12: else

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

14: end if

15:else

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

17:end if

18:end while

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

3.3 算法流程

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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