霍 剛，尚俊娜

(杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018)

差分全球定位系統(tǒng)(Differential Global Position System，DGPS)是利用已知精確三維坐標的差分GPS 基準站，求得偽距修正量或位置修正量，將此修正量發(fā)送給監(jiān)測站，監(jiān)測站使用接收的基準站修正量進行誤差修正，從而提高GPS 定位精度。差分GPS 根據(jù)差分GPS 基準站發(fā)送的差分校正目標參量分為位置差分、偽距差分和載波相位差分。在采用載波相位差分測量時，整周模糊度的確定是核心問題。整周模糊度是指在測量中，基準站與監(jiān)測站的載波相位觀測值作差，其差值是載波波長中的小數(shù)部分長度，但是其載波波長的整數(shù)部分是個未知數(shù)，此未知數(shù)即為整周模糊度。通常整周模糊度求解步驟如下:首先利用最小二乘法得到模糊度的浮點解和協(xié)方差矩陣；其次對模糊度浮點解和協(xié)方差陣進行去相關(guān)處理降低模糊度間的相關(guān)性，然后構(gòu)建模糊度搜索空間；最后通過LAMBDA 算法、麻雀搜索算法、混合策略麻雀搜索算法等方法搜索整周模糊度固定解[1－3]。本文引入混合策略麻雀搜索算法求解整周模糊度。

麻雀搜索算法(Sparrow Search Algorithm，SSA)是近年來提出的一種新型群體智能優(yōu)化算法，被成功應(yīng)用于各個行業(yè)當(dāng)中[4－5]。該算法主要受麻雀日常的覓食行為啟發(fā)，在實際應(yīng)用中具有局部搜索能力強、所需調(diào)節(jié)參數(shù)少等特點。然而在搜索過程中，種群多樣性減少，易陷入局部最優(yōu)，全局搜索能力弱。為提升麻雀搜索算法的尋優(yōu)性能，國內(nèi)外學(xué)者對其算法的改進進行了研究。張曉萌等[6]在前人研究的基礎(chǔ)上，對麻雀搜索算法進行了優(yōu)化和完善，借助于正弦搜索方法來提升算法的局部檢索能力，甚至還融入了生物種群聚集的相關(guān)概念和規(guī)律，促使算法的檢索功能更為強大。此外，段玉先等[7]則將Sobel 理念與麻雀搜索算法相結(jié)合，并通過縱橫交叉策略來改善算法的全局檢索能力，擴大了算法的適用范圍。

SSA 具有較快的收斂速度與求解精度，在面對解空間較大的高維問題時也有良好表現(xiàn)，但其全局搜索能力不足、易于陷入局部最優(yōu)，因此本文提出一種混合策略麻雀搜索算法(Hybrid Strategy Sparrow Search Algorithm，HSSSA)。改進算法引入Circle 混沌映射進行種群初始化，提高初始種群的多樣性，改善全局搜索能力[8]。引入粒子群算法(PSO)中粒子移動時的速度策略，加強麻雀種群每一代之間的聯(lián)系，加強個體間的信息交流，增強算法的尋優(yōu)能力。引入高斯變異策略對最優(yōu)麻雀個體進行擾動，改善算法易陷入局部最優(yōu)的問題，有效增強了算法的適用性[9]。選取9 個基準函數(shù)對HSSSA 算法的性能與SSA 算法、PSO 算法、GWO 算法和其他文獻改進麻雀搜索算法的性能進行對比，進而驗證HSSSA 算法的優(yōu)越性。通過應(yīng)用HSSSA 算法于DGPS 整周模糊度的解算當(dāng)中，進一步驗證了HSSSA 算法的有效性和可行性。

1 麻雀搜索算法基本原理

麻雀搜索算法(SSA)是在麻雀覓食的行為規(guī)律基礎(chǔ)上經(jīng)過創(chuàng)新而得到的一種檢索算法。在數(shù)據(jù)檢索中，該算法就像麻雀覓食一樣來探尋有效數(shù)據(jù)樣本，同時還具備一定的預(yù)警功能。SSA 將麻雀種群分為發(fā)現(xiàn)者和跟隨者，同時加入警戒者機制，隨機選取一定數(shù)量的警戒者。

1.1 更新發(fā)現(xiàn)者位置

種群中的發(fā)現(xiàn)者作為整個種群中的覓食引導(dǎo)者，引導(dǎo)跟隨者向食物的方向靠近。一旦發(fā)現(xiàn)有捕獵者靠近，即預(yù)警值大于安全值，將會帶領(lǐng)種群朝安全地區(qū)前進。其位置更新公式如下:

