基于蟻群的天基預警多目標優化算法

程禹， 魏承， 游斌弟， 趙陽， 吳限德

(1.哈爾濱工業大學 航天學院，黑龍江 哈爾濱 150001； 2.哈爾濱工程大學 航天與建筑工程學院，黑龍江 哈爾濱 150001)

天基紅外系統具有覆蓋范圍廣、預警速度快、作戰用途多等特點，在反導信息保障中占據重要地位[1],受到了美國、俄羅斯等軍事強國的高度關注和大力投入[2-3]。天基預警系統傳感器調度優化是天基預警系統的關鍵問題。多傳感器調度優化是一個存在監控沖突的多目標、動態、復雜多約束的非線性優化問題[4]。在傳感器調度問題中，優化目標之間存在沖突，如何在改善目標評價的同時不使另一個目標的評價惡化，實現多個目標共同優化，這就是多目標優化問題(multiobjective optimization problem，MOP)[5]。與單目標優化問題不同，在解決MOP問題時，需要尋找所有目標中最權衡的解[6]。

國內外實驗室、科研機構和工程單位已經開發了許多基于規則的元啟發式算法[7]解決多傳感器調度優化問題。然而，盡管它們具有高效率的特點，但元啟發式算法也存在若干限制，例如，大多數算法在每次運行中生成單個解決方案，并且按照固定邏輯進行決策。這些局限性推動了替代解決方案技術的發展。

多目標進化算法(multiobjective optimization evolutionary algorithm,MOEAs)是基于進化的元啟發式算法，是解決高度復雜的MOP問題的常用方法之一[8]。文獻中提供了多種MOEAs方法，例如非支配排序遺傳算法Ⅱ(NSGA-Ⅱ)[9]或基于分解的多目標進化算法(MOEA/D)[10]。MOEAs采用了基于帕累托排序的選擇機制，即基于帕累托最優性對解決方案進行排名，使非支配解決方案被選擇的概率更高。然而，基于帕累托的MOEAs在處理具有多目標的MOP問題時表現不佳[11-12]。

蟻群優化算法(ant colony optimization,ACO)最初的目的是解決組合優化問題，多年來ACO不僅應用在天基預警系統中[4]，同時在空間碎片清除、中繼數據傳輸和地面目標觀測等航天領域也有比較成熟的應用[13-15]，解決了動態任務分配和多目標優化等關鍵問題[5，16]。雖然，多目標蟻群優化算法(multiobjective optimization ant colony optimization,MOACO)已經廣泛應用在多目標優化問題的研究[17]，但是，MOACO是一個離散優化算法，對于天基預警任務規劃這種多目標連續優化問題，需要進行改進。本文引入了基于指標的連續搜索空間的多目標蟻群優化算法(iMOACO)。該算法在最先進的MOEAs方面具有足夠競爭力[18]。

1 天基預警連續搜索域蟻群多目標優化算法

1.1 搜索算法ACO_R

基于指標的連續搜索空間蟻群優化算法是一種基于ACO元啟發式的多目標優化算法。對于天基預警這種連續問題，ACO的一個典型拓展是ACO_R，與遺傳算法、概率學習方法和其他與螞蟻相關的算法相比，ACO_R已呈現出良好的計算結果。ACO_R還被用作2個連續領域MOACO算法的搜索方法。因此提出一種以ACO_R為搜索算法的天基預警規劃算法。

1.2 基于R2的天基預警方案排序算法

給定Pareto前沿近似值A，指標的一元版本定義為：

(1)

天基預警方案排序算法的主要目的是創建一個非顯性排序方案。首先，優化一組目標的解決方案，并將解決方案放在排序的最前面。然后，刪除這些已排名的點，并以相同的方式分配第2個方案，依此類推，直到沒有更多的點需要進行排名。該方案的優點是在選擇壓力較大的問題上都具有良好的性能。

關于式(1)中效用函數的選擇，本文使用了價值標度函數(achivement scalarizing function，ASF)。ASF的定義為：

(2)

