基于混沌映射和萊維飛行的黏菌優化算法*

龔 然 施文娟 朱振源

（1.鹽城工學院信息工程學院 鹽城 224000）（2.鹽城師范學院物理與電子工程學院 鹽城 224000）

1 引言

近年來，元啟發式優化算法受到工程領域的廣泛關注。研究者們提出了很多先進的元啟發式優化算法來解決復雜的工程領域優化問題，如鯨魚優化算法（Whale Optimization Algorithm，WOA）［1］，灰狼優化算法（Grey Wolf Optimization Algorithm，GWO）［2］，蜻蜓優化算法（Dragonfly Optimization Algorithm，DA）［3］，蟻獅優化算法（Ant Lion Optimization Algorithm，ALO）［4］，飛蛾優化算法（Moth Optimization Algorithm，MOA）［5］。2020 年Li 等［6］提出一種新型元啟發式優化算法，稱為黏菌算法（Slime Mould Algorithm，SMA）。該算法模擬了黏菌在不同濃度環境下的覓食過程以及狀態變化，并且利用權值來模擬黏菌在覓食過程中產生的正負反饋，形成了黏菌發現食物、接近食物以及包裹食物三種不同的狀態。

針對標準黏菌算法存在收斂精度較低、迭代后期易陷入局部最優等問題，學者們提出了改進SMA的方法［7～11］。賈鶴鳴等［7］將算術優化算法與黏菌算法兩種算法結合，并加入隨機反向學習策略，提出一種融合隨機反向學習的黏菌與算術混合優化算法。郭雨鑫等［8］采取精英反向學習策略提高初始黏菌種群的多樣性，利用二次插值方法增強算法局部開發能力，提出一種精英反向與二次插值改進的黏菌算法。劉成漢等［9］將人工蜂群算法與黏菌算法兩種算法結合，并加入自適應可調節的反饋因子和交叉算子，提出了改進交叉算子的自適應人工蜂群黏菌算法。改進后的黏菌算法已成功應用于特征選擇［10］、圖像分割［11］等領域。

綜上所述，雖然近年來一些學者對黏菌算法進行了改進研究，但其依然存在收斂速度過慢、穩定性較低、易陷入局部最優等問題。因此，本文提出一種基于混沌映射和萊維飛行的黏菌優化算法（Chaotic Map and Levy Flight based Slime Mould Optimization Algorithm，CLSMA）。

2 標準黏菌算法

黏菌算法主要模擬的是自然界中多頭絨泡菌在不同食物濃度下的覓食行為以及狀態變化。黏菌主要分泌酶來消化食物，黏菌的前端延伸成扇形，后端由相互連接的靜脈網絡包圍。環境中不同濃度的食物影響著黏菌靜脈網絡中細胞質的流動，從而形成黏菌覓食的不同狀態。

當黏菌接近食物時，黏菌算法的數學模型如式（1）表示：

其中，t為當前迭代次數，Xb(t)為第t次迭代時黏菌個體最優的位置，Xm(t)和Xn(t)為隨機選擇兩個黏菌個體的位置，vb 作為控制參數范圍是［-a，a］，vc 是從1 線性下降到0 的參數，r 是［0，1］之間的隨機值。W 為黏菌質量，代表適應度權重。控制變量p和參數vb的數學模型公式如下：

a的計算公式如式（4）所示：

其中，i∈1，2，3…，n，S（i）是第i個黏菌適應度值，DF為所有迭代中最佳適應度值。適應度權重W 如式（5）所示：

其中，condition 表示適應度值排在前一半的黏菌個體。fitness sequence 為黏菌的適應度值序列，當求解最小值問題時，其使用升序排列方法。其中，目前迭代次數中最優適應度值用OF 表示，最差適應度值用MF 表示。當黏菌包裹食物時，黏菌算法的數學模型如式（7）所示：

其中，UB 與LB 表示搜索范圍的上下邊界，rand 和r表示［0，1］之間的隨機值。z 為自定義參數，設為0.03。

當黏菌抓取食物時，黏菌的靜脈組織和生物振蕩器產生變化。靜脈接觸的食物濃度越高，生物振蕩器產生的波越強，依靠這種變化，黏菌會抓取更高濃度的食物。黏菌靜脈寬度的變化采用W、vb和vc來實現。

W 模擬了不同食物濃度下黏菌在附近的振蕩頻率。vb在［-a，a］之間隨機變化，隨著迭代次數的增加，逐漸趨近于零。vc 的值在［-1，1］之間振蕩，最終趨于0。當黏菌選擇食物時，vb 和vc 之間的相互協同性發揮著重要的作用。

3 基于混沌映射和萊維飛行的黏菌優化算法

3.1 Circle混沌映射

