基于遺傳算法的Tiling 覆蓋策略天文衛(wèi)星任務(wù)規(guī)劃*

徐子羚 劉玉榮 馮準(zhǔn)

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

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

0 引言

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

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

機(jī)遇目標(biāo)觀測(cè)相對(duì)于常規(guī)觀測(cè)是無法預(yù)先安排的觀測(cè)對(duì)象，這是因?yàn)橛^測(cè)目標(biāo)未知且目標(biāo)坐標(biāo)未知，或者已知目標(biāo)具有行為不可預(yù)測(cè)的可變行為，所以機(jī)遇目標(biāo)觀測(cè)是事先不知道確切目標(biāo)、時(shí)間、坐標(biāo)或儀器配置詳細(xì)信息的觀測(cè)。機(jī)遇目標(biāo)觀測(cè)的時(shí)效性要求高，當(dāng)ToO 出現(xiàn)時(shí)觀測(cè)系統(tǒng)要快速響應(yīng)，制定有效的觀測(cè)隊(duì)列方案，因此空間天文衛(wèi)星機(jī)遇目標(biāo)任務(wù)規(guī)劃是空間天文衛(wèi)星運(yùn)行控制系統(tǒng)的重要工作。Tiling 覆蓋策略天文衛(wèi)星機(jī)遇目標(biāo)任務(wù)規(guī)劃的目的是針對(duì)一個(gè)天區(qū)觀測(cè)目標(biāo)，快速安排觀測(cè)任務(wù)，解決科學(xué)觀測(cè)需求與衛(wèi)星系統(tǒng)資源約束的矛盾，制定合理任務(wù)執(zhí)行觀測(cè)方案，更高效地利用資源，得到更大的科學(xué)觀測(cè)收益。

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

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

1 目標(biāo)任務(wù)規(guī)劃問題建模

1.1 問題描述

Tiling 覆蓋策略的天文衛(wèi)星機(jī)遇目標(biāo)任務(wù)規(guī)劃問題可以簡(jiǎn)要描述為，根據(jù)科學(xué)的觀測(cè)需求，結(jié)合星地資源以及環(huán)境約束進(jìn)行約束檢驗(yàn)，根據(jù)時(shí)間窗口、衛(wèi)星姿態(tài)、觀測(cè)時(shí)長等約束，規(guī)劃對(duì)Tile 的合理觀測(cè)方案，生成高效可行的衛(wèi)星工作計(jì)劃。其中觀測(cè)需求來源通常是由科學(xué)團(tuán)隊(duì)提出的機(jī)遇目標(biāo)，包括引力波、γ 暴等。觀測(cè)目標(biāo)范圍是一片天區(qū)，根據(jù)Tiling策略進(jìn)行天區(qū)劃分得到一組Tile，其中每一個(gè)Tile 通過概率密度函數(shù)求解出各自的優(yōu)先級(jí)。本文重點(diǎn)在于規(guī)劃算法的設(shè)計(jì)，因此Tile 及其時(shí)間窗口等均由預(yù)處 理求解得出，直接作為輸入使用。

1.2 問題假設(shè)

天文觀測(cè)是復(fù)雜的系統(tǒng)工程，實(shí)際天文衛(wèi)星機(jī)遇目標(biāo)任務(wù)規(guī)劃涉及衛(wèi)星平臺(tái)、地面站、運(yùn)行軌道、時(shí)間窗口、任務(wù)類型等一系列因素，是NP-hard 問題。本文研究Tiling 覆蓋策略的天文衛(wèi)星機(jī)遇目標(biāo)任務(wù)規(guī)劃問題的基本規(guī)劃方法，對(duì)于復(fù)雜問題提出建模假設(shè)，這些假設(shè)不影響研究算法的效果。結(jié)合實(shí)際任務(wù)規(guī)劃問題做出的具體假設(shè)如下。

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

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

（3）假設(shè)衛(wèi)星調(diào)姿需要的時(shí)間與調(diào)姿角度線性相關(guān)，調(diào)姿需要的能量與調(diào)姿角度線性相關(guān)。

（4）假設(shè)衛(wèi)星觀測(cè)的數(shù)據(jù)量與觀測(cè)時(shí)長成正比。

（5）假設(shè)同一時(shí)間段內(nèi)衛(wèi)星只能執(zhí)行一項(xiàng)觀測(cè)任務(wù)，一項(xiàng)觀測(cè)任務(wù)至多執(zhí)行一次且在執(zhí)行過程中不被其 他任務(wù)搶占或中斷執(zhí)行。

1.3 數(shù)學(xué)模型

1.3.1 數(shù)學(xué)變量

為了描述Tiling 覆蓋策略天文衛(wèi)星機(jī)遇目標(biāo)任務(wù) 規(guī)劃問題，定義相關(guān)變量及符號(hào)（見表1）。

