基于遺傳算法的Tiling 覆蓋策略天文衛星任務規劃*

徐子羚 劉玉榮 馮準

1(中國科學院國家空間科學中心 北京 100190)

2(中國科學院大學 北京 100049)

0 引言

面向天文觀測的空間科學衛星是對目標天體或天區進行天文觀測的重要手段。空間的機遇目標（Target of Opportunity，ToO），例如引力波（Gravitational Wave，GW）、γ 射線暴（Gamma Ray Burst，GRB）等是天文觀測的重要現象，包含著物理發展新規律。典型的ToO 是一個瞬態目標，發現后必須盡快對其進行觀測，否則其亮度會降至可檢測的極限以下。某些瞬態目標衰減相對較慢，在幾天或幾周內保持可觀測狀態，例如超新星和新星。某些目標必須在發現后的數小時內觀測到，例如γ 射線暴會快速消失。當正在衰減的目標仍保持足夠大的亮度時，可以從光譜數據變化中獲得更高的信噪比，所以對這些機遇目標觀測響應時間的小幅改進可能會獲得極大的科學觀測收益。

機遇目標觀測是多信使天文學（Multi-messenger Astronomy）的重要手段。2017年10月16日（美國東部時間10月16日10:00 LT）美國國家科學基金會召開新聞發布會，美國引力波探測器LIGO 和意大利引力波探測器處女座Virgo 于2017年8月17日共同探測到引力波事件GW170817，在該事件發生的隨后幾秒內，NASA 的Fermi 衛星和ESA 的INTEGRAL 衛星均探測到一個極弱的短時γ 射線暴GRB170817 A。這是第一次使用引力波和電磁波同時觀測到同一個天體物理事件，標志著多信使天文學時代的開始[1]。引力波事件發生時通常所在的天區有幾十到幾百平方度，對這樣較大天區的機遇目標觀測一般根據天文望遠鏡視場的大小劃分為小的天區，Tiling 覆蓋策略是對天區劃分的常用方法。Tiling 覆蓋策略是指針對空間天文衛星的任務目標，根據載荷視場大小、觀測角和視場形狀，設計單位網格Tile，對被觀測天區的輪廓進行覆蓋，并根據概率密度函數積分計算等方式對每個Tile 賦予優先級。劃分結果產生Tile 編號、優先級和天球坐標等信息。

機遇目標觀測相對于常規觀測是無法預先安排的觀測對象，這是因為觀測目標未知且目標坐標未知，或者已知目標具有行為不可預測的可變行為，所以機遇目標觀測是事先不知道確切目標、時間、坐標或儀器配置詳細信息的觀測。機遇目標觀測的時效性要求高，當ToO 出現時觀測系統要快速響應，制定有效的觀測隊列方案，因此空間天文衛星機遇目標任務規劃是空間天文衛星運行控制系統的重要工作。Tiling 覆蓋策略天文衛星機遇目標任務規劃的目的是針對一個天區觀測目標，快速安排觀測任務，解決科學觀測需求與衛星系統資源約束的矛盾，制定合理任務執行觀測方案，更高效地利用資源，得到更大的科學觀測收益。

