基于多個(gè)改進(jìn)策略的增強(qiáng)麻雀搜索算法

李大海，詹美欣，王振東

（江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000）

0 引言

現(xiàn)實(shí)中的工程問題大多可以轉(zhuǎn)化為求解函數(shù)最優(yōu)值問題，一般具有多峰值、非線性、多約束等特點(diǎn)［1］，如車輛側(cè)面碰撞設(shè)計(jì)問題［2］、發(fā)電機(jī)優(yōu)化調(diào)度［3］等。隨著現(xiàn)實(shí)問題的不斷復(fù)雜化，對(duì)算法性能的要求也越來越高，難以通過傳統(tǒng)優(yōu)化算法如牛頓法、梯度法等進(jìn)行求解。智能優(yōu)化算法是一類來源于對(duì)自然界規(guī)律、生物群體現(xiàn)象或者人類行為進(jìn)行模擬的隨機(jī)搜索算法，只需要通過目標(biāo)函數(shù)值和少量的參數(shù)設(shè)置就能實(shí)現(xiàn)問題的最優(yōu)值求解［4］。智能優(yōu)化算法因高效的優(yōu)化能力和簡(jiǎn)單易實(shí)現(xiàn)的特點(diǎn)，近年來一直被作為現(xiàn)實(shí)工程優(yōu)化問題的常用解決方案，所以對(duì)于智能優(yōu)化算法的持續(xù)改進(jìn)也一直是算法研究領(lǐng)域的熱點(diǎn)［3，5-7］。

麻雀搜索算法（Sparrow Search Algorithm，SSA）是2020 年由Xue 等［8］提出的一種新型高效智能優(yōu)化算法，因?yàn)榫哂惺諗克俣瓤旌鸵子趯?shí)現(xiàn)等優(yōu)點(diǎn)，已被廣泛使用于分布式電源配置［9］、肺組織分割［10］等領(lǐng)域。在優(yōu)化復(fù)雜工程問題時(shí)，SSA仍存在如收斂精度低且易陷入局部最優(yōu)等缺陷。

對(duì)于上述問題，諸多學(xué)者已經(jīng)提出若干改進(jìn)的麻雀算法并應(yīng)用于實(shí)際工程問題。王海瑞等［9］為了提高SSA 在求解電源配置時(shí)的穩(wěn)定性和尋優(yōu)精度，提出了一種改進(jìn)的SSA 算法。首先，引入Tent 混沌映射進(jìn)行種群初始化，增加了種群多樣性；其次，利用Levy 飛行和柯西-高斯變異增強(qiáng)算法的探索多樣性；最后，優(yōu)化麻雀?jìng)€(gè)體的位置更新方式，摒除大量無效個(gè)體，提高了解的質(zhì)量。歐陽(yáng)城添等［11］引入折射學(xué)習(xí)和瘋狂算子提高了SSA 的全局搜索能力和收斂精度，同時(shí)使用模擬退火機(jī)制對(duì)解進(jìn)行精練，改善了解的質(zhì)量。付華等［12］提出了一種融合多策略的改進(jìn)SSA 算法，為了增加種群多樣性，使用精英混沌反向?qū)W習(xí)對(duì)種群初始化；同時(shí)，結(jié)合雞群算法的隨機(jī)跟隨策略對(duì)麻雀跟隨者位置更新方式進(jìn)行擾動(dòng)，以平衡算法的局部和全局搜索能力，最后采用柯西-高斯變異策略改善了算法在優(yōu)化過程中的多樣性保持能力。李愛蓮等［13］針對(duì)SSA 尋優(yōu)后期種群多樣性損失等問題，提出了融合正余弦和柯西變異的改進(jìn)SSA。首先，通過折射反向?qū)W習(xí)對(duì)算法的種群進(jìn)行初始化；其次，在麻雀發(fā)現(xiàn)者位置更新引入正余弦策略以平衡算法的全局和局部搜索能力；最后在跟隨者更新階段融合柯西變異對(duì)最優(yōu)解進(jìn)行擾動(dòng)。上述學(xué)者提出的改進(jìn)策略能在一定程度上提高算法的優(yōu)化性能，但隨著優(yōu)化問題規(guī)模的不斷增加，SSA 的優(yōu)化能力面臨新的挑戰(zhàn)，原有的改進(jìn)方法難以解決相應(yīng)問題。

綜上所述，上述改進(jìn)SSA 一般是通過增加初始種群多樣性、對(duì)麻雀?jìng)€(gè)體采取變異擾動(dòng)等方式提升算法的優(yōu)化能力。盡管這些方法能夠提升SSA 的優(yōu)化能力，但在面對(duì)一些復(fù)雜多峰問題時(shí)，SSA 仍然存在易陷入局部最優(yōu)和尋優(yōu)精度低等問題。為了進(jìn)一步提升SSA 的優(yōu)化性能，本文提出了一種基于多個(gè)改進(jìn)策略的增強(qiáng)麻雀搜索算法（Enhanced Sparrow Search Algorithm based on Multiple Improvement strategies，EMISSA），主要采取了以下三項(xiàng)改進(jìn)策略：

1）利用模糊推理系統(tǒng)的非線性輸出功能，提出了一種結(jié)合模糊邏輯的比例因子，動(dòng)態(tài)調(diào)整發(fā)現(xiàn)者在麻雀種群中的占比，平衡SSA 算法的勘探和開發(fā)能力。

