考慮成像質量的敏捷衛星任務調度模型與算法

李志亮，李小將，孫 偉

(1. 裝備學院研究生院，北京101416；2. 裝備學院航天裝備系，北京101416；3. 北京航空航天大學儀器科學與光電工程學院，北京100191)

?

考慮成像質量的敏捷衛星任務調度模型與算法

李志亮1，李小將2，孫 偉3

(1. 裝備學院研究生院，北京101416；2. 裝備學院航天裝備系，北京101416；3. 北京航空航天大學儀器科學與光電工程學院，北京100191)

針對敏捷衛星任務調度中成像質量受觀測時間影響的特點，構建考慮觀測時間因素的約束滿足模型，提出一種將離散差分進化與變鄰域搜索相結合的求解算法(DDE-VNS)。首先，描述敏捷衛星任務調度時間約束；其次，考慮觀測時間對成像質量的影響、任務間姿態轉換時間約束、星上存儲與能量約束等因素構建了敏捷衛星任務調度的約束滿足模型；再次，設計離散差分進化的變異、交叉和選擇算子，采用變鄰域搜索對每次迭代的最優解進行局部搜索以尋找更好的鄰域解，并給出了算法的實現流程。仿真結果表明,利用該模型可獲得收益值較高的調度方案，且該算法在收斂速度更有優勢。

敏捷衛星；任務調度；離散差分進化；變鄰域搜索

0 引 言

敏捷衛星是指有效載荷固定于衛星平臺，依靠姿態軌道控制系統實現滾動、俯仰和偏航三個軸向快速機動的衛星[1]。相比于傳統成像衛星，敏捷衛星姿態機動能力更強、觀測時間窗口更長、任務沖突的解決方式更多，單次過境的任務執行能力大大增強。目前，各航天大國已研制發射了多顆敏捷衛星，如美國的WorldView系列衛星、法國的Pleiades星座、以色列的EROS-B衛星。敏捷衛星在軍事偵察、抗震救災等任務中能夠發揮分散目標快速成像、復雜任務高效執行、不確定因素有效應對等優勢，具有廣闊的應用前景，是新型衛星發展的重要方向。

敏捷衛星潛在的優勢依賴于有效的調度模型和算法。文獻[1]認為敏捷衛星靈活機動優勢帶來的觀測時間不確定性使得該問題兼具選擇和調度特性，考慮單星單軌構建了數學規劃模型，并分析了貪婪搜索、動態規劃、約束規劃和局部搜索等算法的求解效率。文獻[2]構建了考慮任務間姿態轉換、星上存儲和能量等約束的數學模型，設計了一種混合遺傳算法進行求解。文獻[3]通過改變種群迭代次序提出一種基于二進制指標的多目標局部搜索算法，計算結果表明該方法在運算方面更為高效。文獻[4]分析了敏捷衛星成像幾何模型和時間模型，提出一種條帶劃分和時間窗口求解算法。文獻[5]考慮時間窗口、星上存儲和最長連續工作時間約束構建了數學規劃模型，提出一種評價調度收益和資源消耗的優先級指標，并根據該指標設計了蟻群優化算法。文獻[6]基于復雜網絡理論研究了單星調度問題，將每個節點作為目標的觀測機會，提出節點和目標的重要性指標，并設計了一種近似求解算法。

通過社會協作、自我適應和競爭實現進化的群體智能算法是解決多約束組合優化問題的有效方法[7]。差分進化(Differential evolution, DE)算法是由Store和Price[8]提出的一種基于群體智能的優化算法，它采用實數編碼、基于差分的簡單變異操作和一對一的競爭策略，具有較強的全局搜索能力。文獻[9]提出一種求解流水車間調度問題(Flow shop scheduling problem，FSP)的離散差分進化(Discrete differential evolution, DDE)算法，該算法通過取模運算改進變異算子。文獻[10]基于標度法和層次分析法研究了自適應離散差分進化算法的候選解產生策略選擇問題。文獻[11]將DDE算法用于求解武器-目標分配(Weapon-target assignment，WTA)問題。文獻[12]針對信號采集衛星系統的調度問題，提出一種基于二次映射編碼的動態調度差分進化算法。

