改進(jìn)交叉算子的自適應(yīng)人工蜂群黏菌算法

劉成漢，何 慶

(貴州大學(xué) 大數(shù)據(jù)與工程學(xué)院，貴陽 550025)(貴州省公共大數(shù)據(jù)重點(diǎn)實驗室，貴陽 550025)

1 引 言

近年來，群智能優(yōu)化算法在許多應(yīng)用學(xué)科中非常流行，因為群智能優(yōu)化算法在各種優(yōu)化問題中比確定性算法性能好、速度快.隨著研究的深入，各學(xué)者研究出了各種智能優(yōu)化算法，例如：粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法[1]、灰狼優(yōu)化(Grey Wolf Optimization，GWO)算法[2]、正余弦優(yōu)化算法(Sine Cosine Algorithm，SCA)[3]、蜉蝣算法(Mayfly Algorithm，MA)[4]、海鷗優(yōu)化算法(Seagull Optimization Algorithm，SOA)[5]等.

黏菌算法(Slime Mould Algorithm，SMA)是由Li等人[6]于2020年提出的一種新型群智能優(yōu)化算法，其靈感來源于黏菌的分散覓食行為，SMA與其他群智能優(yōu)化算法相比具有參數(shù)少，尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn).然而，SMA同樣存在著收斂速度慢，易陷入局部極小值的問題，針對這些問題，眾多學(xué)者對SMA做出了改進(jìn)，例如：Houssein等人[7]將SMA與自適應(yīng)差分進(jìn)化算法(AGDE)結(jié)合使用，提出了一種求解組合優(yōu)化和全局優(yōu)化問題的混合黏菌算法，采用AGDE的交叉策略加快算法收斂，突變策略來增加種群的多樣性并避免算法過早收斂；Chen等人[8]在SMA中加入了混沌映射，提出了一種混沌黏菌優(yōu)化算法，從而提高算法的搜索效率并更好地利用算法的局部搜索能力；Ewees等人[9]將螢火蟲算法的位置更新思想結(jié)合到SMA中，提出了一種基于螢火蟲算法的改進(jìn)黏菌算法，為SMA尋優(yōu)提供更多靈活性，從而加快了算法搜索速度；Abdel-Basset等人[10]提出了一種高效的二進(jìn)制黏菌算法，該算法將標(biāo)準(zhǔn)SMA轉(zhuǎn)換為二進(jìn)制版本(BSMA)，然后引入兩相突變(TM)與BSMA集成，最后結(jié)合一種新的攻擊策略(AF)，從而提高了SMA算法的收斂速度并改善了算法易陷入局部最優(yōu)值的問題；Rizk-Allah等人[11]提出了一種混沌對立增強(qiáng)的黏菌算法，通過引入交叉策略增強(qiáng)算法的多樣性，采用混沌搜索策略，提高算法的開發(fā)能力，從而避免了算法過早收斂的問題；Naik等人[12]針對基本黏菌算法開發(fā)效率底下，收斂速度慢的問題，提出了一種基于精英領(lǐng)導(dǎo)的黏菌算法，采用全局最優(yōu)解領(lǐng)導(dǎo)其他個體更新位置的方式，解決了上述問題.

綜上所述，雖然上述改進(jìn)方案在一定程度上改善了SMA搜索開發(fā)能力弱，收斂速度慢等問題，但是SMA仍然存在收斂精度不高，易早熟收斂的問題.因此，本文提出一種改進(jìn)交叉算子的自適應(yīng)人工蜂群黏菌算法(ISMA)，采用自適應(yīng)可調(diào)節(jié)的反饋因子和交叉算子提高算法的收斂速度和精度；引入改進(jìn)的人工蜂群搜索策略防止算法早熟收斂，最后采用8個基準(zhǔn)測試函數(shù)以及部分CEC2014測試函數(shù)對改進(jìn)算法進(jìn)行尋優(yōu)測試，并結(jié)合Wilcoxon值和統(tǒng)計檢測驗證了改進(jìn)算法的有效性.

