基于混合策略改進(jìn)的社會(huì)群體優(yōu)化算法

張小萍 譚 歡

(1.廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004；2.中國(guó)移動(dòng)通信集團(tuán)廣西有限公司，南寧 530022)

元啟發(fā)式算法可以直觀有效地解決科學(xué)和工程研究領(lǐng)域的許多實(shí)際問題。粒子群優(yōu)化算法、遺傳優(yōu)化算法和蟻群優(yōu)化算法都是非常經(jīng)典的元啟發(fā)式算法。近年來又出現(xiàn)了許多新興的元啟發(fā)式算法，如烏鴉優(yōu)化算法[1]、蝴蝶優(yōu)化算法[2]和樽海鞘群優(yōu)化算法[3]等，這些算法被廣泛應(yīng)用于光伏陣列MPPT研究[4]、冷熱電聯(lián)供微網(wǎng)日前優(yōu)化調(diào)度[5]和應(yīng)急救援供給點(diǎn)選擇[6]等方面。

社會(huì)群體優(yōu)化算法(SGO)是2016年提出的一種新穎的元啟發(fā)式算法[7]。SGO算法將個(gè)體獲取知識(shí)的方式分為提高階段和獲取階段。在提高階段，群體中每個(gè)個(gè)體的知識(shí)都是在最優(yōu)個(gè)體的幫助下得到提高；在獲取階段，每個(gè)個(gè)體的知識(shí)是通過和其他個(gè)體進(jìn)行交流或在最優(yōu)個(gè)體的幫助下來獲取。雖然SGO算法的收斂速度較快，但與其他元啟發(fā)式算法類似，存在迭代后期種群多樣性不足而易陷入局部最優(yōu)的問題。劉亞軍等人提出多子群的社會(huì)群體優(yōu)化算法(MPSGO)[8]，采用多子群學(xué)習(xí)方法，對(duì)個(gè)體學(xué)習(xí)方法進(jìn)行改進(jìn)，既提高了群體的多樣性，又保證了子群個(gè)體的充分進(jìn)化。

針對(duì)SGO算法易陷入局部最優(yōu)的問題，本次研究提出一個(gè)基于混合策略改進(jìn)的社會(huì)群體優(yōu)化算法(HSGO)。

1 社會(huì)群體優(yōu)化算法

Satapathy等人提出的SGO算法一種新穎的元啟發(fā)式算法，操作簡(jiǎn)單、易于實(shí)現(xiàn)，在一些實(shí)際問題的優(yōu)化中取得了良好的效果。在SGO算法中，每個(gè)個(gè)體都被賦予一定的知識(shí)，具有解決某些問題的能力。通過最好的個(gè)體在群體中傳播知識(shí)以及個(gè)體之間的相互交流來提高整個(gè)群體的知識(shí)水平。SGO算法分為初始化、提高和獲取等3個(gè)階段。

1.1 初始化階段

初始化個(gè)體如式(1)所示：

Xi=Lb+(Ub-Lb)rand(1，m)

(1)

式中：m是變量的維度；Ub和Lb分別是變量的上限和下限；rand(1，m)是0～1的m維向量；Xi是種群中的第i個(gè)個(gè)體，i=1，2，…，n，n是種群個(gè)體總數(shù)。

1.2 提高階段

在提高階段，所有個(gè)體都向最優(yōu)個(gè)體學(xué)習(xí)。假設(shè)最優(yōu)個(gè)體是gb，則提高階段的學(xué)習(xí)策略如式(2)所示：

Xnewij=cXij+r1(gbj-Xij)

(2)

式中：c是自我反省參數(shù)，取值為0～1，一般取0.2；r1是0～1的隨機(jī)數(shù)；gbj是最優(yōu)個(gè)體的第j維變量，j=1,2,…,m；Xij和Xnewij分別表示第i個(gè)個(gè)體更新前后的第j維變量。

1.3 獲取階段

在獲取階段，個(gè)體除了向最優(yōu)個(gè)體學(xué)習(xí)，還與其他個(gè)體進(jìn)行隨機(jī)交流學(xué)習(xí)。獲取階段的學(xué)習(xí)策略如式(3)所示：

(3)

式中：r2和r3為0～1的隨機(jī)數(shù)；f(Xi)和f(Xk)分別表示Xi和Xk的適應(yīng)度。

2 基于混合策略改進(jìn)的社會(huì)群體優(yōu)化算法

2.1 隨機(jī)攪動(dòng)變量

在提高階段，新個(gè)體的生成僅僅依賴于r1，(gbj-Xij)在迭代中相對(duì)不變。為了擴(kuò)大搜索范圍、增加種群多樣性，受蝴蝶優(yōu)化算法的啟發(fā)，本次研究增加隨機(jī)攪動(dòng)變量r。假設(shè)r是0～1的隨機(jī)數(shù)，則提高階段的學(xué)習(xí)策略如式(4)所示:

Xnewij=cXij+r1(r2gbj-Xij)

(4)

加入隨機(jī)攪動(dòng)變量可以在尋優(yōu)前期提升算法的全局搜索能力，在尋優(yōu)后期增加種群多樣性，以避免陷入局部最優(yōu)。

2.2 基于精英個(gè)體的逐維改進(jìn)

