一種基于多策略的改進黏菌算法

王喜敏,袁 杰,寇巧媛

(新疆大學 電氣工程學院，新疆 烏魯木齊 830017)

群智能優化算法包括2個搜索階段： 勘探階段和開發階段[1]?？碧诫A段是指盡可能廣泛、隨機和全局地搜索解空間的過程；開發階段是指算法在勘探階段獲得區域內搜索更精確解的能力，隨機性降低，精確度提高。當算法的勘探能力占優時，可以更好地搜索解空間，產生更多的差異化解集，從而快速收斂。當算法的開發能力占優時，更多地進行局部搜索，以提高解集的質量和精度。然而，當勘探能力得到改善時，會導致開發能力的降低，反之亦然。因此，對優化問題有效的2個階段之間取得適當的平衡是具有挑戰性的。典型群智能優化算法包括粒子群優化算法(PSO)[2]、灰狼優化算法(GWO)[3-4]、鯨魚優化算法(WOA)[5]、螢火蟲算法[6-7]、布谷鳥算法[8]等。黏菌算法(SMA)是由Li等[9]于2020年提出的一種基于種群的元啟發式算法，黏菌的振蕩行為類似于細菌覓食優化算法[10-11]。該算法相比其他群智能算法具有更優的搜索能力，應用于太陽能光伏電池參數優化[12-13]、電力系統穩定器參數優化[14]、路徑規劃[15]、任務調度[16-17]、旅行商問題[18]等領域。

SMA算法仍存在一些缺點，比如算法隨著搜索增加會陷入局部最優、收斂性能下降，所以，研究人員對SMA算法進行了一定的改進。肖亞寧等[19]提出一種基于混沌精英黏菌算法(CESMA)，提高了算法的搜索能力，用于優化PID控制參數；Chen等[20]提出混沌SMA(CSMA)，集成Logistic混沌映射，提高搜索效率，提供了更好的開發模式；Zhao等[21]開發基于Levy飛行的改進SMA，引入Levy flight來代替均勻分布和高斯分布調用的隨機權值，在探索開發階段取得良好的性能；Zhao等[22]提出混合SMA和Harris hawk優化(HHO)，利用更多的方式更新個體；Gao等[23]提出混合GWO算法與SMA算法，以改善原有SMA算法，的早熟收斂性能；Wu等[24]提出一種基于正交學習策略(OLS)和邊界重啟策略(BRS)的OBSMA算法，提高了算法的全局優化能力；Hu等[25]提出一種離散覓食策略的DFSMA算法，應用于生物醫學數據的特征選擇，提高了全局搜索能力，但是存在執行時間過長的問題；Wei等[26]提出一種基于領導者和跟隨者機制的ISMA算法，較好地解決了無功優化調度(ORPD)問題中的精度和計算時間上的不足；Naik等[27]開發了一個領導者SMA(LSMA)以改善SMA的搜索過程，選擇最優的候選解作為LSMA的領導者進行指導，應用于多光譜圖像，取得了良好性能。雖然目前改進方法對算法全局勘探能力和開發能力有所優化，但在平衡算法的勘探和開發能力上還有待提高。

基于上述研究，為了均衡SMA算法的勘探能力和開發能力，本文在SMA中引入Tent混沌映射反向學習策略，生成反向種群，選擇多樣性好的種群作為初始種群來提高搜索效率，更好地利用解的局域性；引入自適應權值策略和擾動策略更新黏菌位置，平衡算法全局搜索能力和局部開發能力，避免算法早熟，快速獲得全局最優位置。最后，對經典測試函數的尋優曲線進行分析，相較于其他算法，改進SMA算法收斂速度和收斂精度均得到提升。

1 基本黏菌算法