上述研究為敏捷衛星任務調度建模和求解提供了很好途徑。同時存在一些不足，文獻[1]忽略了星上存儲和能量約束，并且將姿態轉換時間作為固定值進行了簡化，帶來任務間存在時間沖突的問題。文獻[2-6]將最大化完成任務的優先級之和作為目標函數，沒有考慮敏捷衛星觀測時間對成像質量的影響，文獻[13]基于敏捷成像模型分析了多因素影響下的成像質量評價準則，但是沒有研究考慮成像質量的調度問題。文獻[9-12]的研究為差分進化求解組合優化問題提供了較好的思路，同時，由于編碼方式和輔助算子不同，變異和交叉操作容易產生不合理的個體編碼，其應用擴展性有限。

針對以往研究的不足，本文在描述敏捷衛星任務調度時間約束的基礎上，綜合考慮觀測時間對成像質量的影響、任務間姿態轉換約束、星上存儲和能量約束等，通過改進目標函數建立了調度約束滿足模型，提出一種將離散差分進化與變鄰域搜索相結合的算法(Discrete differential evolution with variable neighborhood search, DDE-VNS)，通過仿真算例校驗了模型的有效性和算法優越性。

1 敏捷衛星任務調度時間約束描述

姿態機動能力增加了敏捷衛星對地觀測的自由度，同時，其任務調度的時間約束變得更加復雜，主要體現在成像、姿態轉換方面。在成像活動中，當一個地面目標被選定后，其觀測時間是可見時間窗口內的一個連續變量，不同觀測時間對應的觀測姿態角不同，觀測姿態角直接影響衛星對地面目標的成像分辨率，而成像分辨率是成像質量好壞的主要評價指標，因此，觀測時間影響衛星對地面目標的成像質量。此外，在姿態轉換活動中，對于相鄰任務，衛星需完成任務間的姿態轉換，姿態轉換時間取決于前后任務的結束和開始時間，當衛星資源有限而成像任務眾多時，姿態轉換時間主要受前一任務的結束時間影響，選擇不同的時間進行姿態轉換，所需轉換時間也不同。

基于一般化的時間約束問題，敏捷衛星任務調度時間約束可以描述為：設一組變量集合X={X1,X2,…,Xn}和一組變量上的約束C={C1,C2,…,Cn}，其中每個變量代表一次成像活動的時間點，變量上的約束代表成像活動的時間窗口約束以及前后相鄰活動間的姿態轉換約束，當賦值{X1=a1,X2=a2,…,Xn=an}滿足所有約束時，稱X={a1,a2,…,an}為該時間約束的解。對于所有可行解，每個活動的時間賦值在一定區間范圍內，不同的時間賦值即不同的觀測時間，對應的成像質量不同。因此，這種時間賦值是調度方案優劣的直接體現，敏捷衛星任務調度中，需要考慮這種時間賦值對調度方案的影響。

2 敏捷衛星任務調度約束滿足模型

首先定義建立調度約束滿足模型所需參數，然后從決策變量、目標函數、約束條件3個方面描述模型。

2.1 參數定義

本文模型相關參數定義如表1所示。

表1 相關參數定義Table 1 Definition of related parameters

2.2 模型描述

針對文獻[1]簡化姿態轉換約束的不足，本文通過計算不同時刻下衛星對地面目標的觀測姿態角，確定姿態機動時間，使任務間姿態轉換約束更為合理。針對文獻[2-6]的研究均沒有考慮觀測時間對成像質量影響的不足，本文在目標函數中增加成像質量評價函數，根據任務優先級和觀測時間確定目標函數值。考慮上述改進的目標函數和增加的約束條件，多敏捷衛星任務調度的約束滿足模型描述如下：

1)決策變量

2)目標函數

在以往對敏捷衛星任務調度的研究中，常見的目標函數是最大化完成任務的優先級之和[2-6]，其描述如下式：

(1)