2）針對(duì)麻雀跟隨者在尋優(yōu)過程中易趨于原點(diǎn)和最優(yōu)發(fā)現(xiàn)者位置，從而導(dǎo)致易陷入局部最優(yōu)的問題，引入差分變異操作產(chǎn)生新的跟隨者位置，提高算法跳出局部最優(yōu)的概率。

3）通過拓?fù)鋵?duì)立學(xué)習(xí)（Topological Opposition-Based Learning，TOBL）獲取麻雀發(fā)現(xiàn)者的拓?fù)鋵?duì)立位置，并選擇其中的優(yōu)質(zhì)個(gè)體，增強(qiáng)算法探索空間的能力。

最后，在12 個(gè)測(cè)試函數(shù)實(shí)驗(yàn)上驗(yàn)證了策略的有效性。同時(shí)，將改進(jìn)的算法應(yīng)用于障礙物環(huán)境下的無線傳感器覆蓋優(yōu)化，獲得了更好的覆蓋率。

1 麻雀搜索算法

麻雀搜索算法（SSA）［8］是根據(jù)模擬麻雀覓食機(jī)制提出的群智能優(yōu)化算法，優(yōu)化模型中存在發(fā)現(xiàn)者、跟隨者、偵查者三種角色。發(fā)現(xiàn)者負(fù)責(zé)尋找整個(gè)搜索區(qū)域中食物較充足的位置，并為所有的跟隨者提供覓食區(qū)域或方向，發(fā)現(xiàn)者在種群中不是一成不變的，只要麻雀可以搜尋到更優(yōu)的食物所在位置，都可以成為發(fā)現(xiàn)者，但發(fā)現(xiàn)者在整個(gè)種群中所占的比例固定。而發(fā)現(xiàn)者受捕食者的影響又分兩種狀態(tài)，當(dāng)周圍不存在捕食者，發(fā)現(xiàn)者會(huì)進(jìn)入廣域搜索；否則所有的麻雀會(huì)向安全區(qū)移動(dòng)。在每一代搜索中發(fā)現(xiàn)者的位置根據(jù)式（1）更新：

其中：t表示當(dāng)前迭代次數(shù)；T是最大迭代次數(shù)表示t次迭代時(shí)第i個(gè)麻雀位置；α是（0，1）內(nèi)的隨機(jī)數(shù)；Q為服從正態(tài)分布的隨機(jī)數(shù)；L是1 ×D的矩陣，D為維度大小，L的元素值都為1；R和S是設(shè)定的報(bào)警值和安全值。

跟隨者會(huì)時(shí)刻觀察發(fā)現(xiàn)者的行為，根據(jù)發(fā)現(xiàn)者的行為調(diào)整自己的位置，跟隨者的位置更新如式（2）所示：

偵查者在種群中會(huì)意識(shí)到危險(xiǎn)，從而調(diào)整在麻雀種群的整體位置，這部分麻雀在整個(gè)種群中隨機(jī)產(chǎn)生，占整個(gè)種群的10%～20%，更新方式如下：

2 改進(jìn)的麻雀搜索算法EMISSA

在基本SSA 中，由于不同麻雀角色的規(guī)模在算法尋優(yōu)中固定不變，算法缺少自適應(yīng)性［14］，因此容易造成算法全局和局部搜索能力的不平衡。此外，麻雀跟隨者在算法搜索過程中跟隨發(fā)現(xiàn)者的搜索區(qū)域進(jìn)行尋優(yōu)，有著趨于局部最優(yōu)點(diǎn)的問題。同時(shí)，通過式（1）～（3）可以發(fā)現(xiàn)，麻雀?jìng)€(gè)體都有趨向原點(diǎn)或最優(yōu)位置的趨勢(shì)，無法充分探索空間，可能丟失更優(yōu)的解。因此，針對(duì)以上SSA 的缺陷，本文提出三種改進(jìn)策略。

2.1 結(jié)合模糊邏輯的比例因子

在SSA 中，麻雀發(fā)現(xiàn)者在整個(gè)種群中占據(jù)著最優(yōu)資源，其種群規(guī)模由比例因子PD決定，而且在算法迭代搜索過程中保持不變。文獻(xiàn)［14］中發(fā)現(xiàn)，在SSA 尋優(yōu)前期，較大的發(fā)現(xiàn)者規(guī)模可以使算法更好地進(jìn)行全局搜索，并且能提高算法的收斂速度；隨著算法到搜索后期，應(yīng)開始偏于局部搜索，這時(shí)應(yīng)減少發(fā)現(xiàn)者的數(shù)量，以便算法進(jìn)行細(xì)致搜索，獲得更高的收斂精度。

為了使發(fā)現(xiàn)者能夠在算法迭代搜索的過程動(dòng)態(tài)調(diào)整以適應(yīng)算法尋優(yōu)機(jī)制，本文引入了模糊推理系統(tǒng)對(duì)麻雀發(fā)現(xiàn)者的比例因子進(jìn)行非線性更新。模糊推理系統(tǒng)以模糊邏輯理論為主要計(jì)算工具，可以方便高效地實(shí)現(xiàn)多輸入變量與單輸出變量之間的復(fù)雜非線性映射關(guān)系［15］。模糊推理系統(tǒng)功能結(jié)構(gòu)如圖1 所示，主要由模糊化、模糊規(guī)則庫(kù)、模糊推理方法及去模糊化四部分組成。

圖1 模糊推理系統(tǒng)Fig.1 Fuzzy inference system

