基于t分布變異的改進(jìn)麻雀搜索算法*

吳超略，韋文山，郭 羿，鄔貴昌

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

0 引言

群智能優(yōu)化算法是一種仿生算法，旨在模擬自然界中某些生物的行為或某些物理現(xiàn)象，因其尋優(yōu)能力強(qiáng)、操作簡單等特點(diǎn)，被許多科研人員研究。常見的群智能優(yōu)化算法有：粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)[1]、螢火蟲算法(Firefly Algorithm，F(xiàn)A)[2]、灰狼 優(yōu) 化算 法 (Grey Wolf Optimizer，GWO)[3]、烏鴉搜索算法(Crow Search Algorithm，CSA)[4]和飛蛾火焰優(yōu)化算法(Moth-Flame Optimization，MFO)[5]。受自然界中麻雀種群覓食行為的啟發(fā)，薛建凱[6]等人于2020年提出了麻雀搜索算法(Sparrow Search Algorithm，SSA）。相比之下，該算法擁有更優(yōu)的收斂率、更高的精度和易于實(shí)現(xiàn)等特點(diǎn)。但是，在算法運(yùn)行的末期，SSA算法也不能避免收斂速度下降、易陷入局部最優(yōu)的問題。

為了改善麻雀搜索算法跳出局部最優(yōu)難的問題，加強(qiáng)算法運(yùn)行效率，許多學(xué)者提出了有效的改進(jìn)策略：呂鑫等[7]通過Tent混沌序列初始化麻雀種群，同時(shí)引入高斯變異和Tent混沌擾動(dòng)對個(gè)體進(jìn)行變異和擾動(dòng)，使算法不易陷入局部最優(yōu)點(diǎn)；柳長安等[8]融合反向?qū)W習(xí)策略和自適應(yīng)t分布變異，引入精英粒子，擴(kuò)大了算法搜索范圍，增強(qiáng)算法后期局部搜索能力；付華等[9]在加入者位置更新時(shí)加入雞群算法的隨機(jī)跟隨策略，保證多樣性的同時(shí)又提高了搜索性能；Zhang等[10]利用Logistic混沌映射對種群位置進(jìn)行初始化提高初始解的質(zhì)量，為了加快SSA算法的收斂速度和效率，采用兩個(gè)自適應(yīng)參數(shù)更新發(fā)現(xiàn)者位置和預(yù)警麻雀數(shù)量。

以上改進(jìn)措施雖然能在一定程度上提高算法跳出局部最優(yōu)的能力，然而，問題仍然存在，如搜索精度不夠、收斂速度不快等?；诖耍疚奶岢鲆环N基于t分布變異的改進(jìn)麻雀搜索算法(t-SSA)，該算法在加入者位置更新后，引入自適應(yīng)t分布變異，對加入者位置進(jìn)行擾動(dòng)變異，避免陷入局部最優(yōu)，提高算法的尋優(yōu)精度。通過在6個(gè)基準(zhǔn)函數(shù)上進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，與SSA算法相比，t-SSA算法具有更好的優(yōu)化精度和更快的收斂速度。

1 麻雀搜索算法的基本原理

麻雀搜索算法(SSA)受自然界中麻雀捕食行為和反捕食行為影響，將麻雀種群抽象為三類：發(fā)現(xiàn)者、加入者和預(yù)警者。其中，發(fā)現(xiàn)者具有較高的適應(yīng)度值，負(fù)責(zé)為麻雀種群尋找食物區(qū)域，并把相關(guān)區(qū)域和方向提供給加入者；為了得到更好的食物，提高自身適應(yīng)度值，加入者會(huì)一直跟隨具有較高適應(yīng)度值的發(fā)現(xiàn)者，不斷監(jiān)視發(fā)現(xiàn)者進(jìn)而爭奪食物；當(dāng)預(yù)警者發(fā)現(xiàn)捕食者后會(huì)立即向種群中的麻雀發(fā)出警報(bào)，此時(shí)處于種群邊沿的個(gè)體會(huì)快速地朝安全區(qū)域飛去，即反捕食行為。此外，在SSA算法中，麻雀種群的發(fā)現(xiàn)者和加入者的身份并不是一成不變的，假如能尋覓到更優(yōu)的食物區(qū)域，每只麻雀都能是發(fā)現(xiàn)者，不過二者在種群總數(shù)量中的比重是固定的。

在SSA算法中，麻雀種群的表示形式為：

其中，n為麻雀的數(shù)量；d為待優(yōu)化變量的維度。可用下述形式來代表麻雀種群的適應(yīng)度值：