大部分群智能優化算法的初始種群是由隨機數法產生的［12］，SMA算法也是如此。但是隨機數法產生的初始種群個體有一定的偶然性，其產生的初始個體無法均勻的分布在搜索空間內，容易陷入局部最優。混沌映射所產生的的混沌序列能夠豐富種群多樣性，可使種群均勻分布在搜索空間內，避免算法陷入局部最小值。本文采用Circle 混沌映射初始化黏菌種群，作為混沌映射的代表，其產生的混沌序列分布比較均勻，能夠提升初始黏菌種群的多樣性。Circle映射數學模型如式（8）所示：

其中，k 表示映射次數，k=1，2，3，4…；Xk表示第k 次映射函數值；c，d 為混沌參數，當c=0.2，d=0.5 時，Cirle 混沌映射產生的混沌序列更均勻。由圖1 可知Cirle 混沌映射值在［0，1］間較均勻分布，能夠改進黏菌初始種群的多樣性。

圖1 Cirle混沌映射值在［0，1］間的分布

3.2 萊維飛行策略（Levy Flight Strategy）

2008年Ghaemi等［13］提出了萊維飛行策略模擬自然界中隨機行走的現象，包括土壤中的變形蟲、白蟻、陸地上的蒼蠅等。根據這種現象所提出的萊維飛行策略在優化算法中得到了廣泛的應用。作為一種隨機運動，萊維飛行的步長采取了長距離和短距離結合的特性，這種分布特性一方面增強了算法跳出局部最優的能力，另一方面加快了算法的收斂速度。黏菌算法中位置更新公式里采用的是均勻分布產生隨機數，收斂速度較慢，因此可以使用萊維分布的特性對黏菌算法在接近食物r＜p時位置進行更新，其數學模型如式（9）所示：

其中，Xb(t)為第t次迭代時適應度最高的黏菌個體位置，Xm(t)和Xn(t)為隨機選擇兩個黏菌個體的位置，vb作為控制參數范圍是［-a，a］，α表示萊維飛行隨機步長，?表示點乘，Levy（λ）表示遵循萊維分布的路徑方法，且滿足Levy～u=t-λ。萊維分布一般使用正態分布求解隨機數的算法來模擬，其步長計算方式為

其中，μ，v 服從標準正態分布，其定義如式（11）、式（12）和式（13）所示：

其中，σv=1，ε取值1.5［14］。

3.3 局部隨機游動策略

2009 年Yang 等［15］提出了布谷鳥算法（Cuckoo Search Algorithm，CS）模擬了自然界中布谷鳥孵化寄生的一種行為，并且融合了萊維飛行全局隨機游動和局部隨機游動的機制。萊維飛行全局隨機游動可以增強CLSMA 的全局尋優能力，而局部隨機游動策略可以加強算法局部優化的能力。兩種策略的結合能夠優化算法的尋優性能。局部隨機游動通過將算法經過混合變異的方式重新生成新的隨機候選解。

由此可見，利用局部隨機游動的策略加強黏菌算法的局部尋優能力，其數學模型如式（14）所示：

其中X(t+1) 是第t+1 次迭代時適應度最高的黏菌位置，X(t)是第t 次迭代時適應度最高的黏菌位置。τ為縮放因子，是0～1 之間的隨機數，Xf(t)和Xg(t)是第t次迭代時兩個隨機解。

由于不能保證利用隨機游動策略后適應度值是否更優，因此利用貪婪原則選擇是否更新黏菌算法的最優位置，此時黏菌算法的最優位置公式如下。

3.4 CLSMA算法描述

針對標準黏菌算法收斂速度較慢、初始種群多樣性低等問題，本文提出一種基于混沌映射和萊維飛行的黏菌優化算法（CLSMA），如算法1所示。

算法1 CLSMA算法流程

輸入：算法種群規模N，最大迭代次數tmax，研究問題維度D，搜索上界UB，下界LB。

輸出：黏菌位置最優解和最佳適應度值。

Step1：設置算法種群規模N，當前迭代t，最大迭代次數tmax，研究問題維度D，搜索上界UB，下界LB；

Step2：根據式（8），利用Circle 混沌映射初始化種群Xi（i=1，2，3，…，N）；

Step3：While t＜tmax時，計算適應度值，記錄當前最優適應度OF和最差適應度MF；

Step4：利用式（5）更新適應度權重W，式（4）更新參數a；

Step5：for i=1 to N，if rand ＜z，利用式（7）更新黏菌位置；

Step6：利用式（2）和式（3）更新vc、vb和p；

Step7：if r ＜p，利用式（9）萊維飛行策略和式（14）局部隨機游動策略更新黏菌位置，同時利用式（15）貪婪原則選擇更新最優的黏菌位置；

Step8：if r ≥p，利用式（7）的第三個公式更新黏菌位置；

Step9：判斷t是否大于tmax，若t＞tmax，輸出黏菌位置最優解和最佳適應度值；若t＜tmax，轉向步驟3。

4 仿真實驗分析

4.1 仿真測試環境