本文提出的動(dòng)態(tài)調(diào)節(jié)比例因子的模糊推理系統(tǒng)的兩個(gè)輸入變量分別為算法的當(dāng)前迭代階段和種群多樣性。迭代階段（iteration）的定義如式（4）所示，即迭代階段為當(dāng)前迭代次數(shù)與最大迭代次數(shù)之間的百分比。

種群的多樣性（diversity）度量的定義如式（5）所示，即種群的多樣性是通過每個(gè)麻雀?jìng)€(gè)體和當(dāng)前最佳個(gè)體之間的歐氏距離來衡量麻雀?jìng)€(gè)體之間在搜索空間中的分散程度。如果麻雀?jìng)€(gè)體相對(duì)分散，則說明種群多樣性較高；反之麻雀?jìng)€(gè)體之間相對(duì)集中，種群多樣性較低。

其中：N為種群規(guī)模大??；D為變量維度；xi，j(t)表示t次迭代時(shí)第i個(gè)麻雀的第j維值；xbest，j(t)表示t次迭代中最優(yōu)麻雀?jìng)€(gè)體的第j維值。

模糊推理系統(tǒng)的兩個(gè)輸入變量迭代階段（iteration）和種群多樣性（diversity）的隸屬度函數(shù)（membership function）的設(shè)計(jì)如圖2 所示?？梢钥闯?，輸入搜索迭代過程通過三個(gè)隸屬度函數(shù)被劃分為“前期（Early）”“中期（Medium）”“后期（Late）”三個(gè)階段。輸入種群多樣性也同樣被三個(gè)隸屬度函數(shù)劃分為“低（Low）”“中（Medium）”“高（High）”三種狀態(tài)。

圖2 變量的模糊化和變化趨勢(shì)Fig.2 Fuzzification and changing trend of variables

此外，為了對(duì)發(fā)現(xiàn)者比例因子PD實(shí)現(xiàn)精確控制輸出，輸出變量PD被5 個(gè)三角隸屬度函數(shù)劃分為“非常?。╒ery_Small）”“?。⊿mall）”“適中（Medium）”“大（Big）”“非常大（Very_Big）”五個(gè)階段。

除了對(duì)輸入和輸出變量進(jìn)行選擇，一個(gè)能夠?qū)崿F(xiàn)精準(zhǔn)控制的模糊推理系統(tǒng)還需要進(jìn)行合理的模糊規(guī)則設(shè)計(jì)。在SSA 尋優(yōu)過程中，當(dāng)算法處在搜索前期，通常需要更多的發(fā)現(xiàn)者進(jìn)行全局搜索，隨著算法的不斷迭代搜索，發(fā)現(xiàn)者規(guī)模應(yīng)當(dāng)逐漸減少，從而專注于局部搜索。同時(shí)，還需要考慮種群多樣性對(duì)比例因子PD的影響，種群多樣性較低時(shí)，應(yīng)當(dāng)增大發(fā)現(xiàn)者的規(guī)模以在搜索空間進(jìn)行充分搜索；而當(dāng)多樣性較高時(shí)，則可以適當(dāng)降低發(fā)現(xiàn)者在種群中的比例。綜上，可以設(shè)計(jì)如表1 所示的模糊規(guī)則。

表1 模糊規(guī)則Tab.1 Fuzzy rules

完成模糊系統(tǒng)規(guī)則的設(shè)計(jì)之后，經(jīng)過去模糊化便可以得到經(jīng)過模糊推理系統(tǒng)輸出的比例因子PD，如圖2（d）所示，比例因子在算法的不同迭代階段和相應(yīng)的種群多樣性下，可以實(shí)現(xiàn)發(fā)現(xiàn)者規(guī)模的動(dòng)態(tài)調(diào)整，從而使算法在尋優(yōu)過程中能更好地進(jìn)行搜索求解。

2.2 混合差分變異操作

從式（2）的跟隨者位置更新公式可知，在算法的每一次迭代過程中，跟隨者都會(huì)向發(fā)現(xiàn)者所在的最優(yōu)位置或原點(diǎn)移動(dòng)。這種更新方式能加快算法收斂，但同時(shí)也可能會(huì)對(duì)麻雀種群的多樣性造成影響。圖3 顯示了麻雀發(fā)現(xiàn)者和跟隨者在一個(gè)多峰函數(shù)BUKIN 上的變化情況。因?yàn)楦S者搜索到的位置信息和發(fā)現(xiàn)者的優(yōu)劣密切相關(guān)，所以當(dāng)發(fā)現(xiàn)者在搜索迭代中陷入了局部最優(yōu)位置時(shí)，跟隨者依然會(huì)隨著發(fā)現(xiàn)者的尋優(yōu)趨勢(shì)繼續(xù)進(jìn)行搜索，從而導(dǎo)致無法向其他搜索區(qū)域調(diào)整自己的位置，最終導(dǎo)致算法陷入局部最優(yōu)無法跳出。

圖3 麻雀?jìng)€(gè)體的搜索趨勢(shì)Fig.3 Search trends of sparrow individuals

差分變異操作是差分進(jìn)化（Differential Evolution，DE）算法中使用的一種利用差分變量機(jī)制改變候選解位置的高效優(yōu)化策略，常被用來和其他算法結(jié)合，以提高解的多樣性［16］。常見的差分變異策略有“DE/rand/1”“DE/current-tobest/1”“DE/best/1”等［17］。其中，“DE/current-to-best/1”和“DE/best/1”選擇的個(gè)體都是當(dāng)前最優(yōu)解或者全局最優(yōu)解，便于局部開發(fā)；而“DE/rand/1”中的個(gè)體均為隨機(jī)選擇的，側(cè)重于全局勘探［18］。如果使用以上的單一變異策略對(duì)算法進(jìn)行優(yōu)化，則有可能對(duì)算法的搜索平衡造成影響。