式中:t代表當(dāng)前迭代次數(shù)，j是每個個體的維度，j＝1，2，3，…，N。MaxIter 是一個常數(shù)，是全局檢索過程中最大的迭代次數(shù)。Xi，j表示第i個發(fā)現(xiàn)者在第j維中的位置信息，Q是服從標準正態(tài)分布的隨機數(shù)，L是一個1×N的全1 矩陣。α∈(0，1]是一個隨機數(shù)。R2(R2∈[0，1])和ST(ST∈[0.5，1])分別表示預(yù)警值和安全值。在本文中，R2是一個隨機值，ST 是一個固定值。

1.2 更新跟隨者位置

跟隨者根據(jù)發(fā)現(xiàn)者提供的信息時刻進行覓食來獲取更高的適應(yīng)度。此外，在算法工作的過程中，兩者是可以相互轉(zhuǎn)換的，但種群的規(guī)模是維持不變的。跟隨者位置更新公式如下:

1.3 更新警戒者位置

警戒者會隨時偵查環(huán)境，警戒周圍環(huán)境所發(fā)生的變化。如果發(fā)現(xiàn)捕食者的蹤跡，會第一時間發(fā)出警示，位于邊緣的個體會朝著安全區(qū)移動，而原本就位于安全位置的個體則會在個體附近移動。警戒者的數(shù)量一般占據(jù)整個種群的10%～20%。警戒者位置更新公式如下:

式中:Xbest是當(dāng)前的全局最優(yōu)覓食位置；fi是當(dāng)前麻雀個體的適應(yīng)度值，fg和fw分別是當(dāng)前全局最佳和最差的適應(yīng)度值；β和K均為步長控制參數(shù)，β服從標準正態(tài)分布，K∈[－1，1]的一個隨機數(shù)；ε是最小的常數(shù)。

1.4 SSA 搜索流程

SSA 搜索流程如算法1 所示。

算法1 SSA

2 混合策略麻雀搜索算法

針對SSA 在求解過程中出現(xiàn)的種群多樣性減少、全局搜索能力弱以及易陷入局部最優(yōu)等問題，提出了一種混合策略麻雀搜索算法(HSSSA)。首先，引入Circle 混沌映射策略進行種群初始化，增強初始種群的多樣性；其次，引入粒子群算法(PSO)中粒子速度策略對發(fā)現(xiàn)者位置更新公式進行改進，增強算法的尋優(yōu)能力；最后，引入高斯變異策略對最優(yōu)個體進行變異以生成新個體，增強跳出局部最優(yōu)的能力。

2.1 HSSSA 算法

HSSSA 搜索流程如算法2 所示。

算法2 HSSSA

2.2 基于Circle 混沌映射策略的種群初始化

麻雀搜索算法采用隨機生成的方式對種群初始化，所以導(dǎo)致初始種群容易出現(xiàn)聚集現(xiàn)象，且初始種群在空間內(nèi)覆蓋不均勻，個體之間差異性較大，給之后的迭代尋優(yōu)帶來極大的負面影響。由于混沌映射具有隨機性、遍歷性和規(guī)律性等優(yōu)點，因此通過引入混沌映射完成種群初始化，其主要思想是利用混沌的特性，將變量映射到混沌變量空間的取值區(qū)間內(nèi)，最后將解線性地轉(zhuǎn)化到優(yōu)化變量空間。考慮到各項映射方法的特點，本文采用Circle 混沌映射對麻雀種群進行初始化，其表達式如下:

式中:a＝0.5，b＝0.2，k表示維度。

將隨機生成和Circle 混沌映射的初始化粒子做歸一化處理，在[0，1]區(qū)間內(nèi)生成粒子分布如圖1所示。

圖1 初始化粒子分布圖

從圖1(a)和圖1(b)對比分析可知，利用Circle映射的粒子分布比隨機生成的粒子分布在空間中更加均勻，擴大了麻雀種群在空間中的搜索范圍，增強種群的多樣性，進而增強算法的尋優(yōu)能力，且能避免在最優(yōu)解附近麻雀種群較少的情況[10]。

2.3 基于粒子速度策略的發(fā)現(xiàn)者位置更新

在SSA 算法中，當(dāng)R2

