基于禁忌搜索差分進化的組合系統選星算法*

朱 軍，許士杰

（安徽大學，安徽 合肥 230601）

0 引言

目前，隨著導航定位系統的發展，全球定位衛星的數量空前巨大，包括美國的GPS，俄羅斯的GLONASS，歐洲的伽利略和中國的北斗系統。隨著衛星數量（即導航信號源）的增加，準確和實時定位的必要性變得越來越重要。冗余信號可以有效地提高定位精度，但是同時信號處理成本也急劇增加[1-2]。如果接收機使用更多的衛星進行定位，則由于高計算處理量，作為定位系統的關鍵標準的實時定位將無法實現。因此，需要一種平衡精度和性能的可見衛星選擇方法。

衛星選擇的標準是可見衛星和用戶接收機之間的空間分布的好壞，例如，幾何精度因子（Geometric Dilution of Precision，GDOP），由測量誤差與輸出位置的誤差之比定義。較小的GDOP值表示更準確的定位[3]。遍歷選星算法（Exhaust Search，ES）從所有可見衛星中遍歷所有組合以找到最優衛星組合，但選星耗時較大。因此，研究人員一直致力于GDOP計算和基于幾何分布的衛星選擇方法的開發，以降低計算成本并實現最小的GDOP[4-6]。研究者利用群體智能優化算法減少GDOP計算，實現快速選星[7-9]。其中，Meng等人對遺傳算法（Genetic Algorithm，GA）進行改進，提高了算法選星結果的準確性。盡管遺傳算法的性能與衛星幾何分布無關，但在實現GA 的計算過程中涉及參數過多，過于依賴參數設計，若設計不當，很難提高選星速度。

與GA不同，差分進化（Differential Evolution，DE）算法在變異操作方面采用差分策略，利用種群個體間的差分來擾動進化方向，避免GA中變異方式的不足，并且需調整參數大大減少。此外，基于禁忌搜索思想，以提高算法速度，提出一種混合的差分進化選星算法。

1 組合系統選星模型

組合系統選星問題可描述為：當可見衛星數目為N時，從中選擇N顆衛星參與導航定位。于是，基于群體智能優化算法的思想，解空間為CMN，依據目標函數最小的標準從解空間中尋找最優的目標解。其中，目標優化函數與可見衛星和用戶接收機的位置信息有關。

在組合系統中[10]，衛星定位的精度主要與以下兩方面因素有關：一是衛星測量誤差，測量誤差的方差越大，定位誤差的方差越大；二是衛星的幾何分布。

三維空間定位誤差的標準差σp可以表示為GDOP與用戶等效距離誤差（User Equivalent Range Error，UERE）σUERE的乘積：

從式（1）可以看出GDOP值和UERE決定了定位精度。GDOP可以看作是定位誤差對UERE的放大。因此GDOP可以在一定程度上反映衛星組合的定位精度[10]。

GDOP表示從用戶接收機指向可見衛星組合的幾何形狀，更好的幾何形狀的定位誤差較小。在衛星選擇中，GDOP的值可作為優化目標，且GDOP的計算可描述為：

式中，G為觀測矩陣，由可見衛星與用戶接收機的位置矢量組成：

式中，下標B和G分別代表BDS衛星系統和GPS衛星系統；下標1,…,m和1,…,n分別代表可見BDS衛星和GPS衛星的索引；(d,m,n)T是用戶接收機指向可見衛星的單位矢量。從式（2）和式（3）可以看出，GDOP僅取決于用戶和空間中可見衛星的幾何分布。于是，以GDOP作為衛星選擇標準，僅考慮幾何分布，且GDOP公式作為目標優化函數。

2 組合系統選星算法

基于選星模型，DE算法可以通過有限次迭代從解空間中快速搜索符合條件的最優解。然而在單獨使用DE時，無法對已搜尋過的解進行屏蔽，因此，本節討論了一種具有禁忌搜索機制的差分進化選星算法（Tabu-Search DE，TSDE）。以下各節介紹DE算法的基本概念，并對主要參數和操作進行詳細描述，包括對TSDE算法進行修改以解決上述組合系統選星問題。

2.1 差分進化結構

差分進化算法是一種模擬生物進化的隨機模型，通過有限次數的迭代過程，將那些能適應生存條件的個體保存下來[11]。

DE主要由初始化種群、變異、交叉及選擇四個步驟組成，進化過程可描述如下：

（1）種群初始化。從解空間中隨機選擇部分解作為目標個體，每個個體由D維向量組成，從而生成初始種群。

（2）變異。在某一代中，從種群中隨機選擇幾個不相同的個體組成差分向量，在變異因子F的縮放下產生變異個體。其中，變異因子F一般取值范圍為(0,1)。常用變異策略為：

式中，Vi,g、Xi,g和Xr,g分別表示即將獲得的g代中第i個變異個體，g-1代的第i個目標個體和隨機目標個體，且各不相同。式（4）是經典差分變異策略。

（3）交叉。在變異后，需要將目標個體與變異個體進行交叉操作生成最終的試驗個體。常用交叉策略為二項式交叉，即：

式中，CR為交叉因子，jrand表示{1,2,…,N}中的任意一個整數，保證變異個體至少有一維基因被保存。

（4）選擇。試驗個體與對應的目標個體一一比較。選擇依據為適應度函數（本文中即目標函數GDOP）的值，若試驗個體具有更優的目標函數值，則將與之對應的目標個體替換為試驗個體；反之，該目標個體保持不變。在本文中，以適應度函數最小為選擇標準。

