基于多個改進策略的增強麻雀搜索算法

李大海，詹美欣，王振東

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

0 引言

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

麻雀搜索算法（Sparrow Search Algorithm，SSA）是2020 年由Xue 等［8］提出的一種新型高效智能優化算法，因為具有收斂速度快和易于實現等優點，已被廣泛使用于分布式電源配置［9］、肺組織分割［10］等領域。在優化復雜工程問題時，SSA仍存在如收斂精度低且易陷入局部最優等缺陷。

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

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

1）利用模糊推理系統的非線性輸出功能，提出了一種結合模糊邏輯的比例因子，動態調整發現者在麻雀種群中的占比，平衡SSA 算法的勘探和開發能力。

2）針對麻雀跟隨者在尋優過程中易趨于原點和最優發現者位置，從而導致易陷入局部最優的問題，引入差分變異操作產生新的跟隨者位置，提高算法跳出局部最優的概率。

3）通過拓撲對立學習（Topological Opposition-Based Learning，TOBL）獲取麻雀發現者的拓撲對立位置，并選擇其中的優質個體，增強算法探索空間的能力。

最后，在12 個測試函數實驗上驗證了策略的有效性。同時，將改進的算法應用于障礙物環境下的無線傳感器覆蓋優化，獲得了更好的覆蓋率。

1 麻雀搜索算法

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

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

跟隨者會時刻觀察發現者的行為，根據發現者的行為調整自己的位置，跟隨者的位置更新如式（2）所示：

偵查者在種群中會意識到危險，從而調整在麻雀種群的整體位置，這部分麻雀在整個種群中隨機產生，占整個種群的10%～20%，更新方式如下：

2 改進的麻雀搜索算法EMISSA

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

2.1 結合模糊邏輯的比例因子

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

為了使發現者能夠在算法迭代搜索的過程動態調整以適應算法尋優機制，本文引入了模糊推理系統對麻雀發現者的比例因子進行非線性更新。模糊推理系統以模糊邏輯理論為主要計算工具，可以方便高效地實現多輸入變量與單輸出變量之間的復雜非線性映射關系［15］。模糊推理系統功能結構如圖1 所示，主要由模糊化、模糊規則庫、模糊推理方法及去模糊化四部分組成。

圖1 模糊推理系統Fig.1 Fuzzy inference system

本文提出的動態調節比例因子的模糊推理系統的兩個輸入變量分別為算法的當前迭代階段和種群多樣性。迭代階段（iteration）的定義如式（4）所示，即迭代階段為當前迭代次數與最大迭代次數之間的百分比。

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

其中：N為種群規模大小；D為變量維度；xi，j(t)表示t次迭代時第i個麻雀的第j維值；xbest，j(t)表示t次迭代中最優麻雀個體的第j維值。

模糊推理系統的兩個輸入變量迭代階段（iteration）和種群多樣性（diversity）的隸屬度函數（membership function）的設計如圖2 所示。可以看出，輸入搜索迭代過程通過三個隸屬度函數被劃分為“前期（Early）”“中期（Medium）”“后期（Late）”三個階段。輸入種群多樣性也同樣被三個隸屬度函數劃分為“低（Low）”“中（Medium）”“高（High）”三種狀態。

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

此外，為了對發現者比例因子PD實現精確控制輸出，輸出變量PD被5 個三角隸屬度函數劃分為“非常小（Very_Small）”“小（Small）”“適中（Medium）”“大（Big）”“非常大（Very_Big）”五個階段。

除了對輸入和輸出變量進行選擇，一個能夠實現精準控制的模糊推理系統還需要進行合理的模糊規則設計。在SSA 尋優過程中，當算法處在搜索前期，通常需要更多的發現者進行全局搜索，隨著算法的不斷迭代搜索，發現者規模應當逐漸減少，從而專注于局部搜索。同時，還需要考慮種群多樣性對比例因子PD的影響，種群多樣性較低時，應當增大發現者的規模以在搜索空間進行充分搜索；而當多樣性較高時，則可以適當降低發現者在種群中的比例。綜上，可以設計如表1 所示的模糊規則。

