多策略融合的改進黏菌算法

邱仲睿，苗 虹，曾成碧

（四川大學 電氣工程學院，成都 610065）

0 引言

群智能算法是一種模擬自然界中生物群體（如蟻群、獸群、鳥群、蜂群等）集體行為的元啟發式算法。這些群體在行為過程中互相交互、共享信息，通過學習彼此的經驗來尋找最優的解決方案［1-3］。相較于其他優化方法，群智能算法實現較為簡單，而且優化效率高。常見的群智能算法有粒子群優化（Particle Swarm Optimization，PSO）［4］、灰狼優化（Grey Wolf Optimization，GWO）［5］、黏菌算 法（Slime Mould Algorithm，SMA）［6］等。

SMA 是Li等［6］于2020 年提出的一種新型群智能算法，模擬了黏菌在尋找食物過程中形態和行為的變化。SMA 的權重系數模擬了黏菌在遇到不同濃度的食物時的生物振蕩器產生的正負反饋：當找到高質量食物時，黏菌會快速靠近；當食物濃度較低時，黏菌會緩慢地向它靠近，從而以更高的效率接近最佳的食物源。SMA 代碼結構簡單、可擴展性強，并且在函數優化和工程設計問題上表現出色，目前已被成功應用于圖像分割［7］、蛋白質序列比對［8］、機器人路徑規劃［9］、軸承缺陷識別［10］等領域。

然而，標準SMA 的尋優機制比較簡單，它在優化高維復雜函數和最優解不在原點的函數時容易出現優化結果不穩定、收斂速度慢以及陷入局部最優等問題。針對以上問題，學者們提出了多種改進方法。Naik等［11］將平衡優化器（Equilibrium Optimizer，EO）中的平衡池機制集成于SMA 的搜索模式中，提出一種平衡黏菌算法（Equilibrium Slime Mould Algorithm，ESMA），提高了SMA 的可搜索性；Houssein等［12］將自適應引導差分進化（Adaptive Guided Differential Evolution，AGDE）算法融入標準SMA，采用AGDE 突變的方式增強種群的局部搜索能力，提高了種群的多樣性，并避免SMA 過早收斂；郭雨鑫等［13］提出的改進SMA 通過引入精英反向學習提高種群的質量，并利用二次插值方法計算下一代黏菌個體的位置，提升了算法的收斂精度；Yu等［14］在SMA 的基礎上集成了量子旋轉門（Quantum Rotation Gate，QRG）和水循環（Water Cycle，WC）兩種機制，使算法在探索和開發之間保持平衡，增強了SMA 的局部搜索能力與魯棒性；Houssein等［15］將改進的對立學習（Modified Opposition-Based Learning，MOBL）和正交學習（Orthogonal Learning，OL）策略融入標準SMA，提高了算法的求解精度，避免了算法長時間停留在局部最優值上。

以上改進不同程度地提升了標準SMA 的優化性能，但這些方法大多是不同策略或不同算法與SMA 的簡單融合，并未深入改進SMA 的位置更新公式，SMA 在求解最優解不在原點的函數時仍存在后期收斂速度慢、優化結果與最優解偏差大的問題。因此，本文提出一種多策略融合的改進黏菌算 法（Improved Slime Mould Algorithm with Multi-Strategy fusion，MSISMA）。針對SMA 求解精度低和易陷入局部最優的問題，引入布朗運動和萊維飛行策略，提升算法的搜索能力和跳出局部最優解的能力；改進黏菌的位置更新公式，將SMA 單一的位置更新機制改進為根據算法進行的階段而變化的模式，以改善算法在探索和開發之間的過渡能力，提高算法的收斂速度和尋優精度；引入區間自適應反向學習策略，優化種群質量，提高收斂速度；加入收斂停滯監測策略，即時判斷算法是否陷入收斂停滯，并對陷入停滯狀態的個體進行位置初始化，幫助算法擺脫收斂停滯狀態。為驗證MSISMA 的有效性，選用了23 個測試函數，將MSISMA 與幾種改進的SMA、標準SMA 以及幾種最新的性能優越的群智能算法進行比較，同時使用Wilcoxon 秩和檢驗方法驗證MSISMA 的有效性。實驗結果表明，MSISMA 在收斂速度和求解精度上有較大的優勢。

