應用禁忌遺傳算法的空間目標協同監視資源調度方法

莊海孝 潘騰 何宗波 李懷鋒 賀冬雷

(北京空間飛行器總體設計部，北京 100094)

空間態勢感知主要是指通過天地基空間態勢感知手段、數據處理系統和地面支持系統等協同完成對在軌衛星、其他飛行器和空間碎片等空間目標的探測跟蹤、觀測識別，給出其空間分布、運行特征、行為動向、活動事件等信息，為空間系統在軌安全運行和空間資源有效利用提供重要的技術支撐[1]。空間動態感知不局限于跟蹤空間碎片和發布撞擊預警，對空間目標進行探測、跟蹤、識別和編目，更為重要的是探測空間威脅，發布告警信息。

空間目標監視作為空間動態感知的支撐技術，近些年呈現快速發展態勢。由于空間目標的高速運動、數量龐大、觀測條件復雜等因素，對其有效監視一直是難點問題。為了提高監視精度、時效性，我國先后發展了各種監視手段，包括地基、天基等多種設備。但這些手段都存在一定的局限性[2]。地基系統可以不受體積和功率的限制，具有很高的觀測精度。但是，部署位置受限，觀測區域存在死角，還有天氣條件、觀測高度和觀測時間等方面限制，導致對空間目標尤其是高軌空間目標監視能力受到制約。天基系統具有全天時、全天候、全天域的優勢，可在地球大氣層外的空間軌道上運行，不受空域的限制，能夠對地基系統進行有效的補充和完善。目前，我國空間目標態勢感知地基監視系統及天基系統的建設均是基于特定任務展開的，缺乏頂層設計，導致已有天地空間目標監視系統各自運行，難以發揮系統資源在聯合觀測、數據處理等方面的協同效應。為此，有必要發展天地一體空間目標監視系統，突破數據處理、自主任務規劃等關鍵技術，實現天基、地基互補，以最大化利用已有資源高效完成各類復雜任務。本文通過對天基、地基資源統一建模，將地基資源按實際能力等效為天基資源，進而可將天基、地基資源一體化處理。調度決定著監視資源業務效能，面向空間目標監視的資源協同調度技術能用來解決天基、地基監視系統多個任務管理過程中的資源爭用和任務沖突問題，優化天基、地基資源的綜合使用效益。未來，全天時、全天候、全天域、廣尺度、多手段的監視能力需求使天基、地基目標監視系統面臨的任務日益精細化和復雜化[3]，這使得傳統的單設備執行模式難以應對此類任務，亟需向自主化、協同化方向發展，即資源協同調度、自主決策、自主多星協同成為空間態勢協同監視系統任務模式發展的新趨勢。

本文討論的天地一體空間目標協同監視資源調度問題，是保障天基、地基設備協同配合、高效運行，提高監視體系綜合性能的關鍵。研究空間目標協同監視的天基、地基資源調度技術，對充分發揮天地監視資源的優勢特點、有效調配資源，以及提升空間目標監視整體效能乃至空間動態感知能力具有參考價值。

1 空間目標協同監視資源調度方法

空間目標協同監視資源調度問題約束條件(資源約束和任務約束)比較復雜，監視任務包含點目標和區域目標，區域目標監視任務在資源調度前需要進行任務分解，因此在任務建模前要進行觀測任務的預處理。任務預處理階段主要分析用戶任務需求，并對任務進行規范化處理及任務分解，在任務分解過程中處理任務約束，為建模過程準備數據。天基、地基空間目標協同監視資源調度問題的求解過程，可劃分為如圖1所示的任務預處理、建模、求解3個主要階段。

圖1 資源調度問題求解過程Fig.1 Problem-solving processes of resource scheduling

基于上述階段劃分，本文提出一種面向空間目標協同監視任務需求的資源調度方法，該方法具體實施步驟如圖2所示，其中的約束滿足優化問題模型構建、資源調度算法求解及仿真分析，是該方法的核心部分，同時也是本文討論的重點內容。

圖2 資源調度方法實施步驟Fig.2 Implementation steps of resource scheduling method

1.1 天地協同監視資源調度問題建模

綜合考慮多星監視任務規劃調度問題的特點，并結合工程實際，按約束的對象將協同監視資源調度問題的約束分為資源約束、時間約束、狀態約束、關系約束4類。資源約束表示資源使用時應滿足的約束關系。這里的資源并不僅指提供服務的監視資源，而是指調度過程中涉及到的所有對象，包括監視資源可用性約束、資源偏好約束、衛星對資源配置方式約束、應急監視約束、有效載荷工作能力約束、衛星存儲容量約束、有效監視距離約束等。時間約束是指測控服務過程中需要滿足的時間要求，也是多星測控調度問題中廣泛存在的一種約束類型。狀態約束主要是根據監視任務要求對資源狀態提出的約束，僅當設備準備就緒才能進行監視，一個資源在任何時刻只能為一個任務提供服務。關系約束是指多個監視服務之間的相互要求對監視調度過程產生的影響，包括時間關系約束和邏輯關系約束。