表1 數(shù)學(xué)模型中的變量定義Table 1 Parameters definition

1.3.2 變量定義

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

定義2觀測(cè)任務(wù)目標(biāo)Tile 集合T。?t∈T。其中，t≡〈Pt,Dt,St〉，Pt表示觀測(cè)坐標(biāo)，Dt表示觀測(cè)時(shí)長，St表示優(yōu)先級(jí)。

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

1.3.3 約束分析

約束1每個(gè)Tile 的觀測(cè)時(shí)長約束，即每個(gè)Tile的觀測(cè)總時(shí)長必須滿足該Tile 觀測(cè)時(shí)長需求Dt，

約束2任務(wù)沖突約束，衛(wèi)星在同一時(shí)刻只能執(zhí)行一個(gè)觀測(cè)任務(wù)，每?jī)蓚€(gè)Tile 之間的觀測(cè)區(qū)間不能沖突，即

約束3規(guī)劃時(shí)間約束，規(guī)劃結(jié)果占有的時(shí)間必須 能容納在規(guī)劃起止時(shí)間段內(nèi)，即

1.3.4 規(guī)劃模型

基于以上定義和約束，模型描述如下：給定一顆衛(wèi)星S，觀測(cè)天區(qū)Z。天區(qū)Z的Tiling 結(jié)果為觀測(cè)任務(wù)目標(biāo)集合T。任務(wù)目標(biāo)集合T的每個(gè)任務(wù)目標(biāo)即每個(gè)Tile 都有各自的位置、觀測(cè)需求時(shí)長和優(yōu)先級(jí)，任務(wù)目標(biāo)集合T每個(gè)任務(wù)目標(biāo)的數(shù)據(jù)已經(jīng)由預(yù)處理求解出。

給定可視時(shí)間窗口集合W，可視時(shí)間窗口集合W的每個(gè)可觀測(cè)時(shí)間段都有各自的起始時(shí)間和結(jié)束時(shí)間。每個(gè)任務(wù)目標(biāo)t必須在該目標(biāo)對(duì)應(yīng)可觀測(cè)時(shí)間窗口集合Wt內(nèi)執(zhí)行。切換任務(wù)目標(biāo)需要調(diào)姿，調(diào)姿需要的時(shí)間與調(diào)姿角度線性相關(guān)，調(diào)姿需要的能量與調(diào)姿角度線性相關(guān)。

機(jī)遇目標(biāo)天文觀測(cè)任務(wù)的基本需求包括：ToO觀測(cè)需要快速響應(yīng)，需要考慮目標(biāo)Tile 的優(yōu)先級(jí)；節(jié)約天文衛(wèi)星的能源，需要考慮盡可能短的路徑；為了延長天文衛(wèi)星的壽命，需要考慮減少天文衛(wèi)星姿態(tài)的頻繁調(diào)整。據(jù)此，建立模型多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù)如下。

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

（2）總距離?？偩嚯x由被規(guī)劃的相鄰兩個(gè)tile 之間調(diào)姿的距離累加和表示，該值越小則表明總體規(guī)劃距離越短，即

（3）調(diào)姿滿足率。調(diào)姿滿足率用來評(píng)價(jià)調(diào)姿角度約束的滿足程度，該值越小表示總體調(diào)姿對(duì)于滿足調(diào)姿角度約束的程度越高。

調(diào)姿角度約束判斷函數(shù)為

基于上述考慮，TPA算法（ToO Planning Algorithm）的目標(biāo)函數(shù)為

多目標(biāo)優(yōu)化在某方面實(shí)現(xiàn)最優(yōu)，大概率會(huì)導(dǎo)致其他方面性能的下降。可以根據(jù)實(shí)際任務(wù)需求改變目標(biāo)函數(shù)的加權(quán)參數(shù)λpri和λdis，從而改變優(yōu)化方向的權(quán)重 以取得更好的平衡。

2 算法設(shè)計(jì)

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

2.1 算法描述

（1）染色體編碼與解碼。根據(jù)機(jī)遇目標(biāo)任務(wù)規(guī)劃特點(diǎn)采用整數(shù)編碼方式，每條染色體由待規(guī)劃的Task任務(wù)組成，Task任務(wù)下標(biāo)數(shù)字表示任務(wù)編號(hào)，對(duì)應(yīng)任務(wù)在序列中執(zhí)行的順序。每個(gè)Task由坐標(biāo)參數(shù)赤經(jīng)和赤緯（RA，DEC）、觀測(cè)時(shí)長、優(yōu)先級(jí)分?jǐn)?shù)組成，如圖1 所示。采用該編碼方式得到的解能夠直接映射到原問題上，直觀方便。

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

（2）適應(yīng)度。每個(gè)染色體都對(duì)應(yīng)一個(gè)目標(biāo)函數(shù)值，稱為染色體的適應(yīng)度。為了描述方便，統(tǒng)一使用f表示目標(biāo)函數(shù)和染色體適應(yīng)度的計(jì)算結(jié)果，有f=λprifpri+λdisfdis+fslewfdis。

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