1 標準黏菌算法

黏菌算法模擬了多頭絨泡菌在覓食階段尋找食物、包圍食物的過程。黏菌的前端呈扇形，后面是相互連接的靜脈網絡。當靜脈接近食物時，黏菌的生物振蕩器會產生擴散波來改變靜脈中細胞質的流動，使黏菌向更好的食物移動。黏菌在接近食物階段的位置更新公式為：

其中：Xb(t)為個體目前發現的最優解的位置；vb是范圍為［-a，a］的一個隨機數；W是黏菌的權重系數；XA(t)和XB(t)為從黏菌中隨機選取的兩個個體的位置；vc是從1 到0 遞減的參數；r為[0，1]的隨機數；p為決定黏菌位置更新方式的參數。p可以用以下公式表示：

其中：S(i)為第i={1，2，…，N}個黏菌個體的適應度；FD為當前迭代下黏菌的最佳適應度。

a值的更新公式如下：

其中：t為當前迭代的次數；tmax表示最大迭代次數。

權重系數W模擬了黏菌在遇到不同濃度的食物時生物振蕩器的振蕩頻率的變化：

其中：r為[0，1]的隨機數；Fb和Fw為當前迭代過程中的最佳適應度和最差適應度；SmellIndex表示個體適應度S按升序排列（在最大值問題中按降序排列）后的個體位置索引。

黏菌在尋找食物的過程中也會分割一部分個體進行隨機探索。綜合上述理論，黏菌的位置更新公式為：

其中：BU和BL是搜索范圍的上限和下限；rand和r為[0，1]區間的隨機數；z是決定隨機分布的黏菌個體占黏菌總體的比例的參數，z=0.03。

2 多策略融合的改進黏菌算法

SMA 是一個簡單有效的算法，有一定的尋優能力，但仍有幾點不足：

1）從黏菌位置更新機制來看，在標準SMA 中，黏菌位置的更新規則由r、p、z三者的大小關系決定。當r＜p時，黏菌的位置更新由當前最優個體的位置和兩個隨機個體的位置決定，此時黏菌表現為在當前最佳位置附近隨機探索。這增強了SMA 前期的全局搜索能力，但無目的的隨機探索也會使SMA 的前期收斂速度變慢。隨著迭代次數增加，黏菌種群會向當前最佳位置靠攏，使SMA 在求解具有多個局部最優值的函數時極易陷入局部最優。當r≥p時，黏菌的位置更新由收斂因子vc和黏菌個體的自身位置決定。隨著迭代次數增加，vc從1 線性收斂到0，使黏菌種群的位置向原點方向收斂。這種位置更新方式不利于最優解不在原點的函數的優化，在優化這類函數時，標準SMA 的求解精度較差。

2）SMA的z參數是一個很小的常數，隨機分布的黏菌個體占總個體的比例很小，SMA 在陷入局部最優時缺乏有效的跳出局部最優的機制。

3）SMA 的尋優機制較簡單，在平衡算法的探索和開發能力上還有較大的提升空間。

針對以上問題，本文提出了多策略融合的改進黏菌算法（MSISMA），在以下方面作出改進：1）引用布朗運動和萊維飛行機制，增加黏菌個體分布的多樣性，增強黏菌在局部區域探索的能力；2）改進黏菌的位置更新策略，使算法在不同階段采用不同的位置更新公式，平衡算法在探索和開發之間的過渡能力；3）采用區間自適應的反向學習策略，增加黏菌分布的多樣性，優化黏菌個體的質量；4）引入收斂停滯監測策略，動態監測算法是否陷入收斂停滯，當監測到算法處于停滯狀態時，該策略會對部分個體的位置重新初始化，避免算法長時間處于收斂停滯狀態。