2 黏菌優(yōu)化算法

SMA是根據(jù)黏菌個體的振蕩捕食行為提出的一種智能優(yōu)化算法，自然界中的黏菌可以根據(jù)空氣中食物氣味的濃度來接近食物，當(dāng)黏菌靜脈接觸的食物濃度越高，生物振蕩越強(qiáng)，黏菌靜脈寬度增大，該區(qū)域聚集更多黏菌；當(dāng)該區(qū)域食物濃度低時，黏菌轉(zhuǎn)向探索其他區(qū)域.黏菌接近食物的數(shù)學(xué)模型描述如公式(1)所示：

(1)

式中，t為當(dāng)前迭代次數(shù)，Xb(t)為當(dāng)前最優(yōu)個體位置，XA(t)和XB(t)為隨機(jī)選擇兩個個體的位置，W為黏菌質(zhì)量，代表適應(yīng)度權(quán)重，vb和vc為控制參數(shù)，其中vb∈[-a，a]，vc從1線性下降到0，r是[0，1]之間的隨機(jī)數(shù)，控制變量p和參數(shù)a的數(shù)學(xué)模型描述如公式(2)和公式(3)所示：

p=tanh|S(i)-DF|

(2)

(3)

式中，i∈1，2，3，…，n，S(i)是當(dāng)前個體適應(yīng)度值，DF為當(dāng)前最佳適應(yīng)度值，tmax為最大迭代次數(shù).權(quán)重參數(shù)W的數(shù)學(xué)模型描述如公式(4)所示：

(4)

SI(i)=sort(S)

(5)

式中，r表示取值[0，1]的隨機(jī)數(shù)，bF表示當(dāng)前迭代最佳適應(yīng)度，S(i)表示當(dāng)前個體適應(yīng)度值，wf表示當(dāng)前迭代最差適應(yīng)度值，i=C表示種群中適應(yīng)度排在前一半個體，i=O表示剩下的個體，SI(i)是適應(yīng)度排序，表示氣味指數(shù).

即使黏菌找到了更好的食物來源，它們?nèi)匀粫蛛x一些個體探索其他領(lǐng)域試圖尋找更高質(zhì)量的食物來源.因此，黏菌種群更新位置的數(shù)學(xué)模型描述如公式(6)所示：

(6)

式中，UB和LB分別表示搜索區(qū)域的上下界，rand表示取值[0，1]之間的隨機(jī)數(shù)，z為自定義參數(shù).

3 多策略改進(jìn)黏菌優(yōu)化算法

3.1 自適應(yīng)可調(diào)節(jié)反饋因子

在SMA中，反饋因子vc用來描述食物濃度與黏菌質(zhì)量之間的反饋關(guān)系，其值從1線性下降到0，這種線性下降的反饋因子并不能準(zhǔn)確地描述實際情況下質(zhì)量和濃度之間的反饋關(guān)系，可能會導(dǎo)致算法收斂速度慢等問題.因此，本文引入一種自適應(yīng)可調(diào)節(jié)的反饋因子：在算法迭代前期，黏菌個體大范圍感受食物濃度，此時食物濃度低，應(yīng)該加快反饋因子的下降速度，減弱反饋關(guān)系，有利于提高算法全局搜索能力；在算法迭代后期，食物濃度高，此時應(yīng)該保持較為平穩(wěn)的反饋系數(shù)，有利于個體局部探索最高的食物濃度(最優(yōu)解).此外，加入下降速率調(diào)節(jié)因子k，可以自動調(diào)節(jié)反饋因子下降速度，自適應(yīng)可調(diào)節(jié)的反饋因子數(shù)學(xué)模型描述如公式(7)所示：

(7)

式中，t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)，k是調(diào)節(jié)因子，線性反饋因子和調(diào)節(jié)參數(shù)k分別取1、4和7時的自適應(yīng)可調(diào)節(jié)反饋因子比較如圖1所示.

圖1 反饋因子曲線圖Fig.1 Feedback factor curve

