基于差分進化算法的衛(wèi)星任務未安排原因分析

孫 龍，李 暉，趙 曼,董理君,吳 杰

(中國地質(zhì)大學(武漢) 計算機學院，湖北 武漢 430074)

基于差分進化算法的衛(wèi)星任務未安排原因分析

孫 龍，李 暉，趙 曼,董理君,吳 杰

(中國地質(zhì)大學(武漢) 計算機學院，湖北 武漢 430074)

在衛(wèi)星任務規(guī)劃過程中，由于衛(wèi)星資源有限、衛(wèi)星約束限制與任務沖突導致衛(wèi)星任務未安排，在實際工程中需要確切地了解其任務未安排的具體原因。針對以上問題，提出了一種基于差分進化算法的衛(wèi)星任務未安排原因分析方法，通過將未安排的任務插入原觀測序列，采用差分進化算法演化接收窗口，并對演化結果進行約束處理及評價，得到其在規(guī)劃過程中未安排的原因。實驗結果表明，該方法能夠準確給出未安排任務的原因，方便用戶對任務進行決策。

差分進化算法；衛(wèi)星任務規(guī)劃；約束處理及評價；衛(wèi)星任務未安排原因

AbstractIn the mission planning process,satellite missions are not scheduled because the satellite resource is limited and the satellite constraints conflict with the mission.It’s required in actual projects to understand exactly the reason for not scheduling the mission.To solve the above problem,an analysis method based on differential evolution algorithm is proposed.By inserting the unscheduled task into the original observation sequences,using the differential evolution algorithm to evolve the receiving window,and performing constraint processing and evaluation of the evolutionary results,the reason why the task is not scheduled is obtained.Experiment results show that this method can precisely give the reasons why a task is not scheduled,making it convenient for users to make decisions on the task.

KeywordsDE algorithm;mission planning;constraint processing and evaluation;reason for not scheduling satellite missions

0 引言

對地觀測衛(wèi)星成像[1]是衛(wèi)星在距離地球一定軌道高度上運行，所載有效載荷根據(jù)需求對地球上特定區(qū)域進行觀測，在飛入地面站上空時，把觀測到的數(shù)據(jù)傳輸?shù)降孛娼邮照?，地面接收站對接收到的?shù)據(jù)進行處理和加工得到用戶所需產(chǎn)品和數(shù)據(jù)。但受限于衛(wèi)星有限的資源，要充分完成各個用戶的成像需求是非常困難的，必然會導致衛(wèi)星任務在規(guī)劃的過程中被調(diào)整甚至被刪除[2]，當衛(wèi)星任務未安排時，有必要明確給出衛(wèi)星任務未安排的原因，方便用戶了解衛(wèi)星規(guī)劃任務是由于哪些約束限制導致任務未安排。

針對衛(wèi)星任務規(guī)劃，目前處理的主流方法是采用群智能優(yōu)化算法[3]來解決多星任務規(guī)劃這類時效性較強的問題[4]，如Pemberton[5]提出了基于動態(tài)規(guī)劃思想的迭代方法，按照某種規(guī)則對成像目標排序分組，將前面分組的調(diào)度結果作為后面分組調(diào)度的約束進行求解。郭浩[6]等針對敏捷衛(wèi)星任務調(diào)度問題，綜合考慮衛(wèi)星工作時長、衛(wèi)星姿態(tài)調(diào)整時間、能量和固存容量等約束條件，提出了一種改進的蟻群算法對衛(wèi)星任務規(guī)劃進行求解。同時，大量研究實驗表明[7]，禁忌搜索算法[8-9]、遺傳算法[10]和模擬退火算法[11]在成像衛(wèi)星對地觀測任務規(guī)劃問題中表現(xiàn)良好，但上述衛(wèi)星規(guī)劃算法，在任務規(guī)劃的過程中，針對衛(wèi)星任務規(guī)劃未給出任務未安排原因，均只有最終的規(guī)劃結果，無法直觀反映衛(wèi)星任務規(guī)劃方案，同時，隨著用戶成像需求的日益增加、衛(wèi)星數(shù)量的增加、不同載荷的成像衛(wèi)星的出現(xiàn)[12]，對于任務未安排原因的需求也將變得越來越明顯。

