一種融合邏輯回歸的麻雀搜索算法研究

彭一凱 蒲紅平

摘? 要：為了改善麻雀搜索算法收斂速度緩慢、局部搜索能力較弱等問題，提出了一種融合邏輯回歸的麻雀搜索算法。文章通過引入Sine-Sine混沌、邏輯回歸模型、步長因子組合策略來改進麻雀搜索算法的不足之處。實驗結果表明該算法具有更好的收斂速度、尋優精度和穩定性的能力。同時，利用該算法預估Taylor定位算法的初始值，解決了TayLor的初值難以選擇問題，進一步驗證了改進策略的有效性。

關鍵詞：麻雀搜索算法；Sine-Sine混沌；邏輯回歸模型；步長因子

中圖分類號：TP18? 文獻標識碼：A? 文章編號：2096-4706（2023）08-0001-07

Abstract： In order to improve the slow convergence speed and weak local search ability of Sparrow Search Algorithm， a Sparrow Search Algorithm incorporating Logic Regression is proposed. This paper improves the shortcomings of the Sparrow Search Algorithm by introducing Sine-Sine chaos， Logical Regression model and step factor combination strategy. The experimental results show that the algorithm has better convergence speed， optimization accuracy and stability. At the same time， the algorithm is used to estimate the initial value of Taylor location algorithm， which solves the problem that it is difficult to select the initial value of TayLor， and further verifies the effectiveness of the improved strategy.

Keywords： Sparrow Search Algorithm; Sine-Sine chaos; Logistic Regression model; step factor

0? 引? 言

針對不同的優化問題，眾多學者提出了相關算法以及改進算法[1-4]。尤其，近年來群體智能優化算法的效果被大眾所認知，進而越來越多新的群體智能算法被提出，如蝴蝶優化算法（Butterfly Optimization Algorithm， BOA）[5]、蝗蟲優化算法（Grasshopper optimization algorithm， GOA）[6]、麻雀搜索算法（Sparrow search algorithm， SSA）[7]等。智能優化算法綜述[8]對近年6種算法進行基準測試函數試驗并分析，它的結論表明SSA在優化問題的求解精度、收斂速度、執行時間等方面具有極好的效果。

SSA的尋優過程分為探索和開發兩個階段。探索階段是以隨機性方式進行全局搜索，進而達到解空間的區域劃分。開發階段是對探索階段的劃分區域進行更精細的局部搜索，從而獲得更高精度的解。從兩個過程中不難發現，探索階段容易導致解的精度下降及收斂速度降低，而開發階段又易使解陷入局部最優。

針對上述問題，呂鑫等[9]通過Tent混沌映射、高斯變異和Tent混沌擾動等方式來克服算法易陷入局部極值點的缺陷。歐陽城添等[10]通過折射反向學習、瘋狂算子等方式來尋找高質量的解。文獻[11]引入可變螺旋因子減少越界個體的數量，保證算法細致靈活的搜索能力，同時以逐維鏡像學習策略來克服算法易陷局部極值點的缺點。這些改進措施在一定程度上提高了算法的尋優能力，但依然有不足之處，例如Tent混沌遍歷性較弱；瘋狂算子和逐維鏡像學習易導致有效解的丟失。因此，本文提出一種融合回歸模型的麻雀搜索算法（Sparrow search algorithm with logistic regression， SSAWLR），首先通過朱明豪[12]提到的Sine-Sine混沌（SSM）映射初始化種群，使得初代麻雀個體具有更高的隨機性及遍歷性；再用Logit模型自適應調整發現者和跟隨者的數量，進而更加靈活的平衡探索和開發兩個階段；同時引入步長因子增加發現者的跳躍步長，增加算法高精度解的搜索能力。最后，選取粒子群算法（PSO）[13]、鯨魚優化算法（WOA）[14]、灰狼優化算法（GWO）[15]、SSA四種算法在15個常用基準測試函數進行仿真試驗，并將SSAWLR用于Taylor迭代初值的估計問題[16]，驗證了本文算法的可行性和有效性。

1? SSA