天基、地基多設備協同監視資源調度問題，可通過系統分析聯合監視中的各種約束和調度目標，對監視需求、調度目標、監視資源等基本要素進行抽象[4]，建立多目標優化的有色面向服務網結構(CSOP)模型。

1)總體功能分析及設計

總體功能分析及設計是指分析多設備協同監視建模任務需求，明確模型功能，確定適當的應用場景，主要包括3種模式。①排班模式：普通狀態下的任務方案，基本需求是在最小能耗的前提下對目標進行盡量多的觀測；②持續跟蹤模式：發現重點觀察對象后的任務方案，需求是在盡量小的能耗下實現對目標盡量長時間的累計觀測；③應急模式：在突發情況下的方案，需求不計能耗地盡快捕獲目標，并對目標進行盡量多的觀測。

2)輸入輸出規范定義與描述

對輸入輸出規范進行定義與描述。其中：輸入信息包括天基監視資源、地基監視資源、測控資源和數傳接收資源；輸出信息包括天基系統運行場景、觀測任務規劃甘特圖、觀測任務規劃進化曲線、觀測指向變化圖。

3)目標函數分析與確定

如表1所示，根據排班模式、持續跟蹤模式、應急模式需求，確立相應的優化目標，進而構建具體的目標函數。

表1 典型場景下的目標函數Table 1 Objective function in typical scenarios

在排班模式中，多個觀測設備對大量的空間目標進行合作觀測?？梢赃x擇的規劃目標有觀測目標數量最多、平均單目標觀測次數最多、各星任務均衡3類。相應的目標函數分別為

max∑xi

(1)

max∑(xi·Ti)/∑xi

(2)

minD(xi·Ti)

(3)

式中：xi由觀測目標i是否被選擇觀測確定，若被選擇，xi=1，否則xi=0，i∈I，I為觀測目標集合；Ti為目標i被觀測的次數；D(·)為方差運算。

在持續跟蹤模式中，多個觀測設備對于重點目標進行接力持續觀測。可以選擇的規劃目標有目標累計觀測時長最長、觀測條件最佳、各星任務均衡3類。前面2類相應的目標函數分別見式(4)和式(5)，第3類的目標函數同式(3)。

max∑r(∑kdr,k)

(4)

max∑r(∑kfr,k)

(5)

式中：dr，k為觀測設備r執行第k個觀測任務的持續時間，r∈R,k∈Or，R為觀測主體集合，Or為觀測主體r的觀測任務集合；fr，k為觀測設備r執行第k個觀測任務的收益值。

在應急模式下，多個觀測設備需要進行快速響應，協同完成對目標群的快速捕獲?？梢赃x擇的規劃目標有全部目標最快捕獲、平均單目標觀測次數最多2種類型，相應的目標函數分別為

min∑i(minn(si，n))

(6)

max∑(xi·Ti)/∑xi

(7)

式中：si，n為觀測目標i在進行觀測任務Oi，n時的初始時間，n∈Oi，Oi為觀測目標i的觀測任務集合。

4)天地協同監視任務資源調度CSOP模型

目標函數模型包括最大化觀測數量、平均單目標觀測次數最多、衛星電量消耗最小、各星任務方差最小。

最大化觀測數量為

Q1=max(∑Vixi)

(8)

式中：Vi為觀測目標i的觀測次數。

平均單目標觀測次數最多為

Q2=max(∑Vixi-∑eixi)

(9)

式中：ei為觀測目標i的觀測任務代價。

衛星電量消耗最小為

Q3=min(∑Vixiyi+∑Vixizi)

(10)

式中：yi為觀測目標i的觀測安排是否與原有任務相同，若相同，yi=1，若不同，yi=β，β∈(0,1)；zi為觀測目標i是否為突發目標，若是突發目標，zi=1，否則，zi=0。

各衛星任務方差最小為

Q4=min((∑(Vixi-u)2)/N)

(11)

式中：u為目標的平均觀測次數；N為可用的衛星及地面站總數。

1.2 天地協同監視資源調度算法設計

在多資源監視調度問題中，場景和監視需求是問題的輸入，在考慮各種約束的情況下盡可能地滿足監視需求是資源調度的目的，同時需要考慮優先保證高優先級任務需求得到服務的原則。依據需求的等級和緊迫性，可以選擇不同的求解方法[5]，在時間要求比較高、調度精度要求不高的情況下，可以采用面向需求的啟發式算法快速生成可用的調度方案；在時間充足且對調度精度要求較高時，可利用遺傳算法。在為數眾多的進化算法中，遺傳算法是尋求組合優化問題滿意解的最佳工具之一，已有研究將遺傳算法應用于求解觀測資源調度相關問題[6]。遺傳算法具有并行搜索、搜索效率較高的優點，但也存在局部搜索能力較弱、容易早熟等缺點。

