基于雙種群進化算法的對地觀測衛星一體化調度研究

周忠寶，李瑞陽，常中祥*，陳恩銘，劉書源

(1.湖南大學 工商管理學院，湖南 長沙 410082；2.應急管理智能決策技術湖南省重點實驗室，湖南 長沙 410082)

0 引言

近年來，我國航天事業快速發展，氣象、海洋、陸地資源衛星和商業化遙感衛星在軌數量已穩居世界第二，尤其是近幾年發展迅速的商業化遙感衛星在區域治理、災害監測和評估與救援等方面提供了重要的技術支撐[1]。然而，面對迅速增長的觀測需求，有限的對地觀測衛星資源仍顯得異常寶貴，如何對衛星資源進行統籌規劃，在有限的時間內利用更少的資源來完成更多觀測需求已經成為衛星管控領域的重要問題[2]。對地觀測衛星任務可以分為衛星成像觀測和成像數據回傳2個階段，而以往的研究中會優先某一階段或聚焦單一階段進行[3]。因此，研究高效、實用的對地觀測衛星一體化調度方法對衛星資源的高效利用具有重要意義[4]。

自1996年Bensana等人[5]提出衛星日常管理問題以來，衛星任務規劃問題已經得到了廣泛且深入的研究[2-6]。2002年，Lematre[7]正式提出敏捷衛星成像規劃問題，分析了敏捷成像的特點并從理論上證明敏捷衛星成像規劃問題為高度復雜的NP-Hard問題。自此，國內外的大量學者圍繞衛星任務規劃問題展開了一系列研究，整體可分為3類[3]：第1類為分離式調度，類似于文獻[7]的研究，此類研究在任務規劃過程中只關注一個階段，如文獻[8-12]只關注成像觀測，而文獻[13-15]只關注數據回傳；第2類為妥協式調度，此類研究在任務規劃過程中重點對某一階段進行優化，并將另一階段轉化為約束條件，在任務規劃過程中一定程度上兼顧了2個階段[16-17]；第3類為一體化調度(亦稱綜合調度)，即在任務規劃過程中綜合考慮衛星成像觀測和成像數據回放2個階段[18]，近年來已有部分學者開始聚焦于此類模型的構建及相關算法的設計[19-21]。Chang等人[3]通過多種測試場景下的仿真實驗證明了一體化調度在上述3類調度中展現出巨大優勢，因此本文在后續研究中也將采取此種調度模式，在問題假設和模型構建中綜合考慮2個階段，從而實現二者協同優化。

衛星任務規劃問題作為一種復雜的組合優化問題，無法在多項式時間內求得其最優解，而且在實際應用中往往存在規模龐大、約束復雜和目標不唯一等問題，這導致很難找到適用于所有問題的通用算法[2]。因此，大量學者將研究重點聚焦在衛星任務規劃問題求解算法的設計，得益于進化算法簡潔且高效的特性，遺傳算法[9,13,22]、蟻群算法[8,15,23]和差分進化算法[24-25]等進化算法在衛星任務規劃問題的算法設計中得到了廣泛的應用[4]。

以上研究雖然已經能夠在一定程度上解決衛星任務規劃的問題，但是仍然存在約束不全面或求解質量不穩定等問題。因此，本文針對對地觀測衛星一體化調度問題，基于存在約束的雙種群進化算法(Constrained Dual-Population Evolutionary Algorithm，c-DPEA)，結合啟發式規則設計了求解算法，為對地觀測衛星資源的高效利用提供了一種高效、可靠的解決方案。

1 對地觀測衛星一體化調度問題

對地觀測衛星一體化調度問題中包括對地觀測衛星、地面站以及觀測任務3個對象。每個任務可分為衛星成像觀測和成像數據回傳2個階段，分別受到對地觀測衛星與觀測任務的可見時間窗口限制和對地觀測衛星與地面站的可見時間窗口限制。為明晰本文研究問題的重點和邊界，做出以下合理假設：

① 本文只考慮點目標，即衛星一次過境可以完整觀測的地面目標；

② 由于衛星觀測需求遠大于衛星觀測資源，假設每個目標至多只能被觀測一次，且成像數據也至多回傳一次；

③ 衛星為“記錄—回放”模式，即只有先完成地面目標觀測，才可以進行成像數據回放；

④ 成像數據按照“先記錄，先回放”的原則進行數據回傳，且成像數據不可分割；