粒子群算法(Particle Swarm Optimization，PSO)是根據(jù)鳥群捕食的行為研究提出的一種群智能算法。在PSO 算法中，各個粒子擁有兩類屬性，其一是粒子的坐標，其二則是粒子運動的速度。前者表示粒子在運動過程中的相對位置，而后者則表示運動的快慢。PSO 算法在工作過程中可以分為以下步驟:首先，每個粒子在搜索空間內(nèi)進行局部檢索，其次找到每個粒子的個體極值與當(dāng)前全局最優(yōu)粒子的個體極值，其中每個粒子的速度由當(dāng)前粒子的個體極值與最優(yōu)粒子的個體極值確定。

根據(jù)粒子群算法中的粒子速度策略，在混合策略麻雀搜索算法中，各個麻雀的位置即是粒子群算法中的粒子，每只麻雀移動的速度大小是根據(jù)自己的當(dāng)前位置和當(dāng)前全局最優(yōu)麻雀位置進行調(diào)整計算，速度更新公式如下:

式中:w為慣性因子，在HSSSA 算法中，w是一個具有隨機的周期性下降的常數(shù)，c1和c2為加速常數(shù)，一般取c1＝c2∈[0，4]，random(0，1)表示區(qū)間[0，1]上的隨機數(shù)。Pi，j表示第i個變量的個體極值的第j維，Pg，j表示全局最優(yōu)解的第j維，Vti，j表示第i個變量第j維的速度值。

經(jīng)過完善之后的發(fā)現(xiàn)者位置更新公式如下:

經(jīng)過優(yōu)化完善之后，每一只麻雀的行動會先跟最優(yōu)麻雀位置參照對比，在最優(yōu)解的基礎(chǔ)上來明確行進的方向，這樣就能夠解決各次迭代缺少信息交流的問題，提高數(shù)據(jù)迭代的精準性。并且由于慣性因子w的存在，麻雀個體的移動在一定程度上受到上一代種群個體的影響，加強了每一代種群之間的聯(lián)系。另一方面，PSO 速度策略的引用，在一定程度上擴大了搜索空間，在式(6)中，速度對發(fā)現(xiàn)者的影響隨著迭代次數(shù)的增加不斷減小，以保證在迭代中搜索空間不會一直增大。

同時，在SSA 算法的警戒者更新公式中，若該麻雀個體不是處于當(dāng)前最優(yōu)覓食位置時，它會跳躍至當(dāng)前的最優(yōu)麻雀位置附近，由于該操作會導(dǎo)致SSA 算法易于陷入局部最優(yōu)，因此對警戒者更新公式做如下修改:

式中:β為標準正態(tài)分布隨機數(shù)；Xbest和Xworst分別是當(dāng)前的全局最優(yōu)覓食位置和全局最差覓食位置。

2.4 基于高斯變異策略的最優(yōu)個體位置更新

最初的SSA 算法中，最優(yōu)個體的位置更新依賴于種群的更新，即每次迭代完成后，由當(dāng)前種群內(nèi)適應(yīng)度最好的個體作為新的最優(yōu)個體，算法沒有主動對最優(yōu)個體進行擾動。如果最優(yōu)個體陷入局部極值空間，會導(dǎo)致算法陷入局部最優(yōu)的泥淖中。因此，為了增強算法跳出局部最優(yōu)能力，本文使用高斯變異策略，對當(dāng)前適應(yīng)度最好的個體進行變異，與變異前的位置進行比較，選擇較優(yōu)的位置進入下一代，具體公式為:

2.5 HSSSA 的時間復(fù)雜度分析

時間復(fù)雜度能夠直觀地反應(yīng)一個算法的性能，假設(shè)麻雀算法的種群規(guī)模參數(shù)和解空間維度參數(shù)分別為N和D，目標函數(shù)求解所需要的執(zhí)行時間為f(D)，根據(jù)文獻[11]知基本麻雀算法的時間復(fù)雜度為:

在HSSSA 算法中，參數(shù)初始化執(zhí)行時間為t0，按照式(6)生成初始種群所需時間為t1，則算法在初始化麻雀種群階段的時間復(fù)雜度為:

麻雀算法的發(fā)現(xiàn)者與警戒者比例分別是SD 與PD，則麻雀種群中，發(fā)現(xiàn)者數(shù)量為SD×N，警戒者數(shù)量為PD×N，跟隨者數(shù)量為(1－SD)×N。

在更新發(fā)現(xiàn)者階段，速度更新所需時間為t2，則該階段的時間復(fù)雜度為:

在更新跟隨者位置階段和更新警戒者階段，HSSSA 算法與麻雀算法的時間復(fù)雜度相同，均為O(D)，其時間復(fù)雜度為:

