基于混沌映射和萊維飛行的黏菌優(yōu)化算法*

龔 然 施文娟 朱振源

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

1 引言

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

針對(duì)標(biāo)準(zhǔn)黏菌算法存在收斂精度較低、迭代后期易陷入局部最優(yōu)等問(wèn)題，學(xué)者們提出了改進(jìn)SMA的方法［7～11］。賈鶴鳴等［7］將算術(shù)優(yōu)化算法與黏菌算法兩種算法結(jié)合，并加入隨機(jī)反向?qū)W習(xí)策略，提出一種融合隨機(jī)反向?qū)W習(xí)的黏菌與算術(shù)混合優(yōu)化算法。郭雨鑫等［8］采取精英反向?qū)W習(xí)策略提高初始黏菌種群的多樣性，利用二次插值方法增強(qiáng)算法局部開發(fā)能力，提出一種精英反向與二次插值改進(jìn)的黏菌算法。劉成漢等［9］將人工蜂群算法與黏菌算法兩種算法結(jié)合，并加入自適應(yīng)可調(diào)節(jié)的反饋因子和交叉算子，提出了改進(jìn)交叉算子的自適應(yīng)人工蜂群黏菌算法。改進(jìn)后的黏菌算法已成功應(yīng)用于特征選擇［10］、圖像分割［11］等領(lǐng)域。

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

2 標(biāo)準(zhǔn)黏菌算法

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

當(dāng)黏菌接近食物時(shí)，黏菌算法的數(shù)學(xué)模型如式（1）表示：

其中，t為當(dāng)前迭代次數(shù)，Xb(t)為第t次迭代時(shí)黏菌個(gè)體最優(yōu)的位置，Xm(t)和Xn(t)為隨機(jī)選擇兩個(gè)黏菌個(gè)體的位置，vb 作為控制參數(shù)范圍是［-a，a］，vc 是從1 線性下降到0 的參數(shù)，r 是［0，1］之間的隨機(jī)值。W 為黏菌質(zhì)量，代表適應(yīng)度權(quán)重。控制變量p和參數(shù)vb的數(shù)學(xué)模型公式如下：

a的計(jì)算公式如式（4）所示：

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

其中，condition 表示適應(yīng)度值排在前一半的黏菌個(gè)體。fitness sequence 為黏菌的適應(yīng)度值序列，當(dāng)求解最小值問(wèn)題時(shí)，其使用升序排列方法。其中，目前迭代次數(shù)中最優(yōu)適應(yīng)度值用OF 表示，最差適應(yīng)度值用MF 表示。當(dāng)黏菌包裹食物時(shí)，黏菌算法的數(shù)學(xué)模型如式（7）所示：

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

當(dāng)黏菌抓取食物時(shí)，黏菌的靜脈組織和生物振蕩器產(chǎn)生變化。靜脈接觸的食物濃度越高，生物振蕩器產(chǎn)生的波越強(qiáng)，依靠這種變化，黏菌會(huì)抓取更高濃度的食物。黏菌靜脈寬度的變化采用W、vb和vc來(lái)實(shí)現(xiàn)。

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

3 基于混沌映射和萊維飛行的黏菌優(yōu)化算法

3.1 Circle混沌映射

大部分群智能優(yōu)化算法的初始種群是由隨機(jī)數(shù)法產(chǎn)生的［12］，SMA算法也是如此。但是隨機(jī)數(shù)法產(chǎn)生的初始種群個(gè)體有一定的偶然性，其產(chǎn)生的初始個(gè)體無(wú)法均勻的分布在搜索空間內(nèi)，容易陷入局部最優(yōu)?；煦缬成渌a(chǎn)生的的混沌序列能夠豐富種群多樣性，可使種群均勻分布在搜索空間內(nèi)，避免算法陷入局部最小值。本文采用Circle 混沌映射初始化黏菌種群，作為混沌映射的代表，其產(chǎn)生的混沌序列分布比較均勻，能夠提升初始黏菌種群的多樣性。Circle映射數(shù)學(xué)模型如式（8）所示：

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

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

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

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

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

其中，μ，v 服從標(biāo)準(zhǔn)正態(tài)分布，其定義如式（11）、式（12）和式（13）所示：

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

3.3 局部隨機(jī)游動(dòng)策略

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

由此可見，利用局部隨機(jī)游動(dòng)的策略加強(qiáng)黏菌算法的局部尋優(yōu)能力，其數(shù)學(xué)模型如式（14）所示：

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

由于不能保證利用隨機(jī)游動(dòng)策略后適應(yīng)度值是否更優(yōu)，因此利用貪婪原則選擇是否更新黏菌算法的最優(yōu)位置，此時(shí)黏菌算法的最優(yōu)位置公式如下。

3.4 CLSMA算法描述

針對(duì)標(biāo)準(zhǔn)黏菌算法收斂速度較慢、初始種群多樣性低等問(wèn)題，本文提出一種基于混沌映射和萊維飛行的黏菌優(yōu)化算法（CLSMA），如算法1所示。

算法1 CLSMA算法流程

輸入：算法種群規(guī)模N，最大迭代次數(shù)tmax，研究問(wèn)題維度D，搜索上界UB，下界LB。