目前，衛星任務規劃研究中面向基于機遇目標天文觀測任務規劃的研究很少。機遇目標觀測的規劃可以借鑒常規天文觀測規劃方法。NASA 發射了多顆空間天文衛星：哈勃望遠鏡（Hubble Space Telescope，HST），雨燕衛星（Swift Gamma-Ray Burst Mission，Swift）等。開發使用了多個任務規劃系統，例如SPIKE 調度規劃系統和TAKO 規劃系統，采用約束滿足問題（Constraint Satisfaction Problem，CSP）、神經網絡（Neural Network，NN）以及N體模擬（N-body）等方法求解規劃問題[2-4]。ESA 同樣發射了多顆空間天文衛星，如XMM-Newton 和Integral 等，ESA 在高級規劃方案APSI（Advanced Planning and Schedule Initiative）框架上開發了規劃系統MrSPOCK、AIMS、XMAS，采用遺傳算法（Genetic Algorithms，GA）和局部搜索算法（Local Search Algorithm），用一個通用的方法說明任務、時間和資源的約束，并結合爬山、禁忌搜索、模擬退火等算法思想解決任務規劃問題[5-8]。中國發射了硬X 射線調制望遠鏡衛星（HXMT），采用貪婪算法、遺傳算法等方法求解規劃問題。Liu等[9]提出了采用多目標遺傳算法對衛星巡天掃描任務進行智能規劃的模型。Wu等[10]在研究天文觀測衛星的任務規劃問題時，建立了多目標任務規劃模型，并基于帶精英策略的快速非支配排序遺傳算法（NSGA-II）設計了并行的基因組編碼方式，有效解決了天文觀測類衛星不同規模的任務規劃問題。Liu等[11]在原有多目標遺傳算法的基礎上，設計了基于觀測窗口序列的多目標遺傳算法，改進了遺傳算法的編碼能力，得到每個觀測任務的觀測窗口序列，提高規劃結果的靈活性和適用性。Han等[12]針對小衛星星群任務運行特點，采用改進型遺傳算法，引入資源隨機分配的解碼策略及精英保留策略，保證了算法的全局收斂性。Liu等[13]研究了基于規則的啟發式算法和遺傳算法求解任務規劃問題，并設計一種動態插入機遇目標任務的重規劃算法。Long等[14]將遺傳算法與模擬退火算法相結合，應用于低軌觀測衛星任務規劃工具的開發。Mao等[15]針對多星多任務的規劃問題，提出一種基于關鍵路徑遺傳算法，具有良好的全局搜索能力和穩定性。

以上研究表明，采用智能優化算法在求解衛星任務規劃問題是可行的方案。現有的任務規劃模型和方法不能直接用于Tiling 覆蓋策略天文衛星目標觀測規劃問題。觀測目標在被觀測天區上分布不均勻或出現概率不均勻，望遠鏡或儀器的每次觀測只能覆蓋一塊觀測區域（Tile），因此在制定觀測計劃過程中，一個優化的Tiling 方案需要在保證完備性的同時縮短觀測時間。由于機遇目標的可觀測時間寶貴，并且每個Tile 的增加都會增加觀測的時間成本，對于預定觀測天區的覆蓋率以及整體的觀測效率要求更高。本文以基于Tiling 策略的天文衛星機遇目標觀測規劃問題為研究對象，建立任務規劃數學模型，設計算法 求解該問題，并進行仿真實驗和結果分析。

1 目標任務規劃問題建模

1.1 問題描述

Tiling 覆蓋策略的天文衛星機遇目標任務規劃問題可以簡要描述為，根據科學的觀測需求，結合星地資源以及環境約束進行約束檢驗，根據時間窗口、衛星姿態、觀測時長等約束，規劃對Tile 的合理觀測方案，生成高效可行的衛星工作計劃。其中觀測需求來源通常是由科學團隊提出的機遇目標，包括引力波、γ 暴等。觀測目標范圍是一片天區，根據Tiling策略進行天區劃分得到一組Tile，其中每一個Tile 通過概率密度函數求解出各自的優先級。本文重點在于規劃算法的設計，因此Tile 及其時間窗口等均由預處 理求解得出，直接作為輸入使用。

1.2 問題假設

天文觀測是復雜的系統工程，實際天文衛星機遇目標任務規劃涉及衛星平臺、地面站、運行軌道、時間窗口、任務類型等一系列因素，是NP-hard 問題。本文研究Tiling 覆蓋策略的天文衛星機遇目標任務規劃問題的基本規劃方法，對于復雜問題提出建模假設，這些假設不影響研究算法的效果。結合實際任務規劃問題做出的具體假設如下。

（1）假設衛星上多個有效載荷等效為一個有效載荷。多個工作模式不同的有效載荷等效為一個有效載荷的多個工作模式。在衛星運行過程中，多個載荷配合工作，本假設符合天文衛星的一般運控模式。