在高斯變異擾動階段，生成高斯變異隨機變量所需要的時間為t3，按照式(10)更新高斯變異所需時間為t4，則此階段時間復(fù)雜度為:

綜上所述，HSSSA 在最大迭代次數(shù)為MaxIter的情況下，其時間復(fù)雜度為:

由此可見，HSSSA 算法與SSA 算法的時間復(fù)雜度相同。

3 混合策略麻雀搜索算法求解整周模糊度

在DGPS 的載波相位差分定位中，原始偽距、載波相位值經(jīng)過單差、雙差處理后，使用最小二乘法可以得到整周模糊度浮點解，即整周模糊度中未固定的解。但整周模糊度的不固定會對測量結(jié)果造成分米級甚至米級的誤差，例如GPS 衛(wèi)星中的L1 載波，其頻率為1 575.42 MHz，波長為0.190 3 m，這代表1 個整周波長對測量結(jié)果的影響是0.190 3 m。因此采用混合策略麻雀搜索算法來求解整周模糊度固定解。

表1 基準測試函數(shù)

利用HSSSA 找出樣本數(shù)據(jù)中的最優(yōu)解，首先要明確搜索的最佳檢索范圍，這個范圍并不是隨意確定的，不僅需要縮小檢索的范圍，提高檢索效率，同時還必須含有系統(tǒng)的最優(yōu)解。對此，檢索空間表示如下:

式中:[Ni]為浮點解N在第i維的整數(shù)取值，m為搜索空間的大小，計算公式為m＝｜1/λ｜，例如，L1 載波，波長為19.03 cm，則m＝｜1/λ｜＝6。因此，HSSSA 算法的上下界可由式(15)確定為lb＝[Ni]－6，ub＝[Ni]＋6。

搜索空間確定后，HSSSA 算法還需確定每只麻雀的適應(yīng)度值，在搜索整周模糊度固定解問題中，其適應(yīng)度函數(shù)的表達式為:

式中:Ni表示為浮點解矩陣，QN表示為協(xié)方差矩陣，N為麻雀每次搜索得到的一組整數(shù)。

至此，混合策略麻雀搜索算法確定整周模糊度工作步驟具體可以參見圖2。首先，算法的輸入值是經(jīng)過一系列預(yù)處理之后的浮點解，接著將這部分數(shù)值進行HSSSA 搜索，最終可以得到整周模糊度固定解[12－13]。

圖2 混合策略麻雀搜索算法搜索整周模糊度流程

4 仿真實驗結(jié)果與驗證

4.1 仿真實驗與結(jié)果分析

4.1.1 基準測試函數(shù)說明和算法參數(shù)設(shè)置

本次實驗選取9 個基準測試函數(shù)對HSSSA 算法的性能進行對比測試檢驗，基準測試函數(shù)的具體信息如表1 所示。

選取麻雀搜索算法(SSA)、粒子群算法(PSO)[14]、灰狼算法(GWO)[15]、融合柯西變異和反向?qū)W習(xí)的改進麻雀算法(ISSA1)[11]、基于Sobol 序列和縱橫交叉策略的麻雀搜索算法(SSASC)、基于螢火蟲改進麻雀搜索的算法(ISSA2)及混合策略麻雀搜索算法(HSSSA)進行尋優(yōu)對比。表2 是每個算法的參數(shù)設(shè)置。七種算法的種群規(guī)模為120，最大迭代次數(shù)30，為降低實驗結(jié)果的統(tǒng)計誤差，每種算法獨立運行50 次，每種算法達到最大迭代次數(shù)后停止迭代，并輸出最優(yōu)解。表3 是50 次獨立實驗每種算法求解各測試函數(shù)的最優(yōu)解(Best)、最差值(Worst)、平均值(Mean)和標準差(Std)。

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

表3 基準測試函數(shù)優(yōu)化對比

4.1.2 仿真結(jié)果分析