⑤ 若觀測數據被回傳或過期，則其所占據的衛星存儲空間被釋放；

⑥ 觀測成像的數據產生速率和數據回傳速率一般成固定比例，在此處為方便計算，假設每個觀測任務的成像速率和回傳速率相等；

⑦ 同一衛星在同一時刻只能與一個地面站進行數據傳輸，且受最短工作時間約束；

⑧ 假設衛星一直處于開機狀態，不考慮設備故障、特殊工況等問題，不考慮中繼衛星。

對地觀測衛星一體化調度問題的描述包括元素構成和約束條件，可將其表示為P：

P={St,Et,GT,S,OTW,G,DTW,OT,DT,Cons}，

(1)

式中，[St,Et]為有效調度時間范圍，本文假設有效調度時間為24 h；GT={gt1,gt2,…,gtnGT}為地面目標集合，每個地面目標gti具有屬性：成像時長di，數據有效期oi，任務優先級ωi；S={s1,s2,…,snS}為對地觀測衛星集合，集合中共包含nS=|S|個衛星，每個衛星的最小成像時間均為d0，最大存儲空間為Θ；OTWij={otwij1,otwij2,…,otwijn(OTWij)}為衛星sj與地面目標gti的可見窗口集合，otwijk是衛星sj上地面目標gti的第k個可見時間窗口，集合中共包含n(OTWij)=|OTWij|個可見窗口，每個可見窗口具有屬性：窗口開始時間ostijk，窗口結束時間oetijk；G={g1,g2,…,gn(G)}為地面站集合，集合中共包含n(G)=|G|個地面站，每一個地面站的最短工作時間為d0；DTWlj={dtwlj1,dtwlj2,…,dtwljn(DTWlj)}為衛星sj與地面站gl的可見窗口集合(亦稱傳輸窗口)，dtwljq是衛星sj與地面站gl的第q個可見時間窗口，集合包括n(DTWlj)=|DTWlj|個可見目標，每個可見窗口具有屬性：窗口開始時間dstljq，窗口結束時間detljq；OT={ot1,ot2,…,otn(OT)}為有效調度時間范圍內，調度形成的觀測成像任務集合，包括n(OT)=|OT|個任務，每個觀測任務oti具有屬性：觀測目標gti，執行觀測任務的衛星si，觀測任務開始時間ost′ijk，觀測任務結束時間oet′ijk；DT={dt1,dt2,…,dtn(DT)}為有效調度時間范圍內，調度形成的數據回傳任務集合，集合包括n(DT)=|DT|個任務，每個數傳任務dtv(其中v=ljq)具有屬性：數傳任務對應的觀測任務集合dSetv，執行數傳任務的衛星sv，數傳任務開始時間dst′ljq，數傳任務結束時間det′ljq；Cons為對地觀測衛星一體化調度問題中所包含的所有約束條件，下面將對此部分內容進行詳細闡述。

2 對地觀測衛星一體化調度模型

在對地觀測衛星一體化調度問題中，綜合考慮觀測和數傳2個環節，因此對一個地面目標只有完成觀測成像并在有效期內完成成像數據回傳才可稱為一次成功的對地觀測，所以考慮Chang等人[3]提出的最小數據獲取失敗率f1(P)作為本模型的第一個優化目標：

(2)

同樣需要考慮如何在任務執行過程中盡量使用較少的能源消耗。因此本模型的第2個優化目標為能源消耗率f2(P)，即觀測和數傳任務所使用的能源消耗占最大能源消耗的比例為：

(3)

式中，TEC為衛星消耗的能源綜合；MEC為執行所有觀測任務并用盡所有傳輸窗口所能產生的最大能源消耗。TEC的計算方法如下：

TEC=(nOT×eo+od×ro)+(nDT×ed+td×rd)+ct×rc+rt×rr，

(4)

式中，eo為觀測任務啟動能耗；od為全體觀測任務的執行總時長；ro為觀測成像耗能功率；ed為數傳任務啟動能耗；td為全體數傳任務的傳輸總時長；rd為數據回傳耗能功率；ct和rt分別為姿態機動和天線校對的總時長；rc和rr分別為姿態機動功率和天線校對功率。類似的，可以計算得到MEC：

MEC=nGT×(eo+ro×max(di))+

