一種改進(jìn)的麻雀搜索算法

劉 睿，莫愿斌

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

2.廣西民族大學(xué) 混雜計(jì)算與集成電路設(shè)計(jì)分析重點(diǎn)實(shí)驗(yàn)室，廣西 南寧 530006；

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

0 引 言

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

在麻雀搜索算法的基礎(chǔ)上，該文提出一種加入螢火蟲(chóng)擾動(dòng)策略的改進(jìn)算法。該改進(jìn)策略主要是在麻雀搜索后，利用螢火蟲(chóng)搜索擾動(dòng)對(duì)麻雀位置進(jìn)行進(jìn)一步的優(yōu)化更新，以提高算法搜索性，增強(qiáng)解的多樣性，從而避免算法陷入局部最優(yōu)。該改進(jìn)策略簡(jiǎn)潔有效，通過(guò)對(duì)6個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，對(duì)比其他算法，表明該算法較SSA尋優(yōu)性能提升明顯，同時(shí)將FSSA應(yīng)用于常見(jiàn)TSP問(wèn)題求解，獲得了較好的結(jié)果，進(jìn)一步驗(yàn)證了所提算法的尋優(yōu)性能。

1 麻雀搜索算法

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

麻雀集合如下所示：

其中，n表示麻雀的規(guī)模，d表示變量的維數(shù)。

麻雀的適應(yīng)度值如下所示：

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

發(fā)現(xiàn)者的位置更新公式為：

(1)

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

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

(2)

麻雀種群中意識(shí)到危險(xiǎn)的麻雀位置更新公式如下：

(3)

2 加入螢火蟲(chóng)搜索擾動(dòng)的麻雀搜索算法

2.1 螢火蟲(chóng)擾動(dòng)策略

螢火蟲(chóng)算法(firefly algorithm，F(xiàn)A)[9]，是由劍橋?qū)W者Yang提出，通過(guò)模擬螢火蟲(chóng)的發(fā)光行為實(shí)現(xiàn)位置優(yōu)化?；镜穆槿杆阉魉惴ù嬖诘娜毕萑缦拢核惴ㄔ诮饪臻g搜尋目標(biāo)時(shí)存在過(guò)早收斂，即容易“早熟”致使最優(yōu)解精度不足，發(fā)現(xiàn)者在位置更新迭代后期容易直接跳躍至當(dāng)前極值附近，導(dǎo)致搜索范圍不夠從而困于局部最優(yōu)，同時(shí)尋優(yōu)精度也會(huì)受到影響。為了改良以上所提到的不足之處，主要在麻雀搜索后，引入螢火蟲(chóng)算法的迭代策略，將螢火蟲(chóng)擾動(dòng)策略應(yīng)用于算法之中，借助螢火蟲(chóng)發(fā)光吸引的特性，尋找鄰域結(jié)構(gòu)內(nèi)位置較優(yōu)的個(gè)體，增強(qiáng)解的多樣性，通過(guò)增加隨機(jī)擾動(dòng)項(xiàng)，擴(kuò)展搜索區(qū)域，提升算法的全局探索能力，有利于引導(dǎo)算法跳出局部最優(yōu)，同時(shí)進(jìn)一步更新麻雀位置，使得種群整體搜索更加充分，有利于提升收斂精度。螢火蟲(chóng)算法涉及到的數(shù)學(xué)建模如下所示。

螢火蟲(chóng)的相對(duì)熒光亮度I為：

I=I0·exp(-γrij)

(4)

其中，I0為最大熒光亮度，是距離為零處自身的熒光亮度，且適應(yīng)度值越優(yōu)的個(gè)體具備的I0值越大；γ為光強(qiáng)吸收系數(shù)，體現(xiàn)螢火蟲(chóng)個(gè)體隨著距離的增加、傳播媒介的吸收影響下熒光的減弱效果；rij為各螢火蟲(chóng)之間的空間距離。

螢火蟲(chóng)的吸引度β為：

(5)

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

螢火蟲(chóng)擾動(dòng)位置更新公式如下：

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

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

2.2 FSSA算法步驟

FSSA算法流程如下：

Step1：初始化種群，設(shè)置種群大小N，最大迭代次數(shù)Iteration，發(fā)現(xiàn)者比例，意識(shí)到危險(xiǎn)的麻雀比例、安全閾值等參數(shù)。

Step2：計(jì)算當(dāng)前麻雀種群個(gè)體的適應(yīng)度值并進(jìn)行排序，找出當(dāng)前最優(yōu)值以及最差值。

Step3：按比例選取適應(yīng)度值較優(yōu)的麻雀作為發(fā)現(xiàn)者，根據(jù)公式(1)更新發(fā)現(xiàn)者位置。

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

Step5：按比例在種群中隨機(jī)選取部分個(gè)體作為意識(shí)到危險(xiǎn)的麻雀，根據(jù)公式(3)更新意識(shí)到危險(xiǎn)的麻雀位置，并計(jì)算新的適應(yīng)度值，如果比當(dāng)前最優(yōu)值好就進(jìn)行更新操作。

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

Step7：利用螢火蟲(chóng)擾動(dòng)公式(6)對(duì)種群進(jìn)行位置更新，并對(duì)處于最優(yōu)位置的螢火蟲(chóng)進(jìn)行隨機(jī)擾動(dòng)。

Step8：計(jì)算適應(yīng)度值，保留最優(yōu)個(gè)體位置。