SMA算法是一種隨機優化方法，模擬黏菌尋找食物過程的3個階段：發現食物、接近食物和包圍食物[28]。SMA算法利用適應性權值W來模擬基于生物振蕩器的黏菌傳播波的正負反饋系統結合產生的過程，該生物振蕩器旨在展示連接食物的最優路徑，權重發生變化，選擇不同的更新策略。但是基于隨機搜索的更新過程，導致種群多樣性差問題；其次，2個隨機個體的選擇導致算法可能會陷入局部最優。

1.1 發現食物階段

當食物濃度滿足條件時，區域附近的權重較大；當食物濃度較低時，該區域的權重會降低，從而轉向其他區域探索。

(1)

式中：

νb=[-a,a]；

(2)

(3)

p=tanh|S(i)-FD|，i∈1,2,…,N。

(4)

W權重更新策略為

(5)

SmellIndex=sort(S)。

(6)

式(1)中：r表示[0,1]區間內的隨機值；Xb(t)表示當前獲得的最佳位置；W為權重；XA(t)和XB(t)是隨機選擇的2個個體；vb是控制參數；vc從1線性減小到0；t代表當前迭代次數；X(t)表示當前位置；p是選擇開關。式(3)中：t表示當前迭代次數；tmax表示最大迭代次數。式(4)中：S(i)是進行排序后的種群；FD是所有迭代中最佳值。式(5)為權重W更新，其中：矢量Fb表示當前迭代過程中獲得的最優適應值；Fω表示當前迭代過程中得到的最差適應值；condition表示S(i)是種群的前半部分，i=N/2。式(6)中SmellIndex對適應度值進行排序。

1.2 接近食物階段

接近食物階段是模擬黏菌靜脈結構內的收縮方法，位置根據食物質量進行調整，也就是說，食物的濃度越高，該區域的權重就越大。否則，根據式(7)將該區域的權值轉換為其他區域。位置更新策略為

(7)

式中：R表示[0,1]區間內的隨機值；Bl和Bu表示搜索空間范圍的下界和上界；z表示切換概率，決定SMA是探索其他食物源還是圍繞最佳個體搜索；其他變量同公式(1)。

1.3 包圍食物階段

包圍食物階段是模擬vb的行為，vb在區間[-a,a]中以隨機方式浮動，并隨著迭代次數的增加逐漸減小到零。vc的值在[0,1]之間浮動，最終到達0。

2 多策略的改進黏菌算法

2.1 基于Tent映射反向學習的初始化種群策略

在SMA算法中，對初始種群使用了隨機策略，通過一定范圍的上下界實現隨機取值，但這種隨機策略使得最優解質量和收斂速度等方面不太理想。為了盡可能充分利用解的空間信息，提高最優解的質量和增強初始解搜索空間的勘探能力，本文針對SMA算法的缺點，采用Tent映射反向學習策略對種群進行重新初始化，以便獲得更優的初始種群。

2.1.1 Tent映射

研究表明，利用混沌運動的隨機性、規律性和遍歷性的優勢，能夠產生豐富且多樣性的初始種群。已知的混沌映射有Tent映射、Logistic映射等，Tent映射的遍歷均勻性要明顯強于Logistic映射[29]，產生的初始值均勻分布在[0,1]區間，在提高算法的收斂速度方面有明顯的效果。Tent混沌映射表達式為

(8)

當φ∈(0,1)，且xk∈[0,1]時，系統(8)處于混沌狀態。

2.1.2 反向學習策略

豐富的種群多樣性能提高算法的搜索效率，減少計算時間，提高全局收斂能力。反向學習策略[30]是一種提高搜索效率的方法，采用對其初始種群求反向解的思想，增加搜索種群的多樣性，進而提高最佳點的質量。其基本思路是：如果在D維度空間X=(X1,X2,…,XD)上存在一點，并且xi(i=1,2,…,D)分布在[c,d]區間內，反向點x′i=c+d-xi，i∈[0,D]。所以種群X′i為Xi的反向種群，反向種群的計算公式為

X′i=Li+Ui-Xi。

(9)