表1 模糊規則Tab.1 Fuzzy rules

完成模糊系統規則的設計之后，經過去模糊化便可以得到經過模糊推理系統輸出的比例因子PD，如圖2（d）所示，比例因子在算法的不同迭代階段和相應的種群多樣性下，可以實現發現者規模的動態調整，從而使算法在尋優過程中能更好地進行搜索求解。

2.2 混合差分變異操作

從式（2）的跟隨者位置更新公式可知，在算法的每一次迭代過程中，跟隨者都會向發現者所在的最優位置或原點移動。這種更新方式能加快算法收斂，但同時也可能會對麻雀種群的多樣性造成影響。圖3 顯示了麻雀發現者和跟隨者在一個多峰函數BUKIN 上的變化情況。因為跟隨者搜索到的位置信息和發現者的優劣密切相關，所以當發現者在搜索迭代中陷入了局部最優位置時，跟隨者依然會隨著發現者的尋優趨勢繼續進行搜索，從而導致無法向其他搜索區域調整自己的位置，最終導致算法陷入局部最優無法跳出。

圖3 麻雀個體的搜索趨勢Fig.3 Search trends of sparrow individuals

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

本文結合SSA 的特點提出了兩種差分變異策略（SSADE/rand/1、SSA-DE/best/1）對跟隨者子群進行混合變異操作，以產生新子群使麻雀個體在搜索空間中進行充分搜索從而跳出局部最優。SSA-DE/rand/1 和SSA-DE/best/1 具體實現方式分別如式（6）和式（7）所示：

其中：ui(t)和ui+k(t)分別為第t次迭代中產生的第i和i+k個變異個體；r1和r2為［0，1］內的權重系數；xi(t)為第t次迭代中第i個麻雀跟隨者的位置；xi+k(t)為第t次迭代中第i+k個麻雀跟隨者的位置；xq(t)為第t次迭代從非最優發現者個體中隨機選擇的發現者個體；xbest(t)為最優發現者個體；xm(t)和xn(t)為不同于當前跟隨者個體位置的兩個隨機位置，并且m≠n。

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

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

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

2.3 拓撲對立學習策略

拓撲對立學習（TOBL）是Dai 等［19］基于對立學習機制提出的一種智能優化增強策略，可以顯著增強算法的空間搜索能力。相較于傳統對立學習方法中每一個個體都只存在一個與它的原始位置完全相反的個體而言，TOBL 中的每一個原始個體都可以獲得2D個備選個體，它的定義如下：

定義1 設xi=(xi，1，xi，2，…，xi，j，xi，D)為D維空間中的一個點，則它的拓撲對立點Ti=(Ti，1，Ti，2，…，Ti，j，Ti，D)如下：

其中：oi，j為第i個對立點的第j維值；xbest，j為最佳個體 的第j維值。oi，j如式（9）所示：

為了提升SSA 中發現者探索空間的能力，本文將上述機制引入SSA。在完成所有麻雀個體的位置更新之后，首先通過式（9）生成每個發現者個體的原始對立點，接下來比較最優麻雀個體和原始對立點以及當前麻雀發現者個體之間的曼哈頓距離［20］。如果原始對立點的位置與最優個體之間的距離最小，則表示此對立點為當前麻雀發現者個體的拓撲對立點。圖6 顯示了一個麻雀發現者個體在三維空間中的潛在拓撲對立點，（x1，1，x1，2，x1，3）為麻雀個體位置。

圖6 三維空間中的拓撲對立點Fig.6 Topological opposition nodes in 3D space

計算拓撲對立點的目的是獲取更優質的麻雀發現者以對搜索空間進行更充分探索，同時其他麻雀個體可以跟隨發現者探索更優質的覓食區域，進而提升SSA 的尋優效率。在獲取麻雀發現者的拓撲對立點之后，再對獲取的對立點進行適應度評估，如果適應度值好于麻雀發現者原始位置，則兩者進行交換。擇優交換公式如下：

其中：f(xi(t))和f(Ti(t))分別為當前麻雀發現者個體與其拓撲對應點的適應度值(t+1)為最終產生的解。

2.4 改進算法的時間復雜度分析