為補充衛(wèi)星任務規(guī)劃過程中對于未安排任務的處理，增加衛(wèi)星任務規(guī)劃的科學性及可靠性，本文提出了一種針對衛(wèi)星任務未安排原因的分析模型，在保證不改變原有規(guī)劃方案的基礎上，對未安排的任務進行未安排原因分析，對實際工程提供了一系列參考方法，具有指導意義。

1 衛(wèi)星任務未安排原因分析模型

1.1 模型表示

衛(wèi)星任務規(guī)劃是根據(jù)用戶任務需求，在滿足衛(wèi)星資源約束的條件下，盡可能充分利用衛(wèi)星資源，完成用戶提出的任務需求，制定衛(wèi)星任務的觀測和接收計劃[13]。對衛(wèi)星任務未安排原因的分析依賴于衛(wèi)星任務規(guī)劃，區(qū)別在于是針對已知的觀測任務進行規(guī)劃，在任務規(guī)劃的過程中給出具體的衛(wèi)星任務未安排的原因。

因此，衛(wèi)星任務未安排原因的分析實質(zhì)上與衛(wèi)星任務規(guī)劃是同一類問題，即帶約束的組合優(yōu)化問題[14]。

一個帶約束的組合優(yōu)化問題P可以定義為4元組P=，其中V={v1,v2,…vn}是P的所有變量的集合；D={d1,d2,…,dn}是P的值域集合，di表示變量vi的值域；C={c1,c2,…cn}是P中的約束集合，ci是變量集合V中某些變量之間的約束項；Z={z1,z2,…zn}是P的優(yōu)化目標函數(shù)集合。

對于本文中的衛(wèi)星任務未安排原因分析模型，定義如下：

① 變量集合V：是由規(guī)劃預案中的觀測元任務和未安排的元任務、接收元任務組成；

② 值域集合D：對觀測元任務而言，其值域為任務的選擇情況，對接收元任務而言，其值域為衛(wèi)星可選的數(shù)傳方式；

③ 約束集合C：表示衛(wèi)星任務規(guī)劃中所涉及的約束，這些約束包括指令模板沖突和數(shù)傳方式約束等；

④ 優(yōu)化目標集合D：表示衛(wèi)星任務規(guī)劃的優(yōu)化目標，優(yōu)化目標可以是衛(wèi)星完成任務數(shù)最多、觀測時長最長、適應值最高等。

1.2 求解過程

對衛(wèi)星任務規(guī)劃的求解過程而言，由于衛(wèi)星資源的特殊性、地面觀測目標的復雜性和地面接收站的分散性，衛(wèi)星執(zhí)行的成像任務會受到諸多的限制[15]。因此，本文在求解衛(wèi)星任務未安排原因時，采用的處理方式是將未安排的任務逐個插入原預案中，通過預處理、演化接收窗口的方式找到任務未安排的原因。

基于差分進化算法的衛(wèi)星任務未安排原因的基本求解過程可以劃分為3個主要階段，如圖1所示。

圖1 衛(wèi)星任務未安排原因求解模型

第1階段，通過讀取常規(guī)任務規(guī)劃得到的衛(wèi)星任務規(guī)劃預案，包括衛(wèi)星觀測任務預案和衛(wèi)星接收任務預案信息，確定原規(guī)劃預案中觀測任務的選擇情況。

第2階段，主要分為預處理、約束檢驗及任務評價2個操作，最終得到任務未安排原因。下面對第2階段進行的操作進行描述。

(1) 任務預處理

任務預處理操作主要針對未安排的觀測元任務的一些屬性進行過濾，排除一些由于任務側擺角度、接收資源等限制而導致任務未安排的原因，主要有以下幾點：

① 相同需求相同軌道的任務。將觀測預案中安排了的觀測元任務按照相同需求相同軌道對任務進行分類，檢測當前未安排的任務是否和觀測預案中某個安排了的任務是同軌同需求，如果是則說明是由于相同需求相同軌道的任務只能做一個而導致該任務未安排。

② 相同需求相同子需求的非監(jiān)測類任務。檢測方法與①類似，如果待檢測的未安排任務與觀測預案中的元任務是相同需求的非監(jiān)測類任務，則說明是由于相同需求相同子需求的非監(jiān)測類任務只能做一個而導致該任務未安排。