輸出：黏菌位置最優(yōu)解和最佳適應(yīng)度值。

Step1：設(shè)置算法種群規(guī)模N，當(dāng)前迭代t，最大迭代次數(shù)tmax，研究問(wèn)題維度D，搜索上界UB，下界LB；

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

Step3：While t＜tmax時(shí)，計(jì)算適應(yīng)度值，記錄當(dāng)前最優(yōu)適應(yīng)度OF和最差適應(yīng)度MF；

Step4：利用式（5）更新適應(yīng)度權(quán)重W，式（4）更新參數(shù)a；

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

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

Step7：if r ＜p，利用式（9）萊維飛行策略和式（14）局部隨機(jī)游動(dòng)策略更新黏菌位置，同時(shí)利用式（15）貪婪原則選擇更新最優(yōu)的黏菌位置；

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

Step9：判斷t是否大于tmax，若t＞tmax，輸出黏菌位置最優(yōu)解和最佳適應(yīng)度值；若t＜tmax，轉(zhuǎn)向步驟3。

4 仿真實(shí)驗(yàn)分析

4.1 仿真測(cè)試環(huán)境

本文仿真測(cè)試相關(guān)配置為Windows10、64bit操作系統(tǒng)，處理器為Intel（R）Core（TM）i5-10200H，內(nèi)存16G，仿真測(cè)試軟件為Matlab 2017b。

4.2 對(duì)比算法與初始參數(shù)設(shè)置

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

表1 各算法參數(shù)設(shè)置

表2 基準(zhǔn)測(cè)試函數(shù)

4.3 算法對(duì)比分析

CLSMA 算法與對(duì)比算法在基準(zhǔn)測(cè)試函數(shù)上的測(cè)試結(jié)果如表3所示，記錄所測(cè)算法在30次運(yùn)行中所得的最佳平均適應(yīng)度值（mean）以及標(biāo)準(zhǔn)差（Std），其中數(shù)據(jù)加粗表示算法在所在函數(shù)的測(cè)試結(jié)果中最優(yōu)。平均值與標(biāo)準(zhǔn)差的值越小表示算法的性能越好。在F1～F12 函數(shù)的求解結(jié)果中，CLSMA 的求解結(jié)果最優(yōu)，且F1、F3 和F7 都達(dá)到理論最優(yōu)值，其中在F1、F7 和F8 函數(shù)上，CLSMA 和SMA的求解結(jié)果相同，說(shuō)明在這兩個(gè)函數(shù)上，兩個(gè)算法的尋優(yōu)能力相當(dāng)。對(duì)于F2、F4～F6 以及F8～F12 函數(shù)，CLSMA 算法和其余幾種算法都沒(méi)有達(dá)到理論最優(yōu)值，但CLSMA 算法的求解精度最好，可以證明CLSMA 算法比其余幾種算法具有更好的勘探能力。在多峰函數(shù)的測(cè)試結(jié)果發(fā)現(xiàn)，CLSMA 的平均值和標(biāo)準(zhǔn)差最小或并列最小，其中在F7 上達(dá)到了理論最優(yōu)值。對(duì)于F8 和F11，CLSMA 和SMA 的求解結(jié)果相同，但在F11 函數(shù)上CLSMA 的標(biāo)準(zhǔn)差更好。在固定維多峰測(cè)試函數(shù)F11 至F12 的求解結(jié)果中，CLSMA 接近理論最優(yōu)值，且平均值和標(biāo)準(zhǔn)差都優(yōu)于其余幾種算法。綜上所述，對(duì)于單峰函數(shù)和多峰函數(shù)的測(cè)試結(jié)果中，CLSMA 都有較好的求解結(jié)果，證明了CLSMA 在與其余元啟發(fā)式算法比較中有更好的尋優(yōu)精度和穩(wěn)定性。

表3 不同算法的函數(shù)測(cè)試結(jié)果

4.4 收斂曲線分析

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

圖2 各算法在不同測(cè)試函數(shù)下的收斂曲線

5 結(jié)語(yǔ)

本文針對(duì)標(biāo)準(zhǔn)黏菌算法的不足，提出一種基于混沌映射和萊維飛行的黏菌優(yōu)化算法（CLSMA）。引入Circle 混沌映射，利用其產(chǎn)生的混沌序列，豐富初始黏菌種群的多樣性，使種群較均勻的分布在搜索空間內(nèi)；采用萊維飛行策略，增強(qiáng)算法跳出局部最優(yōu)的能力和提高算法的收斂速度；利用布谷鳥算法的局部隨機(jī)游動(dòng)策略增強(qiáng)算法的局部?jī)?yōu)化能力。最后在由單峰函數(shù)、多峰函數(shù)組成的12 個(gè)基準(zhǔn)函數(shù)下進(jìn)行測(cè)試，實(shí)驗(yàn)證明改進(jìn)后的黏菌算法收斂精度、穩(wěn)定性以及全局搜索能力都得到了增強(qiáng)。未來(lái)將進(jìn)一步增強(qiáng)CLSMA 算法的尋優(yōu)性能以及探索其在實(shí)際工程領(lǐng)域的應(yīng)用價(jià)值。