根據相關研究[12]，本文引入禁忌搜索中的“禁忌列表”，避免重復計算GDOP。從式（2）和式（3）中可以看出，矩陣求逆涉及GDOP的計算，這相對耗時。禁忌列表記錄了已計算出GDOP值的所有組合。在上述解決方案選擇過程中，該算法避免搜索禁忌列表中已經存在的衛星組合。

在下一節，將具有禁忌搜索思想的差分進化引入組合系統的衛星選擇問題中。

2.2 TSDE選星算法設計

假設某歷元時刻對于用戶接收機的可見衛星為M顆，從中選擇N顆衛星參與計算，獲得盡可能小的GDOP值。執行以下搜索過程即可找到符合條件的目標解。

步驟1：獲取可見衛星。根據一定的截止高度角獲得可見衛星位置信息，計算該歷元時刻的可見衛星數目M。

步驟2：編碼。將可見衛星編碼為序列S={1,2,…,M}，且每個編碼元素對應一顆衛星。

步驟3：初始化種群。N顆衛星為一待選組合，則共有個組合。從中隨機選擇R個子組合作為種群個體Xi，每個個體具有D=N維基因，生成初始種群P。

步驟4：差分變異。設置變異因子F，采取變異策略式（6），生成變異個體Vi。

步驟5：二項交叉。設置交叉因子CR，通過二項交叉式（7）產生試驗個體Ui。

步驟6：禁忌列表。記錄初始種群中個體和執行上述步驟后的個體。

步驟7：適應性比較。根據適應度函數，比較試驗個體與目標個體的適應度值，保留適應度值更小的個體，并根據比較結果更新最優個體，直到達到最大進化代數，終止進化。

在執行以上算法步驟時，還應注意以下問題：一是因衛星編號序列全為整數，是與可見衛星一一對應的，因此在進化中應保持個體基因為整數；二是基因“越界”問題，在經過變異操作后，可能產生超出界限的基因，該界限應限制為1～M。

3 仿真評估

本文使用衛星仿真平臺輸出的BDS/GPS組合系統場景下用戶接收機及衛星的位置信息，并進行仿真實驗[13]。GDOP值的變化隨參與導航的可見衛星數量而變化，并隨衛星數量的增加而單調下降，但會受到限制，且根據可見衛星數量和能滿足基本定位，接收機完好性監測（Receiver Autonomous Integrity Monitoring，RAIM）等條件，本文選擇參與計算的衛星為6顆[14-15]。

設置接收機大地坐標為東經117.28°，北緯32.87°，截止高度角為5°，仿真起始時間為2021年2月1日00時00分00秒，時長24小時，時間間隔10 min。在實驗中，根據TSDE算法選星步驟設置仿真參數：種群大小R=50，變異因子F=0.5，交叉因子CR=0.5，進化代數T=50。本節將以遍歷法和基于GA的選星算法為參考，分析所提選星算法的性能。

基于已設置的截止高度角，一天24 h內可見衛星數目如圖1所示。

圖1 各歷元時刻可見衛星數目分布

從圖1可以看出，在歷元時刻3時，可見衛星數目為26顆，在采用遍歷法選星時，可知需要進行次的GDOP公式的計算，選星耗時為12.974 s，顯然不適應組合系統場景。

圖2為3種算法的不同的GDOP變化，在一天內，基于TSDE的選星算法與基于GA的選星算法相比，與ES選星算法的GDOP分布更加接近。而且TSDE選星算法的GDOP值均在3以下，相比GA選星算法可以提供更高精度的導航定位服務。

圖2 24 h內3種算法的GDOP的變化

為進一步分析TSDE選星算法的穩定性和收斂特性，本文分別在6時和14時兩個歷元時刻，百次仿真獲得TSDE與GA的GDOP均值、標準差和平均收斂代數，仿真結果如表1所示。

表1 TSDE與GA的GDOP均值等參數

從表1中可以看出，TSDE選星算法在6時和14時的GDOP標準差和均值均小于基于GA的選星算法，具有更高的穩定性，且獲得最優解的收斂代數更小，具有更快的計算速度。

為充分驗證基于TSDE的選星算法的快速尋優能力，在組合系統選星問題中，3種算法的整體性能驗證結果如表2所示，其中在該歷元時刻，可見衛星數目為23顆。

表2 3種算法的性能比較

從表2可知，相比GA選星算法，基于TSDE的選星結果也未完全達到ES的結果，但更加接近于ES；經統計分析，對比ES算法，基于TSDE和GA的選星算法在GDOP的偏差上分別增大了2.15%和4.85%，在執行時間上分別減少了92.79%和85.73%；但TSDE選星算法相比GA在GDOP值和執行時間上分別減小了2.58%和49.43%。

4 結語

本文提出了一種基于禁忌搜索機制的差分進化的衛星選擇算法，并將其與傳統的ES算法和基于GA的選星算法進行比較。分析結果表明，相比于GA選星算法，TSDE選星算法的GODP值降低了2.58%，更接近于ES選星結果；選星速度減少49.43%。得益于禁忌搜索機制，TSDE選星算法的快速尋優特性表明在組合系統選星問題中的優異解決能力。本文所提算法優于需要調節過多參數的遺傳算法，且為組合系統選星提供解決新方案。