敏捷衛星對地面目標的觀測時間是可見時間窗口內的一個連續變量，觀測時間離可見時間窗口的中心時刻越近，對應的觀測姿態角越小，成像質量也越好；反之離中心時刻越遠，對應的觀測姿態角越大，成像質量則越差。在敏捷衛星任務調度模型中考慮觀測時間對成像質量的影響，通過合理安排任務的觀測時間提高成像質量，具有一定的現實意義。

當采用P1作為目標函數，且任務ti被選擇觀測時，無論任務ti的觀測時間處于其可見時間窗口內的哪一時刻，計算所得目標函數值均為wi，而實際上，衛星在不同觀測時間對目標的成像質量有一定差異。因此，有必要構建觀測時間與成像質量之間的函數關系式。

(2)

(3)

(4)

(5)

3)約束條件

本文模型考慮以下5方面的約束條件：

(1)任務執行的唯一性約束

(6)

(7)

(2)任務執行的時間窗口約束

(8)

(3)相鄰任務間姿態轉換時間約束

(9)

(4)衛星單個軌道圈次的存儲約束

(10)

(5)衛星單個軌道圈次的能量約束

(11)

上述模型通過引入成像質量評價函數改進目標函數，同時考慮了任務間姿態轉換、星上存儲和能量等約束，是較為復雜的約束滿足模型，本文采用離散差分進化與變鄰域搜索相結合的算法進行求解。

3 DDE-VNS求解算法

敏捷衛星任務調度是NP-Hard問題[1]，具有組合優化特點，難于求解。相比于尋求最優解的精確算法，近似算法在求解衛星任務調度問題上取得了較好的效果，如遺傳算法[2]、蟻群算法[5]。同時，遺傳算法容易陷入局部最優，而蟻群算法依賴于控制參數和啟發式信息。鑒于差分進化在全局搜索方面具有較好的性能，而變鄰域搜索能提高算法的局部搜索能力，本文結合敏捷衛星任務調度問題特征，首先設計離散差分進化解的編碼方式、初始種群生成方式、差分變異算子、交叉及輔助操作算子，然后采用變鄰域搜索對離散差分進化每次迭代的最優解進行局部搜索，以尋找更好的鄰域解，最后給出算法的實現流程。

3.1 離散差分進化設計

1)解的編碼

對解進行編碼是求解調度模型的首要問題。敏捷衛星的調度方案由每顆衛星的任務序列組成，本文根據任務執行順序采用自然數編碼方式，建立衛星與任務的對應關系，同時在不同衛星的任務序列間插入虛擬任務(用0表示)加以區分，形成DDE算法的個體編碼。例如，x=[3 5 1 0 2 4 9 0 6 8 7]即為一個有效的個體編碼。算法中個體的適應度值即模型中的目標函數值。

2)初始種群的生成

本文采用隨機貪婪算法生成初始種群，具體步驟如下：

步驟1：通過預處理獲得每顆衛星在可用軌道圈次上的候選任務，隨機選擇一個軌道圈次，計算該軌道圈次上候選任務的優先級之和Wsum、最早可觀測時間的最小值Bmin和最早可觀測時間的最大值Bmax。

步驟2：計算每個候選任務的選擇概率ai，計算式如下：

(12)

式中：σ是一個很小的正數。

步驟3：采用輪盤賭法選擇一個任務，判斷該任務是否屬于禁忌表，如果不是，則判斷是否滿足約束條件，滿足則寫入任務序列，并更新禁忌表。

步驟4：判斷是否有未選擇的軌道圈次，如果有，則重復步驟1～3，如果沒有，則搜索結束，將每顆衛星的軌道圈次按先后順序排列，生成任務序列。

在初始種群的生成中，通過隨機選擇軌道圈次的方式減少了單顆衛星負載過大的情況，采用輪盤賭法選擇候選任務增加了任務序列的多樣性。

3)變異算子

(13)

式中：r1、r2、r3為隨機選擇的三個個體，且r1≠r2≠r3≠i，F為縮放因子。應用于敏捷衛星任務調度問題，“⊕”和“?”運算通過下式計算得到