SSA是通過模擬麻雀覓食行為和反捕食行而抽象出來的一種群體智能優化算法。其仿生原理是：用搜索空間中的點模擬自然界中的麻雀個體，將搜索優化過程模擬成麻雀覓食和反捕食的過程，將所求問題的適應度函數值度量成麻雀種群個體攜帶的能量高低，將保留高能量個體過程類比為搜索和優化過程中保留最優可行解的過程。

麻雀個體在搜索空間的位置信息可用矩陣，其中 表示第i只麻雀的m維位置信息，則它們對應的適應度函數為 。

麻雀搜索算法中的種群以不同工作機制搜索最優解，并根據不同機制分別劃分為發現者、跟隨者、預警者。發現者為種群提供搜索方向，跟隨者為種群提供精細搜索，預警者為種群增加跳出局部最優能力。發現者占種群總數的10%～20%，其位置更新公式為：

式（1）中：t表示當前迭代次數；T表示最大的迭代次數；α表示（0，1]的均勻隨機數；Q表示服從標準正態分布的隨機數；L表示大小為1×d且元素均為1的矩陣；R表示[0，1]的一個隨機數，即警戒值；ST表示[0.5，1]的一個自選安全值。當R＜ST時，表明周圍無捕食者，發現者能對該區域更精細化搜索。當R＞ST時，表明發現捕食者，發現者會帶領種群前往更安全的區域。

跟隨者占剩余種群的數量，其位置更新公式為：

式（2）中：xp表示當前發現者占據的最優位置；xworst是當前全局最差位置。A表示一個只含有1或-1元素的1×d維矩陣，其中A+=AT（AAT）-1。n表示種群數量，當i＞n/2時，跟隨者沒有獲取食物需要自己尋找食物獲取能量；當i≤n/2，跟隨者追尋發現者的方向與之爭奪更高能量的食物。

預警者從整個種群中隨機挑選，占群體總數的10%～20%，其位置更新公式為：

式（3）中： 表示當前全局最優位置。β表示控制步長的參數，它是服從均值為0，方差為1的正態分布隨機數。K表示屬于[-1，1]的隨機數，它控制著麻雀運動的方向以及步長。ε是一個避免分母為0的極小值。fi、fg、fw分別表示當前第i只麻雀個體的適應度值、麻雀個體中最優適應度值以及麻雀個體中最差適應度值。

2? SSAWLR

2.1? Sine-Sine混沌映射

智能優化算法原理是通過迭代更新初始種群的方式逼近目標函數的解，所以算法尋優效果的好壞與初始種群是否均勻密不可分。在SSA中，采用隨機方式映射種群，這容易造成種群分布不均的情景。相比隨機映射來說，混沌映射具有遍歷性、隨機性、普適性等特點，且它是一種在有限區域內永不重復的映射。所以，通過混沌映射得到的初代種群，不僅能擁有豐富的多樣性，還能提高算法的全局尋優性能。

典型的混沌模型有Logistic映射和Tent映射等，而它們不僅穩定性先天不足，且中間和兩邊密度分布不均勻的缺陷。SSM是具有魯棒性的特殊映射，該映射具有分布均勻和穩定性好等優點。SSM映射的數學表達式為：

yn+1=（u·sin（π·c1·yn）+（1-u）·sin（π·c2·yn））mod1? ?u∈[0，1]（4）

其中，u是整個系統的參數，本文取值為0.75。ci（i={1，2}）是系統的控制參數，分別取值50.96和50.32。mod是取余數。

本文采用SSM映射SSA的初始種群。由式（4）可得，SSAWLR的初始種群公式為：

xi，d=xl+（xu-xl）·yi，d? ? ? ? ? ? ? ? ? ? ? ? ? ?（5）

其中：xl、xu分別表示搜索范圍的下限以及上限，yi，d由式（5）產生的混沌值。

Logistic映射、Tent映射和SSM映射分別進行1 000次迭代運算，結果如圖1所示。Logistic函數迭代結果呈現為明顯的凹槽分布，其初始種群極易分布在上下界周圍。Tent函數迭代結果分布較為均勻，但兩頭的選取次數依然較高，初始種群均勻性較差，易導致初代種群聚集在邊界，影響尋優性能。而SSM函數迭代結果分布更加均勻，優于前兩種映射迭代結果。