與其他個(gè)體相比，精英個(gè)體與全局最優(yōu)解的親和度相對(duì)較大，因此通過精英個(gè)體求得問題最優(yōu)解的可能性也較大。為了提高算法的收斂速度，在每次迭代中利用精英個(gè)體對(duì)當(dāng)前最優(yōu)解進(jìn)行改進(jìn)。利用精英個(gè)體對(duì)當(dāng)前全局最優(yōu)解進(jìn)行逐維改進(jìn)，可以避免高維函數(shù)之間相互干擾，從而提高解的質(zhì)量。精英個(gè)體逐維改進(jìn)全局最優(yōu)解的步驟如下:

Step 1將Xi按其適應(yīng)度值從小到大的順序進(jìn)行排列，X1為當(dāng)前最優(yōu)解，前1/3個(gè)個(gè)體是精英個(gè)體。

Step 2從第2～n/3個(gè)中選擇一個(gè)隨機(jī)整數(shù)k，令temp=X1，fbest=f(temp)。

Step 3每次使用Xk的1個(gè)維度變量來取代temp的相應(yīng)維度變量，計(jì)算出temp的適應(yīng)度值，如果f(temp)

Step 4X1=temp，將逐維改進(jìn)后的temp賦值給X1，則X1為改進(jìn)后的全局最優(yōu)解。

2.3 HSGO算法的具體步驟

Step 1初始化系統(tǒng)參數(shù)，利用式(1)隨機(jī)初始化種群。

Step 2計(jì)算種群中個(gè)體的適應(yīng)度值，記錄全局最優(yōu)解。

Step 3在提高階段，使用式(4)更新個(gè)體位置。

Step 4在獲取階段，使用式(3)進(jìn)行個(gè)體間交流學(xué)習(xí)，更新個(gè)體位置。

Step 5利用精英個(gè)體逐維改進(jìn)全局最優(yōu)解。

Step 6判斷是否滿足迭代停止條件，若滿足則輸出最優(yōu)解，算法停止；否則返回Step 2。

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

為了測(cè)試HSGO算法的性能，選用8個(gè)不同的基準(zhǔn)測(cè)試函數(shù)(f1，f2,…，f8)，測(cè)試算法的有效性。其中，f1—f4是單峰值函數(shù)，f5—f8是多峰值函數(shù)，如表1所示。

表1 基準(zhǔn)測(cè)試函數(shù)

采用Matlab R2020b分別對(duì)面向全局搜索的自適應(yīng)領(lǐng)導(dǎo)者樽海鞘群算法(ALSSA)[9]、具有自適應(yīng)步長(zhǎng)的柯西變異烏鴉算法(CMCSA)[10]、SGO、MPSGO與HSGO算法進(jìn)行仿真實(shí)驗(yàn)。仿真實(shí)驗(yàn)環(huán)境為Windows7 64 bit系統(tǒng)，內(nèi)存為8 GiB，CPU為Intel(R)Xeon雙核2.4 GHz。為了測(cè)試的公平性，所有算法的種群個(gè)體數(shù)都為50，最大迭代次數(shù)為500次，每個(gè)算法獨(dú)立測(cè)試30次，計(jì)算各個(gè)算法在不同基準(zhǔn)測(cè)試函數(shù)中的最小值、平均值和方差，計(jì)算結(jié)果如表2所示。

表2 5種算法的仿真實(shí)驗(yàn)結(jié)果

由表2可知，HSGO算法在f1、f2、f3、f4和f8中方差都為0，且其平均值是所有算法中并列最小的，達(dá)到理論最優(yōu)解。HSGO算法在f5中的平均值與MPSGO算法相同，是所有算法中最小的，只有方差略大于MPSGO算法。HSGO算法在f6中的平均值是所有算法中最小的。HSGO算法在f7中平均值和方差也是所有算法中最小的，達(dá)到理論最優(yōu)解。綜上所述，HSGO算法的求解精度和穩(wěn)定性總體優(yōu)于其他4種算法。

為了更加直觀地觀察算法的收斂精度和速度，繪制了4個(gè)多峰值函數(shù)(f5—f8)的平均收斂曲線(見圖1—圖4)。f1—f4是單峰值函數(shù)，相對(duì)簡(jiǎn)單，其收斂曲線不再贅述。

由圖1—圖4可知，HSGO算法和MPSGO算法在f5和f6中表現(xiàn)非常優(yōu)越，有較快的收斂速度，且收斂精度較高。在f7中，只有CMCSA算法的收斂速度較慢，其他4種算法都能很快收斂到最優(yōu)解域。在f8中，CMCSA算法的收斂速度最快，HSGO算法次之，且只有這2種算法搜索到了理論最優(yōu)解。因此，HSGO算法在收斂速度和求解精度上都比其他4種算法好。

圖1 f5的平均收斂曲線

圖2 f6的平均收斂曲線

圖3 f7的平均收斂曲線

圖4 f8的平均收斂曲線

4 結(jié) 語(yǔ)

本次研究基于SGO算法提出HSGO算法。使用隨機(jī)攪動(dòng)策略改進(jìn)提高階段的學(xué)習(xí)方法，擴(kuò)大算法的搜索范圍，以避免陷入局部最優(yōu)。利用精英個(gè)體逐維改進(jìn)全局最優(yōu)解，以加快算法的收斂速度和求解精度。根據(jù)8個(gè)基準(zhǔn)測(cè)試函數(shù)的仿真實(shí)驗(yàn)結(jié)果可知，HSGO算法在求解精度和收斂速度上均優(yōu)于ALSSA、CMCSA、SGO和MPSGO等4種算法。