本文使用符號O表示時間復雜度的漸進上界。設改進麻雀算法的種群規模為N，最大迭代次數為T，優化問題的維度為D，麻雀發現者在種群中的比例為PD。在EMISSA 初始化階段，對整個麻雀種群進行初始化并評估它的適應度值，所以時間復雜度為O(N×D)。算法開始迭代之后，首先會通過式（4）、（5）計算迭代百分比和種群多樣性，并且調用模糊邏輯計算麻雀發現者的比例因子PD。因為不需要評估個體適應度值且每次計算的次數都為常數項，假設每次計算兩者花費的時間為t1和t2，調用模糊邏輯的時間為t3，可得此處的時間復雜度為O(t1+t2+t3)。在完成以上操作之后會對麻雀個體位置進行更新，它的時間復雜度為O(N×D)；然后對麻雀跟隨者進行差分變異操作，時間復雜度為O((N-PD×N)×D)。最后使用拓撲對立學習獲取麻雀個體的拓撲對立點，并且評估其適應度，時間復雜度為O(PD×N×D)。綜上所述，EMISSA 算法的時間復雜度如下：

2.5 EMISSA算法實現步驟

通過上述分析可知，算法具體實現步驟如下：

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

步驟2 EMISSA 開始初始化種群個體位置，并評估它的適應度；

步驟3 初始化迭代次數t=1；

步驟4 對適應度進行排序，得到最優和最劣個體位置；

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

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

步驟7 通過式（8）和（9）產生麻雀發現者的拓撲對立位置，并使用式（10）擇優交換；

步驟8 當前迭代次數t=t+1；

步驟9 如果算法達到最大迭代次數T，則輸出最佳個體位置和其適應度值；否則從步驟4 繼續進行循環迭代。

3 實驗與結果分析

3.1 實驗設計

本文基于AMD R7-5800HCPU 以及Windows10（64 位）操作系統對EMISSA 以及其他對比算法進行性能測試實驗，實驗仿真軟件為MatLab 2020a。

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

表2 測試函數Tab.2 Test functions

各算法分別在測試函數f1～f12上獨立運行30 次，每個算法的迭代次數為1 500，取各算法獲得的測試函數的最優解的均值（Mean）、方差（Std）以及算法排名（Rank）來評估算法的優化性能和穩定性。在求解極小值問題中，均值越小表示算法的平均性能越好，方差越小則算法越穩定。排名（Rank）的評價標準是先比較各個算法在同一測試函數上獲得的均值，均值越小，則表示算法性能越好；在均值相同的情況下，再比較方差，方差越小，算法性能越好。

3.2 各算法測試結果分析

表3 為EMISSA 和對比算法在30 維的函數優化結果，其中：Count 為各算法排名第1 的總次數；Ave Rank 為各算法的平均排名；Total Rank 是最終排名。可以看出，EMISSA 在4個單峰函數排名上都獲得了第1，不管是尋優精度還是求解穩定性都優于對比算法。這表明EMISSA 比標準SSA 以及其他算法對單峰函數的優化性能更強，因為拓撲對立學習產生的拓撲對立位置使麻雀個體能充分地探索空間，從而獲得更優的尋優結果。f5～f12的基本多峰和組合函數都包含許多局部最小值，這對于算法的優化性能有很大的考驗，而EMISSA除了f9，在其他函數上都獲得了更高的收斂精度，同時具有更高的算法穩定性。在整個函數測試中，EMISSA 在11 個測試函數中獲得了第1，Ave Rank 為1.29，總排名第1。這說明通過EMISSA 通過多策略的改進可以提升優化能力。

表3 維度為30時不同算法的結果對比Tab.3 Comparison of results of different algorithms with 30 dimensions

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

表4 維度為80時不同算法的對比結果Tab.4 Comparison of results of different algorithms with 80 dimensions

3.3 算法收斂性分析

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

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

3.4 Friedman檢驗

本節采用Friedman 檢驗［24］對3.1 節中的測試算法進行非參數檢驗。Friedman 檢驗的一般實現步驟如下：

1）收集算法的實驗數據。

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

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