③ 最大側擺角度。檢測該未安排的觀測元任務側擺角是否超出衛(wèi)星的最大側擺角度，如果是則說明是由于側擺角度超出限制而導致該任務未安排。

④ 接收資源。檢測該未安排的觀測元任務后面所有的接收窗口時間，去除原接收預案中使用的接收窗口，得到對于該任務可用的接收窗口，判斷是否能夠回放該任務所需要的接收時長，如果不能則說明是因為接收資源不足導致該任務未安排。

(2) 任務約束檢驗及評價

如果通過預處理未能得到任務未安排的原因，那么可以通過插入該任務找到由于其他約束項而導致任務未安排的原因。常規(guī)任務規(guī)劃在得到了觀測預案和接收預案后，逐個選擇未安排的任務進行插入，得到觀測元任務集(觀測預案中規(guī)劃出的觀測元任務和當前插入的未安排的觀測元任務)，即固定了染色體的觀測部分。染色體接收部分，是將所有的接收窗口進行隨機選擇，采用差分進化算法進行處理。對接收演化后得到的最優(yōu)接收窗口進行選擇，然后對得出的最優(yōu)染色體進行各類約束處理，當遇到不滿足其中某項約束時，終止執(zhí)行，給出任務未安排的具體約束沖突原因。

這些約束沖突包括：單圈次側擺次數(shù)沖突、單圈次工作時間沖突、指令模板沖突、任務關機時間約束沖突和衛(wèi)星固存約束沖突。

第3階段，是根據(jù)第2階段獲取的衛(wèi)星未安排原因，將其寫入觀測預案中，供用戶進行查閱。

2 差分進化算法對模型的應用

差分進化算法[16]是一種基于群體差異的啟發(fā)式搜索算法，是通過模仿生物群體內(nèi)個體間的合作與競爭產(chǎn)生的啟發(fā)式群體智能來指導優(yōu)化搜索的一種算法。

針對衛(wèi)星任務未安排原因分析的模型，本文采用差分進化算法來演化衛(wèi)星任務的接收窗口，在任務規(guī)劃的過程中給出任務未安排的原因。

2.1 編碼設計

衛(wèi)星任務未安排原因分析的求解對象是如何將未安排的觀測元任務在不影響原預案的情況下合理分配接收窗口，使其完成任務規(guī)劃，若不能完成，則給出不能安排的具體原因，故編碼方案采用整數(shù)編碼，一條染色體表示元任務的狀態(tài)，編碼設計如圖2所示。

① 染色體的結構主要由觀測元任務序列和接收元任務序列拼接而成，觀測元任務序列的基因位表示任務的選中狀態(tài)，接收元任務序列的基因位表示衛(wèi)星選擇的數(shù)傳方式。

② 基因位的取值范圍為[0,di)，其中對觀測元任務序列，di取0或1，表示觀測任務的選中狀態(tài)；接收元任務序列，表示衛(wèi)星任務不同數(shù)傳方式對應的序號。染色體初始化時，染色體基因位中觀測部分序列全部置1，設置為全選中狀態(tài)，接收部分序列中的數(shù)值隨機產(chǎn)生。

③ 染色體的長度為觀測任務序列的長度和接收任務序列的長度之和。

圖2 染色體的編碼設計

2.2 應用過程

差分進化算法在分析衛(wèi)星任務未安排原因的過程中主要用于演化接收窗口，得到最優(yōu)的染色體，最終對染色體進行解碼，通過約束處理判斷染色體是否滿足約束，不滿足約束則給出該原因而導致任務未安排。算法演化接收窗口的過程如圖3所示。

在通過差分進化算法得到接收窗口后，對最優(yōu)染色體解碼后的預案進行約束處理及評價，在約束處理及評價過程中，依次對任務進行單個的約束項處理，如先檢測指令模板約束，再檢測單圈次側擺次數(shù)約束等，一旦檢測不通過，則輸出該原因作為待檢測任務的未安排原因。

圖3 差分進化算法演化接收窗口流程

3 實驗及結果分析

3.1 測試數(shù)據(jù)