nDTW×(ed+rd×max(detljq-dstljq))+rc×nGT×ρ+rr×nDTW×σ。

(5)

綜合以上，可以得到對地觀測衛星一體化調度模型：

min{f1(P),f1(P)}，

(6)

s.t.

xi≤1，

(7)

ostijk·xi≤ost′ijk·xi≤oet′ijk·xi≤oetijk·xi，

(8)

(9)

(ost′i2jk2-oet′i1jk1)·OTAi1i2≥ρ·OTAi1i2，

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(dst′lj2q2-det′lj1q1)·DTAv1v2≥σ·DTAv1v2，

(17)

(18)

xi∈{0,1}。

(19)

本文綜合考慮衛星成像觀測和數據回傳2個階段的工作，因此模型中需要兼顧2個階段中的各類約束[3]，數學模型中各公式含義如下：

3 基于雙種群進化算法的衛星一體化調度算法設計與實現

衛星一體化調度問題是一類典型的約束多目標優化問題(Constrained Multiobjective Optimization Problems，CMOPs)，具有變量類型復雜、強約束和多目標等求解難點。近年來，協同進化算法的出現為解決此類復雜優化問題提供了新的方向[26]。進化算法在解決無約束多目標優化問題(Multi-objective Optimization Problems，MOPs)時已經顯現出巨大的優勢，然而CMOPs由于約束條件的存在求解時往往具有更大的挑戰[27]。Ming等人[28]針對存在約束的多目標優化問題提出了一種基于雙種群的協同進化算法c-DPEA，該算法通過2個種群的互補和協作，實現了算法在求解CMOPs的過程中對收斂性和多樣性的兼顧。2個種群在處理不可行解時分別采取不同的方案，其中種群1為多樣性導向，注重解的目標值優化，保留種群中擁有良好目標值不可行解，保證最終解的多樣性；而種群2則以可行性為導向，優先保留可行解，追求更快的收斂速度。2個種群相互補充并在生成子代的過程中進行信息交換，從而實現兼顧收斂性、多樣性和可行性的高效進化。

3.1 基于排序的雙種群適應度分配

Ming等人[28]在c-DPEA算法中提出了一種基于排序的自適應適應度分配方法bCAD，適應度計算函數形式如下，

(20)

(21)

3.2 基于貪婪策略的種群初始化

由于衛星一體化調度問題的復雜性，直接應用進化算法無法在短時間內獲得優質解。通過啟發式規則形成較好的初始種群勢必有利于子代種群在優化迭代的過程中快速向真實前沿靠攏，因此本文也在種群初始化過程中采用了一類受到廣泛使用的貪婪策略。具體流程如下：

① 隨機生成觀測任務開始時刻，并將觀測任務序列中的所有任務初始化為“執行”；

② 首先對每顆衛星的所有觀測任務按照優先級由高到低排序；

③ 按照順序對觀測任務依次執行時間窗口約束檢查，如果不滿足，則將對應任務刪除，并對下一個觀測任務執行時間窗口約束檢查，否則對觀測任務執行④；

④ 對當前觀測任務的前、后相鄰任務執行時間沖突檢查，如存在時間沖突則刪除較低優先級的觀測任務；

⑤ 按照“先觀測，先回傳”的原則生成數傳任務序列和數傳任務開始時間；

⑥ 再次進行約束檢查，刪除無法在有效期內回傳的觀測任務，得到初始解。

3.3 遺傳算子設計

由于本文中包含整數變量和實數變量2類變量，此處引入2類交叉算子和2類變異算子。交叉算子和變異算子均在一定概率下執行。

交叉算子：針對整數變量，使用2點交叉算子，隨機選擇交配池中的2個個體，在觀測任務序列片段或數傳任務序列片段中隨機選擇2個交叉點，交換兩交叉點間的片段，即完成交叉操作。針對實數變量，使用模擬二進制交叉(Simulated Binary Crossover，SBX)。

變異算子：針對整數變量，按照一定的變異概率對種群中的個體執行變異操作，即選中一個個體后，隨機選擇一個變異位，改變變異位原始值，即將0改為1或將1改為0。針對實數變量，采用多項式變異。

3.4 種群更新

在每一代結束時，將種群1和種群2中的個體合并為一個種群規模為2N的組合種群，然后通過二元錦標賽從組合種群中選擇個體進入交配池。首先對組合種群基于bCAD進行排名，然后從組合種群中隨機選出的2個解，選擇bCAD分配排名更好的一個進入交配池，在形成規模為2N的交配池后，通過引入交叉算子和變異算子產生種群規模為N的后代種群。