（2）假設衛星資源和地面資源滿足任務規劃需求。包括電源電量、存儲器容量以及衛星和地面站的硬件條件等滿足規劃的需要，不考慮資源或故障對算法的影響。常規情況下，衛星資源能夠保障衛星在軌按照正常模式開展科學觀測。

（3）假設衛星調姿需要的時間與調姿角度線性相關，調姿需要的能量與調姿角度線性相關。

（4）假設衛星觀測的數據量與觀測時長成正比。

（5）假設同一時間段內衛星只能執行一項觀測任務，一項觀測任務至多執行一次且在執行過程中不被其 他任務搶占或中斷執行。

1.3 數學模型

1.3.1 數學變量

為了描述Tiling 覆蓋策略天文衛星機遇目標任務 規劃問題，定義相關變量及符號（見表1）。

表1 數學模型中的變量定義Table 1 Parameters definition

1.3.2 變量定義

定義1可視時間窗口W。Wt為Tilet的可視時間窗口集合，表示可以被觀測的時間段。?wt∈Wt，其中，為Tilet的可視時間窗口集合中第k個時間窗口，為第k個時間窗口的開始時間，為第k個時間窗口的結束時間。

定義2觀測任務目標Tile 集合T。?t∈T。其中，t≡〈Pt,Dt,St〉，Pt表示觀測坐標，Dt表示觀測時長，St表示優先級。

定義3規劃方案R。?r∈R。其中rt≡〈Et,Nt,Ot,Θt,Lt,?t,?t〉。Et表示Tilet的規劃判決結果，Et為1 表示可規劃，0 表示未規劃。Nt表示Tilet的執行順序。Ot表示Tilet的觀測時間窗口集合，其中，為Tilet觀測時間窗口集合ot中第n個觀測時間窗口，為第n個觀測窗口的開始時間，為第n個觀測窗口的結束時間。Lt為由前一目標到觀測當前Tilet目標需要調姿的距離。Θt表示Tilet的調姿時間窗口集合，?θt∈Θt，?t表示由前一目標到觀測當前Tilet目標需要調姿的角度。?t表示Tilet的等待時間窗 口集合，

1.3.3 約束分析

約束1每個Tile 的觀測時長約束，即每個Tile的觀測總時長必須滿足該Tile 觀測時長需求Dt，

約束2任務沖突約束，衛星在同一時刻只能執行一個觀測任務，每兩個Tile 之間的觀測區間不能沖突，即

約束3規劃時間約束，規劃結果占有的時間必須 能容納在規劃起止時間段內，即

1.3.4 規劃模型

基于以上定義和約束，模型描述如下：給定一顆衛星S，觀測天區Z。天區Z的Tiling 結果為觀測任務目標集合T。任務目標集合T的每個任務目標即每個Tile 都有各自的位置、觀測需求時長和優先級，任務目標集合T每個任務目標的數據已經由預處理求解出。

給定可視時間窗口集合W，可視時間窗口集合W的每個可觀測時間段都有各自的起始時間和結束時間。每個任務目標t必須在該目標對應可觀測時間窗口集合Wt內執行。切換任務目標需要調姿，調姿需要的時間與調姿角度線性相關，調姿需要的能量與調姿角度線性相關。

機遇目標天文觀測任務的基本需求包括：ToO觀測需要快速響應，需要考慮目標Tile 的優先級；節約天文衛星的能源，需要考慮盡可能短的路徑；為了延長天文衛星的壽命，需要考慮減少天文衛星姿態的頻繁調整。據此，建立模型多目標優化問題的目標函數如下。

（1）優先級。優先級以Tile 本身的優先級以及其被安排順序的乘積表示，該值越小表明優先級高的tile 越早被安排，即

（2）總距離。總距離由被規劃的相鄰兩個tile 之間調姿的距離累加和表示，該值越小則表明總體規劃距離越短，即