本文結(jié)合SSA 的特點(diǎn)提出了兩種差分變異策略（SSADE/rand/1、SSA-DE/best/1）對(duì)跟隨者子群進(jìn)行混合變異操作，以產(chǎn)生新子群使麻雀?jìng)€(gè)體在搜索空間中進(jìn)行充分搜索從而跳出局部最優(yōu)。SSA-DE/rand/1 和SSA-DE/best/1 具體實(shí)現(xiàn)方式分別如式（6）和式（7）所示：

其中：ui(t)和ui+k(t)分別為第t次迭代中產(chǎn)生的第i和i+k個(gè)變異個(gè)體；r1和r2為［0，1］內(nèi)的權(quán)重系數(shù)；xi(t)為第t次迭代中第i個(gè)麻雀跟隨者的位置；xi+k(t)為第t次迭代中第i+k個(gè)麻雀跟隨者的位置；xq(t)為第t次迭代從非最優(yōu)發(fā)現(xiàn)者個(gè)體中隨機(jī)選擇的發(fā)現(xiàn)者個(gè)體；xbest(t)為最優(yōu)發(fā)現(xiàn)者個(gè)體；xm(t)和xn(t)為不同于當(dāng)前跟隨者個(gè)體位置的兩個(gè)隨機(jī)位置，并且m≠n。

在本文提出的改進(jìn)SSA 中，兩種差分變異策略的具體使用方式如圖4 所示。若存在s個(gè)麻雀跟隨者，則前k個(gè)跟隨者都將通過式（6）進(jìn)行變異操作，其余的都通過式（7）進(jìn)行變異。其中k的值為麻雀跟隨者規(guī)模的50%，若跟隨者規(guī)模大小為奇數(shù)，則k的值向上取整。在使用兩種差分變異策略后，跟隨者的位置變化如圖5 所示。和式（2）的原SSA 更新跟隨者位置的機(jī)制相比，在進(jìn)行兩種差分變異操作后，跟隨者不再全部趨向原點(diǎn)或發(fā)現(xiàn)者搜索到的最優(yōu)位置，而是一部分跟隨者會(huì)與最優(yōu)發(fā)現(xiàn)者進(jìn)行差分操作產(chǎn)生新個(gè)體，另一部分則會(huì)和隨機(jī)選擇的位置較差的發(fā)現(xiàn)者個(gè)體進(jìn)行差分變異。兩種不同的變異方式同時(shí)對(duì)跟隨者進(jìn)行操作，可以使麻雀?jìng)€(gè)體在跳出局部最優(yōu)進(jìn)行空間探索的同時(shí)保持算法開采和勘探能力的平衡。

圖4 混合差分變異操作Fig.4 Mixed differential mutation operation

圖5 差分變異過程Fig.5 Differential mutation process

2.3 拓?fù)鋵?duì)立學(xué)習(xí)策略

拓?fù)鋵?duì)立學(xué)習(xí)（TOBL）是Dai 等［19］基于對(duì)立學(xué)習(xí)機(jī)制提出的一種智能優(yōu)化增強(qiáng)策略，可以顯著增強(qiáng)算法的空間搜索能力。相較于傳統(tǒng)對(duì)立學(xué)習(xí)方法中每一個(gè)個(gè)體都只存在一個(gè)與它的原始位置完全相反的個(gè)體而言，TOBL 中的每一個(gè)原始個(gè)體都可以獲得2D個(gè)備選個(gè)體，它的定義如下：

定義1 設(shè)xi=(xi，1，xi，2，…，xi，j，xi，D)為D維空間中的一個(gè)點(diǎn)，則它的拓?fù)鋵?duì)立點(diǎn)Ti=(Ti，1，Ti，2，…，Ti，j，Ti，D)如下：

其中：oi，j為第i個(gè)對(duì)立點(diǎn)的第j維值；xbest，j為最佳個(gè)體 的第j維值。oi，j如式（9）所示：

為了提升SSA 中發(fā)現(xiàn)者探索空間的能力，本文將上述機(jī)制引入SSA。在完成所有麻雀?jìng)€(gè)體的位置更新之后，首先通過式（9）生成每個(gè)發(fā)現(xiàn)者個(gè)體的原始對(duì)立點(diǎn)，接下來比較最優(yōu)麻雀?jìng)€(gè)體和原始對(duì)立點(diǎn)以及當(dāng)前麻雀發(fā)現(xiàn)者個(gè)體之間的曼哈頓距離［20］。如果原始對(duì)立點(diǎn)的位置與最優(yōu)個(gè)體之間的距離最小，則表示此對(duì)立點(diǎn)為當(dāng)前麻雀發(fā)現(xiàn)者個(gè)體的拓?fù)鋵?duì)立點(diǎn)。圖6 顯示了一個(gè)麻雀發(fā)現(xiàn)者個(gè)體在三維空間中的潛在拓?fù)鋵?duì)立點(diǎn)，（x1，1，x1，2，x1，3）為麻雀?jìng)€(gè)體位置。