2.2? Logit模型

SSA中的發現者和跟隨者的數量是固定不變的，其中發現者的職責是指明種群前進的方向，但到后期并不能提高尋優精度，而跟隨者是依據發現者的方向進行局部搜索，前期更多的跟隨者反而會使全局搜索能力下降。針對這種情景，可以采用動態調整策略來改變它們各自的數量。Logit模型曲線具有兩頭較平緩，中間陡峭的特點，這能滿足算法迭代前期發現者數量多且緩慢下降，后期發現者數量少的需求，因此本文借鑒了該模型曲線。動態調整策略的公式為：

式（6）中：k1、k2表示控制參數，分別控制P的取值上限以及取值下限；t為當前迭代次數；tmax是最大迭代次數。在本文中取值k1=1，k2=0.1。

針對動態調整公式的仿真如圖2所示。由圖可知，前期發現者在麻雀總數中占比高，中期發現者數量陡降，后期發現者占比小且穩定。

2.3? 步長因子

針對麻雀搜索算法的發現者的位置更新公式（見式（1））中的? 進行迭代仿真。假設種群規模為30，迭代次數為200次。仿真結果如圖3所示。

從仿真結果可得，指數項高密度區間是[0.8，1]，這導致發現者的移動步長較短，影響了算法收斂速度。因此，針對此問題，在原有公式基礎上增加了步長因子λ。改進的發現者位置更新公式為：

針對改進后的發現者位置更新公式（如式（7）所示）中的? 進行迭代仿真。假設條件相同，仿真結果如圖4所示。由圖可知，改進后的指數項密度區間為[0.6，1]，更寬的密度區間有利于搜索空間更均勻劃分，加強了算法局部開發能力。

2.4? 越界處理方式

越界處理通常有2種方式：1）邊界值替換越界值；2）隨機回歸值替換越界值。方式1）會導致解容易聚集于邊界，降低了尋優效率以及精度。方式2）雖然解決了邊界聚集問題，但也丟失了麻雀個體位置更新的趨勢。為了解決兩種方式的各自缺陷，本文將兩種方法進行結合，越界處理公式為：

式（9）中：h是一個[0，1]區間的隨機數。該方法既能讓部分越界值的回歸具有一定的彈性，還能使得其他越界值保留位置更新趨勢，提升了麻雀個體的多樣性。

2.5? 算法流程

算法流程圖如圖5所示。

2.6? 時間復雜度分析

時間復雜度是衡量算法性能的重要指標，能直觀表達算法的運算時間。

假設原算法的種群規模為P，最大迭代次數為N，維數為D，那么原算法的時間復雜度為O（P·N·D）。從宏觀上看，改進后的麻雀算法并沒有改變算法的本身結構和循環過程，所以它的時間復雜度也是O（P·N·D），與原算法時間復雜度一致。從微觀上看，混沌映射增加了初始種群時算法的復雜度，Logit模型以及步長因子增加了發現者的算法復雜度，但這些改進策略的引入并沒有增加算法的數量級，所以時間復雜度還是O（P·N·D）。

3? 算法性能測試

3.1? 實驗設計

為了驗證SSAWLR的性能及可行性，本文選取PSO、GWO、WOA、SSA四種算法在15個常用的基本測試函數進行對比測試。算法參數在表1中列出，15個測試函數在表2中列出，其中F1～F5的單峰值函數測試算法的精度以及收斂能力，F6～F9的多峰值函數和F10～F15的固定維函數能測試算法跳出局部極值點的能力。每個算法的種群規模和最大迭代次數分別為30和1 000，為了避免偶然因素影響，每個算法分別獨立運行30次計算其最佳值（best）、平均值（Ave）、標準值（Std），每個指標的最優值以粗體處理，最后進行實驗結果分析。

3.2? 算法性能對比分析

