基于貪心—線性規劃算法的敏捷衛星觀測時段選取

孫 慧，李 暉，趙 曼，張 超，應 文

(1.中國地質大學(武漢) 計算機學院，湖北 武漢 430074； 2.中國電子科技集團公司航天信息應用技術重點實驗室，河北 石家莊 050081； 3.中電科海洋信息技術研究院(北京)有限公司，北京 100041)

0 引言

21世紀是我國全面發展的時代，經濟、科學等方面的發展突飛猛進，航天技術方面也取得了一定的成績。對地觀測是衛星通過一定的傳感裝置對地球進行觀測，獲取地球表面信息并對其進行一定的處理過程。為了更有效地利用衛星資源，須結合實際任務需求進行資源的優化規劃，即衛星任務規劃。衛星技術不斷發展，具有三維調整能力的敏捷衛星成為目前重要的對地觀測衛星之一[1]，這使得衛星的觀測較之前更為靈活和復雜，同時也意味著增加了任務規劃的復雜性。在敏捷衛星任務規劃中，當觀測目標是點目標時，衛星對目標的實際觀測時間比較短，不會占用整個可視窗口，因此，在敏捷衛星的任務規劃過程中，還需要為每個點目標規劃出觀測時間段，即觀測時間片段的選取問題[2]。

大多數衛星任務規劃問題都是優化問題[3]，研究者采用各種優化算法對衛星任務規劃問題進行求解[4]。許多研究表明，這些優化算法(例如差分演化算法)在解決衛星任務規劃問題中凸顯了自身的優勢，得到了廣泛應用[5]。因此，本文以差分演化算法為主要求解算法。在衛星任務規劃過程中，存在很多約束條件，由差分演化算法直接迭代產生個體并不一定滿足實際需求，需要對算法產生的個體進行沖突消解[6]，以滿足衛星任務規劃中的各項約束條件，該過程稱為約束處理。本文在約束處理過程解決觀測時間片段選取的問題，提出按最早可開始時間的貪心算法(以下簡稱貪心算法[7])和基于線性規劃問題的求解方式(以下簡稱線性規劃算法[8])進行求解，并將二者相結合，尋找出較好的求解方法。

1 敏捷衛星任務規劃基本原理

1.1 敏捷衛星工作原理及對地觀測過程

攜帶有傳感器的敏捷衛星在圍繞地球旋轉的過程中以一定的姿態(俯仰、測擺和偏航)通過影像獲取其星下點附近的地面信息，即衛星對地觀測過程，如圖1所示。衛星要獲取的地面信息，即衛星的觀測任務[9]。衛星對其星下點的觀測可視范圍，即可視時間窗口。

敏捷衛星運行包括許多復雜環節，其中對目標任務的圖像采集是許多工作中十分重要的一個，其典型流程如下：首先明確觀測目標與需求，確定觀測任務的優先級和需求屬性；對分級后形成的候選任務集進行任務規劃，根據需求安排衛星資源；將確定好的規劃過程轉化為衛星控制指令；衛星根據程序指令執行相應的動作，完成成像工作[10]。

圖1 敏捷衛星對地觀測過程

1.2 敏捷衛星任務規劃原理及過程

敏捷衛星任務規劃就是在衛星成像之前，通過軌道方程計算，得出每個點目標的可視窗口(本文實驗通過STK仿真軟件計算[11])，然后通過各種算法，在滿足各種約束的情況下，確定每個點目標的成像時間和觀測順序，得出滿足需求的規劃方案[12]。本文研究的問題是對點目標成像時間片段的選取，是敏捷衛星觀測任務規劃中的一部分，因此首先要實現對敏捷衛星觀測任務的規劃[13]。