(22)

其中，

(23)

(24)

式中，γ為2個種群中相同解占種群規模的比例。

種群2則是通過將所有的不可行解投影至Fmax，Fmax為整個種群在各目標維度的最大值所組成的負理想點，修正如式(25)所示，其中wf為Fmax所屬的單位向量。種群2通過對不可行解的修正，在種群更新過程中盡快實現對不可行解的淘汰，從而實現可行性導向的種群進化，即：

(25)

2個種群差異化的更新方式結合bCAD自適應適應度分配方法，最終使得本算法能夠實現在廣泛搜索的同時兼顧快速收斂，使得求解質量和求解效率均得到保證。

3.5 操作算子設計

作為一種混合整數規劃問題，直接使用進化算法求解衛星一體化調度問題往往很難得到較好的結果。隨著啟發式規則的引入，通過一些操作算子對種群個體的任務序列進行破壞和修復，能夠極大地改善算法的尋優效率[29]。為此，本文引入4類破壞算子和對應的4類修復算子，具體情況如下。

(1) 破壞算子

① 優先級準則破壞算子，按照優先級從低到高對所有已調度任務進行排序，并按照次序刪除任務，即優先刪除低優先級任務，并將對應任務存入禁忌池。

② 能耗準則破壞算子，按照能耗從高到低對所有已調度任務進行排序，并按照次序刪除任務，即優先刪除高能耗任務，并將對應任務存入禁忌池。

③ 隨機準則破壞算子，將所有已調度任務隨機排序，并按照次序刪除任務，并將對應任務存入禁忌池。

④ 擁堵度準則破壞算子，按照擁堵度(每個觀測任務時間窗口與其他觀測任務時間窗口發生沖突的次數)由高到低將所有已調度任務排序，然后按照次序刪除任務，并將對應任務存入禁忌池。

(2) 修復算子

① 優先級準則修復算子，按照優先級從高到低對所有未調度且不在禁忌池內的任務進行排序，并按照次序依次嘗試插入任務，即優先插入高優先級任務。

② 能耗準則修復算子，按照能耗從低到高對所有未調度且不在禁忌池內的任務排序，然后按照次序依次嘗試插入任務，即優先插入低能耗任務。

③ 隨機準則修復算子，將所有未調度且不在禁忌池內的任務排序，然后按照次序依次嘗試插入任務。

④ 擁堵度準則修復算子，按照擁堵度由低到高將所有未調度且不在禁忌池內的任務排序，然后按照次序依次嘗試插入任務。

本算法在每次迭代產生子代后，隨機選取一部分子代執行約束檢查，然后進行任務刪除和任務插入操作。將生成的新子代重新放回全部子代，通過環境選擇進入后續種群。

3.6 算法實現

本研究算法步驟如下：

① 設置種群規模、最大迭代次數和插入概率等參數；

② 基于貪婪規則產生初始種群，并對種群中每個個體進行混合整數編碼；

③ 對個體進行沖突檢查和處理，然后復制得到種群1和種群2；

④ 判斷是否達到最大迭代次數，如果達到最大迭代次數則輸出種群2，否則執行⑤；

⑤ 通過錦標賽選擇產生交配池；

⑥ 通過交叉、變異得到子代種群，并隨機對子代種群執行沖突檢查和任務插入；

⑦ 通過種群1和種群2的環境選擇，更新種群1和種群2，然后執行④。

算法流程如圖1所示。

圖1 算法流程Fig.1 Algorithm flow

4 算例與分析

為了驗證基于雙種群進化算法對衛星一體化調度問題求解的收斂速度，采用Chang等人提出的基于現實的模擬實例生成方法產生模擬數據建立仿真算例，模擬數據產生過程中設定如下：

① 對地觀測衛星：設定衛星數量為10顆，分別為“高分”系列衛星(GF0101，GF0201，GF0601)、“高景”系列衛星(SV01，SV02，SV03，SV04)以及資源系列衛星(ZY02C，ZY3，ZY0104)；

② 地面站：設定為4個，密云站(40°N/117°E)、喀什站(39°N/76°E)、三亞站(18°N/109°E)和挪威站(67°N/21°E)；