式中：r為參考向量；λ為權重向量，維數均為Λ={λi|i=1,2，…,N}。為了定義效用函數集，需要創建一組權重向量Λ={λi|i=1,2，…,N}。使用創建網格{m,h}的單純形網格設計(simplex lattice design,SLD)計算Λ，其中m是目標數，h是比例參數。這個結構由每個目標函數的所有可能的比例組合組成。因此，權重向量的系數是在0和1之間取h+1個均勻分布的值，即：

(3)

圖1 基于R2的天基預警方案排序算法Fig.1 Sorting algorithm of space-based early warning scheme based on R2

在基于R2的天基預警方案排序算法中，假設規劃結果集合p.F:中的每個規劃結果p.F:都具有以下結構：

p.F: 目標向量；p.α: 權重向量λ的當前價值；p.u*: 獲得最優價值；p.rank: 由算法分配的解的排列結果。

1.3 更新參考點

引入了2個重要的參考向量：理想向量z*和最低點向量znad。前者保留每個目標的最小值，后者由帕累托最優前沿的解得到的最大目標值組成。這些向量在目標的規范化過程中特別相關。

基于R2的天基預警結果排序算法要求對目標向量進行歸一化，以生成排序。進行歸一化：

(4)

本文提出了一種機制，分別生成理想向量和最低點向量的統計近似值zmin和zmax。在每次迭代中監控當前總體的最低點，確定距離真正帕累托前沿的解有多接近。方差越高代表解離帕累托前沿越遠。

圖2 更新參考點Fig.2 Update reference point

1.4 基于指標的天基預警連續搜索空間蟻群優化算法

在本節中，描述了用于構建基于指標的天基預警連續搜索空間蟻群優化算法的基本機制(參見算法3)。該方案是ACO元啟發式算法的一個推廣，用于求解以ACO_R為搜索引擎，無變量相關機制的連續多目標優化問題。該優化算法的2個主要特點如下：1)使用了一個不同的信息素存檔方式，它根據方案排序算法存儲最好的解決方案；2)信息素更新過程促進了新創建的解決方案與存儲在存檔中的當前解決方案之間的競爭。

每個螞蟻a∈A和信息素p∈Γ，其中A表示一組螞蟻，Γ表示信息素檔案，具有以下結構：

x: 決策變量；F: 目標向量；Fnorm: 歸一化目標向量；α: 當前利益值；u*: 最優利益值。

天基預警連續空間蟻群優化算法需要6個參數：Gmax、q、ε、ξ、α和h。Gmax是最大的蟻群代數。參數q和ξ由基于ACO_R的搜索引擎使用。參考向量的更新需要參數α和ε，分別是方差閾值和公差閾值。最后，h是用于在SLD上構造單純形格的比例參數，以創建N個權重向量集。N同樣被用作螞蟻數量和信息素存檔Γ的基數。這一決定是基于R2指標的μ-最優分布，即如果有μ≥N的解決方案μ和權重向量N，解決方案μ-N將不會對R2指標值產生影響。

如圖4所示是天基預警連續搜索空間蟻群優化算法描述。首先計算N個權重向量集，然后根據信息素存檔Γ使用統一分布進行初始化并計算z*和znad。然后創建并初始化記錄實例。使用天基預警方案排序算法對Γ中的觀測方案進行排序，確定解的質量。之后執行算法的主循環，直到超過最大迭代次數。每個螞蟻使用ACO_R的標準機制生成一個新的預警觀測方案。然后計算理想觀測方案和最低點觀測方案的統計近似值。在這之后描述了信息素更新過程。設Ψ=A∪Γ。然后，對所有解的目標向量進行歸一化，目的是通過天基預警方案排序算法進行排序。隨后，根據如下指標：切換次數、疲勞度和觀測時長，按遞增順序對Γ進行排序。排序將確保把些接近帕累托最優集的解排在最前端。將前N個觀測方案復制到存檔中然后刪除了Γ的所有觀測方案。如上所述，信息素的更新過程促進了新創造的信息素和舊信息素之間的競爭，目的是保留那些使R2指標值最大化的觀測方案。在搜索過程結束時，返回Γ的內容作為帕累托前沿近似值。