衛星在對目標進行實際觀測的過程中有很多約束條件，例如由于敏捷衛星對點目標的可視范圍較大，窗口時間比較長，距離相近的點目標的窗口會出現重疊的情況，存在任務沖突；由于衛星工作需要指令控制，在一次觀測過程中涉及一系列的指令如圖2所示，因此在選片段的過程中要預留指令模板的時間，來避免指令模板沖突。此外，衛星的整個規劃過程中還有許多約束要考慮，包括能量約束、單圈次觀測時長約束和固存約束等。很多約束條件十分復雜，涉及到多個學科領域的專業知識，要將這些約束條件全部考慮進來會大大增加規劃的難度。

圖2 衛星觀測過程指令序列示意

本文所涉及的規劃只包含觀測部分，因此只考慮指令模板約束。指令模板沖突是指在2個連續觀測任務之間時間間隔小于2個觀測任務所需的指令模板時間之和，即在上一個任務的指令模板還未執行結束，下一個任務的指令模板卻已開始。

1.3 敏捷衛星任務規劃模型

一個觀測可見時間窗口對應一個觀測元任務。對需求中的每個點目標計算出對應的觀測元任務，得到元任務集。選用差分演化算法對元任務集進行規劃，并采取貪心—線性規劃算法為每個元任務選擇觀測時間片段，以盡可能多地安排點目標。根據以上目標，建立任務規劃模型的假設及約束變量的定義為：

③ 觀測元任務可視時間窗口的開始時間和結束時間分別用s，e表示，第j個元任務的窗口開始時間變量為sj，結束時間變量為ej；元任務的實際觀測開始時間和結束時間用sa，ea表示，第j個元任務的實際開始時間為saj，實際結束時間為eaj；

④ 定義觀測元任務決策變量x，如果元任務j能夠完成，則xj=1，2…，反之，xj=0；

⑤ 側擺所需時間用Tcs表示，單位為s；側擺角度用c表示；指令模板間隔計算公式為：Tcs=k*c+d，k，d為常數，可以根據實際情況進行配置。對于連續側擺10°與側擺30°的模板間隔為(k*10+d)+(k*30+d)，對于n個元任務，指令模板時間間隔集合表示為Tcs=Tcs1，Tcs2，…，Tcsn；

⑥ 整個規劃開始時間用TS表示，截止時間用TE表示。

基于以上的假設，建立相應數學模型：

(1) 規劃目標

共有n個點目標要規劃，為每個點目標選取合適的成像片段，使完成元任務數最多，表示方式如式(1)所示：

(1)

(2) 考慮約束

① 所有任務的窗口開始和結束時間必須在整個規劃的時間段TS，TE之內，表示方式如下：

對?j，1≤j≤n，滿足

TS≤sj≤TE，TS≤ej≤TE。

(2)

② 所有的觀測元任務的實際觀測片段必須在觀測可見時間窗口內，表示方式為：

對于?j，1≤j≤n，滿足saj≥sj且eaj≤ej。

(3)

③ 相鄰2個觀測元任務ai、aj之間的實際觀測開始時間間隔不小于這2個元任務所需的指令模板時間之和，表示方式如下：

saj-eai≥Tcsi+Tcsj，?i，j1≤i，j≤n，

assume： saj>sai。

(4)

2 基于差分演化算法的觀測時間片段選取問題求解

基于差分演化算法在解決衛星任務規劃問題上已有很多應用，本文使用差分演化算法作為任務規劃的主要求解算法[15]。首先將衛星任務數據對應到染色體中，形成染色體種群；然后對每個染色體對應的元任務進行約束處理(沖突消解)，使得該染色體對應的解可行，本文在該過程中進行成像片段的選擇；再對每條染色體進行適應值評價，并將當前代的最優染色體保存下來，然后通過差分演化算法迭代產生下一代種群，重復上面的步驟，直到迭代結束，選出最優的染色體，最后對最優染色體進行解析，對應到衛星規劃問題中，得出每個點目標的成像片段，并得出規劃的點目標數[16]。算法規劃流程如圖3所示。

圖3 算法規化流程

2.1 基于最早可開始時間的貪心算法選擇成像片段