由圖1可知，改進(jìn)的反饋因子曲線的下降速度隨著調(diào)節(jié)因子k的增大而增大.在具體算法調(diào)試中，k值的選取不宜過大也不能太小，k值太大可能會導(dǎo)致算法前期收斂過快，算法開發(fā)能力減弱從而陷入局部極小值點(diǎn)；而k值太小則不能體現(xiàn)反饋因子在平衡算法搜索能力上的優(yōu)勢，算法收斂速度變慢.為了平衡算法的搜索能力，本文經(jīng)過大量實驗分析，最后選取k=4最為合適.

3.2 算數(shù)交叉算子

交叉算子是遺傳算法中3個關(guān)鍵算子之一，通過交換兩個父代的位置信息產(chǎn)生新的個體，新的個體繼承了父代的有效信息.本文為了加快SMA的收斂速度，引入改進(jìn)的算數(shù)交叉算子更新個體位置，即以一定的概率Pt讓當(dāng)前個體與種群最優(yōu)個體進(jìn)行交叉操作.交叉算子數(shù)學(xué)模型如公式(8)所示：

(8)

式中，t為當(dāng)前迭代次數(shù)，XA1和XA2分別為交叉產(chǎn)生的兩個子代個體位置，XA為當(dāng)前個體位置，Xbest為當(dāng)前種群最優(yōu)個體位置，L為取值(0，1)的隨機(jī)參數(shù).

由公式(8)可知，子代主要由父代和參數(shù)L確定，其中參數(shù)L控制子代從兩個父代獲取信息的比例，為了使子代獲取更多優(yōu)秀父代的基因，并保持種群多樣性，本文改進(jìn)了原始的隨機(jī)參數(shù)，引入用拉普拉斯系數(shù)[13]控制的參數(shù)L.改進(jìn)后的控制參數(shù)L數(shù)學(xué)模型描述如公式(9)所示：

(9)

式中，μ和λ為拉普拉斯系數(shù)，其中μ取自然數(shù)，控制位置，λ>0控制尺度，r為取值[0，1]的隨機(jī)數(shù).由公式(9)可知，改進(jìn)后的參數(shù)L通過引入系數(shù)λ調(diào)節(jié)父代與子代的距離，λ越小子代越靠近父代，種群多樣性越高，同時，在拉普拉斯系數(shù)μ和λ的共同調(diào)節(jié)下，子代能選擇性獲得更多優(yōu)秀父代的位置信息.

3.3 改進(jìn)的人工蜂群搜索策略

人工蜂群算法(Artificial Bee Colony Algorithm，ABC)[14]是由Karaboga等人于2006年提出的一種智能優(yōu)化算法，該算法通過模擬自然界蜂群的采蜜行為實現(xiàn)對復(fù)雜優(yōu)化問題的處理，在復(fù)雜多峰函數(shù)尋優(yōu)上具有良好的性能，擁有強(qiáng)大的探索能力.針對SMA易早熟收斂的問題，本文引入人工蜂群搜索策略并做出改進(jìn)，基本人工蜂群搜索策略數(shù)學(xué)模型描述如公式(10)所示：

Zi，j=xi，j+φi，j(xi，j-xk，j)

(10)

式中，Zi，j為產(chǎn)生的候選解，xi，j為當(dāng)前個體，xk，j為隨機(jī)個體，k和j為隨機(jī)參數(shù)，k∈{0，1，…，M}，j∈{1，2，…，d}，M為固定值，d表示維度，且k不等于i，φi，j為取值[-1，1]的隨機(jī)數(shù).由公式(10)可知，候選解由隨機(jī)選取兩個個體進(jìn)行差分操作產(chǎn)生.

雖然人工蜂群搜索策略在搜索能力上有著很大的優(yōu)勢，但是其開發(fā)能力不強(qiáng)，因此本文引入一種新的搜索策略，在人工蜂群強(qiáng)大搜索能力的基礎(chǔ)上加入全局最優(yōu)位置引導(dǎo)，從而提高其開發(fā)能力，改進(jìn)策略數(shù)學(xué)模型描述如公式(11)所示：