（3）調姿滿足率。調姿滿足率用來評價調姿角度約束的滿足程度，該值越小表示總體調姿對于滿足調姿角度約束的程度越高。

調姿角度約束判斷函數為

基于上述考慮，TPA算法（ToO Planning Algorithm）的目標函數為

多目標優化在某方面實現最優，大概率會導致其他方面性能的下降。可以根據實際任務需求改變目標函數的加權參數λpri和λdis，從而改變優化方向的權重 以取得更好的平衡。

2 算法設計

由于該問題是一個NP-hard 問題，問題復雜度隨規模呈指數增加，求解收斂難度增加。遺傳算法作為一個全局搜索算法，能夠在整個可行解域開展搜索，同時組合優化問題中，可行解通常是有限但是非常大的，因此遺傳算法特別適于求解組合優化問題。本文基 于遺傳算法設計多目標優化任務規劃算法TPA。

2.1 算法描述

（1）染色體編碼與解碼。根據機遇目標任務規劃特點采用整數編碼方式，每條染色體由待規劃的Task任務組成，Task任務下標數字表示任務編號，對應任務在序列中執行的順序。每個Task由坐標參數赤經和赤緯（RA，DEC）、觀測時長、優先級分數組成，如圖1 所示。采用該編碼方式得到的解能夠直接映射到原問題上，直觀方便。

圖1 染色體編碼Fig.1 Example of a chromosome coding

（2）適應度。每個染色體都對應一個目標函數值，稱為染色體的適應度。為了描述方便，統一使用f表示目標函數和染色體適應度的計算結果，有f=λprifpri+λdisfdis+fslewfdis。

（3）選擇算子。根據基因計算得到的適應度，選出最好的基因和中位數以上的基因。如果不符合條件，則讓該基因進行交叉變異操作。

（4）交叉算子。隨機選擇兩條基因交叉得到一條新基因，交叉方式隨機產生兩個結點，將父結點2 片段保留至新基因的相應位置，其余位置由父基因1填補。

（5）變異算子。一條基因變異得到一條新基因，變異方式隨機產生兩個結點，該基因相應結點位置進行 翻轉。

2.2 算法流程

TPA 算法的輸入參數包括種群大小Sp、交叉概率Pc、變異概率Pm以及最大迭代次數Ie。

步驟1根據Sp、Pc、Pm，令k=0，初始化染色體種群Pop(k)。染色體種群中每個染色體隨機生成全排列組成。

步驟2評估種群Pop(k)，即計算Pop(k)中每一個體的目標函數值，即適應度。

步驟3應用精英主義策略，記錄Pop(k)中的最優解。

步驟4從種群Pop(k)選擇得到配對池M(k)。

步驟5對配對池M(k)執行交叉和變異操作，具體方法如2.1 節所述。

步驟6構造新種群Pop(k+1)。

步驟7判斷終止條件為k是否大于等于Ie，如果滿足則停止迭代，輸出最優解，否則k=k+1跳轉至步驟2。

算法流程如圖2 所示。

圖2 TPA 規劃算法流程Fig.2 Flow chart of TPA algorithm

3 實驗及結果分析

為了驗證本文算法的有效性，選擇GW170814 為觀測目標，該事件在2017年8月14日10:30:43 UTC，發生于Eridanus 星座的方向，是一個黑洞合并事件，赤經范圍34.41°－53.43°，赤緯范圍–54.34°－–7.78°。

本文實驗中觀測目標共劃分230 個Tile，輸入數據包括每個Tile 相應的觀測坐標、觀測時長及優先級（見表2）。

表2 輸入數據TileTable 2 Input data of Tile

