張小萍 譚 歡

(1.廣西大學 計算機與電子信息學院，南寧 530004；2.中國移動通信集團廣西有限公司，南寧 530022)

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

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

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

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

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

1.1 初始化階段

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

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

(1)

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

1.2 提高階段

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

Xnewij=cXij+r1(gbj-Xij)

(2)

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

1.3 獲取階段

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

(3)

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

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

2.1 隨機攪動變量

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

Xnewij=cXij+r1(r2gbj-Xij)

(4)

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

2.2 基于精英個體的逐維改進

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

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

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

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

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

2.3 HSGO算法的具體步驟

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

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

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

Step 4在獲取階段，使用式(3)進行個體間交流學習，更新個體位置。

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

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

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

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

表1 基準測試函數(shù)

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

表2 5種算法的仿真實驗結(jié)果

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

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

由圖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é) 語

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