圖6 三維空間中的拓?fù)鋵?duì)立點(diǎn)Fig.6 Topological opposition nodes in 3D space

計(jì)算拓?fù)鋵?duì)立點(diǎn)的目的是獲取更優(yōu)質(zhì)的麻雀發(fā)現(xiàn)者以對(duì)搜索空間進(jìn)行更充分探索，同時(shí)其他麻雀?jìng)€(gè)體可以跟隨發(fā)現(xiàn)者探索更優(yōu)質(zhì)的覓食區(qū)域，進(jìn)而提升SSA 的尋優(yōu)效率。在獲取麻雀發(fā)現(xiàn)者的拓?fù)鋵?duì)立點(diǎn)之后，再對(duì)獲取的對(duì)立點(diǎn)進(jìn)行適應(yīng)度評(píng)估，如果適應(yīng)度值好于麻雀發(fā)現(xiàn)者原始位置，則兩者進(jìn)行交換。擇優(yōu)交換公式如下：

其中：f(xi(t))和f(Ti(t))分別為當(dāng)前麻雀發(fā)現(xiàn)者個(gè)體與其拓?fù)鋵?duì)應(yīng)點(diǎn)的適應(yīng)度值(t+1)為最終產(chǎn)生的解。

2.4 改進(jìn)算法的時(shí)間復(fù)雜度分析

本文使用符號(hào)O表示時(shí)間復(fù)雜度的漸進(jìn)上界。設(shè)改進(jìn)麻雀算法的種群規(guī)模為N，最大迭代次數(shù)為T，優(yōu)化問題的維度為D，麻雀發(fā)現(xiàn)者在種群中的比例為PD。在EMISSA 初始化階段，對(duì)整個(gè)麻雀種群進(jìn)行初始化并評(píng)估它的適應(yīng)度值，所以時(shí)間復(fù)雜度為O(N×D)。算法開始迭代之后，首先會(huì)通過式（4）、（5）計(jì)算迭代百分比和種群多樣性，并且調(diào)用模糊邏輯計(jì)算麻雀發(fā)現(xiàn)者的比例因子PD。因?yàn)椴恍枰u(píng)估個(gè)體適應(yīng)度值且每次計(jì)算的次數(shù)都為常數(shù)項(xiàng)，假設(shè)每次計(jì)算兩者花費(fèi)的時(shí)間為t1和t2，調(diào)用模糊邏輯的時(shí)間為t3，可得此處的時(shí)間復(fù)雜度為O(t1+t2+t3)。在完成以上操作之后會(huì)對(duì)麻雀?jìng)€(gè)體位置進(jìn)行更新，它的時(shí)間復(fù)雜度為O(N×D)；然后對(duì)麻雀跟隨者進(jìn)行差分變異操作，時(shí)間復(fù)雜度為O((N-PD×N)×D)。最后使用拓?fù)鋵?duì)立學(xué)習(xí)獲取麻雀?jìng)€(gè)體的拓?fù)鋵?duì)立點(diǎn)，并且評(píng)估其適應(yīng)度，時(shí)間復(fù)雜度為O(PD×N×D)。綜上所述，EMISSA 算法的時(shí)間復(fù)雜度如下：

2.5 EMISSA算法實(shí)現(xiàn)步驟

通過上述分析可知，算法具體實(shí)現(xiàn)步驟如下：

步驟1 輸入EMISSA 的最大迭代次數(shù)T、種群大小N，問題維度D；

步驟2 EMISSA 開始初始化種群個(gè)體位置，并評(píng)估它的適應(yīng)度；

步驟3 初始化迭代次數(shù)t=1；

步驟4 對(duì)適應(yīng)度進(jìn)行排序，得到最優(yōu)和最劣個(gè)體位置；

步驟5 使用式（4）和（5）計(jì)算iteration 和diversity，并調(diào)用模糊邏輯得到比例因子PD；

步驟6 使用式（1）和（2）更新麻雀發(fā)現(xiàn)者和跟隨者位置之后，通過式（6）和（7）進(jìn)行混合差分變異操作產(chǎn)生變異子群，并通過式（3）更新偵查者位置；

步驟7 通過式（8）和（9）產(chǎn)生麻雀發(fā)現(xiàn)者的拓?fù)鋵?duì)立位置，并使用式（10）擇優(yōu)交換；

步驟8 當(dāng)前迭代次數(shù)t=t+1；

步驟9 如果算法達(dá)到最大迭代次數(shù)T，則輸出最佳個(gè)體位置和其適應(yīng)度值；否則從步驟4 繼續(xù)進(jìn)行循環(huán)迭代。

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文基于AMD R7-5800HCPU 以及Windows10（64 位）操作系統(tǒng)對(duì)EMISSA 以及其他對(duì)比算法進(jìn)行性能測(cè)試實(shí)驗(yàn)，實(shí)驗(yàn)仿真軟件為MatLab 2020a。

