錢 敏，黃海松，范青松

(貴州大學現代制造技術教育部重點實驗室，貴州 貴陽 550025)

1 引言

近期，群體智能(Swarm Intelligence，SI)優(yōu)化算法備受學者的關注，如Kennedy等人[1]模擬自然界中鳥群捕食行為，研究種群覓食的搜索機制從而提出了一種全局尋優(yōu)的粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)；Suash Deb等人[2]模擬布谷鳥獨特的寄生行為，運用與其它鳥類相似的飛行搜索策略，從而提出了一種布谷鳥搜索算法(Cuckoo Search Via Lévy Flights，CS)；Seyedali Mirjalili等人[3]模擬狼群中的頭狼引導群體捕食的社會行為進行數學建模，從而提出了一種灰狼算法(Grey Wolf Optimizer，GWO)。此外，根據鯨魚自身的泡泡網覓食方法進行食物的搜索，與改進螺旋方式進行位置的更新，而提出了一種鯨魚優(yōu)化算法[4](Whale Optimization Algorithm，WOA)。由于SI算法參數僅存在少數需要調整、易于實現且操作難度低，所以在各個領域應用廣泛[5-8]。

無免費午餐定理(No Free Lunch，NFL)[9]表明任何一種算法只能解決一部分問題而不能優(yōu)化工程實際中存在的所有問題，因而不斷有學者提出改進的SI算法。如劉雪紅等人[10]提出一種可行領域結構與精英分批兩種策略對候鳥算法進行改進，有效提高了算法全局搜索效率(Improved Migrating Birds Optimization，IMBO)：張文勝等人[11]提出一種自適應遞減的收斂因子，并在灰狼位置更新公式引入慣性權重從而協調算法的全局領導與開發(fā)能力(Transformed Grey Wolf Optimizer Algorithm，TGWO)；王樂洋等人[12]通過采用分段慣性因子調整粒子速度，修改局部和全局最優(yōu)解的加速因子從而降低算法后期陷入局部最優(yōu)的風險(Dynamic Particle Swarm Optimization，DPSO)；吳澤忠等人[13]在初始化種群時采用反向學習策略及隨機調整控制參數策略，利用正態(tài)變異算子與改進螺旋更新位置對鯨魚種群進行干擾從而提高全局搜索速度(Improved The Whale Optimization Algorithm，IMWOA)。麻雀搜索算法(Sparrow Search Algorithm，SSA)是由Jiankai Xue等人[14]于2020年提出的一種新型SI優(yōu)化算法。該算法模擬麻雀的覓食和反捕食行為，具體為一類麻雀領導覓食，另一類麻雀跟隨并搶奪食物等過程找尋全局最優(yōu)食物來源等一系列的捕食行為。與其它現有算法相比，SSA求解精度、收斂速度、穩(wěn)定性和魯棒性均有較好的性能，但仍無法避免種群尋優(yōu)前期多樣性較差導致搜尋速度較慢，降低了整體搜索速度，后期也存在陷入局部最優(yōu)的風險。

本文針對SSA種群初始質量較差與后期易陷入局部最優(yōu)的缺陷提出了新的改進方案，在SSA搜索前期，利用反向學習策略豐富種群多樣性加快全局收斂速度，后期引入混沌策略進行干擾以降低陷入局部最優(yōu)的風險。通過與其余四種SI算法相比，ISSA在求解12個基本測試函數函數上尋優(yōu)性能更好，且能夠有效提高算法的收斂精度及穩(wěn)定性。

2 麻雀搜索算法

SSA是模擬自然界中麻雀覓食和搶食行為的一種新型SI優(yōu)化算法。SSA將麻雀種群分為領導者與跟隨者兩類，種群中的領導者積極尋找食物來源，跟隨者則由領導者引導覓食從而獲取食物。為更快地獲取食物，跟隨者會不停地監(jiān)視領導者的行為，若發(fā)現比自身更好的食物來源時，便上前進行搶奪。成功掠食則意味跟隨者擁有了更好的食物來源，麻雀的身份便由跟隨者轉換為領導者，發(fā)現危險時引導麻雀逃離[14]。種群中領導者位置更新的數學模型如下