測試數(shù)據(jù)選自衛(wèi)星任務規(guī)劃的觀測元任務預案，針對同一方案編號，對應的觀測元任務會選擇一定的數(shù)傳方式進行數(shù)傳，若其數(shù)傳模式為空，則表示該任務未安排，此時需要對其未安排原因進行分析，某一預案相關信息如表1所示。

表1 規(guī)劃預案信息

FABHGCYRWBHSCMSGCKSSJGCJSSJ917113899記錄2014-02-1910:45:302014-02-1910:50:30917113913Null2014-02-2113:12:402014-02-2113:18:40917113901記錄2014-02-1912:57:102014-02-1912:58:10917113907實傳2014-02-1915:37:432014-02-1915:43:37917113903記錄2014-02-2001:26:002014-02-2001:31:00917113908記錄2014-02-2011:09:342014-02-2011:18:34917113910實傳2014-02-2014:26:002014-02-2014:33:00917113904記錄2014-02-2016:15:202014-02-2016:18:50917113912記錄2014-02-2111:33:232014-02-2111:42:33917113905實傳2014-02-2114:49:022014-02-2114:57:02917113902Null2014-02-1914:02:002014-02-1914:08:00917113906Null2014-02-2200:36:002014-02-2200:41:00917113909Null2014-02-2012:49:382014-02-2012:55:38917113900記錄2014-02-1902:24:202014-02-1902:30:30

本文所采用的符號含義如下：FABH：方案編號；GCYRWBH：待檢測的元任務編號；SCMS：數(shù)傳方式；GCKSSJ：觀測開始時間；GCJSSJ：觀測結束時間；WAPYY：未安排原因；GCXQBH：觀測需求編號；GDQH：軌道圈號；ZXQBH：子需求編號；XJYQ：相機要求；GCLX：觀測類型。

3.2 算法參數(shù)設置

由于采用差分進化算法演化接收窗口，而差分進化算法對遺傳算子的取值有很大的依賴性，不同的算子演化效果有著明顯的不同。當種群大小設置較大時，算法收斂速度較緩，規(guī)劃效率比較低。迭代次數(shù)的選擇也是需要慎重的，當?shù)螖?shù)過大時會影響規(guī)劃速度，迭代次數(shù)過低會導致不能收斂到全局最優(yōu)。所以，在演化接收窗口算法的參數(shù)選擇上，本文做了大量測試，最終確定相關參數(shù)如下：種群大?。?00個個體；迭代代數(shù)：50代；變異概率：0.8；拉伸因子：0.7。

3.3 實驗結果與分析

為了對各種任務未安排原因均進行測試，本文進行了大量的實例測試，將其分為2個測試實例集，分別為預處理未安排原因測試集、約束處理及評價未安排原因測試集。

3.3.1 測試用例1

未安排任務通過預處理操作找到的部分任務未安排原因如表2所示。

表2 觀測任務規(guī)劃預案

FABHGCYRWBHWAPYY90715071相同需求、相同軌道、相同載荷的任務只能做一個,與編號為15074的觀測元任務沖突!110216587相同需、相同軌道、相同載荷的任務只能做一個,與編號為16658的觀測元任務沖突!910544101相同需求、相同軌道、相同載荷的任務只能做一個,與編號為44102的觀測元任務沖突!910444103相同需求、相同軌道、相同載荷的任務只能做一個,與編號為44104的觀測元任務沖突!923044106相同需求、相同子需求、非調(diào)查類點目標的任務只能做一個,與編號為44105的沖突!924344107相同需求、相同子需求、非調(diào)查類點目標的任務只能做一個,與編號為44110的沖突!

從表2中可以得到部分任務未安排的原因，為了驗證結果的正確性，部分觀測任務以及與之沖突的觀測任務信息如表3和表4所示。

表3 待檢測任務與原預案中任務

GCYRWBHGCXQBHGDQHZXQBHXJYQ15071338745421A相機15074338745421A相機165873361,336247221,1A相機166583361,336247221,1A相機4410136036401B相機4410236036401B相機4410336036381B相機4410436036381B相機4410636036401B相機4410536036401B相機

表4 待檢測任務與原預案中任務

GCYRWBHGCXQBHZXQBHGCLX4410636031其他4410536031其他4410736031定標4411036031定標