2.1 布朗運動與萊維飛行

2.1.1 標準布朗運動

布朗運動是一種無規則的隨機游走過程，已被研究者們廣泛用于群智能算法的設計及改進，以提升算法的搜索性能。沙林秀等［16］提出一種基于布朗運動與梯度信息的交替優化算法（Alternately Optimizing Algorithm based on Brownianmovement and Gradient-information，AOABG），在算法全局搜索階段加入布朗運動機制，使種群以最優個體的位置為中心作布朗運動，增強了算法的全局搜索能力。湯安迪等［17］在麻雀搜索算法的基礎上引入布朗運動，增強了算法的全局探索能力，并有助于算法脫離局部最優狀態。在標準SMA 的前期迭代過程中，黏菌個體容易快速向當前種群的最佳位置靠近，導致算法的全局探索能力較差，難以找到全局最優解。本文將標準布朗運動引入MSISMA 迭代前期的位置更新公式中，增加黏菌個體的位置的多樣性，從而提高算法的全局探索能力。

標準布朗運動的步長由均值為0（μ=0）、方差為1（σ2=1）的正態分布概率密度函數決定：

引入布朗運動后的黏菌位置更新公式為：

其中：XC(t)為在適應度排序為前N/3 的個體中隨機選取的個體的位置；α為步長控制因子；RB為布朗運動步長。由式（8）可知，在黏菌的基本位置更新公式上加入布朗運動，可增強黏菌個體的搜索軌跡的隨機性，進而增強算法的搜索能力。

2.1.2 萊維飛行

在標準SMA 中，隨著算法進入迭代后期，黏菌個體的位置分布趨于集中，SMA 容易陷入局部最優，導致收斂停滯。萊維飛行是一種步長服從萊維分布的隨機游走，它的運動方式既有小范圍的游走，也有大距離的跨越。萊維飛行已被廣泛用于優化算法領域，例如帝王蝶優化（Monarch Butterfly Optimization，MBO）［18］和哈里 斯鷹優化器（Harris Hawks Optimizer，HHO）［19］都在種群位置更新公式上引入萊維飛行機制，有效地提升了算法的尋優效果。Mantegna［20］于1994年提出了一種生成萊維分布隨機數的算法，萊維飛行步長s的計算方式如下：

u和v服從均值為0、方差分別為σu、σv的正態分布：

其中：β取值為1.5。

本文使用文獻［20］中的算法模擬萊維飛行，并將萊維飛行引入MSISMA 迭代后期的位置更新公式中，使黏菌個體保持它的位置的活躍性，增加黏菌個體跳出局部極值的概率，從而有效改善標準SMA 在迭代后期易陷入局部最優的缺陷。改進后的黏菌位置更新公式表示如下：

其中：X(t)為t次迭代時黏菌的位置；δ為步長控制因子；RL為萊維飛行步長。

2.2 黏菌位置更新的改進

在標準SMA 中，黏菌的尋優過程主要由當前最佳個體和兩個隨機個體的位置引導，尋優機制比較單一。在迭代初期，下一代黏菌種群的位置受兩個隨機個體的位置的影響，使SMA 全局搜索的效果較差，前期收斂速度較慢；在迭代后期，黏菌種群的位置受收斂因子vc的影響而向原點方向移動，當優化問題的最優解不在原點時，SMA 的尋優過程會受到干擾，導致算法收斂精度較差。為改善SMA 在前期探索和后期開發之間的過渡過程，提高SMA 在迭代前期的收斂速度，優化求解精度，本文改進黏菌位置的更新公式，將位置更新過程劃分為三個階段。

1）階段1。

2）階段2。

3）階段3。