圖3 天基預警連續搜索空間蟻群優化算法流程Fig.3 Ant colony optimization algorithm flow of space-based early warning continuous search space

圖4 基于規則的元啟發式算法計算結果Fig.4 Results of rule based meta heuristic algorithm

下面分析天基預警連續空間蟻群優化算法的計算復雜性。新解決方案的產生需要O(N2n)。更新參考向量需要O(Nm)。對A和Γ以及目標向量做標準化需要O(Nm)。天基預警方案排序算法的計算復雜度是O(N2(logN+m))(其中N=|P|，P為規劃結果集合)。從Γ中移除之前的解決方案需要O(1)。從ψ中復制最好的前N個值到Γ中需要O(N(n+m))。最后，再次執行天基預警排序算法，這里需要O(N2(logN+m))，其間，排序工作占用了O(NlogN)。因此，天基預警連續空間蟻群優化算法每步迭代的計算復雜度為O(N2(logN+m+n))，存儲數據的計算復雜度為O(N(n+m))。

2 仿真測試與分析

2.1 仿真場景設計

本文參考了美國低軌天基預警系統STSS(space tracking and surveillance system)，即空間跟蹤與監視系統，其主要任務是彈道導彈初段，中段及末段跟蹤與識別。

2.1.1 天基預警系統組成

本文仿真場景星座采用的是Walker-Delta構型，用衛星數目T、軌道面數P、相位參數F描述，用來表示，整個系統由24顆衛星組成。

天基預警系統的星座構架T/P/F為24/3/1，地1個軌道面初始時刻的升交點赤經為0°，第1個軌道面第1顆衛星初始時刻的幅角為0°，為了滿足全球覆蓋，所以采用極地軌道，其軌道傾角為90°；每顆衛星的軌道高度為1 600 km。

2.1.2 天基預警系統的工作方式

天基預警系統中每顆低軌衛星采用臨邊觀測跟蹤傳感器，采用短波長探測方式。臨邊以上的工作方式指的是自衛星與地球切線開始向切線上方掃描的過程，臨邊即沿切線的含義。臨邊觀測本質上是一種基于空域的觀測方式。

2.2 算法對比

本節基于該場景將天基預警連續搜索空間蟻群多目標優化算法與基于規則的元啟發式算法[7]以及動態蟻群算法[19]進行對比。

天基預警任務中，由于星座均勻分布，因此目標分布越集中，預警系統的可用資源越少，對算法的要求越高。因此，為了全面比較3種算法，將導彈設置為相同發射點不同落點，并設計了資源充足，資源緊缺和資源嚴重不足3種場景。算法評價值為優化目標的加權和：

(5)

2.2.1 資源充足場景仿真

資源充足場景選擇2枚單彈頭的二級導彈作為觀測目標。2枚導彈選擇了相同的發射點，不同的飛行高度和不同的目標點。這種情況對任務規劃算法的壓力較低，以此來比較3種算法在資源充足場景中的能力。

1)彈道參數

2枚導彈選擇相同發射點經度：100°、緯度：41°、高度：1 km，同時，彈道高度和目標點相距較遠，使得預警資源比較充足，通過下面的計算結果比較3種算法的不同能力。

表1 導彈參數Table 1 Missile parameters

2)計算結果

資源充足場景中，3種算法總觀測時長比較接近，均可以獲得長時間覆蓋目標的觀測結果。同時，多目標蟻群算法的傳感器切換次數和單星觀測時長均小于前2種算法，顯示出優異的優化性能，在資源充足場景中更合理的利用觀測資源。

表2 評價指標Table 2 Evaluating indicator

2.2.2 資源緊缺場景仿真

資源緊缺場景選擇5枚中遠射程導彈作為觀測目標。5枚導彈選擇了相同的發射點，不同的飛行高度和不同的目標點。相比于上一個場景，本場景對資源的需求量更大，以此來比較3種算法在資源緊缺場景中的能力。