表3和表4可以看出，未安排的任務與觀測預案中規(guī)劃的觀測任務的需求編號、子需求編號和觀測類型發(fā)生沖突，可以驗證給出的未安排原因的正確性。

通過預處理的方式可以將不參與規(guī)劃的約束項導致任務未安排原因排查出來，這種方式具有十分高效的特點。

3.3.2 測試用例2

在預處理排查部分衛(wèi)星任務未安排原因時，只是針對觀測元任務自身的屬性進行初步過濾，并未真正采用差分進化算法進行規(guī)劃求解。當預處理操作無法得出任務未安排原因時，需要采用約束處理及評價的方式找到任務未安排的原因。

約束處理及評價處理排查任務未安排原因的部分規(guī)劃數(shù)據(jù)如表5所示。

表5 約束處理及評價排查任務未安排原因測試數(shù)據(jù)

FABHGCYRWBHGCKSSJGCJSSJWAPYY8908440602015-04-1705:33:002015-04-1705:33:30關機時間沖突!6420352402014-09-3009:54:542014-09-3010:05:00常規(guī)任務數(shù)傳調(diào)整沖突1269179622014-03-2010:57:022014-03-2011:06:02常規(guī)任務指令模板沖突9234440602015-04-1705:33:002015-04-1705:33:30觀測時間沖突9229160072014-03-0519:37:002014-03-0519:39:00數(shù)傳模式不滿足約束!9067440762015-04-1513:05:002015-04-1513:08:00單圈次側擺次數(shù)超出限制!1074161512014-03-1011:48:162014-03-1011:58:50固存溢出或無回放窗口9119440792015-04-1512:00:002015-04-1512:05:05單圈次工作時間超出限制!8943440752015-04-1513:05:002015-04-1513:05:30接收窗口不足!

以表5中規(guī)劃預案9119中觀測元任務編號為44079的觀測元任務分析為例，參與規(guī)劃的任務有18個，規(guī)劃結果中，安排了10個，其中編號為44079的觀測元任務被刪除。

被刪除的原因分析如下：對比編號為44079號的任務，其觀測開始于2015-04-15 12:00:00，其觀測時長有305 s，查看其接收計劃，在其之前有接收計劃，開始于2015-04-15 11:30:00，接收時長有480 s，二者相距時間不到1 h，在一個圈次內(nèi)，如2個同時安排，單圈工作時間約束條件限制必然使得此接收提前結束，進而引起在編號為44079的觀測任務之前的數(shù)傳任務沒有完整的下傳，從而導致固存無法在前一個任務接收完后進行清空固存操作，固存一直被占用而接近耗盡，最終導致編號為44079號的任務因沒有充足的固存而無法進行觀測，因此編號44079的任務必須刪除。

3.4 實驗結論

通過對比分析實驗結果，得出以下結論：

① 基于差分進化算法的衛(wèi)星任務規(guī)劃分析模型能有效排查在任務規(guī)劃過程中某些任務的未安排原因，且測試過程中對任務未安排的原因分析的結果與預期分析一致；

② 在進行約束處理及任務評價排查任務未安排原因時，需要借助差分進化算法演化接收窗口，采用這種方式能保證在擁有足夠的接收窗口供觀測元任務使用時，最大化完成任務數(shù)，即不改變原始預案的結果，同時能分析出任務未安排的原因。

4 結束語

本文根據(jù)實際工程需要，提出了一種基于差分進化算法的衛(wèi)星任務未安排原因分析模型，并設計了實驗數(shù)據(jù)進行了測試。測試結果表明，本文提出的基于差分進化算法的衛(wèi)星任務未安排原因分析模型能有效地求解衛(wèi)星規(guī)劃過程中關于某些任務未安排問題。本文展示了部分測試數(shù)據(jù)規(guī)劃出來的任務未安排原因，通過對其未安排原因分析，驗證了本文提出模型和處理方法的有效性及正確性。因而在實際工程應用中，這種基于差分進化算法的衛(wèi)星任務未安排原因分析模型具有一定的應用價值。

本文對模型的構建比較簡單，模型考慮的約束項僅僅列出了個別項，同時，給出的任務未安排原因沒有特別詳盡具體，在后續(xù)的研究中，還需要擴充模型，針對不同的衛(wèi)星添加不同的約束項，使其具有通用性，給出更為詳盡具體的任務未安排原因。