天地協同監視資源調度問題作為一個帶有時間窗約束的復雜組合優化問題，決策變量數量多，與之相應的解空間也自然巨大，相比之下，遺傳算法能夠獲取質量更高的解，但是遺傳算法是一種隨機性的搜索算法，需要逐步在整個解空間中搜索，因此算法時間開銷會較大。根據上述分析，本文綜合考慮衛星資源、地基資源、任務需求等因素，將禁忌搜索與遺傳算法相結合，提出基于禁忌遺傳算法的協同監視資源調度優化求解方法[7]，探索以較小的時間開銷求解天地多資源聯合監視任務規劃問題。禁忌遺傳算法基本思想是：利用遺傳算法的進化功能使得搜索迅速集中在較優解周圍，然后利用禁忌搜索方法在小范圍內進一步搜索最優解。結合遺傳算法思想和禁忌搜索方法的優點[8]，能有效地利用全局信息及搜索過程中獲得的信息，在鄰域中重復搜索[9]，快速地向最優解的方向移動，從而有效地克服局部最優，達到提高求解效果和搜索效率的目的[10]。具體實現過程如圖3所示，主要分為以下3個階段。

圖3 禁忌遺傳算法實現過程Fig.3 Implementation process of tabu genetic algorithm

(1)初步優化。輸入原始數據及所需參數，形成初始化的種群，設置種群迭代次數N的初始值為1，計算得到適應值并進行初步優化。

(2)禁忌處理。基于精英選擇法進行選擇，基于禁忌搜索進行交叉、變異，并更新禁忌表。

(3)終止判斷。判斷是否滿足禁忌算法終止條件。若滿足，則跳出禁忌優化，并進行遺傳優化操作；若不滿足，則繼續進行禁忌操作，直至找到生存概率最大的染色體。

2 仿真驗證

2.1 系統功能驗證

依據前述協同監視資源調度算法，采用模塊化思想，以3顆衛星(Sat1，Sat2，Sat3)、5個地面站、200個目標為典型約束條件，開展仿真驗證。為了減小偶然性影響，在進行求解時，每種應用模式進行多次計算，并優化目標平均值和最優解次數，優化結果如表2所示。可以看出：在給定的資源條件和目標數量要求下，基于本文所介紹資源調度方法的系統可有效支持對廣域探測、持續跟蹤、應急響應及自定義4種任務模式的資源調度優化，任務方案優化時間在6.6 min以內。

表2 目標函數求解優化結果Table 2 Optimization results for objective function

圖4給出了某監視任務資源調度的初步優化方案，根據優化方案實施天基、地基資源調配計劃，可快速響應任務需求。圖4(a)是根據優化方案生成的協同監視任務甘特圖，縱坐標是可被調度的天基、地基監視資源，橫坐標是監視任務周期。圖4(b)是被調度的天基監視資源在監視任務周期內不同時刻相應的在軌姿態角度，橫坐標是執行監視任務的具體時刻。圖4(c)反映了在監視任務周期內不同時段的天基衛星被調用情況，橫坐標同樣是是執行監視任務的具體時刻。

圖4 資源調度初步方案Fig.4 Preliminary scheme of resource scheduling

2.2 效能分析

為檢驗本文方法的效能，以天地聯合監視任務為應用背景，以獲得最大任務收益為目標函數，進行分析。目標函數累計收益最大為式(5)，以衛星、地面站聯合監視任務規劃為背景，進行觀測任務調度仿真計算。應用禁忌遺傳算法基于目標函數進行優化求解。為了減小偶然性影響，在進行求解時，獨立運行30次，記錄其找到的解、找到最優解的次數、找到最優解的輪數及平均運行時間，結果統計如表3所示。 從表3結果可以看出：在復合型優化目標函數下，本文方法優化收斂速度可以滿足實際需求，并且具有更強的發現最優解的能力。該方法在尋優質量和尋優速度上表現優越，且對復雜的目標函數適應良好。

表3 計算結果Table 3 Calculation results

進一步驗證衛星調度能力和監視跟蹤目標容量。基于衛星參數，分別管控3,5,10，20顆衛星，依次進行廣域探測模式、持續跟蹤模式、應急模式和自定義模式下的仿真測試，并記錄仿真時長，見表4。由表4可知，可支持管控20顆衛星。基于目標參數，導入100,200,300,500，1000個目標，分別進行廣域探測模式、持續跟蹤模式、應急模式和自定義模式下的仿真測試，并記錄仿真時長，見表5。由表5可知，監視跟蹤目標容量不少于1000個。仿真結果表明，本文方法在目標監視容量、資源管控數量及任務優化時效性方面均具有明顯優勢。

表4 管控衛星數量測試Table 4 Test of satellite number in management and control

表5 監視跟蹤目標容量測試Table 5 Volume test for detecting and tracking space objects

3 結束語

本文系統分析了空間目標協同監視資源調度方法的需求背景、當前問題及應對措施，面向實際任務需求提出了應用禁忌遺傳算法的天基、地基協同監視資源調度方法。以任務收益作為具體的衡量值，證實了基于禁忌遺傳算法的資源調度方法在調度優化求解速度、算法收斂速度、求解精度等方面的明顯優勢，對于解決空間目標監視本身的復雜性，以及天基、地基手段多樣差異性等問題，更好地發揮天基、地基監視手段各自的優勢，提升空間目標監視能力和空間動態感知整體效能具有參考價值。