1)彈道參數

5枚導彈選擇相同的發射點經度100°、緯度41°、高度1 km，并且選擇中遠射程導彈，相比于上一場景中的近程導彈，對預警系統的資源需求量更大。

2)計算結果

資源緊缺場景中元啟發式算法雖然也獲得了滿足覆蓋時間的優化結果，但單星觀測時長平均值為827.2 s，高于另2個算法，傳感器疲勞度較高，因此評價值最低。動態蟻群算法的優化結果擁有最長的目標覆蓋時間，同時單星觀側時長低于元啟發式算法，因此評價值較高。多目標蟻群算法的優化結果不僅平均切換次數最少，同時單星觀側時間也遠低于前兩種算法，對3種優化目標的均衡性和尋優性最好，因此高評價值最高。

圖5 動態蟻群算法計算結果Fig.5 Results of dynamic ant colony algorithm

圖6 連續域蟻群算法結果Fig.6 Continuous domain ant colony algorithm results

表3 導彈參數Table 3 Missile parameters

2.2.3 資源嚴重不足場景仿真

資源嚴重不足場景選擇8枚遠程導彈作為觀測目標。8枚導彈選擇相同發射點經度100°、緯度41°、高度1 km，并同時發射，因此預警系統資源無法同時觀測所有目標，導彈飛行高度分布在1 200～3 100 km不等，射程在3 406～6 089 km不等，在滿足資源嚴重不足的條件的同時，豐富彈道種類，以檢驗算法普遍性。此場景仿真目的是對天基預警系統傳感器資源嚴重不足的情況進行仿真，測試3種算法在資源嚴重不足場景中的能力。

1)彈道參數

圖7 基于規則的元啟發式算法計算結果Fig.7 Results of rule based meta heuristic algorithm

圖8 動態蟻群算法計算結果Fig.8 Results of dynamic ant colony algorithm

圖9 連續域蟻群算法結果Fig.9 Continuous domain ant colony algorithm results

表4 評價指標Table 4 Evaluating indicator

表5 導彈參數Table 5 Missile parameters

2)計算結果

資源嚴重不足場景中，元啟發式算法的總觀測時長，但同時存在切換次數多和單星疲勞度高等問題，元啟發式算法為固定邏輯搜索算法，在資源壓力較大時，存在多目標優化性能弱的問題。動態蟻群算法通過隨機尋優的方式，優化結果中切換次數和疲勞度2個優化目標均優于元啟發式算法，但仍沒有多目標蟻群算法的尋優結果理想。多目標蟻群算法在滿足總觀測時長的前提下，切換次數和疲勞度均低于另外2種算法，可見，在資源嚴重不足的場景中，多目標蟻群優化算法具有更好的優化性能。

圖10 基于規則的元啟發式算法計算結果Fig.10 Results of rule based meta heuristic algorithm

圖11 動態蟻群算法計算結果Fig.11 Results of dynamic ant colony algorithm

圖12 連續域蟻群算法結果Fig.12 Continuous domain ant colony algorithm results

表6 評價指標Table 6 Evaluating indicator

3 結論

1)本文針對天基預警系統傳感器調度問題中，本文根據任務中的約束情況，提出了一種天基預警連續搜索空間多目標蟻群優化算法，解決了傳統蟻群算法在天基預警任務規劃中存在多目標權衡能力差，連續搜索空間計算效率低等問題。

2)本文以擴展蟻群算法為搜索引擎，采用基于R2指標的天基預警方案排序算法來尋找最優解。該算法適用于天基預警星座系統對彈道導彈等具有紅外特性運動目標的跟蹤方案優化問題。

3)本文參考美國天基預警系統設計仿真場景，并將算法與元啟發式和動態蟻群算法在資源充足、資源緊缺和資源嚴重不足3種仿真場景中進行對比仿真，仿真結果基于蟻群的天基預警多目標優化算法在3種場景中均表現出良好的優化性能。