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

朱 軍，許士杰

（安徽大學(xué)，安徽 合肥 230601）

0 引言

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

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

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

1 組合系統(tǒng)選星模型

組合系統(tǒng)選星問題可描述為：當(dāng)可見衛(wèi)星數(shù)目為N時，從中選擇N顆衛(wèi)星參與導(dǎo)航定位。于是，基于群體智能優(yōu)化算法的思想，解空間為CMN，依據(jù)目標(biāo)函數(shù)最小的標(biāo)準(zhǔn)從解空間中尋找最優(yōu)的目標(biāo)解。其中，目標(biāo)優(yōu)化函數(shù)與可見衛(wèi)星和用戶接收機的位置信息有關(guān)。

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

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

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

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

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

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

2 組合系統(tǒng)選星算法

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

2.1 差分進化結(jié)構(gòu)

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

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

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

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

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

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

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

（4）選擇。試驗個體與對應(yīng)的目標(biāo)個體一一比較。選擇依據(jù)為適應(yīng)度函數(shù)（本文中即目標(biāo)函數(shù)GDOP）的值，若試驗個體具有更優(yōu)的目標(biāo)函數(shù)值，則將與之對應(yīng)的目標(biāo)個體替換為試驗個體；反之，該目標(biāo)個體保持不變。在本文中，以適應(yīng)度函數(shù)最小為選擇標(biāo)準(zhǔn)。

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

在下一節(jié)，將具有禁忌搜索思想的差分進化引入組合系統(tǒng)的衛(wèi)星選擇問題中。

2.2 TSDE選星算法設(shè)計

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

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

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

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

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

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

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

步驟7：適應(yīng)性比較。根據(jù)適應(yīng)度函數(shù)，比較試驗個體與目標(biāo)個體的適應(yīng)度值，保留適應(yīng)度值更小的個體，并根據(jù)比較結(jié)果更新最優(yōu)個體，直到達(dá)到最大進化代數(shù)，終止進化。

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

3 仿真評估

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

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

基于已設(shè)置的截止高度角，一天24 h內(nèi)可見衛(wèi)星數(shù)目如圖1所示。

圖1 各歷元時刻可見衛(wèi)星數(shù)目分布

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

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

圖2 24 h內(nèi)3種算法的GDOP的變化

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

表1 TSDE與GA的GDOP均值等參數(shù)

從表1中可以看出，TSDE選星算法在6時和14時的GDOP標(biāo)準(zhǔn)差和均值均小于基于GA的選星算法，具有更高的穩(wěn)定性，且獲得最優(yōu)解的收斂代數(shù)更小，具有更快的計算速度。

為充分驗證基于TSDE的選星算法的快速尋優(yōu)能力，在組合系統(tǒng)選星問題中，3種算法的整體性能驗證結(jié)果如表2所示，其中在該歷元時刻，可見衛(wèi)星數(shù)目為23顆。

表2 3種算法的性能比較

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

4 結(jié)語

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