在階段1，r＜p時，黏菌種群位置更新由當前最佳個體和一個隨機個體的位置引導，位置更新模式表現為以當前最佳個體為中心的放射性擴散，階段1 在保證算法的全局搜索能力的同時加快了種群向最優個體移動的過程，以提升算法在前期的收斂速度。在階段2，rand≥z時，黏菌種群位置更新由當前最佳個體和適應度排在前N/3 的一個隨機個體的位置引導，此時種群的搜索軌跡在較優個體所在的區域內；同時在基本位置更新公式上加入了布朗運動，以增強算法在較優個體附近的搜索能力。在階段3，rand≥z時，種群位置更新由當前最佳個體和本體的位置引導，此時種群在最佳個體附近進行局部搜索，以提高算法在迭代后期的尋優精度，加入的萊維飛行機制則給算法提供了跳出局部最優的能力。此外，在三個階段，rand＜z時會對黏菌個體的位置重新隨機，從而使黏菌種群在算法的整個迭代過程都具有多樣性。

2.3 區間自適應反向學習策略

Tizhoosh［21］于2005 年提出了一種反向學習（Opposition-Based Learning，OBL）方法以提升算法的尋優效率。該方法首先計算當前解的反向解，然后將反向解與當前解進行比較，最后保留兩者中更接近最優解的一項用于下次的迭代計算。反向點的定義如下：

定義1反向點。D維空間內有一點h=(x1，x2，…，xD)，且x1，x2，…，xD∈R，xi∈[ai，bi]，i={1，2，…，D}，則h點的反向點為

設優化問題為求解最小值，優化問題的函數為f(x)，當前解為h，反向解為，則解的保留策略為：

其中：t為當前迭代數。

傳統OBL 方法計算反向解時，邊界ai和bi是固定值，生成的反向解的質量可能較差。因此本文提出一種區間自適應反向學習（Interval Adaptative Opposition-Based Learning，IAOBL）策略優化反向學習的邊界，進一步提高反向解的質量。IAOBL的反向解計算公式如下：

其中：i={1，2，…，D}；j={1，2，…，N}；D為求解問題維度；N為種群個體數；t為當前迭代數。IAOBL 策略中的上下邊界隨算法迭代的進行不斷變化，當種群集中到某區域時，生成反向解的上下邊界也在不斷縮小。將IAOBL 引入標準SMA中，有助于提升黏菌種群的整體質量，加快算法的收斂進度。

2.4 收斂停滯監測策略

SMA 在迭代過程中會遇到收斂速度變慢，甚至收斂停滯的情況。為了識別并改善這種情況，本文提出一種收斂停滯監測策略，具體方案如下。

步驟1設gc為算法t次迭代與t-3 次迭代的適應度差值：

其中：t={ 4，5，…，tmax}；tmax為最大迭代次數。

步驟2設gmin為適應度監測因子：

其中：t={4，5，…，tmax}。

步驟3 比較gc與gmin的大小關系，如果gc＜gmin，則視為算法收斂停滯，即對1/3 的黏菌個體進行位置重新隨機的操作：

收斂停滯策略能實時監測算法的收斂狀態，判斷算法是否停止收斂，并在算法進入收斂停滯狀態時對部分種群進行重新初始化，從而增加黏菌個體分布的多樣性，避免算法長時間處于收斂停滯狀態。

2.5 算法具體流程

MSISMA 首先對種群的位置進行初始化，并計算所有個體的適應度和權重系數；然后判斷算法所處的階段，根據不同階段選擇不同的位置更新策略；隨后應用IAOBL 策略生成反向種群，通過解的保留策略對當前種群和反向種群中的個體進行選擇和保留；最后通過收斂停滯監測策略判斷算法是否處于收斂停滯，如果算法處于停滯狀態則對部分個體的位置再進行初始化。MSISMA 的具體步驟如下：

步驟1 算法參數初始化。設置黏菌個體數N，問題維度D，最大迭代次數tmax，搜索邊界BU和BL，黏菌的位置X。

步驟2 計算每個個體的適應度，并對適應度進行排序，記錄最佳適應度Fb和最差適應度Fw。

步驟3 根據式（4）更新黏菌的權重系數W。

步驟4 根據式（13）～（15）更新黏菌個體的位置。

步驟5 根據式（17）生成當前種群的反向種群，并根據式（16）決定要保留的個體。