Zi，j=xi，j+φi，j(xi，j-xk，j)+Ωi，j(pg，j-xi，j)

(11)

式中，Ω為取值[0，1.5]的隨機(jī)數(shù)，pg為全局最優(yōu)位置.

綜上所述，本文在SMA迭代過程中引入改進(jìn)的人工蜂群搜索策略，在每一次迭代結(jié)束時，對于原始算法更新產(chǎn)生的個體和引入人工蜂群策略生成的個體，采用貪婪策略保留其中較優(yōu)的個體，加快算法收斂，同時，人工蜂群搜索策略強(qiáng)大的搜索能力可以減少局部極值點(diǎn)對SMA的影響，從而提高算法跳出局部最優(yōu)解的能力.

3.4 ISMA實現(xiàn)步驟

綜上改進(jìn)策略，ISMA實現(xiàn)步驟如下所示：

步驟1.參數(shù)初始化：設(shè)置搜索上界UB、下界LB，種群規(guī)模N，最大迭代次數(shù)tmax，維度D.

步驟2.初始化種群：在搜索空間隨機(jī)產(chǎn)生初始種群.

步驟3.計算種群每個個體的適應(yīng)度并排序，記錄最好適應(yīng)度wF和最差適應(yīng)度bF.

步驟4.根據(jù)公式(6)更新候選解位置.

步驟5.根據(jù)公式(8)以一定的概率Pt讓當(dāng)前個體與種群最優(yōu)個體進(jìn)行交叉操作.

步驟6.引入人工蜂群搜索策略，根據(jù)貪婪策略保留較優(yōu)個體.

步驟7.判斷結(jié)束條件，若滿足迭代條件則算法終止，否則重復(fù)步驟3-步驟6.

步驟8.輸出最優(yōu)值，算法結(jié)束.

ISMA實現(xiàn)流程圖如圖2所示.

圖2 ISMA實現(xiàn)流程圖Fig.2 ISMA implementation flowchart

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

4.1 參數(shù)設(shè)置說明

仿真實驗采用的計算機(jī)配置為，Intel Core i5-7500U，32GB內(nèi)存，64bit操作系統(tǒng)，計算環(huán)境為Matlab2016(a).本文選取粒子群優(yōu)化(PSO)算法，灰狼優(yōu)化(GWO)算法，鯨魚優(yōu)化算法(WOA)和SMA與ISMA進(jìn)行實驗對比，基本參數(shù)統(tǒng)一設(shè)置為：最大迭代次數(shù)tmax=500，低維維度d=30，高維維度d=200，種群規(guī)模N=30.各算法內(nèi)部參數(shù)設(shè)置如表1所示.

表1 算法參數(shù)設(shè)置Table 1 Algorithm parameter setting

4.2 測試函數(shù)介紹

為了測試ISMA在實際算法上的尋優(yōu)效果，選取8個基準(zhǔn)測試函數(shù)進(jìn)行仿真實驗，其中f1-f5為單峰測試函數(shù)，f6-f8為復(fù)雜多峰測試函數(shù).測試函數(shù)基本信息如表2所示.

4.3 各改進(jìn)SMA尋優(yōu)性能對比

為了驗證ISMA改進(jìn)策略的效果，將ISMA與基本SMA、文獻(xiàn)[15]提出的LF-SMA和文獻(xiàn)[16]提出的BTβSMA進(jìn)行基準(zhǔn)測試函數(shù)尋優(yōu)性能對比實驗，其中LF-SMA是引入萊維飛行的黏菌算法，BTβSMA是引入自適應(yīng)β爬山策略的黏菌算法.相比于基本的SMA，LF-SMA和BTβSMA在對于基準(zhǔn)測試函數(shù)的尋優(yōu)性能上相比于SMA有很大提升，為了體現(xiàn)實驗的公平性，實驗參數(shù)統(tǒng)一設(shè)置為：最大迭代次數(shù)tmax=500，維度d=30，種群規(guī)模N=30，算法尋優(yōu)執(zhí)行30次，取平均值和標(biāo)準(zhǔn)差，測試函數(shù)相關(guān)信息由表2給出，尋優(yōu)性能對比結(jié)果如表3所示.