為了規劃完成的任務數最大，在選擇成像片段過程中，需要盡可能地避免模板上的沖突。本文采用的貪心算法就是通過調整觀測元任務所選取的成像片段來減少它對其他任務的影響[17]。

選擇成像片段的算法實現過程如圖4所示。首先將觀測元任務按照窗口時間先后進行排序，選取每個窗口的最后時間片段作為初始選擇；由于沒有其他任務的限制，可將第一個元任務的時間片段調整到可視窗口的開始位置；然后按順序獲取下一個元任務，判斷該任務與上一個任務是否有指令模板沖突，如果有則刪除該任務，如果沒有，則調整該元任務的觀測開始時間；繼續上面的步驟，獲取下一個元任務，選擇時間片段，直到所有的任務都遍歷完，則結束選成像片段過程。

圖4 基于最早可開始時間選擇成像片段的貪心算法流程

在上述流程中，主要通過判斷是否有指令模板沖突來調整觀測時間片段，具體過程如圖5所示。

圖5 調整成像片段示意

從圖5中可以看出，從左到右有4個點目標，分別記為目標1、目標2、目標3和目標4，這些目標的順序按其可視窗口的時間先后而定，假設目標1是當前一批目標中可視窗口最早的目標，點目標要求的觀測時長為t。對于每個觀測元任務，初始時均選取可視窗口的最后t時段作為選取的成像片段，如圖5中的灰色部分；該窗口開始時間是觀測的最晚開始時間，否則不能滿足觀測時長要求。然后根據約束，進行成像片段的調整，如圖5中的黑色部分，調整順序按窗口排序依次進行。對于當前批的第1個元任務，其時間片段的選取不會受前面元任務的影響，因此可將成像片段調整到窗口開始t時段。

然后對第2個元任務進行調整，處理方法是在第1個元任務選中的成像片段結束時間加上該任務的結束指令模板時間和第2個任務的開始指令模板時間，得到一個允許的最早開始時刻t1。t1時刻存在的區間有3種情況：① 晚于第2個任務的窗口開始時間但早于第2個任務初始選中片段的開始時間；② 早于第2個任務的窗口開始時間；③ 晚于第2個任務初始選中片段的開始時間。針對以上3種情況的調整情況是：將時間片段調整到t1時刻；將時間片段調整到窗口開始時刻；刪除任務。分別對應圖5中的目標2、目標3和目標4。

2.2 基于線性規劃問題的求解方法選擇成像片段

線性規劃問題是在一系列線性約束條件下，對目標函數求最優解的過程[18]。由此可將求解線性規劃問題的方法應用到衛星任務規劃中，以此來選出點目標合適的觀測時間片斷[19]。要運用線性規劃的解決算法，首先要對衛星規劃問題采用線性規劃問題的建模方式進行模型的建立[20]，在本文的研究中，主要考慮的約束條件是時間窗口約束和指令模板約束，即元任務的實際觀測時間要在可視窗口的時間范圍內，觀測元任務之間的時間安排要符合指令模板約束。假設每個點目標的觀測時間只需要5 s，以上約束關系可表示為：

(5)

式中，xi和xj分別表示第i和j個觀測元任務的實際開始觀測時間，xi≥0，xj≥0且j≠i；ti_start和ti_end分別表示第i個觀測元任務某個可視時間窗口的開始時間和結束時間；ΔT表示元任務i和元任務j之間指令模板間的時間間隔。

但是上述約束條件不能運用線性規劃的求解方式來求解，因為線性規劃問題中，線性約束條件之間是相與的關系，即所有的關系必須同時滿足[21]。而式(5)中存在相或的關系，因此，對衛星規劃中的約束條件做如下改進，即

(6)

式中，xi≥0，xj≥0且xj>xi。