Friedman 統計值計算公式如式（11）所示，Ff的值越小，各算法之間的差異性越就越大，當n和k足夠大時（根據經驗n>10，k>5），它服從k-1 自由度的χ2分布。

本次檢驗的依據來自表3～4，檢驗結果如表5 所示。其中，P-value 表示漸進顯著性，如果它的值小于0.01，則說明各項數據之間存在顯著性差異。

表5 不同算法的Friedman檢驗結果對比Tab.5 Comparison of Friedman test results of different algorithms

可以看出，P-value 遠小于0.01，表明EMISSA 和對比算法間存在顯著差異性。EMISSA 的秩平均值也獲得了最小的結果。因此，EMISSA 的優化能力在統計學意義上提升較大。

4 障礙物環境下的WSN覆蓋優化

無線傳感器網絡（Wireless Sensor Network，WSN）是由若干傳感器節點組成的信息傳輸網絡，有易部署、覆蓋范圍廣等特點［25］，它通過獲取外部環境中的相關信息并發送給基站達到監測效果，已被廣泛應用于災害預警、環境檢測、智能家居等領域［26］。WSN 對所在區域的覆蓋率影響著整個網絡的傳輸效率［27］，而無線傳感器節點在監測環境中的位置部署情況直接決定了整個網絡的覆蓋面積，因此WSN 的覆蓋優化問題一直是學者們研究的熱點。

4.1 問題模型

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

傳感器節點會感知外部信息然后傳輸給數據中心，合適的感知方式可以增加覆蓋模型的合理性。由于實際的WSN部署環境十分復雜，節點會遇到很多影響感知的外部因素，所以本文選用概率感知模型［28］來判斷區域是否被當前節點覆蓋，并結合實際環境對感知模型進行了改進。

假設需要檢測的目標點的坐標為g(xg，yg)，則傳感器節點nk對g的感知概率為：

其中：dnkg是傳感器節點nk和目標點g之間的歐氏距離；re是傳感器節點在復雜環境下不確定感知能力的一個度量，且0

圖8 節點感知模型Fig.8 Node awareness model

式（13）中顯示的是單個節點的感知概率，而在WSN 中，各個節點會有重復感知的區域，所以綜上可知整個WSN 的聯合感知概率為：

進而可以得出整個區域的覆蓋率為：

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

4.2 避障設計

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

圖9 障礙物內節點移動方式Fig.9 Movement modes of nodes in obstacles

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

此外，如圖9（b）所示，當障礙物周圍存在部署區域邊界A，為了防止節點在移動過程中越過邊界，原本向邊界方向移動的節點會按式（17）所受力的反方向移動。

4.3 實驗設置

本節在多障礙部署環境下對EMISSA 的WSN 節點部署效果進行測試。實驗設置與第3 章一致，所有算法都使用4.2 節中的避障策略。具體設置如表6 所示。

4.4 算法覆蓋效果分析

圖10 和圖11 分別顯示了各算法在障礙環境中的WSN的覆蓋優化收斂過程和最終優化效果。從圖10 中可以看出，EMISSA 與對比算法相比獲得了最高的覆蓋率，標準SSA在算法迭代前期就陷入了局部最優，直到算法尋優結束也無法跳出。而EMISSA 通過拓撲對立學習獲得了更多的位置信息，從而可以在每次迭代搜索中比大多數對比算法獲得更好的覆蓋率。同時，EMISSA 的收斂曲線較平穩，這是因為通過模糊邏輯調整的動態比例因子保證了種群最優群體發現者的搜素平衡，繼而保持了整個種群的搜索平衡。此外，當算法迭代到900 代左右，EMISSA 陷入了一段時間的搜索停滯，沒有找到更好的節點部署方案，但隨著算法的迭代，最終跳出了局部最優，獲得了更高的覆蓋率，這可能是對跟隨者進行混合差分變異操作產生的效果。同時，從圖11 可以看出，EMISSA 的WSN 節點部署效果相較于對比算法，節點分布更均勻、覆蓋冗余更少。這說明，EMISSA 在實際工程應用中也具有良好的優化能力。

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

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

5 結語

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