[1] 顧中舜,陳英武.對地觀測衛(wèi)星任務規(guī)劃問題研究[J].飛行器測控學報,2007,26(6)：7-13.

[2] 賀仁杰,高鵬,白保存,等.成像衛(wèi)星任務規(guī)劃模型,算法及其應用[J].系統(tǒng)工程理論與實踐,2011,31(3)：411-422.

[3] HABET D,VASQUEZ M.Solving the Selecting and Scheduling Satellite Photographs Problem with a Consistent Neighborhood Heuristic[C]∥IEEE International Conference on Tools with Artificial Intelligence,IEEE,2004:302-309.

[4] 韓偉,張學慶.一種基于離散粒子群的多星任務規(guī)劃算法[J].無線電工程,2015,45(1):1-4.

[5] PEMBERTON J C,GREENWALD L G.On the Need for Dynamic Scheduling of Imaging Satellites[J].International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences,2002,34(1)：165-171.

[6] 郭浩,邱滌珊,伍國華,等.基于改進蟻群算法的敏捷成像衛(wèi)星任務調(diào)度方法[J].系統(tǒng)工程理論實踐,2012,32(11)：2533-2539.

[7] LEMA TRE M,VERFAILLIE G,JOUHAUD F,et al.Selecting and Scheduling Observations of Agile Satellites[J].Aerospace Science & Technology,2002,6(5):367-381.

[8] LIN W C,LIAO D Y.A Tabu Search Algorithm for Satellite Imaging Scheduling[J].Systems,Man and Cybernetics,2004 IEEE International Conference on IEEE,2004(2)：1601-1606.

[9] CORDEAU J F,LAPORTE G.Maximizing the Value of an Earth Observation Satellite Orbit[J].Journal of the Operational Research Society,2005,56(8):962-968.

[10] WOLFE W J,SORENSEN S E.Three Scheduling Algorithms Applied to the Earth Observing Systems Domain[J].Management Science,2000,46(1):148-166.

[11] 徐歡,祝江漢,王慧林.基于模擬退火算法的電子偵察衛(wèi)星任務規(guī)劃問題研究[J].裝備指揮技術學院學報,2010,21(3)：62-66.

[12] 韓瓊.多星聯(lián)合成像任務規(guī)劃技術研究[D].北京:中國科學院大學,2013.

[13] 姜維,郝會成,李一軍.對地觀測衛(wèi)星任務規(guī)劃問題研究述評[J].系統(tǒng)工程與電子技術,2013,35(9)：1878-1885.

[14] 姜維,龐秀麗,郝會成.成像衛(wèi)星協(xié)同任務規(guī)劃模型與算法[J].系統(tǒng)工程與電子技術,2013,35(10)：2093-2101.

[15] 王軍民,王鵬,李菊芳.成像衛(wèi)星魯棒性調(diào)度策略研究[J].系統(tǒng)工程與電子技術,2010,32(1):109-114.

[16] 劉波,王凌,金以慧.差分進化算法研究進展[J].控制與決策,2007,22(7)：721-729.

ResearchonDifferentialEvolutionAlgorithmforAnalysisofReasonforNotSchedulingSatelliteMissions

SUN Long,LI Hui,ZHAO Man,DONG Li-jun,WU Jie

(SchoolofComputerScience,ChinaUniversityofGeosciences,WuhanHubei430074,China)

TP302.1

A

1003-3106(2017)11-0067-06

孫龍男，(1990—)，碩士研究生。主要研究方向：智能計算與智能信息處理。

10.3969/j.issn.1003-3106.2017.11.15

孫龍,李暉,趙曼,等.基于差分進化算法的衛(wèi)星任務未安排原因分析[J].無線電工程,2017,47(11):67-72.[SUN Long,LI Hui,ZHAO Man,et al.Research on Differential Evolution Algorithm for Analysis of Reason for Not Scheduling Satellite Missions[J].Radio Engineering,2017,47(11):67-72.]

2017-01-10

湖北省自然科學基金資助項目(2016CFB278)。

李暉女，(1967—)，教授，碩士生導師。主要研究方向：智能計算與智能信息處理。