式中：Li和Ui分別為上下界；Xi為原初始種群；X′i為反向種群。

將原始種群和反向種群合并為一個新種群X=(Xi∪X′i)，然后計算適應度值并進行排序，選取前N個點作為初始種群X。

2.2 自適應權值策略

受群智能優化算法的啟發，黏菌算法在搜索過程中的隨機分布限制了全局搜索范圍。位置更新中加入一個隨迭代次數變化的權值ω，ω的特點是迭代早期值較大，后期值較小。在算法迭代前期，選擇較大搜索步長，以提高全局搜索能力，提高算法遍歷全局的效果，避免出現早熟收斂；在迭代后期，選擇較小搜索步長，以提高局部搜索，加快收斂速度。姜天華[31]提出非線性調整收斂因子，采用帶有權重的個體位置更新和局部搜索算法，提高了算法的局部搜索能力。本文引入非線性變化的自適應權值策略，均衡算法勘探和開發能力，充分保證算法的有效性，自適應權值如式(10)[32]，式中：ωinitial、ωfinal表示初始值和最終值，ω的范圍為[0,1]；t是當前的迭代次數；T是最大迭代次數。

(10)

改進后的位置更新公式為

(11)

本文引入自適應權值策略的位置更新，隨著迭代次數增加，非線性動態改變權值。早期迭代中權值較大，能夠獲得較強的探索能力，快速向全局最優值靠攏，從而提高算法的收斂速度；后期迭代中選擇較小權值，提高跳出局部最優值的能力。

2.3 擾動策略

黏菌更新位置的時候，一般選擇當前最優位置進行更新，使得搜索范圍變窄，迭代次數減少。為了提高全局搜索效率，選擇對當前最優位置添加一個擾動，并對位置信息進行貪婪策略判斷，判斷當前位置是否最優。對當前位置進行隨機擾動，公式為

(12)

采用貪婪機制策略進行判斷是否保留擾動，公式為

(13)

本文提出的改進SMA算法步驟如下：

Step1 初始化各參數，基于Tent混沌映射和反向學習策略生成初始種群X；

Step2 計算適應度值，進行排序；

Step3 根據迭代條件更新p、vb、vc；

Step4 每次迭代中通過式(5)、(7)、(11)更新位置、權重；

Step5 重新計算適應度值，同時選擇適應的更新位置公式，選擇最優位置；

Step6 利用式(12)和(13)對當前最優位置進行擾動更新；

Step7 判斷是否滿足設定的終止條件，如果是，輸出全局最優值，算法結束，否則回到Step2。

3 仿真實驗及分析

本文仿真實驗的所有算法均在相同條件下進行，保證公平性。將PSO[2]、GWO[3]、WOA[5]、SMA[9]和本文多策略的改進SMA算法應用于選取的測試函數，并對結果進行對比分析。

3.1 測試函數

本文選取5個經典測試函數來驗證算法的有效性，測試函數如表1所示。單峰函數f1和f2用來測試本文算法的局部開發能力，多峰函數f3、f4、f5用來測試本文算法的全局搜索能力。

表1 測試函數Tab. 1 Test function

算法的參數設置如表2所示，參數的選擇是基于原文作者使用的參數或各種研究人員廣泛使用的參數[6]。其中，設置種群的規模N=30，最大迭代次數T=1 000，維度D=30，為了減少算法運行隨機因素的影響，將算法在測試函數中單獨運行30次，取平均值作為最終運行結果。

表2 參數設置Tab. 2 Parameter settings

3.2 實驗對比與分析

所有仿真實驗在Windows10操作系統，Intel Core i5處理器上，基于MATLAB 2018b進行。通過結合算法迭代到最優值的迭代次數和尋到最優值所用時間來綜合評價收斂速度，通過數據分析收斂精度，本文從收斂速度和收斂精度2個角度分析算法的搜索效率。

3.2.1 改進SMA算法與SMA、PSO、GWO、WOA的對比