由表3可知，SSAWLR在大部分函數中排名第一，尤其在函數F7、F9、F12、F14、F15中不僅尋到了理論最優值而且其方差最小，可見SSAWLR具備很好的尋優能力。SSAWLR對比其他算法來說，單峰值函數中除函數F5外的優化精度高出了大量數量級，說明其具有很好的尋優精度；多峰值函數中除函數F6外最優值最小，可見其具有良好的跳出局部極值的能力。固定維函數中除函數F11外，計算的方差最小，說明其具有良好的穩定性。綜上分析，SSAWLR算法具有良好的性能及可行性且它的改進策略是有效的。

3.3? 算法收斂曲線分析

收斂曲線能夠更加直觀地展示算法收斂的速度以及精度。由圖6可知，SSAWLR算法在大多數測試函數中收斂的速度最快以及精度最高。從單峰值函數來看，SSAWLR均能快速迭代并獲得最優值，可見其具有較快的收斂速度。除函數F6外的剩余測試函數來看，SSAWLR依然具有更好的尋優能力，并找到最好的適應度值。尤其在函數F7、F8中，SSAWLR均能在迭代50次之前到達理論最優值。綜上，SSAWLR算法不僅具有快速的收斂速度還有更高的收斂精度。

4? 基于SSAWLR和Taylor算法的協同定位方法

基于到達時間差（Time Difference of Arrival， TDOA）的迭代定位算法中以Taylor算法最為經典。該算法思想是通過不斷迭代來修正待定目標位置的估計值，直到估計值逼近目標的真實位置坐標，所以它的精度極易受估計值的影響。本文采用SSAWLR進行估計值的預估，然后將結果帶入Taylor中進行定位計算。本文適應度函數設計如式（12），評價函數則以均方根誤差式（13）作為定位優劣的測度：

其中f1=p2-p1-r2，1，f2=p3-p1-r3，1，f3=p4-p1-r4，1，f4=p5-p1-r5，1。pi（i=1，2，3，4，5）是目標估計值到基站的距離，ri，1是目標到基站i與基站1距離差的測量值。（xkr，ykr）是第k個目標真實坐標，（xk，yk）是計算出的第k個估計位置，n是目標的個數。

為了驗證本文所提SSAWLR-Taylor算法的性能，因此，與Chan[17]、Taylor、SSA_Taylor進行仿真對比。仿真實驗基站坐標為（0，0）、、、、，并假設滿足均值為0，且標準差分別為0.01、0.02、0.03、0.04、0.05、0.06、0.07、0.08、0.09、0.10的具有理想高斯分布特性的測量誤差。基站（0，0）作為中心基站，并以它為圓心，在其半徑為7內隨機生成100個目標坐標，同時把目標的橫坐標與縱坐標分別加上[-1，1]區間上的隨機數作為Yaylor定位算法的初值。SSA和SSAWLR麻雀種群規模為Num=100，最大迭代次數Max=50次，目標函數維度Dim=2，邊界的上界和下界分別為Ub=7，Lb=-7，上述物理量的量綱單位均是千米。圖6是不同測量誤差（SD）下100個目標的均方根誤差（RMSE）對比。

從圖7可知，在不同測量誤差下，即使目標的初次估計值距離目標坐標1 km內變化，Taylor算法的均方根誤差依然高于Chan算法，更何況初次估計值離目標較遠時，Taylor就更難完成目標坐標定位。而SSA_Taylor和SSAWLR_Taylor的定位效果優于Taylor算法，它們的均方根誤差和閉式解的Chan算法接近，說明它們都提供了高質量的初代估計值，進而很大程度上增加了Taylor算法的定位精度。由此可見，SSAWLR和SSA分別與Taylor算法的融合是有效可行的，并且使得Taylor在有限次迭代內具有閉式解的精度。

5? 結? 論

本文提出了一種融合邏輯回歸的麻雀算法，該算法引入了四種策略：SSM映射、邏輯回歸函數、步長因子、改進的邊界控制。該算法克服了初代種群多樣性欠缺、發現者和跟隨者數量利用率低及收斂速度緩慢的缺陷。測試函數結果反應了該算法有良好的性能和普適性。Taylor初值估計的結果表明了該算法具有好的實用性。