為了驗(yàn)證EMISSA 在函數(shù)優(yōu)化上的能力，本文從于2013年進(jìn)化計(jì)算大會(huì)（2013 Congress on Evolutionary Computation，CEC2013）中舉行的單目標(biāo)算法競(jìng)賽所使用的測(cè)試函數(shù)中選取了12 個(gè)有代表性的函數(shù)作為性能測(cè)試函數(shù)［21］。將EMISSA 和SSA 與混沌麻雀搜索優(yōu)化算法（Chaotic Sparrow Search Optimization Algorithm，CSSOA）［14］、混合策略改進(jìn)的麻雀搜索算法（Mixed Strategy improved Sparrow Search Algorithm，MSSSA）［22］、改進(jìn)麻雀搜索算法（Improved Sparrow Search Algorithm，ISSA）［23］以及增強(qiáng)型麻雀搜索算法（Enhanced Sparrow Search Algorithm，ESSA）［14］在12 個(gè)函數(shù)上進(jìn)行了測(cè)試。其中：f1～f4為單峰函數(shù)；f5～f12為基本多峰函數(shù)和組合函數(shù)。各測(cè)試函數(shù)的參數(shù)取值范圍統(tǒng)一設(shè)置為［-100，100］，函數(shù)具體名稱及全局最優(yōu)點(diǎn)F*見表2。

表2 測(cè)試函數(shù)Tab.2 Test functions

各算法分別在測(cè)試函數(shù)f1～f12上獨(dú)立運(yùn)行30 次，每個(gè)算法的迭代次數(shù)為1 500，取各算法獲得的測(cè)試函數(shù)的最優(yōu)解的均值（Mean）、方差（Std）以及算法排名（Rank）來評(píng)估算法的優(yōu)化性能和穩(wěn)定性。在求解極小值問題中，均值越小表示算法的平均性能越好，方差越小則算法越穩(wěn)定。排名（Rank）的評(píng)價(jià)標(biāo)準(zhǔn)是先比較各個(gè)算法在同一測(cè)試函數(shù)上獲得的均值，均值越小，則表示算法性能越好；在均值相同的情況下，再比較方差，方差越小，算法性能越好。

3.2 各算法測(cè)試結(jié)果分析

表3 為EMISSA 和對(duì)比算法在30 維的函數(shù)優(yōu)化結(jié)果，其中：Count 為各算法排名第1 的總次數(shù)；Ave Rank 為各算法的平均排名；Total Rank 是最終排名?？梢钥闯?，EMISSA 在4個(gè)單峰函數(shù)排名上都獲得了第1，不管是尋優(yōu)精度還是求解穩(wěn)定性都優(yōu)于對(duì)比算法。這表明EMISSA 比標(biāo)準(zhǔn)SSA 以及其他算法對(duì)單峰函數(shù)的優(yōu)化性能更強(qiáng)，因?yàn)橥負(fù)鋵?duì)立學(xué)習(xí)產(chǎn)生的拓?fù)鋵?duì)立位置使麻雀?jìng)€(gè)體能充分地探索空間，從而獲得更優(yōu)的尋優(yōu)結(jié)果。f5～f12的基本多峰和組合函數(shù)都包含許多局部最小值，這對(duì)于算法的優(yōu)化性能有很大的考驗(yàn)，而EMISSA除了f9，在其他函數(shù)上都獲得了更高的收斂精度，同時(shí)具有更高的算法穩(wěn)定性。在整個(gè)函數(shù)測(cè)試中，EMISSA 在11 個(gè)測(cè)試函數(shù)中獲得了第1，Ave Rank 為1.29，總排名第1。這說明通過EMISSA 通過多策略的改進(jìn)可以提升優(yōu)化能力。

表3 維度為30時(shí)不同算法的結(jié)果對(duì)比Tab.3 Comparison of results of different algorithms with 30 dimensions

表4 是各算法在80 維時(shí)的函數(shù)優(yōu)化結(jié)果。在12 個(gè)函數(shù)中，EMISSA 均獲得了第1；而且，對(duì)于大多數(shù)函數(shù)，EMISSA在獲得更好尋優(yōu)精度的同時(shí)求解穩(wěn)定性也更好。說明隨著優(yōu)化函數(shù)維度的升高，在多個(gè)改進(jìn)策略的作用下，EMISSA 的優(yōu)化能力并沒有降低，同樣可以獲得較好的尋優(yōu)結(jié)果。

表4 維度為80時(shí)不同算法的對(duì)比結(jié)果Tab.4 Comparison of results of different algorithms with 80 dimensions

3.3 算法收斂性分析

圖7 為各算法在30 維情況下6 個(gè)典型測(cè)試函數(shù)上的收斂情況。圖7（a）～（c）為3 個(gè)單峰函數(shù)f1、f3、f4的收斂曲線，可以看出，EMISSA 的收斂精度遠(yuǎn)遠(yuǎn)高于比對(duì)算法。對(duì)于f1、f3，EMISSA 在整個(gè)算法搜索過程中獲得的解都要好于其他算法，這可能得益于融合模糊邏輯的比例因子對(duì)麻雀發(fā)現(xiàn)者的動(dòng)態(tài)調(diào)整。從圖7（c）可以看出，在算法迭代搜索到700 代左右，EMISSA 的收斂精度劣于ISSA，但隨著算法進(jìn)入迭代中后期，收斂精度便超過了ISSA。圖7（d）～（f）為基本多峰函數(shù)f7、f8以及組合函數(shù)f11的收斂曲線。EMISSA 跳出局部最優(yōu)的能力在它的收斂曲線上體現(xiàn)，當(dāng)算法迭代搜索到中后期，除了EMISSA 跳出了局部最優(yōu)，向前繼續(xù)探索，其他算法已經(jīng)收斂，沒有找到更優(yōu)的值。這進(jìn)一步表明，EMISSA 在多策略的作用下，它的函數(shù)優(yōu)化能力得到顯著提升。

圖7 不同算法在典型測(cè)試函數(shù)上的收斂曲線Fig.7 Convergence curves of different algorithms on typical test functions