Step9：檢驗(yàn)是否滿足停止條件，若滿足則算法結(jié)束輸出最優(yōu)結(jié)果，否則轉(zhuǎn)向Step2。

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

為了驗(yàn)證FSSA的尋優(yōu)性能，通過(guò)選取文獻(xiàn)[10-12]中6個(gè)不同類型的基準(zhǔn)測(cè)試函數(shù)，將FSSA與粒子群優(yōu)化算法(particle swarm optimization，PSO)[13]、鯨魚(yú)優(yōu)化算法(whale optimization algorithm，WOA)[14]、SSA算法進(jìn)行仿真對(duì)比實(shí)驗(yàn)。

所有計(jì)算過(guò)程重復(fù)進(jìn)行30次，結(jié)果取最好值、最差值、平均值以及標(biāo)準(zhǔn)差作為算法性能的評(píng)判標(biāo)準(zhǔn)，實(shí)驗(yàn)的集成開(kāi)發(fā)環(huán)境為Matlab(R2018b)，操作系統(tǒng)為win10，64位。設(shè)置四種算法迭代次數(shù)為1 000，種群數(shù)量為100，表1為基準(zhǔn)測(cè)試函數(shù)相關(guān)信息，表2記錄了四種算法的實(shí)驗(yàn)結(jié)果。為了直觀地體現(xiàn)算法的尋優(yōu)效果，圖1給出了基準(zhǔn)函數(shù)的搜索空間以及對(duì)應(yīng)四種算法的收斂曲線。

由表2對(duì)單峰測(cè)試函數(shù)、多峰測(cè)試函數(shù)以及低維多峰測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果可反映出四種算法關(guān)于局部開(kāi)發(fā)能力、全局探索能力以及跳出局部最優(yōu)的能力的強(qiáng)弱；從單峰測(cè)試函數(shù)f1～f3的測(cè)試結(jié)果來(lái)看，F(xiàn)SSA表現(xiàn)出了良好的收斂速度以及尋優(yōu)精度，可以準(zhǔn)確尋優(yōu)到理想值，優(yōu)于其他算法，相比之下改進(jìn)算法有明顯提升。對(duì)于多峰測(cè)試函數(shù)f4和f5，F(xiàn)SSA能夠有效地逃脫局部最優(yōu)并找到全局最優(yōu)解，對(duì)比其他算法，尋優(yōu)結(jié)果數(shù)量級(jí)有較大提升，在取得較好的平均值同時(shí)標(biāo)準(zhǔn)差值較小，說(shuō)明FSSA具有良好的魯棒性，進(jìn)一步說(shuō)明了改進(jìn)算法的有效性。對(duì)于低維多峰測(cè)試函數(shù)f6，雖然FSSA較其他算法尋優(yōu)效果僅有小幅提升，但是FSSA具備的尋優(yōu)精度最高，通過(guò)對(duì)平均值與標(biāo)準(zhǔn)差的對(duì)比，F(xiàn)SSA的尋優(yōu)穩(wěn)定性明顯優(yōu)于其余算法。

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

表2 仿真實(shí)驗(yàn)結(jié)果

圖1 搜索空間及優(yōu)化曲線

4 FSSA在TSP問(wèn)題中的應(yīng)用

4.1 TSP問(wèn)題描述

旅行商問(wèn)題(traveling salesman problem，TSP)，又譯為旅行推銷員問(wèn)題等，最早由Dantzig等人于1959年提出[15]，是組合優(yōu)化中一道著名的NP難問(wèn)題，對(duì)其的求解也一直是學(xué)術(shù)界關(guān)注的熱點(diǎn)。

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

設(shè)各座城市為V=(v1,v2,…,vn)，對(duì)城市的訪問(wèn)順序?yàn)門(mén)=(t1,t2,…,tn)，每座城市之間的距離為d(vi,vj)，則TSP問(wèn)題的目標(biāo)函數(shù)為：

(7)

4.2 仿真實(shí)驗(yàn)

該文采用具有14座城市的TSP問(wèn)題進(jìn)行測(cè)試，各城市的初始坐標(biāo)見(jiàn)表3，設(shè)置種群數(shù)量為100，最大迭代次數(shù)為1 000，分別對(duì)SSA與FSSA進(jìn)行20次獨(dú)立測(cè)試，表4記錄了兩種算法求解TSP問(wèn)題的最好值、最差值和平均值。圖2為各城市初始位置分布情況與FSSA求解TSP的最優(yōu)解，圖3為FSSA、SSA收斂曲線對(duì)比。

表3 14座城市的坐標(biāo)

表4 兩種算法的測(cè)試結(jié)果

圖2 TSP問(wèn)題仿真實(shí)驗(yàn)

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

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

5 結(jié)束語(yǔ)

該文提出了一種加入螢火蟲(chóng)搜索擾動(dòng)的改進(jìn)麻雀搜索算法，通過(guò)在麻雀搜索后利用螢火蟲(chóng)擾動(dòng)策略對(duì)麻雀位置進(jìn)一步的優(yōu)化更新，提高了算法的搜索性，豐富了解的多樣性，同時(shí)采用6種不同的基準(zhǔn)測(cè)試函數(shù)驗(yàn)證了FSSA的尋優(yōu)性能，與PSO、WOA和SSA相比，F(xiàn)SSA具有更好的收斂速度與收斂精度。

最后通過(guò)將FSSA應(yīng)用于具有14座城市的TSP路徑規(guī)劃，取得了較好的結(jié)果，進(jìn)一步驗(yàn)證了FSSA的尋優(yōu)能力。