其中，f(Xn)為麻雀個(gè)體的適應(yīng)度值。

對于發(fā)現(xiàn)者，用下式表示其位置變化：

對于加入者，其位置更新公式如下：

對于預(yù)警者，數(shù)量通常占麻雀種群數(shù)量的10%～20%，且位置隨機(jī)確定，其位置更新公式如下：

2 改進(jìn)的麻雀搜索算法(t-SSA)

2.1 t分布變異

t分布又稱學(xué)生t分布(Student′s t-Distribution)，它的概率密度函數(shù)曲線與其自由度n有關(guān)，n的值越大，其曲線中間越高。當(dāng)n=1時(shí)，有t(n=1)→C(0，1)；當(dāng)n=∞時(shí)，有t(n=∞)→N(0，1)。其中，C(0，1)為柯西分布，N(0，1)為高斯分布。即柯西分布和高斯分布為t分布自由度n分別為1和∞時(shí)的兩個(gè)特例。t分布的函數(shù)分布如圖1所示。

圖1 t分布函數(shù)分布圖

t分布既有柯西分布的特點(diǎn)，也有高斯分布的特點(diǎn)，本文將t分布的自由度參數(shù)用算法迭代次數(shù)代替，使t分布在算法迭代初期趨近于柯西分布，此時(shí)算法的全局尋優(yōu)能力得到提升；隨著迭代次數(shù)的增加，t分布又趨近于高斯分布，提高了算法的局部搜索水平，進(jìn)而提高算法的尋優(yōu)精度。

本文利用當(dāng)前迭代次數(shù)中發(fā)現(xiàn)者所能搜索到的最優(yōu)位置，結(jié)合t分布變異對發(fā)現(xiàn)者的位置進(jìn)行擾動(dòng)，其公式如下：

其中，Xnew表示經(jīng)t分布變異擾動(dòng)后的新位置；表示當(dāng)前發(fā)現(xiàn)者所搜索到的最優(yōu)位置；t(iter)表示以當(dāng)前迭代次數(shù)iter為自由度的t分布；表示當(dāng)前由式(4)計(jì)算得到的第i個(gè)加入者位置；fnew表示新位置的適應(yīng)度值，fi表示第i個(gè)加入者的適應(yīng)度值。當(dāng)fnew＜fi時(shí)，表示經(jīng)過t分布變異擾動(dòng)之后得到的新位置優(yōu)于當(dāng)前加入者位置，并把該位置更新給加入者。

2.2 改進(jìn)的麻雀搜索算法流程

本文提出的基于t分布變異的改進(jìn)麻雀搜索算法(t-SSA)步驟如下：

(1)進(jìn)行初始化，并設(shè)置參數(shù)，如種群數(shù)量n、發(fā)現(xiàn)者數(shù)量PD、預(yù)警者數(shù)量SD、最大迭代次數(shù)itermax、安全值ST等。

(2)計(jì)算麻雀個(gè)體適應(yīng)度值，記錄當(dāng)前全局最優(yōu)值和最劣值，及其對應(yīng)位置。

(3)根據(jù)設(shè)置好的發(fā)現(xiàn)者數(shù)量PD，挑選適應(yīng)度值較好的麻雀數(shù)量當(dāng)作發(fā)現(xiàn)者，并按照式(3)更新發(fā)現(xiàn)者位置。

(4)剩余的麻雀為加入者，按照式(4)更新加入者位置。

(5)應(yīng)用式(6)計(jì)算出t分布變異擾動(dòng)后的新位置，并按照式(7)對加入者位置進(jìn)行相應(yīng)的替換。

(6)根據(jù)設(shè)置好的預(yù)警者數(shù)量SD，隨機(jī)選取部分麻雀作為預(yù)警者，并按照式(5)更新預(yù)警者位置。

(7)更新麻雀種群個(gè)體最優(yōu)位置和全局最優(yōu)位置。

(8)判斷當(dāng)前迭代次數(shù)是否滿足算法最大迭代次數(shù)，若是，則循環(huán)結(jié)束，輸出結(jié)果；否則返回步驟(2)。

3 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文所提出的t-SSA算法的可行性和尋優(yōu)能力，本文基于Intel?CoreTMi5-7200U CPU@2.50 GHz，8 GB內(nèi)存，Windows 10操作系統(tǒng)和仿真軟件MATLAB R2019b進(jìn)行仿真實(shí)驗(yàn)。

3.1 對比實(shí)驗(yàn)設(shè)計(jì)和參數(shù)設(shè)置