仿真使用了2022年9月26日的時間窗口數據（見表3）。為避免太陽光照對載荷儀器視場的強光影響（在SVOM 衛星工程中，太陽避免角度設為91°），該時間窗口數據剔除了太陽光照矢量進入載荷視場的時間，同時剔除了衛星進出SAA 區域的時間。對多種組合參數進行了仿真實驗，其中：種群大小為100～1000，步進100；交叉概率0.1～0.6，步進0.1；變異概率0.1～0.6，步進0.1；迭代次數范圍為500～10000。根據多次實驗得出的經驗，如果種群數太大則迭代時間會變長，種群數太小則收斂速度慢。如果交叉變異率太高，則收斂過程中適應度波動太大導致收斂變慢，交叉變異率太低又很難跳出局部最優。因此算法的相關參數設置如下：種群大小為600，交叉概率為0.5，變異概率為0.2，既保證了收斂速度，也不會過于早熟，種群大小在兼顧迭代速度和收斂速度下進行了折中選擇。適應度函數中λpri和λdis均取為1，最大迭代次數為5000。

表3 時間窗口的輸入數據Table 3 Input data of time windows

圖3 和圖4 給出了GW170814 的TPA 規劃結果。圖3 為GW170814 的Tiling 規劃軌跡，彩色點為被規劃的Tile，優先級數值越大代表該Tile 優先級越高，灰色為未被規劃的Tile。由圖3 可見Tiling 規劃軌跡具有規律性，優先級高的Tile 能夠被優先規劃且整個規劃結果走了盡可能短的路徑。從表4 中同樣可以得出，優先級高的Tile 能夠被優先規劃。

圖3 GW170814 的Tiling 規劃軌跡Fig.3 Tiles track after scheduled of GW170814

該算法能夠滿足對于高優先級任務先執行的需求，以提出的任務目標優先級為主要因素，兼顧路徑規劃。圖4 給出的是GW170814 的時間規劃結果。圖4 中每條藍色橫向線條表示該Tile 的時間窗口，其中藍色細虛線表示可觀測時間段，藍色粗實線表示不可觀測時間段。TPA 算法規劃結果為：共230 個Tile 中有84 個可規劃，其中綠色粗實線表示該Tile占用的觀測時間段，總觀測時間占比為57.87%；紅色粗實線表示該Tile 由于地球遮擋所占用的等待時間段，總等待時間占比為40.48%；黃色粗實線表示該Tile 到下一個Tile 占用的調姿時間段；總調姿時間占比為1.65%。將被規劃的所有Tile 的可觀測時間段的總和除以被規劃的所有Tile 的數量的值定義為平均可觀測時間。實驗結果表明，該算法得到的規劃方案具有高時間利用率的優點，規劃結果可觀測時間是平均可觀測時間的1.39 倍。

圖4 GW170814 的時間規劃結果Fig.4 Planning results of GW170814

輸出結果為歷史最優解，圖5 為算法收斂圖像，用于輔助觀察算法迭代的整體收斂趨勢，不作為結果的輸出依據。可以看出隨著迭代次數增加，種群中最好基因對應的適應度值呈下降趨勢，從44176.74 降至19497.86。適應度數值由優化準則決定，越小表明規劃結果越好。在1000 次迭代時適應度值基本達到最優。TPA 算法設計的交叉變異使迭代結果不陷入局部最優值。

圖5 TPA 算法收斂圖像Fig.5 TPA algorithm convergence image

4 結論

以上結果表明了本文提出TPA 算法的有效性。

通過對基于Tiling 覆蓋策略的天文衛星機遇目標任務規劃問題進行分析，建立了以距離、任務優先級、調姿角度限制滿足率為評價準則的多目標優化數學模型，設計了基于遺傳算法的多目標優化任務規劃算法。將該算法應用于SVOM 前期工程仿真，采用GW170814 數據對算法進行了實驗，結果表明所建立的模型和方法能夠有效解決問題，達到合理優化觀測收益的目的。在應用中，可以根據實際需求對目標函數參數進行優化，實現加速收斂。

表 4 規劃結果中Tile 優先級Table 4 Tile’s priority in planning results

致謝仿真目標源為GW170814，仿真數據由中法天文衛星SVOM 團隊的JAUBERT Jean 提供。