步驟6 根據式（20）對陷入搜索停滯的黏菌個體進行位置重新隨機。

步驟7 迭代次數加1，判斷結束條件，若滿足，則算法終止，輸出最佳適應度及對應位置；若沒有，則返回步驟2。

2.6 時間復雜度分析

設黏菌種群規模為N，問題維度為D，迭代次數為tmax，則MSISMA 的時間復雜度分析如下。

步驟1 黏菌種群的位置初始化階段需要進行D次運算，時間復雜度為O(D)。

步驟2 計算每個黏菌個體的適應度，時間復雜度為O(N)。對所有黏菌個體的適應度進行排序，時間復雜度為O(N× logN)。

步驟3 計算所有黏菌個體的權重系數，時間復雜度為O(N×D)。

步驟4 更新黏菌個體的位置，時間復雜度為O(N×D)。

步驟5 根據當前黏菌種群的位置生成反向種群，時間復雜度為O(D)。比較當前黏菌種群和反向種群的適應度值，判斷要保留的個體。此過程需要進行N次判斷，時間復雜度為O(N)。

步驟6 判斷算法是否處于收斂停滯狀態，需要1 次計算，時間復雜度為O(1)。若滿足收斂停滯監測條件，則對部分黏菌個體的位置進行重新隨機，時間復雜度為O(N/3)。

所以在滿足收斂停滯監測條件時，MSISMA 的總體時間復雜度為O（D+T（7/3×N+D+N·logN+2ND+1））；不滿足收斂停滯監測條件時，MSISMA 的總體時間復雜度為O（D+T（2N+D+N·logN+2ND+1））。標準SMA 的時間復雜度主要是黏菌種群的位置初始化、適應度計算、適應度排序、權重系數更新以及種群的位置更新，時間復雜度計算為：O（D+T（N+N·logN+2ND）。相較于標準SMA，MSISMA 的時間復雜度最大增加了O（T（4/3×N+D+1））。而2TND遠大于T（4/3×N+D+1），所以MSISMA 與標準SMA 的時間復雜度大致相同。

3 實驗與結果分析

3.1 實驗環境

本次仿真實驗環境如下：CPU 為Intel Core i7-10750H，主頻2.60 GHz；32 GB 內存；Windows 10（64 位）操作系統；運行軟件為Matlab R2021b 64 位。

3.2 測試函數

本節使用了文獻［22］中的23 個基準函數對算法的性能進行測試。其中：f1～f7為多維的單峰函數，這類函數只有一個最小值，因此可以測試算法的收斂速度；f8～f13為多維的多峰函數，這類函數存在多個局部極小值，并且局部極小值的數量隨維度的增加呈指數增長，這類函數可以測試算法定位全局最優解和擺脫局部最優的能力；f14～f23為固定維的多峰函數，這類函數的局部極小值數量較少。

3.3 對比算法及參數設置

為驗證本文的多策略改進黏菌算法（MSISMA）的有效性，將MSISMA 與平衡黏菌算法（ESMA）［11］、黏菌-自適應引導差分進化混合算法（Slime Mould Algorithm combined to Adaptive Guided Differential Evolution，SMA-AGDE）［12］、SMA［6］以及最近提出的海洋捕食者算法（Marine Predators Algorithm，MPA）［23］和平衡優化器（EO）［24］這5 種算法進行比較。為了比較的公平性，設置所有算法的種群規模N=30，維度D=30，最大迭代次數tmax=500，運行次數Times=30。各算法的內部參數設置如表1 所示。

表1 各算法的參數設置Tab.1 Parameter setting for each algorithm

3.4 測試函數實驗結果與分析

所有算法在每個測試函數上獨立運行30 次，記錄下每次運行后的優化結果，然后計算30 次運行結果的平均值（Avg）和標準差（Std），得到結果如表2 所示。

由表2 可以看出，相較于其他算法，MSISMA 在19 個測試函數上獲得了最佳平均值，在12 個測試函數上獲得了最佳標準差值。相較于ESMA、SMA-AGDE、SMA、MPA 和EO，MSISMA 的優化精度平均提高了26.04%、55.97%、36.79%、23.39%和54.18%。

