一種改進的麻雀搜索算法

劉 睿，莫愿斌

(1.廣西民族大學 電子信息學院，廣西 南寧 530006；

2.廣西民族大學 混雜計算與集成電路設計分析重點實驗室，廣西 南寧 530006；

3.廣西民族大學 人工智能學院，廣西 南寧 530006)

0 引 言

麻雀搜索算法(sparrow search algorithm，SSA)[1]是2020年由薛建凱和沈波提出的一種群體智能優化算法，該算法模擬了麻雀的覓食行為和反捕食行為，具有實現簡單、調節參數少的優點，并且在文獻[2-3]中與其他群體智能優化算法進行了對比，在收斂速度、搜索精度、穩定性方面有一定的優勢，是一種很有潛力的群智能優化算法。如今，SSA在支持向量機故障診斷[4]、動態路徑規劃[5]、工控入侵檢測[6]等眾多領域得到了廣泛的應用。然而，SSA與其他群體智能算法類似，在優化過程中也存在著易陷入局部最優、收斂精度不足等缺陷，需要進一步的研究和探索。眾多學者針對SSA存在的不足進行改進，其中李敦橋[7]首先采用反向對立學習策略將麻雀種群進行初始化，再結合模擬退火算法產生的Metropolis準則對當前解與新解比較替換，提高了算法的尋優能力；呂鑫等人[8]受BSA算法的啟發，對發現者和加入者位置更新公式做出了改進，保障了全局收斂，同時具有一定的種群多樣性。上述改進策略均在一定程度上避免了SSA陷入局部最優，提升了算法的性能，但SSA在尋優精度、收斂速度以及穩定性等方面仍有待進一步改善。

在麻雀搜索算法的基礎上，該文提出一種加入螢火蟲擾動策略的改進算法。該改進策略主要是在麻雀搜索后，利用螢火蟲搜索擾動對麻雀位置進行進一步的優化更新，以提高算法搜索性，增強解的多樣性，從而避免算法陷入局部最優。該改進策略簡潔有效，通過對6個基準測試函數進行仿真實驗，對比其他算法，表明該算法較SSA尋優性能提升明顯，同時將FSSA應用于常見TSP問題求解，獲得了較好的結果，進一步驗證了所提算法的尋優性能。

1 麻雀搜索算法

SSA算法的設計靈感來源于鳥類的生物特性，依據麻雀的覓食行為建立的數學模型可歸類為發現者-加入者模型，并加入了預警的機制，隨機選取種群中的部分麻雀作為意識到危險的麻雀建立反捕食機制。每只麻雀是搜索空間中的一個粒子，可以代表問題的一個解。設定在種群中有發現者(Producer)和加入者(Scrounger)兩種角色，發現者具備較高的適應度值，為加入者提供覓食即粒子搜索的方向和區域，引導種群進行搜索。麻雀個體在兩種身份之中的變化處于動態平衡，且適應度值的變化決定了加入者是否跟隨發現者。種群遭遇危險時，將觸發反捕食行為，當預警值大于安全值時，加入者會追隨發現者進行位置更新前往更安全區域覓食，在邊緣的麻雀會向著群體中心更新自己的位置以規避危險，而位于種群中心的麻雀則會進行隨機游走。

麻雀集合如下所示：

其中，n表示麻雀的規模，d表示變量的維數。

麻雀的適應度值如下所示：

其中，f([xi,d])表示個體適應度值。

發現者的位置更新公式為：

(1)

其中，t為當前的迭代數，itermax為最大迭代數，α為(0,1]之間均勻分布的隨機數，R2∈[0,1]，ST∈[0.5,1]分別表示預警值與安全值。Q為服從正態分布的隨機數，L為1×d的矩陣，其中每個內部元素均為1。當R2

加入者的位置更新公式為：

(2)

麻雀種群中意識到危險的麻雀位置更新公式如下：

(3)

2 加入螢火蟲搜索擾動的麻雀搜索算法

2.1 螢火蟲擾動策略

螢火蟲算法(firefly algorithm，FA)[9]，是由劍橋學者Yang提出，通過模擬螢火蟲的發光行為實現位置優化。基本的麻雀搜索算法存在的缺陷如下：算法在解空間搜尋目標時存在過早收斂，即容易“早熟”致使最優解精度不足，發現者在位置更新迭代后期容易直接跳躍至當前極值附近，導致搜索范圍不夠從而困于局部最優，同時尋優精度也會受到影響。為了改良以上所提到的不足之處，主要在麻雀搜索后，引入螢火蟲算法的迭代策略，將螢火蟲擾動策略應用于算法之中，借助螢火蟲發光吸引的特性，尋找鄰域結構內位置較優的個體，增強解的多樣性，通過增加隨機擾動項，擴展搜索區域，提升算法的全局探索能力，有利于引導算法跳出局部最優，同時進一步更新麻雀位置，使得種群整體搜索更加充分，有利于提升收斂精度。螢火蟲算法涉及到的數學建模如下所示。

螢火蟲的相對熒光亮度I為：

I=I0·exp(-γrij)

(4)

其中，I0為最大熒光亮度，是距離為零處自身的熒光亮度，且適應度值越優的個體具備的I0值越大；γ為光強吸收系數，體現螢火蟲個體隨著距離的增加、傳播媒介的吸收影響下熒光的減弱效果；rij為各螢火蟲之間的空間距離。

螢火蟲的吸引度β為：

(5)

其中，β0為最大吸引度，即個體光源處的吸引度。

螢火蟲擾動位置更新公式如下：

xi=xi+β·(xj-xi)+α·[rand(*)-1/2] (6)

其中，xi和xj為麻雀i和j的空間位置，α為步長控制參數，rand(*)∈[0,1]為服從均勻分布的隨機因子。