表2 基準(zhǔn)測試函數(shù)介紹Table 2 Introduction to benchmark functions

由表3可知，ISMA對于基礎(chǔ)測試函數(shù)的尋優(yōu)性能整體優(yōu)于其他改進(jìn)SMA，對于單峰測試函數(shù)f1-f4和多峰測試函數(shù)f6、f7，ISMA能夠收斂到理論最小值0；對于單峰測試函數(shù)f5和f8，雖然ISMA不能收斂到理論值，但其收斂精度優(yōu)于LF-SMA和BTβSMA，并且相對于SMA有一定提升，說明本文提出的ISMA在基準(zhǔn)測試函數(shù)上具有一定的優(yōu)勢.

表3 各改進(jìn)算法性能對比Table 3 Performance comparison of the improved algorithms

4.4 ISMA高維尋優(yōu)性能測試

為了進(jìn)一步測試ISMA處理高維問題的能力，將其與基本PSO算法，GWO算法，WOA以及SMA進(jìn)行高維測試函數(shù)尋優(yōu)對比，統(tǒng)一采取維度d=200，最大迭代次數(shù)tmax=500，種群規(guī)模N=30，各算法其他內(nèi)部參數(shù)由表1給出，測試函數(shù)相關(guān)信息由表2給出，為了更直觀地分析ISMA處理高維問題的性能，圖3給出了在200維時各算法獨(dú)立運(yùn)行30次后的適應(yīng)度平均值收斂曲線.

圖3 基準(zhǔn)測試函數(shù)平均收斂曲線(200維)Fig.3 Function average convergence curve(200d)

由圖3結(jié)果可知，相比與基本PSO算法、GWO算法、WOA以及SMA，ISMA在高維優(yōu)化問題的處理上仍然具有很大的優(yōu)勢.對于高維基準(zhǔn)測試函數(shù)f1、f2、f3、f4、f6和f7，ISMA能夠收斂到全局最小值0，且收斂速度也是最快的，例如：對于單峰函數(shù)f1，SMA和ISMA都能找到0，但是ISMA在迭代142次時算法收斂，而SMA則需要迭代439次；對于單峰測試函數(shù)f5和復(fù)雜多峰測試函數(shù)f8，ISMA雖然沒有收斂到全局最優(yōu)值，但能快速跳出局部最優(yōu)值，并收斂到更加接近全局最小值.由此可知，ISMA在高維函數(shù)處理時同樣具有優(yōu)越的性能.

4.5 Wilcoxon秩和檢測

Wilcoxon秩和檢測是一種比較兩組數(shù)據(jù)的非參數(shù)統(tǒng)計檢驗，測試本質(zhì)上是計算對比數(shù)據(jù)之間的差異，并分析這些差異，以確定它們是否在統(tǒng)計上存在顯著不同.為了全面體現(xiàn)ISMA的優(yōu)勢，本文引入Wilcoxon秩和統(tǒng)計檢驗驗證ISMA對于基準(zhǔn)測試函數(shù)仿真結(jié)果的有效性，選取基本PSO算法、GWO算法、WOA、SMA以及本文引入改進(jìn)人工蜂群算法策略的SMA變體(ASMA)與ISMA對表2所示8個基本測試函數(shù)仿真結(jié)果進(jìn)行秩和統(tǒng)計分析并計算p值，當(dāng)p<5%時，可以被認(rèn)為是拒絕零假設(shè)的有力驗證[17].結(jié)果+、-和=分別表示ISMA秩和統(tǒng)計結(jié)果優(yōu)于、差于和等于對比算法，NaN表示沒有數(shù)據(jù)進(jìn)行對比，Wilcoxon秩和檢驗結(jié)果如表4所示.