（4）交叉算子。隨機(jī)選擇兩條基因交叉得到一條新基因，交叉方式隨機(jī)產(chǎn)生兩個(gè)結(jié)點(diǎn)，將父結(jié)點(diǎn)2 片段保留至新基因的相應(yīng)位置，其余位置由父基因1填補(bǔ)。

（5）變異算子。一條基因變異得到一條新基因，變異方式隨機(jī)產(chǎn)生兩個(gè)結(jié)點(diǎn)，該基因相應(yīng)結(jié)點(diǎn)位置進(jìn)行 翻轉(zhuǎn)。

2.2 算法流程

TPA 算法的輸入?yún)?shù)包括種群大小Sp、交叉概率Pc、變異概率Pm以及最大迭代次數(shù)Ie。

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

步驟2評(píng)估種群Pop(k)，即計(jì)算Pop(k)中每一個(gè)體的目標(biāo)函數(shù)值，即適應(yīng)度。

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

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

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

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

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

算法流程如圖2 所示。

圖2 TPA 規(guī)劃算法流程Fig.2 Flow chart of TPA algorithm

3 實(shí)驗(yàn)及結(jié)果分析

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

本文實(shí)驗(yàn)中觀測(cè)目標(biāo)共劃分230 個(gè)Tile，輸入數(shù)據(jù)包括每個(gè)Tile 相應(yīng)的觀測(cè)坐標(biāo)、觀測(cè)時(shí)長及優(yōu)先級(jí)（見表2）。

表2 輸入數(shù)據(jù)TileTable 2 Input data of Tile

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

表3 時(shí)間窗口的輸入數(shù)據(jù)Table 3 Input data of time windows

圖3 和圖4 給出了GW170814 的TPA 規(guī)劃結(jié)果。圖3 為GW170814 的Tiling 規(guī)劃軌跡，彩色點(diǎn)為被規(guī)劃的Tile，優(yōu)先級(jí)數(shù)值越大代表該Tile 優(yōu)先級(jí)越高，灰色為未被規(guī)劃的Tile。由圖3 可見Tiling 規(guī)劃軌跡具有規(guī)律性，優(yōu)先級(jí)高的Tile 能夠被優(yōu)先規(guī)劃且整個(gè)規(guī)劃結(jié)果走了盡可能短的路徑。從表4 中同樣可以得出，優(yōu)先級(jí)高的Tile 能夠被優(yōu)先規(guī)劃。

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

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

圖4 GW170814 的時(shí)間規(guī)劃結(jié)果Fig.4 Planning results of GW170814

輸出結(jié)果為歷史最優(yōu)解，圖5 為算法收斂圖像，用于輔助觀察算法迭代的整體收斂趨勢(shì)，不作為結(jié)果的輸出依據(jù)?？梢钥闯鲭S著迭代次數(shù)增加，種群中最好基因?qū)?yīng)的適應(yīng)度值呈下降趨勢(shì)，從44176.74 降至19497.86。適應(yīng)度數(shù)值由優(yōu)化準(zhǔn)則決定，越小表明規(guī)劃結(jié)果越好。在1000 次迭代時(shí)適應(yīng)度值基本達(dá)到最優(yōu)。TPA 算法設(shè)計(jì)的交叉變異使迭代結(jié)果不陷入局部最優(yōu)值。

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

4 結(jié)論

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

通過對(duì)基于Tiling 覆蓋策略的天文衛(wèi)星機(jī)遇目標(biāo)任務(wù)規(guī)劃問題進(jìn)行分析，建立了以距離、任務(wù)優(yōu)先級(jí)、調(diào)姿角度限制滿足率為評(píng)價(jià)準(zhǔn)則的多目標(biāo)優(yōu)化數(shù)學(xué)模型，設(shè)計(jì)了基于遺傳算法的多目標(biāo)優(yōu)化任務(wù)規(guī)劃算法。將該算法應(yīng)用于SVOM 前期工程仿真，采用GW170814 數(shù)據(jù)對(duì)算法進(jìn)行了實(shí)驗(yàn)，結(jié)果表明所建立的模型和方法能夠有效解決問題，達(dá)到合理優(yōu)化觀測(cè)收益的目的。在應(yīng)用中，可以根據(jù)實(shí)際需求對(duì)目標(biāo)函數(shù)參數(shù)進(jìn)行優(yōu)化，實(shí)現(xiàn)加速收斂。

表 4 規(guī)劃結(jié)果中Tile 優(yōu)先級(jí)Table 4 Tile’s priority in planning results

致謝仿真目標(biāo)源為GW170814，仿真數(shù)據(jù)由中法天文衛(wèi)星SVOM 團(tuán)隊(duì)的JAUBERT Jean 提供。