(1)

其中，第i只麻雀在第d維空間上的位置由xi，d表示。j=1，2，…，d，t是當前迭代次數。M是最大迭代次數，α∈(0，1]是隨機數，R2∈(0，1]和ST∈(0.5，1.0]分別表示警報值和安全閥值。Q是服從均值為0標準差為1的高斯分布的隨機數，L是每個元素都為1的1×d矩陣。當R2

種群里的追隨者在覓食的同時會監(jiān)視領導者，一旦發(fā)現位置更好的領導者便立即前往進行搶奪。若搶奪失敗，則繼續(xù)跟隨覓食；其位置更新如下

(2)

意識到危險的麻雀占種群數量的20%，其位置更新如下

(3)

SSA算法流程見圖1。

圖1 SSA算法流程圖

3 改進的麻雀算法

3.1 反向學習初始化種群

反向學習策略 (Opposition-based Learning，OBL)由Tizhoosh 等人[15]引入，此策略被學者廣泛應用于SI算法，并取得了較好的實驗效果[16-19]。SSA在尋優(yōu)前期采用隨機初始化種群，導致搜索初期種群的多樣性較差從而影響全局搜索的效率。種群初始化的質量好壞是影響全局尋優(yōu)快慢的重要因素，因此本文在麻雀種群初始位置引入反向學習策略，擴大麻雀的搜索空間提高種群初期質量以增強全局搜索能力。反向學習策略通過選擇原始種群和對立種群的最優(yōu)解形成新的麻雀種群，其偽代碼如下。

Algorithm 1 initiation based on opposition-based learning

Set population size n，Search range boundary maximumμ，boundary minimum l，opposite solution oxi，j

fori=1to n do

for j=1to n do

xi，j=li，j+rand(0，1)·(μi，j-li，j)

end for

end for

for i=1 to n do

for j=1 to n do

oxi，j=li，j+μi，j-xi，j

end for

end for

{x(n)∪ox(n)}，Choose a better population

3.2 Sinusoidal map種群擾動

混沌系統具有隨機性、遍歷性，因此將混沌理論與SI算法結合是改進優(yōu)化算法的一種思路，研究表明其能有效逃離局部最優(yōu)和提高收斂精度[20-23]。SSA在尋找最優(yōu)解時可能會陷入局部最優(yōu)，其會導致尋優(yōu)精度與收斂速度的降低。因此，本文在麻雀搜索后期引入Sinusoidal map混沌映射[24]，避免麻雀種群在搜索過程中陷入局部最優(yōu)。Sinusoidal map映射的數學表達式如下

(4)

麻雀經過擾動后的位置如下

xSi=g(i)·xi

(5)

通過對比擾動前后種群中麻雀的位置，保留適應度值較優(yōu)的麻雀。其中g(1)=0.7，a=2.3。

3.3 改進麻雀算法(ISSA)算法步驟

ISSA算法流程圖見圖2，詳細步驟如下：

Step1：設置麻雀算法初始參數，麻雀種群數量n，當前迭代次數t，領導者數量PD，跟隨者數量SD，最大迭代次數G。

Step2：隨機生成麻雀個體位置，再引入反向策略得到麻雀對立位置。

Step3：計算麻雀種群適應度值并進行排序，得到xp及xworst。

Step4：根據等式(1)更新種群中的領導者位置。R2

Step5：根據等式(2)更新跟隨者位置，跟隨者覓食同時會監(jiān)視領導者并搶奪食物。

Step6：根據等式(3)更新意識到危險的麻雀位置。

Step8：重復Step4至Step7，直至滿足尋優(yōu)要求結束。

圖2 ISSA算法流程圖

4 仿真研究

4.1 測試函數及對比函數

為驗證改進麻雀算法的尋優(yōu)能力，本文將它用于求解12個國際上通用的標準測試函數，并與SSA、TGWO、WOA與DPSO進行實驗比較。測試函數見表1所示，其中F1-F7是單峰測試基準函數，F8-F12是多峰測試基準函數其測試函數具體表達式及變量范圍。單峰函數用來衡量算法的局部開發(fā)能力，多峰函數衡量全局搜索與局部開發(fā)的平衡性能。