由表4結(jié)果可知，ISMA算法與PSO算法、GWO算法、WOA、SMA以及ASMA的Wilcoxon秩和檢驗對比結(jié)果p值基本上都小于5%，說明從統(tǒng)計學(xué)上來說，ISMA算法對于基本函數(shù)的尋優(yōu)結(jié)果優(yōu)勢是明顯的，從而進(jìn)一步體現(xiàn)了ISMA的魯棒性.

表4 Wilcoxon秩和檢驗結(jié)果Table 4 Wilcoxon rank sum test results

4.6 CEC2014測試函數(shù)尋優(yōu)對比

為了驗證ISMA求解復(fù)雜優(yōu)化問題的性能，本文采用部分CEC2014函數(shù)進(jìn)行仿真實驗，CEC2014測試函數(shù)具有復(fù)雜的特征，常用于驗證算法有效性，其中包括單峰(UN)、多峰(MF)、混合(HF)和復(fù)合(CF)類型函數(shù)，部分CEC2014測試函數(shù)相關(guān)信息如表5所示.實驗參數(shù)統(tǒng)一為：種群規(guī)模N=50，維度d=30，最大迭代次數(shù)tmax=2000，每個函數(shù)獨(dú)立運(yùn)行30次取平均值和標(biāo)準(zhǔn)差.本文選取PSO算法、SCA、L-SHADE算法以及LFSMA與ISMA進(jìn)行尋優(yōu)結(jié)果對比，其中，PSO算法和SCA算法實驗數(shù)據(jù)分別來源于文獻(xiàn)[18]和文獻(xiàn)[19]；LFSMA[20]是引入量子旋轉(zhuǎn)門策略的SMA；L-SHADE算法[21]由于其在CEC2014中的優(yōu)秀表現(xiàn)，常用來進(jìn)行對比實驗.各算法對于CEC2014測試函數(shù)尋優(yōu)結(jié)果對比分析如表6所示.

表5 部分CEC2014函數(shù)介紹Table 5 Part of the CEC2014 function

表6 CEC2014函數(shù)優(yōu)化對比Table 6 CEC2014 function optimization comparison

由表6結(jié)果可知，在求解單峰CEC03函數(shù)時，L-SHADE算法表現(xiàn)優(yōu)秀，但是對于多峰、混合和復(fù)合類型的函數(shù)優(yōu)化上ISMA表現(xiàn)出了絕對的優(yōu)勢；對于CEC07、CEC12、CEC14和CEC19函數(shù)，ISMA能夠找到最優(yōu)值，對于其他混合和復(fù)合類型的CEC2014函數(shù)，ISMA也能收斂到最優(yōu)值附近；雖然SMA變體LFSMA對于CEC2014函數(shù)的尋優(yōu)效果也具有一定優(yōu)勢，但是整體性能略差于ISMA.說明ISMA在對于復(fù)雜問題的處理上同樣具有很好的魯棒性.

5 結(jié)束語

為了解決黏菌算法存在的收斂速度慢，易早熟收斂的問題，本文提出了一種改進(jìn)交叉算子的自適應(yīng)人工蜂群黏菌算法.引入自適應(yīng)可調(diào)節(jié)反饋因子和改進(jìn)的交叉算子加快算法收斂；考慮到人工蜂群算法強(qiáng)大的搜索能力，引入一種全局最優(yōu)解引導(dǎo)的人工蜂群搜索策略，從而提高了算法跳出局部最小值的能力.通過8個基準(zhǔn)函數(shù)和部分具有復(fù)雜特征的CEC2014測試函數(shù)，以及Wilcoxon秩和統(tǒng)計檢測進(jìn)行實驗仿真，結(jié)果表明，本文提出的ISMA具有很好的尋優(yōu)性能.下一步研究內(nèi)容考慮將ISMA應(yīng)用到實際工程問題中，進(jìn)一步驗證ISMA在處理實際問題的優(yōu)越性.