2.2 FSSA算法步驟

FSSA算法流程如下：

Step1：初始化種群，設置種群大小N，最大迭代次數Iteration，發現者比例，意識到危險的麻雀比例、安全閾值等參數。

Step2：計算當前麻雀種群個體的適應度值并進行排序，找出當前最優值以及最差值。

Step3：按比例選取適應度值較優的麻雀作為發現者，根據公式(1)更新發現者位置。

Step4：種群中剩下的作為加入者，根據公式(2)更新加入者位置。

Step5：按比例在種群中隨機選取部分個體作為意識到危險的麻雀，根據公式(3)更新意識到危險的麻雀位置，并計算新的適應度值，如果比當前最優值好就進行更新操作。

Step6：引入螢火蟲算法，此時種群中搜索粒子等價于螢火蟲個體；依據上一步迭代后的位置，計算適應度函數值作為各螢火蟲最大熒光亮度I0，并根據公式(4)、(5)計算螢火蟲的熒光亮度I與吸引度β，決定種群的搜索方向。

Step7：利用螢火蟲擾動公式(6)對種群進行位置更新，并對處于最優位置的螢火蟲進行隨機擾動。

Step8：計算適應度值，保留最優個體位置。

Step9：檢驗是否滿足停止條件，若滿足則算法結束輸出最優結果，否則轉向Step2。

3 基準函數測試

為了驗證FSSA的尋優性能，通過選取文獻[10-12]中6個不同類型的基準測試函數，將FSSA與粒子群優化算法(particle swarm optimization，PSO)[13]、鯨魚優化算法(whale optimization algorithm，WOA)[14]、SSA算法進行仿真對比實驗。

所有計算過程重復進行30次，結果取最好值、最差值、平均值以及標準差作為算法性能的評判標準，實驗的集成開發環境為Matlab(R2018b)，操作系統為win10，64位。設置四種算法迭代次數為1 000，種群數量為100，表1為基準測試函數相關信息，表2記錄了四種算法的實驗結果。為了直觀地體現算法的尋優效果，圖1給出了基準函數的搜索空間以及對應四種算法的收斂曲線。

由表2對單峰測試函數、多峰測試函數以及低維多峰測試函數的實驗結果可反映出四種算法關于局部開發能力、全局探索能力以及跳出局部最優的能力的強弱；從單峰測試函數f1～f3的測試結果來看，FSSA表現出了良好的收斂速度以及尋優精度，可以準確尋優到理想值，優于其他算法，相比之下改進算法有明顯提升。對于多峰測試函數f4和f5，FSSA能夠有效地逃脫局部最優并找到全局最優解，對比其他算法，尋優結果數量級有較大提升，在取得較好的平均值同時標準差值較小，說明FSSA具有良好的魯棒性，進一步說明了改進算法的有效性。對于低維多峰測試函數f6，雖然FSSA較其他算法尋優效果僅有小幅提升，但是FSSA具備的尋優精度最高，通過對平均值與標準差的對比，FSSA的尋優穩定性明顯優于其余算法。

表1 基準測試函數

表2 仿真實驗結果

圖1 搜索空間及優化曲線

4 FSSA在TSP問題中的應用

4.1 TSP問題描述

旅行商問題(traveling salesman problem，TSP)，又譯為旅行推銷員問題等，最早由Dantzig等人于1959年提出[15]，是組合優化中一道著名的NP難問題，對其的求解也一直是學術界關注的熱點。

TSP問題可描述為：假設一位旅行商需要途經若干城市以推銷其貨物，從其中一座城市出發，遍歷每座城市一次最后回到出發點，且各城市之間位置已知，則如何選取、規劃路線才能使得旅行商總行程最短。

設各座城市為V=(v1,v2,…,vn)，對城市的訪問順序為T=(t1,t2,…,tn)，每座城市之間的距離為d(vi,vj)，則TSP問題的目標函數為：

(7)

4.2 仿真實驗

該文采用具有14座城市的TSP問題進行測試，各城市的初始坐標見表3，設置種群數量為100，最大迭代次數為1 000，分別對SSA與FSSA進行20次獨立測試，表4記錄了兩種算法求解TSP問題的最好值、最差值和平均值。圖2為各城市初始位置分布情況與FSSA求解TSP的最優解，圖3為FSSA、SSA收斂曲線對比。

表3 14座城市的坐標

表4 兩種算法的測試結果

圖2 TSP問題仿真實驗

圖3 兩種算法求解TSP的收斂曲線

從表4的實驗結果可以看出，FSSA算法在求解TSP問題時可以在最大迭代次數內尋找到最優解，且隨著實驗次數的增多平均值仍近似等于最優值，體現了FSSA良好的魯棒性；通過圖3可看出，SSA的迭代收斂次數近似于400次，而FSSA在迭代少于50次時即完成收斂產生最優路徑長度30.98，說明該文所提算法具有較快的收斂速度與較高的收斂精度；對比最終求解結果，FSSA較SSA在獲得的最優解上提升了3.34%，最差解上提升了16.60%，平均值上提升了10.51%，進一步說明了該算法的有效性。

5 結束語

該文提出了一種加入螢火蟲搜索擾動的改進麻雀搜索算法，通過在麻雀搜索后利用螢火蟲擾動策略對麻雀位置進一步的優化更新，提高了算法的搜索性，豐富了解的多樣性，同時采用6種不同的基準測試函數驗證了FSSA的尋優性能，與PSO、WOA和SSA相比，FSSA具有更好的收斂速度與收斂精度。

最后通過將FSSA應用于具有14座城市的TSP路徑規劃，取得了較好的結果，進一步驗證了FSSA的尋優能力。