一種用于DGPS 整周模糊度解算的混合策略麻雀搜索算法?

霍 剛，尚俊娜

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

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

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

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

1 麻雀搜索算法基本原理

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

1.1 更新發現者位置

種群中的發現者作為整個種群中的覓食引導者，引導跟隨者向食物的方向靠近。一旦發現有捕獵者靠近，即預警值大于安全值，將會帶領種群朝安全地區前進。其位置更新公式如下:

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

1.2 更新跟隨者位置

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

1.3 更新警戒者位置

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

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

1.4 SSA 搜索流程

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

算法1 SSA

2 混合策略麻雀搜索算法

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

2.1 HSSSA 算法

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

算法2 HSSSA

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

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

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

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

圖1 初始化粒子分布圖

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

2.3 基于粒子速度策略的發現者位置更新

在SSA 算法中，當R2

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

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

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

經過完善之后的發現者位置更新公式如下:

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

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

式中:β為標準正態分布隨機數；Xbest和Xworst分別是當前的全局最優覓食位置和全局最差覓食位置。

2.4 基于高斯變異策略的最優個體位置更新

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

2.5 HSSSA 的時間復雜度分析

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

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

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

在更新發現者階段，速度更新所需時間為t2，則該階段的時間復雜度為:

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

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

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

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

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

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

表1 基準測試函數

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

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

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

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

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

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

4 仿真實驗結果與驗證

4.1 仿真實驗與結果分析

4.1.1 基準測試函數說明和算法參數設置

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

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

表2 算法參數設置

表3 基準測試函數優化對比

4.1.2 仿真結果分析

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

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

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

圖3 9 個基準測試函數的尋優實驗收斂曲線

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

4.2 實測結果與分析

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

表4 算法參數設置

表5 四種算法解算結果對比

圖4 現場測試圖

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

5 結論

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