從表3 分析可知，HSSSA 算法的統(tǒng)計結(jié)果在9個基準測試函數(shù)的求優(yōu)實驗中明顯優(yōu)于其他六種算法。在單峰函數(shù)f1、f2、f3、f4的實驗中，HSSSA 能夠穩(wěn)定地找到其理論最優(yōu)解，尋優(yōu)效果遠超SSA、PSO、GWO、SSASC、ISSA1、ISSA2；在單峰函數(shù)f5的實驗中，七種算法都不能找到理論最優(yōu)解，但HSSSA 算法的尋優(yōu)結(jié)果優(yōu)于其他六種對比算法；在多峰函數(shù)f6、f7的實驗中，SSA、SSASC、ISSA1、ISSA2以及HSSSA 都能穩(wěn)定地尋找到其理論最優(yōu)解，說明了該算法本身的優(yōu)越性；在多峰函數(shù)f8的實驗中，七種算法都不能找到其理論最優(yōu)解，但HSSSA 在最優(yōu)值、平均值和標準差上相比于其他算法有較大的提升；在低維多峰函數(shù)f9的實驗中，HSSSA 和ISSA1可以找到最優(yōu)值，但HSSSA 算法的平均值、標準差優(yōu)于ISSA1，且尋優(yōu)效果達到100%。

通過上述分析可知，對于五種單峰函數(shù)的測試，HSSSA 算法的尋優(yōu)效果優(yōu)于其他六種算法，說明HSSSA 算法收斂效率優(yōu)于其他六種算法；其次，對于四種多峰函數(shù)的測試，HSSSA 算法的尋優(yōu)效果優(yōu)于其他六種算法，說明HSSSA 算法具有良好的跳出局部最優(yōu)的能力。

為了更加直觀地說明HSSSA 有著更好的尋優(yōu)精度以及收斂速度，圖3 給出各個算法優(yōu)化測試函數(shù)的收斂曲線對比，圖3 中橫坐標為迭代次數(shù)，縱坐標為適應(yīng)度值。

圖3 9 個基準測試函數(shù)的尋優(yōu)實驗收斂曲線

從圖3 可以看出，對于9 個基準測試函數(shù)在相同的收斂精度下，HSSSA 所需迭代次數(shù)最少，其收斂速度優(yōu)于其他六種對比算法。在相同的尋優(yōu)次數(shù)下，HSSSA 的求解精度高于其他六種對比算法的求解精度。至此，HSSSA 的可行性和有效性得以證明。

4.2 實測結(jié)果與分析

本次實驗以現(xiàn)場測試來了解改進后算法的性能，具體試驗圖可以參見圖4。在圖中，整個測試系統(tǒng)包含兩個天線模組，數(shù)據(jù)的接收模塊能夠處理多種類型的數(shù)據(jù)，并輸出偽距、載波相位等數(shù)據(jù)。計算機對接收到的數(shù)據(jù)進行處理，使用傳統(tǒng)LAMBDA 算法、麻雀搜索算法(SSA)、融合柯西變異和反向?qū)W習(xí)的改進麻雀算法(ISSA1)和混合策略麻雀搜索算法(HSSSA)進行整周模糊度解算。本實驗一共觀測了7 200 個歷元，選取其中3 000 個歷元進行解算。表4 所示是每個算法的參數(shù)設(shè)置，所有算法的種群規(guī)模為120，最大迭代次數(shù)為30，對四個算法的成功率和解算時間進行了對比，如表5 所示。

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

表5 四種算法解算結(jié)果對比

圖4 現(xiàn)場測試圖

從表5 分析可知，本文提出的HSSSA 算法在解算整周模糊度的性能上有一定的提升，在解算時間上，HSSSA 與LAMBDA 算法接近，略慢于SSA，優(yōu)于ISSA1；其成功率優(yōu)于其他三種算法，其中，HSSSA的成功率比LAMBDA 算法高3.34%，比SSA 高20.6%，比ISSA1 高1.6%。

5 結(jié)論

針對SSA 在求解過程中出現(xiàn)的種群多樣性減少、全局搜索能力弱以及易陷入局部最優(yōu)的問題，本文創(chuàng)新性地提出了一種混合策略麻雀搜索算法。首先，引入Circle 混沌映射提高樣本初始種群的分布均勻度，增強種群多樣性，提升算法的全局搜索能力；其次，引入粒子群算法中粒子速度策略，增強個體間的信息交流以及每一代種群之間的聯(lián)系；最后借助于高斯變異策略豐富種群內(nèi)部多樣性，提高算法跳出局部最優(yōu)的能力，從而提升算法的尋優(yōu)精度。9 個基準測試函數(shù)的實驗結(jié)果表明，與SSA 相比，HSSSA 具有更好的求解精度、尋優(yōu)能力和收斂速度，驗證了HSSSA 的改進效果。使用HSSSA 對整周模糊度解算中，通過與LAMBDA 算法、SSA 以及ISSA1 的對比，進一步驗證了HSSSA 的有效性和應(yīng)用可行性。