式(6)在式(5)的基礎上進行一定的修改，去掉表示指令模板約束的式子中的絕對值，并且要求xj>xi，即任務j的實際觀測開始時間早于任務i的實際觀測開始時間，這意味著假設存在某一個可行的規劃方案，任務j可以安排在任務i之后進行，但這個規劃結果會被線性規劃解決方法遺漏，可能會使線性規劃得到的解并不是衛星規劃中的最優解。雖然存在上述的不足，但是在單純形算法解決線性規劃問題的時候，如果問題有解，那么找到的一定是最優解。針對這一特性，利用線性規劃的思想解決衛星規劃問題還是有一定研究意義的。

在確定好約束條件后，需要構造對應的目標函數。衛星規劃的優化目標是一次規劃安排的點目標的個數，對應到線性規劃問題中，就是當目標函數有解時對應的x個數[22]。由此發現，實際目標函數是X={x1，x2，x3，......xn}，其中，X中xi的個數最多，即最多個點目標被規劃。但是，該目標函數無法用線性公式表示，不符合線性規劃要求。因此，構造式(7)所示目標函數，當該目標函數有解，即實際目標函數達到最大值。

ymin=x1+x2+x3+x4+x5+…+xn，

(7)

式中，n為所有點目標的個數。

根據以上目標函數，當目標函數有解時，對應x的解即可得到每個點目標的成像片段。

當構造的目標函數無解時，意味著在該約束條件下，目標函數中涉及的x變量所對應的點目標不能全部被安排[8]。需要刪除某些點目標，重構目標函數。

本文引用沖突量概念作為刪除依據，計算每個點目標與其后目標的窗口沖突時長，沖突時間越長，沖突量越大。刪除沖突量最大的點目標，繼續上述規劃算法，求最優解。重復上述過程，直到目標函數有解。

3 實驗測試與分析

算法的參數會一定程度上影響算法的計算效果。在實驗過程中，要根據不同的實驗數據規模來確定算法參數。本文測試過程中選取了不同數據量的測試實例對算法進行測試，選取了以下2類具有代表性的測試用例對測試結果進行分析。2個測試實例的元任務數及參數設置如表1所示。

表1 測試實例元任務個數及差分演化算法參數設置

測試實例觀測元任務數種群大小迭代次數變異概率拉伸因子測試實例118100500.80.7測試實例22873002000.80.7

3.1 規劃結果對比分析

本文中的實驗對基于最早可開始時間選擇觀測片段的貪心算法和基于線性規劃選擇時間片段的算法進行了組合測試，即在程序設計上，將這2個算法可以分別運用到2個地方：① 在差分演化算法迭代過程中，在每次迭代中運用上述之一的算法進行成像片段選取及指令模板約束處理；② 在迭代結束后對選擇出評價結果最好的染色體進行解析，計算出成像時間片段。

對2個算法進行組合，共有4種實驗方案：

① 基于最早可開始時間的貪心算法(G)+基于最早可開始時間的貪心算法(G)；

② 基于最早可開始時間的貪心算法(G)+基于線性規劃問題的求解算法(L)；

③ 基于線性規劃問題的求解算法(L)+基于最早可開始時間的貪心算法(G)；

④ 基于線性規劃問題的求解算法(L)+基于線性規劃問題的求解算法(L)；

在上述4項選擇中，“+”前面表示在差分演化算法迭代過程中運用，“+”面表示在最后解析最優染色體過程中運用。

2組測試實例針對4種實驗方案的規劃結果(即安排的點目標個數)對比如表2所示。

表2 結果對比表

測試實例組合方式差分演化算法結束后規劃元任務數解析后規劃元任務數任務完成率/%測試實例1G+G5527.777 8G+L5844.444 4L+G10316.666 7L+L101055.555 6測試實例2G+G20520571.428 6G+L20519266.899 0L+G26018965.853 7L+L25825889.895 5