(14)

式中：rand(·)為(0,1)的隨機數，mod(·)為取模運算，NT為任務數量。

通過上述操作得到變異個體不一定是合理的任務序列，但是考慮到變異的作用是對目標個體產生擾動，因此可以在交叉算子中設計輔助算子得到合理的任務序列。

4)交叉算子

根據DDE的機理[9]，試驗個體由變異個體和目標個體通過交叉操作產生：

(15)

式中：R為交叉概率，⊙為輔助操作算子，針對敏捷衛星，本文設計了基于刪除和插入鄰域的輔助操作算子。交叉操作具體步驟如下：

在基于刪除和插入鄰域的輔助操作算子中，每次尋找任務的可行插入位置時，需確定任務的觀測時間，文獻[1]采用基于最早可觀測時間的方法，本文在此基礎上，以接近時間窗口中心作為啟發式規則確定觀測時間。

經過交叉得到試驗個體，一部分來自目標個體，另一部分來自變異個體，并且通過輔助算子(步驟2～3)確保了試驗個體的合理性。

5)選擇算子

采用一對一貪婪競爭機制選擇適應度值較大的個體作為子代個體

(16)

3.2 變鄰域搜索設計

在搜索過程中，充分利用問題信息增強離散差分進化的局部搜索能力是提高其優化性能的有效途徑。鑒于目標種群的最優個體往往攜帶有價值的信息，因此對每次迭代的最優個體進行局部搜索，以獲得更好的鄰域解[7]。

為了減小鄰域搜索的范圍，提高搜索效率，本文結合敏捷衛星特點設計了三種鄰域結構：插入鄰域、替換鄰域、移位鄰域。插入鄰域是將未選中執行的任務插入到衛星的任務序列中；替換鄰域是指當插入鄰域不滿約束條件時，根據優先級關系替換任務序列中已安排的任務；移位鄰域是指根據每顆衛星的負載，從負載最大的衛星任務序列中隨機選擇一個任務，將其插入到負載最小的衛星任務序列中。衛星的負載通過下式計算：

變鄰域搜索的步驟如下：

步驟1：計算未安排觀測的任務集，將其中任務按照優先級從大到小進行排列，選擇優先級最大的任務，根據插入鄰域計算可行的插入位置，如果能插入，將該任務寫入禁忌表，如果不能，轉向步驟2。

步驟2：若不能插入則選擇使用替換鄰域，如果不能替換已有序列中的任務，則將該任務寫入禁忌表。

步驟3：采用移位鄰域對多顆衛星的任務序列進行調整，產生新的鄰域解。

步驟4：評價新解的適應度值，若大于當前最優解，則用新解替換當前最優解。

步驟5：判斷當前是否滿足終止條件，若滿足最大迭代次數或最優解不變連續迭代次數，則結束搜索，否則轉向步驟1。

3.3 算法實現流程

綜合上述的分析和設計，DDE-VNS算法的實現主要包括三部分：算法初始化、DDE搜索、VNS搜索，其中算法初始化包括參數初始化和初始種群生成；DDE搜索即通過設計的變異、交叉和選擇算子產生每一代的最優解；VNS搜索利用三種鄰域結構對DDE每次迭代的最優解進行鄰域搜索，獲得新解并評價，然后更新最優解。DDE-VNS算法的實現流程如圖1所示。

圖1 DDE-VNS算法實現流程圖Fig.1 Algorithm flowchart of DDE-VNS

4 仿真校驗

采用Matlab R2010b對敏捷衛星任務調度約束滿足模型的有效性和DDE-VNS算法的優越性進行仿真校驗。

4.1 參數設置

仿真算例中敏捷衛星的軌道參數和有效載荷參數參考Pleiades衛星[1]，軌道高度為694km，軌道傾角為98.13°，升交點赤經為70.251°；成像任務采取隨機生成的方式獲得，考慮到點目標是成像的基本單元，而且條帶目標可以看作具有一定觀測時長的點目標，區域目標通過分解可由點目標和條帶目標組成，本文選擇在(60°E～150°E)、(0°N～50°N)的范圍內隨機生成5組不同規模的點目標任務集，分別為50、100、200、300、600個，每個任務的優先級為[1,10]之間的隨機數。通過組合產生5組實例(衛星數-任務數)：2-50、3-100、4-200、5-300、6-600。