3.4 Friedman檢驗(yàn)

本節(jié)采用Friedman 檢驗(yàn)［24］對(duì)3.1 節(jié)中的測(cè)試算法進(jìn)行非參數(shù)檢驗(yàn)。Friedman 檢驗(yàn)的一般實(shí)現(xiàn)步驟如下：

1）收集算法的實(shí)驗(yàn)數(shù)據(jù)。

2）列出每個(gè)問題i的最好與最差結(jié)果排名，定義為（1 ≤K≤j）。

3）在所有問題中求出各個(gè)算法的平均排名，并計(jì)算出最終排名。秩平均值越小，則算法性能越好。

Friedman 統(tǒng)計(jì)值計(jì)算公式如式（11）所示，F(xiàn)f的值越小，各算法之間的差異性越就越大，當(dāng)n和k足夠大時(shí)（根據(jù)經(jīng)驗(yàn)n>10，k>5），它服從k-1 自由度的χ2分布。

本次檢驗(yàn)的依據(jù)來自表3～4，檢驗(yàn)結(jié)果如表5 所示。其中，P-value 表示漸進(jìn)顯著性，如果它的值小于0.01，則說明各項(xiàng)數(shù)據(jù)之間存在顯著性差異。

表5 不同算法的Friedman檢驗(yàn)結(jié)果對(duì)比Tab.5 Comparison of Friedman test results of different algorithms

可以看出，P-value 遠(yuǎn)小于0.01，表明EMISSA 和對(duì)比算法間存在顯著差異性。EMISSA 的秩平均值也獲得了最小的結(jié)果。因此，EMISSA 的優(yōu)化能力在統(tǒng)計(jì)學(xué)意義上提升較大。

4 障礙物環(huán)境下的WSN覆蓋優(yōu)化

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由若干傳感器節(jié)點(diǎn)組成的信息傳輸網(wǎng)絡(luò)，有易部署、覆蓋范圍廣等特點(diǎn)［25］，它通過獲取外部環(huán)境中的相關(guān)信息并發(fā)送給基站達(dá)到監(jiān)測(cè)效果，已被廣泛應(yīng)用于災(zāi)害預(yù)警、環(huán)境檢測(cè)、智能家居等領(lǐng)域［26］。WSN 對(duì)所在區(qū)域的覆蓋率影響著整個(gè)網(wǎng)絡(luò)的傳輸效率［27］，而無線傳感器節(jié)點(diǎn)在監(jiān)測(cè)環(huán)境中的位置部署情況直接決定了整個(gè)網(wǎng)絡(luò)的覆蓋面積，因此WSN 的覆蓋優(yōu)化問題一直是學(xué)者們研究的熱點(diǎn)。

4.1 問題模型

假設(shè)節(jié)點(diǎn)被部署在S=L×W的二維平面區(qū)域中，整個(gè)區(qū)域被離散化為L(zhǎng)×W個(gè)像素點(diǎn)，區(qū)域中存在阻礙節(jié)點(diǎn)部署的障礙物。節(jié)點(diǎn)集合為N={n1，n2，…，nk}和障礙物集合為，其中：k和j分別為節(jié)點(diǎn)和障礙物的個(gè)數(shù)；i為障礙物的類型。節(jié)點(diǎn)nk在區(qū)域內(nèi)的坐標(biāo)為(xk，yk)，它的感知范圍是一個(gè)半徑為r的圓，通信半徑為R，并且R=2r。

傳感器節(jié)點(diǎn)會(huì)感知外部信息然后傳輸給數(shù)據(jù)中心，合適的感知方式可以增加覆蓋模型的合理性。由于實(shí)際的WSN部署環(huán)境十分復(fù)雜，節(jié)點(diǎn)會(huì)遇到很多影響感知的外部因素，所以本文選用概率感知模型［28］來判斷區(qū)域是否被當(dāng)前節(jié)點(diǎn)覆蓋，并結(jié)合實(shí)際環(huán)境對(duì)感知模型進(jìn)行了改進(jìn)。

假設(shè)需要檢測(cè)的目標(biāo)點(diǎn)的坐標(biāo)為g(xg，yg)，則傳感器節(jié)點(diǎn)nk對(duì)g的感知概率為：

其中：dnkg是傳感器節(jié)點(diǎn)nk和目標(biāo)點(diǎn)g之間的歐氏距離；re是傳感器節(jié)點(diǎn)在復(fù)雜環(huán)境下不確定感知能力的一個(gè)度量，且0

圖8 節(jié)點(diǎn)感知模型Fig.8 Node awareness model

式（13）中顯示的是單個(gè)節(jié)點(diǎn)的感知概率，而在WSN 中，各個(gè)節(jié)點(diǎn)會(huì)有重復(fù)感知的區(qū)域，所以綜上可知整個(gè)WSN 的聯(lián)合感知概率為：

進(jìn)而可以得出整個(gè)區(qū)域的覆蓋率為：

本文的目的就是得到WSN 在障礙物環(huán)境下fco的最大值。

4.2 避障設(shè)計(jì)