根據以上測試結果可以看出，在第1組測試實例中，方案基于線性規劃問題的求解算法+基于線性規劃問題的求解算法(L+L)的規劃結果最好，完成任務率最高，其次是方案②、方案①和方案③。通過對比可以發現，在解析最優染色體階段使用線性規劃的解決方法一般可以規劃較多的任務數，并且可以優化貪心算法得出的結果；而用貪心算法解析線性規劃得出的最優染色體則會使原本的結果變差。如果單純某一種算法，沒有優化的效果。

在對測試實例2的大量實驗過程中，大部分實驗結果符合上述針對測試實例1的實驗結論，但也存在一些結果并非與上述結論完全一致，如表2中關于測試實例2的結果中，方案②在解析階段使用線性規劃求解問題的方法并沒有得出像測試實例1中的優化效果，這是由于線性規劃處理階段存在隨機性，有時會有優化效果，有時效果反而變差。因此，在實際規劃過程中，可以先采用貪心算法得出規劃結果，然后用線性規劃求解算法進行解析，如果結果變好，則用優化后的規劃結果，如果沒有優化，則用之前的規劃結果。因此，說明采用線性規劃的算法是一種可選的優化方案，但得到的結果并不一定是最優的，在實際應用中，可以將線性規劃的結果作為一個參考項與貪心算法結果進行比較，擇優選擇解決方法。

3.2 規劃時間及算法收斂性對比分析

與上述實驗方法相同，對2組測試實例在運行時間和算法收斂性方面進行分析總結。2組實例的時間對比情況如表3所示。

表3 各項運行時間對比 (s)

由表3可以看出，在整個規劃過程中，差分演化算法迭代會占用較多的時間，解析過程所占的時間比重十分小；線性規劃算法耗時比較長，貪心算法耗時比較短。因此，一般只在解析階段使用線性規劃對結果進行優化，不會用到演化過程中，而貪心算法在演化過程中的效率比較高。

對2組測試結果進行對比分析可以得出，在數據量小的情況下，在差分演化算法過程中使用線性規劃算法的耗時還在一定的可以接受范圍內，但當數據量即要規劃的點目標個數增大時，線性規劃的耗時對整個算法的運行效率影響很大，在實際工程應用中是無法接受的，這也說明線性規劃使用在差分演化算法過程中是不適用的，只適合最后的優化選項過程。

對測試實例2進行收斂性分析，分別用方案①(貪心算法+貪心算法)和方案④(線性規劃算法+線性規劃算法)的規劃組合進行實驗，2種不同的策略對應差分演化算法的收斂情況如圖6所示。

圖6 2種策略收斂情況對比

由圖6可以看出，貪心算法在100代左右收斂，而此時線性規劃還在優化過程中，直到160代左右收斂，由此可見，二者收斂速度都較快，貪心算法比線性規劃算法使差分演化算法收斂相對更快些。

3.3 實驗結論

結合上述對規劃結果、運行時間和算法收斂速度3個方面的對比測試可以發現，在選擇成像片段的過程中，如果采用線性規劃的解決方法則可以較多地規劃任務數，但是線性規劃的耗時十分長，是貪心算法的10倍以上，會影響整個程序的性能。相比之下，貪心算法收斂速度快并且耗時少；在選擇成像片段的過程中，為了能夠盡可能多地規劃任務并且使耗時在可接受的范圍內，可以將耗時少的貪心算法運用到差分演化迭代過程中來選擇最優染色體，在得出一個結果后，選擇線性規劃方法嘗試優化，如果結果比原來的好，則采用該方法選片段，否則，維持原來已有的結果。

4 結束語

本文提出基于貪心—線性規劃相結合的方式進行敏捷衛星任務規劃過程中觀察時間片段的選取。在差分演化算法迭代過程中采用貪心算法可以比較快速地得出點目標的成像片段，在解析最優染色體的過程中采用線性規劃算法多數情況下可以優化規劃結果，安排更多的點目標。該方法提高了整個衛星規劃的效果，更好地利用衛星資源，有著很好的研究價值和應用前景。