SSAWLR_Taylor有很好的優化性能，但仍有不足之處。比如算法跳出極值點的能力較弱及某些性能指標較差且不穩定。針對不足之處，今后還需要做一些工作：一是，如何增強算法的全局開發能力。二是，如何提高算法的穩定性。三是，如何有效利用越界個體攜帶的信息。

參考文獻：

[1] CHEN J F，WANG L，PENG P. A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling [J/OL].Swarm and Evolutionary Computation，2019，50（C）：100557[2022-08-09].https：//doi.org/10.1016/j.swevo.2019.100557.

[2] LIU W，GONG Y，CHEN W，et al. Coordinated Charging Scheduling of Electric Vehicles：A Mixed-Variable Differential Evolution Approach [J].IEEE Transactions on Intelligent Transportation Systems，2020，21（12）：5094-5109.

[3] ZHOU S，XING L，ZHENG X，et al. A Self-Adaptive Differential Evolution Algorithm for Scheduling a Single Batch-Processing Machine With Arbitrary Job Sizes and Release Times [J].IEEE Transactions on Cybernetics，2021，51（3）：1430-1442.

[4] XUE Y，ZHANG Q，ZHAO Y. An improved brain storm optimization algorithm with new solution generation strategies for classification [J/OL].Engineering Applications of Artificial Intelligence，2022，110：104677[2022-08-09].https：//doi.org/10.1016/j.engappai.2022.104677.

[5] ARORA S，SINGH S. Butterfly optimization algorithm：a novel approach for global optimization [J].Soft Computing，2019，23（3）：715-734.

[6] ARORA S，ANAND S. Chaotic grasshopper optimization algorithm for global optimization [J].Neural Computing and Applications，2019，31（8）：4385-4405.

[7] XUE J，SHEN B. A novel swarm intelligence optimization approach：sparrow search algorithm [J].Systems Science & Control Engineering，2020，8（1）：22-34.

[8] 張九龍，王曉峰，蘆磊，等.若干新型智能優化算法對比分析研究 [J].計算機科學與探索，2022，16（1）：88-105.

[9] 呂鑫，慕曉冬，張鈞，等.混沌麻雀搜索優化算法 [J].北京航空航天大學學報，2021，47（8）：1712-1720.

[10] 歐陽城添，朱東林，王豐奇，等.基于折射麻雀搜索算法的無人機路徑規劃 [J].電光與控制，2022，29（6）：25-31.

[11] YAN S，YANG P，ZHU D，et al. Improved Sparrow Search Algorithm Based on Iterative Local Search [J].Computational Intelligence and Neuroscience，2021，2021：1-31.

[12] 朱明豪.基于1D離散混沌映射的組合系統研究 [D].長沙：湖南大學，2020.

[13] KENNEDY J，EBERHART R C. A discrete binary version of the particle swarm algorithm [C]//1997 IEEE International conference on systems，man，and cybernetics. Computational cybernetics and simulation. IEEE，1997：4104-4108.

[14] MIRJALILI S，LEWIS A. The whale optimization algorithm [J].Advances in Engineering Software，2016，95：51-67.

[15] MIRJALILI S，MIRJALILI S M，Lewis A. Grey Wolf Optimizer [J].Advances in Engineering Software，2014，69：46-61.

[16] FOY W H. Position-Location Solutions by Taylor-Series Estimation [J].IEEE Transactions on Aerospace and Electronic Systems，1976，AES-12（2）：187-194.

[17] CHAN Y T，HO K C. A simple and efficient estimator for hyperbolic location [J].IEEE Transactions on Signal Processing，1994，42（8）：1905-1915.

作者簡介：彭一凱（1990—），男，苗族，湖南懷化人，碩士研究生在讀，主要研究方向：目標識別與跟蹤、多點定位；蒲紅平（1975—），男，漢族，四川廣安人，副教授，博士，主要研究方向：大數據分析、智能控制、智能信號分析與處理、工業自動化研究與工程應用。