表1 標準測試函數(維度=30)

4.2 實驗參數設置

本文算法參數設置為：迭代次數為1000，種群數量為100。TGWO算法中，φmax=0.9，φmin=0.4；WOA算法參數a在整個搜索中由2下降為0；DPSO中C1s=C2e=1，C1e=C2s=2.05。本文實驗中ISSA與其余四種算法各運行30次，分別計算Ave與Std并把保存結果。算法的優(yōu)化性能的好壞采用平均值(Ave)與標準差(Std)去衡量。平均值的大小代表了算法的收斂速度的快慢，算法的魯棒性的優(yōu)劣則由標準差的大小衡量，實驗結果見表2、表3、表4及表5。

4.3 實驗分析

表2 基準函數測試結果1

表3 基準函數測試結果2

表4 基準函數測試結果3

表5 基準函數測試結果4

由表2至表4可知，ISSA，SSA與TGWO三種算法在求解單峰基準測試函數F1、F3時皆能收斂至函數最小值0且算法的穩(wěn)定性強，WOA與DPSO算法則相對表現較差。在求解函數F2，F4，F5，F6時，Ave值與Std值可以清晰得到ISSA收斂精度與穩(wěn)定性優(yōu)于其余四種算法。在求解函數F7時，ISSA局部開發(fā)能力相比于TGWO算法表現較差，但明顯優(yōu)于SSA，WOA，DPSO其余三種算法。根據上述分析可得，ISSA能有效增強原算法的尋優(yōu)性能與局部開發(fā)能力，并有效提高了SSA的全局收斂精度。

多峰基準測試函數含有多個局部高峰，優(yōu)化算法求解時極易陷入局部最優(yōu)，因此多峰基準測試函數通常用于測試算法逃離局部最優(yōu)的能力。ISSA，SSA，TGWO，WOA在求解函數F8時皆能收斂到全局最優(yōu)值，同時四種算法的穩(wěn)定性也相對較優(yōu)。求解函數F9時，ISSA與SSA沒有收斂到函數最小值，但也明顯優(yōu)于其余三種算法。針對求解F11，F12函數時，其尋優(yōu)精度顯然高于其余四種算法且能很好地平衡算法全局搜索與局部開發(fā)。總體而言，ISSA在求解多峰函數時較于其它算法均表現更優(yōu)，能更好地降低算法陷入局部最優(yōu)的風險從而提高整體搜索速度。

為更直觀顯示實驗對比分析結果，本文給出ISSA與其余四中算法在相同實驗條件下得到的函數仿真曲線，見圖3。

由圖3可知，與另外四種算法相比，ISSA在函數F1，F2，F3上收斂速度更快。針對函數F4，F5，ISSA前期搜索速度較慢，但后期局部搜索速度明顯優(yōu)于SSA。求解函數F6時，ISSA收斂速度與精度略優(yōu)于SSA。

圖3 算法對比尋優(yōu)曲線

根據上述實驗數據可知，TGWO在求解F7時速度顯然比其余四種算法更好，但由收斂曲線圖可看出ISSA算法性能與TGWO接近。通過求解F8，F10函數結果也可看出ISSA收斂更快，從其余的收斂曲線也能清晰得到ISSA收斂速度與逃離局部最優(yōu)的能力都優(yōu)于SSA，TGWO，WOA，DPSO。

綜上所述，改進后的算法在搜索中能有效改善全局尋優(yōu)精度，提高了算法穩(wěn)定性，并使算法具有較強的逃離局部最優(yōu)的能力。

5 結語

麻雀算法是模擬麻雀覓食行為的一種仿生智能算法，本文針對其尋優(yōu)過程中精度不足的缺陷，并具有陷入局部最優(yōu)的風險提出一種改進的麻雀算法。麻雀尋優(yōu)前期實施反向學習策略以增加初始種群的多樣性，從而增加全局搜索速度；在后期引入Sinusoidal map混沌思想以增強逃離局部最優(yōu)的能力。通過求解12個基本測試函數并與其余四種智能算法進行比較，ISSA能有效提高算法的收斂精度，且提高整個搜索過程的搜索速度與穩(wěn)定性。