為了直觀清晰觀察算法的收斂性，給出測試函數f1～f5收斂曲線，如圖1所示。收斂曲線能直觀看出收斂速度和陷入局部最優問題，橫坐標為迭代次數，縱坐標為適應度值。記錄最優函數值的標準差和平均值數據，如表3所示。

圖1 與經典算法對比時函數f1 ～ f5尋優曲線Fig. 1 Optimization curve of functions f1 ～ f5 when the classicol algorithm compares

表3 改進的SMA算法與SMA、PSO、GWO、WOA算法實驗結果對比Tab. 3 Comparison of test function results between improved SMA algorithm and SMA, PSO, GWO and WOA algorithms

圖1給出各算法分別在30維度空間的尋優曲線。從收斂速度分析，圖1(a)中，PSO、WOA、GWO在1 000次迭代過程中未搜索到極值點；SMA算法在迭代次數為50時出現陷入局部極值的情況，直到700次附近找到極值點0；而多策略的改進SMA算法的曲線平滑，沒有出現陷入局部極值點現象，在迭代次數達到300附近已經尋得全局極值點0。

圖1(b)中存在陷入局部極值現象，PSO、WOA、GWO陷入不同的局部極值中；SMA算法在迭代中多次陷入局部最優，到達1 000次迭代時出現平行于x軸的平行線，均未尋得極值點0；而改進的SMA算法由于策略的引入，避免陷入局部最優，在迭代次數為600左右時，尋得全局極值點0，使得算法的收斂速度優于其他算法。

觀察圖1(c)(多峰函數f3)，PSO算法陷入局部最優值，WOA、GWO、SMA、改進的SMA算法找到全局最優極值點0。WOA和GWO快速跳出局部現象，當迭代次數達到300附近時找到全局最優極值點0，SMA算法在200次附近找到全局極值點，而改進SMA算法比SMA算法提前約150代找到全局極值點0，迭代次數相較SMA算法減少約170代。

在圖1(d)中，PSO、WOA、GWO、SMA算法的收斂曲線均在多策略改進的SMA算法上方，已經出現局部問題，收斂速度慢，而改進的SMA算法在搜索過程中未出現陷入局部極值現象，迭代次數在50左右快速收斂尋得全局最優值8.882×10-16，改進的SMA算法相較于SMA算法收斂速度得到提高。

Griewank(f5)函數能夠測試算法跳出局部能力，改進的SMA算法在迭代次數50之前已經找到全局極值點0，SMA算法出現陷入局部最優的現象。圖1(e)說明引入多策略的改進SMA算法大幅度減少了算法收斂到全局最優值的迭代次數。

從收斂精度分析，表3數據顯示，改進的SMA算法得到的平均值和標準差均優于比較算法，找到f2函數全局極值點0，而SMA算法的最優值為5.330×10-207，未找到全局極值點0，改進算法的收斂精度得到提高。

綜上所述，圖1(a)、(b)中表現出算法的局部開發能力明顯提高，圖1(c)、(d)、(e)在全局搜索方面表現較優，PSO、WOA、GWO、SMA算法存在陷入局部最優的現象，而多策略的改進SMA算法避免了局部極值問題，曲線的收斂速度優于其他算法，能較快找到全局最優值，收斂精度得到較大提高。

3.2.2 改進的SMA算法與SMA、CESMA的仿真實驗分析

為進一步充分驗證改進的SMA算法的有效性，選取SMA、CESMA與改進的SMA算法比較，結果如圖2所示。給出相關算法在30維空間運行30次的數據，記錄最優函數值的標準差和平均值，如表4所示。

圖2 與改進算法對比時f1 ～ f5函數尋優曲線Fig. 2 Optimization curve of function f1 ～ f5 when the improred algorithm compares

表4 改進的SMA算法與CESMA、SMA算法實驗結果對比Tab. 4 Comparison of test function results between improved SMA algorithm, CESMA algorithm and SMA algorithm