本文將t-SSA算法與3種基本算法：灰狼優(yōu)化算法(GWO)[3]、飛蛾火焰優(yōu)化算法(MFO)[5]和麻雀搜索算法(SSA)[6]，分別測試6個(gè)基準(zhǔn)函數(shù)(其中f1～f3為單峰函數(shù)，f4～f6為多峰函數(shù))，進(jìn)行對比。 為確保實(shí)驗(yàn)的公平性，將全部算法統(tǒng)一設(shè)置種群數(shù)量100，迭代次數(shù)200，其余算法參數(shù)見表1。6個(gè)基準(zhǔn)測試函數(shù)具體信息見表2。選取各算法在基準(zhǔn)測試函數(shù)獨(dú)立運(yùn)行30次的結(jié)果的平均值和標(biāo)準(zhǔn)差作為實(shí)驗(yàn)結(jié)果，具體實(shí)驗(yàn)結(jié)果如表3所示，基準(zhǔn)測試函數(shù)收斂情況如圖2所示。

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

表2 基準(zhǔn)函數(shù)信息

3.2 實(shí)驗(yàn)結(jié)果分析

從表3和圖2能看出，在測試單峰函數(shù)f1～f3時(shí)，t-SSA算法均取得了其理論最優(yōu)值，且具有更快收斂速度和更強(qiáng)的魯棒性。在測試多峰函數(shù)f4～f6時(shí)，對于f4，t-SSA雖然收斂精度稍差于MFO，但與其余算法相比，其在前期的收斂速度較快；對于f5，t-SSA和SSA收斂結(jié)果相同，并且比GWO、MFO優(yōu)，但從圖2可以看出，t-SSA收斂速度明顯更快；對于f6，t-SSA具有較好的尋優(yōu)精度和較強(qiáng)的魯棒性。

表3 算法優(yōu)化結(jié)果對比

綜合來看，本文所提出的t-SSA算法較其他算法在收斂精度、收斂速度和魯棒性方面都有很大的提升，這表明本文所提出的改進(jìn)策略是有效的，既提高了算法的尋優(yōu)精度，又降低了算法陷入局部最優(yōu)的概率，且擁有更好的性能。

3.3 Wilcoxon秩和檢驗(yàn)

為進(jìn)一步評估t-SSA算法的優(yōu)化性能，仍需要對算法進(jìn)行統(tǒng)計(jì)檢驗(yàn)。因此，本文選擇Wilcoxon秩和檢驗(yàn)驗(yàn)證t-SSA算法每輪的優(yōu)化結(jié)果是否與所對比算法存在明顯區(qū)別。用P表示檢驗(yàn)結(jié)果，當(dāng)P＜5%時(shí)，說明兩種算法之間存在顯著差異；當(dāng)P＞5%時(shí)，說明兩種算法之間差距不明顯，性能相當(dāng)。在本文3.1節(jié)同樣的實(shí)驗(yàn)條件下，t-SSA分別與GWO、MFO、SSA的詳細(xì)檢驗(yàn)結(jié)果P如表4所示，其中NaN代表兩個(gè)對比算法性能接近，無法比較。

表4 Wilcoxon秩和檢驗(yàn)結(jié)果

由表4可知，除t-SSA與SSA的f4、f6，其余大部分的P值都小于5%，這說明t-SSA算法與其他算法在統(tǒng)計(jì)上存在顯著差異。對于f5，t-SSA與SSA差異不明顯，尋優(yōu)效果相當(dāng)。

4 結(jié)論

為了改善麻雀搜索算法(SSA)在其運(yùn)行末期出現(xiàn)種群多樣性下降、難以跳出局部最優(yōu)等問題，本文提出一種新的改進(jìn)麻雀搜索算法(t-SSA)。首先，引入自適應(yīng)t分布變異，對加入者位置進(jìn)行擾動(dòng)變異，防止跳不出局部最優(yōu)點(diǎn)，增強(qiáng)算法性能。然后，通過在6個(gè)基準(zhǔn)函數(shù)上進(jìn)行仿真實(shí)驗(yàn)，結(jié)果證明本文提出的t-SSA的收斂精度與速度優(yōu)于其他算法。綜合來看，本文所提出的改進(jìn)方法是有效的，能夠明顯提升SSA算法的尋優(yōu)性能，下一步將考慮將t-SSA算法應(yīng)用于實(shí)際工程問題的優(yōu)化中，驗(yàn)證其在工程問題上的應(yīng)用價(jià)值。