算法參數設置如下：離散差分進化中種群規模NP=100，進化代數Imax=300，縮放因子F=0.8，交叉概率R=0.5；變鄰域搜索中最大迭代次數Gmax=10，最優解不變連續迭代次數Gremain=3。

4.2 調度約束滿足模型仿真結果分析

圖2 成像質量隨觀測時間的變化Fig.2 Change of imaging quality with observation time

圖3 兩種方案的觀測時間分布情況Fig.3 Distribution of observation time in different schemes

表2 不同目標函數下調度方案對比Table 2 Comparison of schedule schemes under different objective function

4.3 DDE-VNS求解算法仿真結果分析

為校驗本文算法DDE-VNS的優越性，將本文算法與遺傳算法(GA)[2]、蟻群優化算法(ACO)[5]、標準離散差分進化算法(DDE)[9]在5組算例上進行對比，目標函數采用綜合考慮成像質量和任務優先級的P2，以平均收益、最大收益、最大任務數量、平均運行時間作為算法對比的主要評價指標。計算機配置為Intel Core i7-3770 CPU @3.4GHz、8核4GB內存，操作系統為Windows 7、編程環境為Matlab R2010b。每組算例運行20次并取平均值，結果如表3所示。

表3 本文算法與GA、ACO、DDE算法性能對比Table 3 Comparison of algorithm proposed in this paper with GA, ACO and DDE

由表3可知，與GA、ACO相比，本文算法在收益值和運行時間上均有優勢，在收益值上分別平均提高了8.4%和6.7%，運行時間也較少，但隨著算例規模的增大，其運行時間也大幅增加。與DDE相比，本文算法在收益值上平均提高了6.5%，同時，每次迭代中對最優解按照一定迭代次數尋找鄰域解也增加了運行時間。此外，以算例4-200為例，將通過P2計算所得目標函數值作為收益值，GA、ACO、DDE、DDE-VNS的收斂性對比如圖4所示。

圖4 算法的收斂性對比Fig.4 Comparison of convergence of different algorithms

由圖4可知，本文算法在收益值和收斂速度上優于其他4種算法，GA和ACO，GA、ACO分別需要需運行93代、132代左右能夠收斂到其最優解，而本文算法需35代左右即可收斂到最優解；本文算法與DDE在收斂速度上相差較小，分別為35代、32代左右，但本文算法在收益值上高于DDE。說明本文算法相對于GA、ACO具有更好的全局搜索能力，而VNS能夠增強DDE的局部搜索能力，在全局探索和局部開發上較為均衡的DDE-VNS具有更好的性能。

5 結 論

本文描述了敏捷衛星任務調度時間約束，建立了考慮觀測時間對成像質量影響、任務間姿態轉換時間、星上存儲與能量約束等因素的約束滿足模型，設計了DDE-VNS求解算法，仿真結果表明，本文模型在調度方案的優化上更有效，DDE-VNS算法相對于其他算法在收益值和收斂性上更有優勢，研究內容為敏捷衛星任務調度建模和求解提供了很好的途徑。同時，本文研究沒有考慮調度中不確定因素的影響，如應急任務加入、衛星資源失效、云層遮擋等。在后續工作中，可進一步考慮這些不確定因素，研究不確定條件下的調度模型與求解算法，以期促進敏捷衛星任務調度方法的不斷完善。

[1] Lemaitre M, Verfaillie G, Jouhaud F, et al. Selecting and scheduling observations of agile satellites[J]. Aerospace Science & Technology, 2002,6(5):367-381.

[2] Li Y, Xu M, Wang R. Scheduling observations of agile satellites with combined genetic algorithm[C]. The Third International Conference on Natural Computation, Haikou, China, Aug. 24-27,2007.