復(fù)雜環(huán)境下的節(jié)點(diǎn)部署存在障礙物限制，需要考慮落在障礙物區(qū)域節(jié)點(diǎn)的移動(dòng)問題，一般會(huì)對(duì)優(yōu)化的目標(biāo)函數(shù)加上約束條件，從而在算法優(yōu)化過程中避開障礙物［28］或者對(duì)節(jié)點(diǎn)進(jìn)行再次移動(dòng)［30］。但前者對(duì)約束條件的選擇很重要，不合適的約束條件往往會(huì)導(dǎo)致傳感器節(jié)點(diǎn)部署的聚集性，造成覆蓋率的下降。因此，本文提出了一種基于人工勢(shì)場(chǎng)法中虛擬斥力場(chǎng)概念［31］的方法對(duì)節(jié)點(diǎn)位置進(jìn)行重新處理。如圖9所示，建立了適合傳感器節(jié)點(diǎn)部署的障礙物模型，模型中的實(shí)際障礙物被包含在一個(gè)圓中，障礙物的大小決定了這個(gè)圓半徑ro的大小，同時(shí)圓的范圍也是斥力場(chǎng)存在的區(qū)域。節(jié)點(diǎn)與障礙物的距離被簡(jiǎn)化為與圓心oi的距離，當(dāng)節(jié)點(diǎn)落在圓內(nèi)，便會(huì)受到來自障礙物的斥力作用，并沿著斥力方向移動(dòng)相應(yīng)斥力大小的距離，從而達(dá)到避開障礙物的目的。斥力大小如式（16）所示：

圖9 障礙物內(nèi)節(jié)點(diǎn)移動(dòng)方式Fig.9 Movement modes of nodes in obstacles

其中：d(ni，oicenter)表示節(jié)點(diǎn)和障礙物之間的距離；r.o表示障礙物的斥力有效范圍，即圓的半徑；Fno表示節(jié)點(diǎn)和障礙物之間的斥力大小，被用來作為節(jié)點(diǎn)的移動(dòng)距離。

此外，如圖9（b）所示，當(dāng)障礙物周圍存在部署區(qū)域邊界A，為了防止節(jié)點(diǎn)在移動(dòng)過程中越過邊界，原本向邊界方向移動(dòng)的節(jié)點(diǎn)會(huì)按式（17）所受力的反方向移動(dòng)。

4.3 實(shí)驗(yàn)設(shè)置

本節(jié)在多障礙部署環(huán)境下對(duì)EMISSA 的WSN 節(jié)點(diǎn)部署效果進(jìn)行測(cè)試。實(shí)驗(yàn)設(shè)置與第3 章一致，所有算法都使用4.2 節(jié)中的避障策略。具體設(shè)置如表6 所示。

4.4 算法覆蓋效果分析

圖10 和圖11 分別顯示了各算法在障礙環(huán)境中的WSN的覆蓋優(yōu)化收斂過程和最終優(yōu)化效果。從圖10 中可以看出，EMISSA 與對(duì)比算法相比獲得了最高的覆蓋率，標(biāo)準(zhǔn)SSA在算法迭代前期就陷入了局部最優(yōu)，直到算法尋優(yōu)結(jié)束也無法跳出。而EMISSA 通過拓?fù)鋵?duì)立學(xué)習(xí)獲得了更多的位置信息，從而可以在每次迭代搜索中比大多數(shù)對(duì)比算法獲得更好的覆蓋率。同時(shí)，EMISSA 的收斂曲線較平穩(wěn)，這是因?yàn)橥ㄟ^模糊邏輯調(diào)整的動(dòng)態(tài)比例因子保證了種群最優(yōu)群體發(fā)現(xiàn)者的搜素平衡，繼而保持了整個(gè)種群的搜索平衡。此外，當(dāng)算法迭代到900 代左右，EMISSA 陷入了一段時(shí)間的搜索停滯，沒有找到更好的節(jié)點(diǎn)部署方案，但隨著算法的迭代，最終跳出了局部最優(yōu)，獲得了更高的覆蓋率，這可能是對(duì)跟隨者進(jìn)行混合差分變異操作產(chǎn)生的效果。同時(shí)，從圖11 可以看出，EMISSA 的WSN 節(jié)點(diǎn)部署效果相較于對(duì)比算法，節(jié)點(diǎn)分布更均勻、覆蓋冗余更少。這說明，EMISSA 在實(shí)際工程應(yīng)用中也具有良好的優(yōu)化能力。

圖10 不同算法的收斂曲線Fig.10 Convergence curves of different algorithms

圖11 不同算法的覆蓋優(yōu)化效果Fig.11 Coverage optimization effects of different algorithms

5 結(jié)語(yǔ)

為了改善SSA 的性能，本文提出一種基于多個(gè)改進(jìn)策略的增強(qiáng)麻雀搜索算法（EMISSA）。首先，利用模糊邏輯對(duì)發(fā)現(xiàn)者的比例進(jìn)行動(dòng)態(tài)輸出；其次，引入混合差分變異操作解決麻雀跟隨者易被發(fā)現(xiàn)者最優(yōu)位置吸引而陷入局部最優(yōu)的問題；最后通過拓?fù)鋵?duì)立學(xué)習(xí)擴(kuò)大麻雀搜索范圍，增強(qiáng)了算法探索空間的能力。12 個(gè)測(cè)試函數(shù)驗(yàn)證了EMISSA 的有效性，而障礙物環(huán)境下的WSN 覆蓋優(yōu)化表明了EMISSA 在實(shí)際工程問題中的可行性。但EMISSA 還存在相應(yīng)問題，如對(duì)于部分函數(shù)的收斂精度還是不足。下一步將對(duì)SSA 繼續(xù)改進(jìn)并應(yīng)用在更復(fù)雜的無線傳感器節(jié)點(diǎn)部署問題上。