③ 地面目標：設定為中國境內隨機產生的100個地面目標，所有地面目標的中心點均勻分布于我國大陸范圍內(3°～53°N以及74°～133°E)，地面目標的優先級服從均勻分布[1,10]，需求成像時長服從均勻分布[5,20]，單位s，數據有效期計算方式參照文獻[3]。

其他參數設定為：觀測任務啟動能耗eo=500 J，觀測成像耗能功率ro=50 W，數傳任務啟動能耗ed=500 J，數據回傳耗能功率rd=80 W。姿態機動功率和天線校對功率rc和rr均為100 W。姿態機動時間ρ設定為100 s，天線校對時間σ設定為100 s。

算法的主要參數設定為：種群規模100，最大迭代次數100，交叉概率為0.9，變異概率為0.1，4類破壞操作算子和4類修復操作算子的選擇概率均為0.25，插入概率(選擇執行約束檢查和任務刪除與插入的概率)為0.5。

經過30次運行加入貪婪策略的c-DPEA衛星一體化調度算法，得到運行結果如表1所示。

表1 算法運行整體情況Tab.1 Description of algorithm operation

經過多次實驗發現，不同的任務插入概率下操作算子對最優解和收斂速度均產生不同的影響，這里采用多目標優化評價指標超體積(Hypervolume，HV)對不同任務插入概率下的進化過程進行分析[30]。

此處以0.1為間隔選取[0,1]內的11個值為插入概率，并設置最大迭代次數為100時得到各個個體的超體積，如圖2所示。在以上各個情況下分別得到最終代帕累托前沿，如圖3所示，橫縱坐標分別為目標函數值，目標函數已經做了無量綱化的處理。

圖2 不同插入概率下的HVFig.2 HV with different insert rates

圖3 不同插入概率下的收斂分布Fig.3 Convergence distribution with different insert rates

不難發現，隨著插入概率的增大，種群將能夠搜索到更優的前沿，但與此同時算法的收斂速度也隨之下降，因此在實際問題中可以根據精度需求設置合理的插入概率，從而實現求解質量和求解速度的兼顧。

在求解質量方面，本文選取Chang等人[3]提出的ALNS+NSGA-II算法作為比較對象，分別選取100地面目標、200地面目標、300地面目標和500地面目標4種測試場景對算法進行測驗，每個算法都以相同的初始解進行迭代尋優，得到最終的帕累托前沿，如圖4所示，各子圖橫縱坐標為目標1和目標2的函數值。可以看到，基于貪婪策略的c-DPEA算法在各個場景下均可以獲得更為寬廣的帕累托前沿，即算法可以更為廣泛地搜索整個空間，求得更具多樣性的解。由于最大迭代次數的限制，c-DPEA算法所獲得的部分前沿劣于ALNS+NSGA-II，然而通過設置更大的最大迭代次數，即通過犧牲一定的求解速度，可以進一步獲得更為優秀的帕累托前沿，從而實現解的進一步優化，如圖5所示。

(a) 100 targets

(b) 200 targets

(c) 300 targets

(d) 500 targets圖4 c-DPEA和ALNS+NSGA-II的收斂分布Fig.4 Convergence distribution of c-DPEA and ALNS+NSGA-II

圖5 不同最大迭代次數下的c-DPEA帕累托前沿Fig.5 Pareto front of c-DPEA with different maximum iterations

5 結束語

針對一類同時關注對觀測成像任務和成像數據回傳任務的對地觀測衛星一體化調度問題進行了分析和建模。基于現實應用場景構建了對地觀測衛星一體化調度模型，并設計了與之對應的混合整數規劃模型。通過對模型中約束條件和問題特性進行分析，設計了一種基于貪婪策略的初始解生成方法，在c-DPEA算法中引入操作算子設計了針對衛星一體化調度問題的貪婪雙種群進化算法。該方法通過雙種群的互補和協作，兼顧了衛星一體化調度問題求解過程中的求解多樣性和收斂速度。

本文仍存在一些不足，算法中將操作算子的權重設為恒定值，可以通過引入自適應的權重更新方法幫助子代個體在解空間內更為快速、廣泛地探索，從而進一步提高算法求解質量和收斂速度，實現算法效率的進一步提升。此外，本文只考慮了4類操作算子，未來還可以引入更多類型的操作算子來進一步提高算法對衛星一體化調度的求解能力。