[3] Tangpattanakul P, Jozefowiez N, Lopez P. A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite[J]. European Journal of Operational Research, 2015, 245(2): 542-554.

[4] Bunkheila F, Ortore E, Circi C. A new algorithm for agile satellite-based acquisition operations[J]. Acta Astronautica, 2016, 123: 121-128.

[5] Xu R, Chen H, Liang X, et al. Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization[J]. Expert Systems with Applications, 2016, 51: 195-206.

[6] Wang X, Chen Z, Han C. Scheduling for single agile satellite, redundant targets problem using complex networks theory [J]. Chaos, Solutions and Fractals, 2016, 83: 125-132.

[7] 王凌,錢斌.混合差分進化與調度算法[M].北京: 清華大學出版社, 2012:204-222.

[8] Storn R, Price K. Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization, 1997, 1(4): 341-359.

[9] Pan Q K, Wang L, Gao L. An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers[J]. Information Sciences, 2011,181(3):668-685.

[10] 薛羽, 莊毅, 顧晶晶, 等. 自適應離散差分進化算法策略的選擇[J]. 軟件學報, 2014, 25(5): 984-996. [Xue Yu, Zhuang Yi, Gu Jing-jing, et al. Strategy selecting problem of self-adaptive discrete differential evolution algorithm[J]. Journal of Software, 2014, 25(5): 984-996.]

[11] 張春美,陳杰,辛斌. 武器目標分配問題的離散差分進化算法[J]. 北京理工大學學報, 2014,34(3):289-293. [Zhang Chun-mei, Chen Jie, Xin Bin. A discrete differential evolution algorithm for the weapon target assignment problem[J]. Transactions of Beijing Institute of Technology, 2014,34(3): 289-293.]

[12] 皮本杰, 翟淑寶. 信號采集系統星地資源快速調度優化方法[J]. 宇航學報, 2016,37(3):348-356. [Pi Ben-jie, Zhai Shu-bao. Quick optimal schedule method of onboard and ground resources for signal collection satellite system[J]. Journal of Astronautics, 2016,37(3): 348-356.]

[13] 陳錦偉. 敏捷衛星遙感圖像配準和拼接技術研究[D]. 杭州: 浙江大學, 2014. [Chen Jin-wei. Research on registration and stitching of remote sensing image of agile satellite[D]. Hangzhou: Zhejiang University, 2014.]

[14] Rosa B, Souza M, Souza S, et al. Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties[J]. Computers and Operations Research, 2017, 81: 203-215.

通信地址：北京市懷柔區八一路1號(101416)

電話：13522097833

E-mail:lemonslee@163.com

Task Scheduling Model and Algorithm for Agile Satellite Considering Imaging Quality

LI Zhi-liang1, LI Xiao-jiang2, SUN Wei3

(1. School of Postgraduate, Academy of Equipment, Beijing 101416, China;2. Department of Space Equipment, Academy of Equipment, Beijing 101416, China;3. School of Instrumentation Science and Opto-electronics Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100191, China)

A constraint satisfaction model and a discrete differential evolution combined with variable neighborhood search (DDE-VNS) are proposed in this paper for an agile satellite task scheduling considering the influence of the observation time on the imaging quality. Firstly, the temporal constraint of the agile satellite task scheduling is described. Secondly, considering the influence of the observation time on the imaging quality, the constraint of the attitude transition between tasks, and onboard storage and energy, the constraint satisfaction model of the agile satellite task scheduling is established. Thirdly, the mutation, crossover and selection operators of the discrete differential evolution are designed, the variable neighborhood search is adopted to exploit better solution from the optimal solution at each iteration, and also the workflow of the proposed algorithm is described. Simulations have demonstrated that the model and algorithm proposed can get schedule plans with cracking reward and quick converge.

Agile satellite; Task scheduling; Discrete differential evolution; Variable neighborhood search

2016-11-21;

2017-04-25

V19

A

1000-1328(2017)06-0590-08

10.3873/j.issn.1000-1328.2017.06.005

李志亮(1988-)，男，博士生，主要從事航天任務分析與設計研究。