圖2給出測試函數在30維空間的尋優曲線。從收斂速度分析，圖2(a)是Sphere(f1)函數仿真結果，改進的SMA算法的收斂曲線位于CESMA和SMA下方，迭代次數為300左右時尋得全局極值點0；而CESMA和SMA在搜索過程中出現較多的局部極值，由于CESMA算法引入Tent混沌映射反向學習策略，相較于SMA算法，更快找到全局最優值。改進的SMA算法引入自適應權值策略和擾動策略，明顯提高了全局搜索能力，迅速朝著全局最優值搜索，避開了局部最優值，算法的收斂速度效果較佳，相較于CESMA算法，迭代次數減少約58%，收斂效果優于CESMA和SMA算法。

圖2(b)是Schwefel 2.22函數仿真結果，改進的SMA在550次左右找到全局極值點0，此時CESMA和SMA陷入局部最優值，無法避免局部極值點，最終未尋到全局極值點0。相較于CESMA和SMA算法，改進的SMA算法尋得全局極值點0，收斂精度相對較高。

在圖2(c)、圖2(e)中，改進的SMA收斂速度優于CESMA和SMA算法，在迭代次數為30左右已經尋得極值點0。CESMA和SMA算法雖然找到全局最優值，但是SMA在迭代過程中經過更多的迭代次數才跳出局部極值現象，跳出局部能力較弱；CESMA算法在迭代次數為60左右時迅速跳出局部，尋得全局最優值0。引入Tent混沌反向學習策略的CESMA算法相較于SMA算法克服了陷入局部極值問題，引入自適應權值策略和擾動策略的改進SMA算法解決了早期容易陷入局部極值問題，同時算法的搜索效率相較于SMA算法和CESMA算法都有所提高。

圖2(d)中改進的SMA相較于CESMA算法尋到全局最優值的迭代次數減少約75%，相較于SMA算法減少約76%。

從收斂精度分析，表4數據中，改進的SMA算法，除f4外均找到極值點0，而CESMA雖然精度高于SMA算法，但二者均未找到f2和f4函數極值點0，多策略的改進SMA算法收斂精度優于CESMA和SMA算法。

綜上所述，圖2(a)、(b)中表現出改進的SMA算法的局部開發能力明顯提高，圖2(c)、(d)、(e)表現出其在全局搜索方面較優。多策略的改進SMA算法通過引入映射反向學習策略提高了算法的收斂精度；引入自適應權值策略和擾動策略進一步提高算法的勘探能力，快速獲得全局最優解。

本文還對算法的收斂速度通過該算法迭代到最優值的迭代次數和平均總運行時間進行綜合評估。表5給出收斂精度較高的3種算法迭代到全局最優值的迭代次數、每代消耗時間、平均總運行時間數據。從表5數據分析可知，改進的SMA算法尋到全局最優值的迭代次數相對較少，在較短時間內找到全局最優值，平均總運行時間也相對較短，進一步說明改進的SMA算法在收斂速度上的優越性。

表5 平均總運行時間Tab. 5 Average total running time

4 結語

針對黏菌算法(SMA)搜索效率低和易陷入局部最優的問題，本文提出一種多策略的改進黏菌算法。通過Tent混沌映射反向學習策略優化初始種群，提高了算法收斂速度。自適應權值策略避免了算法局部極值現象，提高了黏菌靠近和獲取食物的速度，算法的勘探能力和收斂精度得到較大提高。擾動策略對最優位置進行擾動更新，找到較佳的全局最優值，算法能夠避免早熟現象。通過分析測試函數的尋優結果，表明多策略的改進SMA算法打破了早熟現象，獲得較高的搜索效率，不僅收斂速度得到提高，較快地找到全局最優值，而且具有較高的收斂精度，尋得極值點。相較于對比算法，具有較好的全局搜索和跳出局部極值能力，充分驗證了改進算法的有效性。