表2 不同算法的測試函數優化結果Tab.2 Test functions optimization results of different algorithms

對于單峰函數f1～f7，MSISMA 在求解f1～f4時的每次運行都能取得函數的全局最優解；對于f5，MSISMA 的求解精度最高，并且標準差最??；MSISMA 求解f6的結果僅次于MPA，但要優于其他改進的SMA；對于f7，MSISMA 計算的平均值和標準差僅次于ESMA。從單峰函數優化結果來看，MSISMA 的表現優于對比算法，且MSISMA 的標準差很小，說明算法有較好的魯棒性。對于可變維多峰函數f8～f13，MSISMA 的優化精度最高，且標準差最小。特別是在函數f8、f12、f13的優化上，MSISMA 明顯優于其他算法。說明MSISMA 解決了SMA 在求解具有多個局部最優解的函數時優化精度不高、容易陷入局部最優的問題。對于f14、f16～f19，MSISMA 的求解精度最高，接近函數的最小值，但標準差不如MPA；對于f15，MSISMA 的優化精度比MPA、EO 差，但優于ESMA、SMA-AGDE 和SMA；對于f20，MSISMA 的表現較差；對于f21、f22和f23，MSISMA 的優化精度提升比較明顯，優化平均值與函數的全局最優值非常接近。綜合來看，MSISMA 無論是在優化精度還是算法的魯棒性上相較于對比算法都更有優勢。

為了更直觀地比較各個算法的收斂速度和求解精度，圖1 給出了算法運行30 次后部分測試函數的平均收斂曲線。對于單峰函數f1和f2，MSISMA 的收斂速度最快，能夠以最快速度收斂到函數的最優值；對于單峰函數f5，MSISMA 的收斂速度最快，運算精度最高，而且沒有在迭代過程中陷入局部最優。對于多峰函數f8、f10、f12、f14和f21，MSISMA 無論是收斂速度還是最后的優化結果都有明顯的優勢。

圖1 部分測試函數收斂曲線對比Fig.1 Comparison of convergence curves of some test functions

3.5 Wilcoxon秩和檢驗

為了進一步評估MSISMA 的性能，本文使用Wilcoxon 秩和檢驗方法來檢驗MSISMA 和對比算法的運行結果是否有顯著性差別。顯著性水平設置為0.05，將所有算法運行30次的優化結果作為樣本。當檢驗的p值大于0.05 時，說明兩種算法的運行結果沒有顯著差異；否則，兩種算法運行結果存在顯著差異。表3 為MSISMA 與對比算法的Wilcoxon 秩和檢驗結果。

由表3 可知，MSISMA 在17 個測試函數上的表現優于ESMA 與SMA，在19 個測試函數上表現優于SMA-AGDE，在12 個測試函數上的表現優于MPA，在16 個測試函數上表現優于EO。因此MSISMA 的性能在統計上有顯著的優越性。

表3 Wilcoxon秩和檢驗結果Tab.3 Wilcoxon rank-sum test results

實驗結果表明，本文提出的多策略融合的改進黏菌算法的收斂速度、求解精度和魯棒性都有明顯提升。

4 結語

為了提高黏菌算法的優化性能，本文提出了一種多策略融合的改進黏菌算法（MSISMA）。引入布朗運動和萊維飛行機制增強算法的搜索能力；改進算法的位置更新公式，以平衡算法在探索和開發之間的過渡能力，提升尋優效率和精度；引入區間自適應的反向學習策略，優化解的質量；引入收斂停滯監測策略，避免算法長時間處于收斂停滯狀態。在測試函數上的實驗結果表明，MSISMA 在收斂速度、尋優精度和魯棒性上比ESMA、SMA-AGDE、SMA、MPA 和EO 更優秀。然而，MSISMA 在優化某些固定維的多峰函數時仍存在精度較低的情況，未來將在種群位置更新模式方面作進一步研究和優化。