本文仿真測試相關配置為Windows10、64bit操作系統，處理器為Intel（R）Core（TM）i5-10200H，內存16G，仿真測試軟件為Matlab 2017b。

4.2 對比算法與初始參數設置

為了更好地驗證CLSMA 的算法性能，論文選取了鯨魚算法（Whale Optimization Algorithm，WOA）［1］、灰狼算法（Grey Wolf Optimization，GWO）［2］、蜻蜓算法（Dragonfly Optimization，DA）［3］、蟻獅算法（Ant Lion Optimization，ALO）［4］、標準黏菌算法（SMA）［6］與CLSMA 進行對比。選取12 個不同的測試函數進行仿真實驗，充分研究該算法對不同類型問題的有效性。其中F1～F5 為單峰測試函數，F6～F10為多峰測試函數，F11～F12為固定維多峰測試函數。不同函數的測試目的不同，單峰測試函數由于全局最優解只有一個，可以在同等條件下對比算法的收斂速度。多峰測試函數具有多個局部最優解和一個全局最優解，往往可以使所測算法陷入局部最優，所以其可以檢驗算法跳出局部最優的能力。為了實現公平性，所有算法均在相同的條件下執行，所有算法在每個函數下分別運行30 次。初始參數統一設置為最大迭代次數tmax=500，種群規模N=30，維度D=30。各個算法初始內部參數如表1所示［6］；基準測試函數具體信息如表2所示。

表1 各算法參數設置

表2 基準測試函數

4.3 算法對比分析

CLSMA 算法與對比算法在基準測試函數上的測試結果如表3所示，記錄所測算法在30次運行中所得的最佳平均適應度值（mean）以及標準差（Std），其中數據加粗表示算法在所在函數的測試結果中最優。平均值與標準差的值越小表示算法的性能越好。在F1～F12 函數的求解結果中，CLSMA 的求解結果最優，且F1、F3 和F7 都達到理論最優值，其中在F1、F7 和F8 函數上，CLSMA 和SMA的求解結果相同，說明在這兩個函數上，兩個算法的尋優能力相當。對于F2、F4～F6 以及F8～F12 函數，CLSMA 算法和其余幾種算法都沒有達到理論最優值，但CLSMA 算法的求解精度最好，可以證明CLSMA 算法比其余幾種算法具有更好的勘探能力。在多峰函數的測試結果發現，CLSMA 的平均值和標準差最小或并列最小，其中在F7 上達到了理論最優值。對于F8 和F11，CLSMA 和SMA 的求解結果相同，但在F11 函數上CLSMA 的標準差更好。在固定維多峰測試函數F11 至F12 的求解結果中，CLSMA 接近理論最優值，且平均值和標準差都優于其余幾種算法。綜上所述，對于單峰函數和多峰函數的測試結果中，CLSMA 都有較好的求解結果，證明了CLSMA 在與其余元啟發式算法比較中有更好的尋優精度和穩定性。

表3 不同算法的函數測試結果

4.4 收斂曲線分析

改進后的CLSMA 算法在收斂速度以及收斂精度上得到了明顯的改善。圖2 給出了各算法在12個不同測試函數下的收斂曲線。整體收斂曲線的趨勢表明，CLSMA 的收斂速度和收斂精度優于其它算法。對于測試函數F1～F5，CLSMA從迭代開始收斂曲線明顯下降，收斂速度快，證明CLSMA 在單峰測試函數上具有一定的優勢，算法的尋優性能較好。對于F2 和F4 函數，CLSMA 算法沒有達到理論最優值，但相較于其它算法，其更接近理論最優值，證明SMA 算法在引入Circle 混沌映射和萊維飛行策略后，CLSMA 算法能夠更快地達到最優解，增強了SMA 算法的有效勘探能力和收斂速度。對于多峰測試函數F6～F10，CLSMA 的收斂效果明顯優于其它算法，其中對于F6 和F8 測試函數，CLSMA 在迭代初期便達到全局最優值，證明了改進后的算法有較好的全局探索能力。對于F7 和F9 函數，CLSMA 能夠快速地跳出局部最優解，并且更接近最優值。對于固定維多峰函數F11 和F12，CLSMA 的收斂速度較優于其余算法。

圖2 各算法在不同測試函數下的收斂曲線

5 結語

本文針對標準黏菌算法的不足，提出一種基于混沌映射和萊維飛行的黏菌優化算法（CLSMA）。引入Circle 混沌映射，利用其產生的混沌序列，豐富初始黏菌種群的多樣性，使種群較均勻的分布在搜索空間內；采用萊維飛行策略，增強算法跳出局部最優的能力和提高算法的收斂速度；利用布谷鳥算法的局部隨機游動策略增強算法的局部優化能力。最后在由單峰函數、多峰函數組成的12 個基準函數下進行測試，實驗證明改進后的黏菌算法收斂精度、穩定性以及全局搜索能力都得到了增強。未來將進一步增強CLSMA 算法的尋優性能以及探索其在實際工程領域的應用價值。