基于任務分解的多星成像規(guī)劃模型建立與求解

朱政霖 馬廣彬 黃鵬 林友明

(1 中國科學院遙感與數(shù)字地球研究所，北京 100094) (2 中國科學院大學，北京 100049)

多星成像規(guī)劃是指在使用多顆成像衛(wèi)星的前提下，考慮衛(wèi)星性能指標、星上遙感器成像能力等因素的影響，合理安排衛(wèi)星，制定成像方案，發(fā)送衛(wèi)星指令，在一定的成像時間內盡可能多地對地面目標區(qū)域成像[1-2]。多星成像規(guī)劃能對衛(wèi)星資源進行合理分配，更好地利用遙感器，對優(yōu)化衛(wèi)星系統(tǒng)整體性能、發(fā)揮最大綜合效益具有重要意義[3-4]。多星成像規(guī)劃問題是一類大規(guī)模組合優(yōu)化問題，常規(guī)求解算法通常無法在較短的時間內得出較優(yōu)的解。這是因為：衛(wèi)星在一定時間內經過目標區(qū)域上空的次數(shù)有限，而只有經過目標區(qū)域上空時才能對其成像。同時，對于星下點軌跡周圍的目標區(qū)域，要通過側擺的方式成像[5]，這就需要有足夠的時間調整側擺姿態(tài)，因此在進行成像規(guī)劃時應考慮有充足的側擺轉換時間。而且，多顆衛(wèi)星對同一組目標區(qū)域成像，各個目標區(qū)域會有多個可供選擇的時間窗，每個目標區(qū)域可在多個時間窗內成像，大大增加了成像規(guī)劃的復雜度[6-7]。另外，不同衛(wèi)星的性能指標存在差異，建立統(tǒng)一的模型描述不同的性能指標較為困難。

對于多星成像規(guī)劃，國內外已有大量研究[8-9]，通常包括規(guī)劃模型的建立和求解兩部分。目前，衛(wèi)星的性能指標基本包括星上存儲容量、電能、遙感器開關機時間、側擺轉換時間等，因此，基于性能指標建立的模型基本一致，但求解算法不同。常見的求解算法包括：①基于先驗信息對各個任務節(jié)點進行評價的算法。其中，較為典型的是文獻[10]中提出的基于貪心算法的調度方案：首先對所有待成像目標區(qū)域，根據其權值、與其他任務的沖突程度、占用時間窗的長短等因素進行評價，優(yōu)先安排評價值較高的目標區(qū)域。此類算法根據先驗信息對任務進行調度，但利用先驗信息作為任務分配的標準易造成規(guī)劃結果與最優(yōu)解的偏離程度較大。②全局搜索算法。首先建立全部約束條件，然后利用現(xiàn)有軟件在整個解空間進行搜索。其中，較為典型的是文獻[11]中提出的嘗試性全局搜索算法，該算法首先建立模型約束，在不考慮約束的情況下對組合問題利用現(xiàn)有的商用求解軟件CPLEX進行求解，如果得到的解不滿足某一約束，就在模型中添加當前解不滿足的約束，重新求解，直至得到的解滿足所有約束條件。此類算法從整個解空間搜索最優(yōu)解，得到的解質量較高，但搜索空間過大，耗時過長。

基于以上，本文提出一種任務分解的思路，將成像規(guī)劃過程分為兩部分，首先通過免疫算法把成像點目標分配給衛(wèi)星，然后針對每顆衛(wèi)星分配到的成像點目標進行規(guī)劃求解，并把當前分配方案能夠成像的點目標權值總和作為反饋信息傳遞給免疫算法，根據反饋信息調整當前分配方案，使調整后的分配方案能夠拍攝到的成像點目標權值總和增大，提高免疫算法分配成像點目標方案的合理程度。該算法采取反饋的思路處理成像點目標分配與單顆衛(wèi)星調度的關系，避免根據先驗信息分配成像點目標造成的分配方案不合理，同時將求解算法分為成像點目標分配和單軌道圈次調度兩部分，能夠減小解的搜索空間，降低算法的時間復雜度。

1 多星成像規(guī)劃模型

本文研究的多星成像規(guī)劃問題可簡述為：有一系列光學衛(wèi)星和雷達衛(wèi)星，面對大量不同權值的成像點目標(指范圍較小的目標，可被遙感器單次覆蓋)，每個成像點目標有多個時間窗，如何在滿足側擺轉換時間、最大側擺次數(shù)的前提下，為每顆衛(wèi)星合理分配成像點目標，并確定衛(wèi)星每個軌道圈次的動作序列，使得成像點目標的權值總和最大。對于多星成像規(guī)劃，需要考慮的限制因素較多。本文對相關限制因素進行歸納總結，重點考慮衛(wèi)星側擺次數(shù)約束、側擺轉換時間約束、電能約束和星上存儲容量約束，并以此建立成像規(guī)劃模型。

在以往的多星成像規(guī)劃研究中，通常以單顆衛(wèi)星作為調度單位，且認為每個成像點目標在調度時間內只能被該衛(wèi)星觀測一次[12]。但隨著調度時間的增長，同一顆衛(wèi)星將會多次經過成像點目標的上方，這將造成每個成像點目標在整個調度時間內有多個時間窗，對模型的建立與求解造成困難。為此，本文以衛(wèi)星的每個軌道圈次為調度單位，確保每個成像點目標在單個調度單位里只有一個時間窗。此外，衛(wèi)星的電能來源是太陽電池陣，在每個軌道圈次內獲得的電能是一定的；與地面站數(shù)據傳輸時，能夠方便計算出每個軌道圈次的存儲容量。因此，以每個軌道圈次為調度單位，能夠方便建立電能和存儲容量約束。

衛(wèi)星通過側擺的方式成像，由于側擺會對其穩(wěn)定性造成影響[13]，因此衛(wèi)星在每個軌道圈次內的側擺次數(shù)不得超過側擺次數(shù)的最大值。此外，衛(wèi)星執(zhí)行成像任務需要的電量隨成像時間的增長而增多，點目標成像時間較短，成像消耗的電能較少，而衛(wèi)星每個軌道圈次只能獲取一定的電量，通過限制衛(wèi)星的單軌道圈次側擺次數(shù)，能夠同時滿足電能約束。另外，衛(wèi)星只會在成像時增加星上存儲容量的占用，占用的存儲容量隨成像時間的增長而增加，而點目標成像時間較短，因此占用的存儲容量較少，不會出現(xiàn)存儲容量不足的問題。

對于成像點目標集合{R1,R2,R3,…}和軌道圈次集合{C1,C2,C3,…}，本文建立多星成像規(guī)劃模型如下。

(1)

式中：xij為決策變量，xij=1表示在軌道圈次Cj對點目標Ri成像；Wi為成像點目標Ri的權值；NR為成像點目標總數(shù)；NC為軌道圈次總數(shù)；i=1,2,3,…,NR；j=1,2,3,…,NC。

(2)

(3)

式中：Mj為軌道圈次Cj內最大側擺次數(shù)。

Twe,ij+Ttrans(i,i+1)≤Tws,(i+1)j

xij=1,x(i+1)j=1,Twe,ij≤Tws,(i+1)j

(4)

式中：Twe,ij為軌道圈次Cj內衛(wèi)星遙感器對點目標Ri成像結束時間；Tws,(i+1)j為軌道圈次Cj內對點目標Ri+1成像開始時間；Ttrans(i,i+1)為Twe,ij和Tws,(i+1)j的時間間隔，也就是衛(wèi)星遙感器的側擺轉換時間，見式(5)。

Ttrans(i,i+1)=Tsc,j+Tso,j+

|θ(i+1)j-θij|/Vsr,j+Tss,j

(5)

式中：Tsc,j，Tso,j，Tss,j為軌道圈次Cj內衛(wèi)星遙感器的關閉時間、開啟時間和穩(wěn)定時間；|θ(i+1)j-θij|/Vsr,j為衛(wèi)星遙感器的側擺角度改變時間，其中，θ為側擺角，Vsr,j為衛(wèi)星遙感器的側擺轉換速率。

式(1)是優(yōu)化目標，多星成像規(guī)劃問題的目標是選擇適當?shù)臎Q策變量，使得成像點目標權值總和最大。式(2)是任務排它性約束，即每個成像點目標只能被分配到一個特定軌道圈次內或者不被分配。式(3)代表側擺次數(shù)約束，衛(wèi)星遙感器通過側擺的方式成像，在成像點目標較為稀疏的情況下，每次側擺只能對一個點目標成像。式(4)是側擺轉換時間約束，對于分配到同一軌道圈次的成像點目標，對一個點目標成像的結束時間與對下一個點目標成像的開始時間的時間間隔，必須不小于側擺轉換時間。式(5)是側擺轉換時間的表達式，轉換時間等于同一軌道圈次內衛(wèi)星遙感器的關閉時間、開啟時間、側擺角度改變時間和穩(wěn)定時間的總和。

求解本文建立的多星成像規(guī)劃模型的難點在于：該模型是一個組合優(yōu)化模型，約束較為復雜，直接求解較為困難，且隨著任務規(guī)模的增大，求解的組合數(shù)將呈指數(shù)式增加。為解決這一問題，本文將求解分為兩部分：①成像點目標分配。將成像點目標按照一定的規(guī)則分配給不同的軌道圈次；②單軌道圈次調度。針對每個軌道圈次分配的成像點目標，在滿足最大側擺次數(shù)約束、轉換時間約束的前提下，計算出所有軌道圈次能夠成像的點目標權值總和。這樣就可以對組合優(yōu)化模型進行分解，以減小求解的搜索空間。不過，這種求解算法存在耦合問題，即成像點目標分配和單軌道圈次調度具有耦合性，采用不同的成像點目標分配方案將影響單軌道圈次調度的結果。因此，將成像點目標分配和單軌道圈次調度作為各自獨立的過程，將導致與最優(yōu)解的偏離程度過大，任務調度的效果難以保證。為此，本文綜合考慮成像點目標分配和單軌道圈次調度，提出求解算法，如圖1所示。

本文首先將成像點目標分配給各軌道圈次，然后將各軌道圈次分配到的成像點目標通過單軌道圈次調度，計算出各軌道圈次可成像點目標權值的總和，將總和作為反饋信息，傳遞給成像點目標分配，根據反饋信息調整分配方案，使所有可成像點目標的權值總和隨著迭代次數(shù)的增加而增大。

1.1 成像點目標分配

免疫算法是根據生物免疫系統(tǒng)原理提出的一種新的智能優(yōu)化算法，它是一種啟發(fā)式搜索算法，與全局搜索算法相比，效率較高[14-15]。免疫算法把確定性和隨機性相結合，將目標函數(shù)作為免疫反應中的抗原，可行解作為免疫反應中的抗體，可行解的質量對應抗原與抗體的親和度，將目標優(yōu)化問題轉換為求解最佳抗體的問題。該算法具有全局搜索能力強、多樣性保持良好和魯棒性強等優(yōu)點[16]。采用免疫算法求解成像點目標分配問題，能夠對較大的解空間進行智能搜索，使搜索方向快速向最優(yōu)解靠近；同時，能夠避免搜索進入局部最優(yōu)解區(qū)域，最終能得出盡可能優(yōu)的組合方案。免疫算法求解成像點目標分配問題的流程如圖2所示。

在免疫算法求解成像點目標分配問題中，構造抗體時，針對成像點目標Ri，如果在某一軌道圈次有時間窗，則Ri可分配至該軌道圈次，Ri可分配至的軌道圈次構成集合{Cj|?[Tws,ij,Twe,ij]}。構造抗體時，針對Ri，從軌道圈次集合中隨機選取軌道圈次Si={Cj|?[Tws,ij,Twe,ij]}，所有成像點目標選取的軌道圈次集合Ω={S1,S2,…,SNT}構成初始抗體。例如，抗體{4,6,3}表示R1分配至軌道圈次4，R2分配至軌道圈次6，R3分配至軌道圈次3。多個初始抗體構成初始抗體種群{Ω1,Ω2,…,ΩNΩ}，NΩ表示抗體種群的抗體個數(shù)。每個抗體對應一種成像點目標分配方案，抗體種群對應所有分配方案。特定抗體激勵度與成像點目標分配方案在所有分配方案中的重復程度呈反比，與成像點目標分配方案的評價值呈正比。因此，合理且不重復的分配方案激勵度較高，取激勵度前NP/2個抗體，能保留較優(yōu)的分配方案，同時淘汰較差的分配方案。經過多次迭代后，可使分配方案的合理程度越來越高。

1.2 單軌道圈次調度

經過第1.1節(jié)的成像點目標分配，所有成像點目標均被分配到特定的軌道圈次中。本節(jié)要解決的問題是，針對某一軌道圈次的所有成像點目標，如何安排衛(wèi)星成像，使成像點目標的權值總和最大。另外，在免疫算法中，每輪迭代都要進行所有軌道圈次的調度運算，因此，對單軌道圈次調度的耗時具有較高的要求，需要在較短的時間內完成。為滿足各種約束，本文采用圖論模型求解。用圖的節(jié)點表示被分配的成像點目標，用圖的有向線段表示各個點目標成像之間的衛(wèi)星遙感器側擺轉換時間約束，邊的權值表示成像點目標的權值，側擺次數(shù)的約束用路徑包含的最多節(jié)點數(shù)表示，最終將求解成像點目標權值總和最大的問題，轉換為節(jié)點總數(shù)不超過特定值時圖的最長路徑問題。轉換方式為：將所有被分配至該軌道圈次的成像點目標{Ri}(分配至某軌道圈次的成像點目標集合，下同),按照成像開始時間的先后順序排序，并用圖的節(jié)點vi依次表示各個成像點目標，形成成像點目標節(jié)點序列{v1,v2,v3,…,vN}(N=|{Ri}|)；在節(jié)點序列的首尾依次添加2個虛節(jié)點v0，vN+1，表示開始節(jié)點和結束節(jié)點。存在vi指向vj的有向邊的條件為

(6)

式中：E(i,j)為1，表示vi和vj之間存在有向邊，此時應滿足的條件是節(jié)點i結束時間與節(jié)點j開始時間的時間間隔大于衛(wèi)星遙感器的側擺轉換時間，轉換時間見式(5)。

另外，對于開始節(jié)點v0，存在該節(jié)點指向所有成像點目標節(jié)點的有向邊，表示成像任務可以從任何一個成像點目標節(jié)點處開始；對于結束節(jié)點vN+1，存在所有成像點目標節(jié)點指向該節(jié)點的有向邊，表示成像任務可以在任何一個成像點目標節(jié)點成像后終止。有向邊權值的計算方法如下。

(7)

每個邊的權值表示該有向邊所指向的成像點目標節(jié)點的權值，結束節(jié)點的權值為0。

基于以上，建立單軌道圈次調度問題的約束優(yōu)化模型為

(8)

式中：h1,h2,h3,…,hNh為求解的成像點目標節(jié)點序列；Nh為成像點目標節(jié)點序列中的成像點目標節(jié)點總數(shù)。

s.t.Nh≤MjNh=|{hi}|

(9)

1≤h1

(10)

E(h1,hi+1)=1i∈{1,2,3,…,Nh-1}

(11)

式(8)為目標函數(shù)，表示成像點目標節(jié)點序列的權值總和最大。式(9)表示成像點目標節(jié)點序列中的成像點目標節(jié)點個數(shù)不超過最大側擺次數(shù)。式(10)表示成像點目標節(jié)點序列是被分配至該軌道圈次所有成像點目標節(jié)點的一個有序子集。式(11)表示成像點目標節(jié)點序列中相鄰2個成像點目標節(jié)點存在有向邊相連。

通過以上轉換，將單軌道圈次調度問題轉化為一個有向無環(huán)圖的最長路徑問題。對有向無環(huán)圖最長路徑的求解，當前已有大量的成熟算法。但是，本文研究的難點在于求解帶有約束條件的有向無環(huán)圖的最長路徑問題。為此，引入網樹算法[17-18]，并對該算法進行改進，提出一種以路徑節(jié)點數(shù)為約束條件的有向無環(huán)圖最長路徑求解算法。算法的基本思路為：利用動態(tài)規(guī)劃算法的思路，針對每個節(jié)點總數(shù)，依次計算以有向圖的每個節(jié)點為最后一個成像點目標節(jié)點的最長路徑，計算公式如下。

Pm,k=We(i,k)+max{Pm-1,k}

i∈{1,2,…,k-1},E(i,k)=1

(12)

式中：Pm,k為最后一個成像點目標節(jié)點為k、成像點目標節(jié)點總數(shù)為m的所有路徑中最長路徑的權值。

最長路徑求解算法流程如圖3所示。設成像點目標節(jié)點總數(shù)為1，依次計算成像點目標節(jié)點總數(shù)為1的所有路徑的最大權值，當成像點目標節(jié)點總數(shù)小于最大側擺次數(shù)時，將成像點目標節(jié)點總數(shù)加1；重復上述過程，直至成像點目標節(jié)點總數(shù)等于最大側擺次數(shù)，此時，以每個成像點目標節(jié)點為最后一個成像點目標節(jié)點的所有路徑的最大權值max{Pm,i} (i∈{1,2,…,Nh})，就是衛(wèi)星單軌道圈次內最大可成像點目標權值總和。

2 測試結果與分析

在多星成像規(guī)劃領域，至今尚無公開的標準測試集[19]。本文隨機生成一組測試數(shù)據對本文算法進行測試。在我國所在的經緯度范圍內隨機依次抽取100，200，300，400個成像點目標，各個成像點目標的權值從[1,9]中均勻選取，成像點目標的權值表示其重要程度，性能較優(yōu)的算法能夠使成像點目標的權值總和盡可能大。選取5顆光學衛(wèi)星作為測試衛(wèi)星，規(guī)劃的時間周期為24 h，衛(wèi)星與成像點目標的時間窗采用STK軟件計算獲取。每個成像點目標的成像持續(xù)時間約為5 s。

為驗證本文算法的性能，將計算結果與文獻[11]中的全局搜索算法、文獻[20]中蟻群-禁忌搜索算法作比較。3種算法均以上文所述測試數(shù)據集為測試對象，測試硬件均采用Intel Xeon CPU E31225，16GB RAM平臺。文獻[11]中提出的全局搜索算法采用整數(shù)規(guī)劃模型直接求解，采用暴力求解的方式在整個解空間內搜索全局最優(yōu)解。文獻[20]中采用的蟻群-禁忌搜索算法，通過成像點目標分配和單顆衛(wèi)星調度相互迭代求解，與本文算法類似。蟻群-禁忌搜索算法和本文算法的參數(shù)取值如表1所示，全局搜索算法采用暴力算法對模型直接求解，不涉及參數(shù)取值的問題。測試時，每組測試數(shù)據用3種算法測試多次，結果取平均值，以減小隨機誤差，如表2所示。圖4(a)是4顆衛(wèi)星時3種算法求解耗時與成像點目標數(shù)的關系，圖4(b)是4顆衛(wèi)星時3種算法獲得的成像點目標權值總和與成像點目標數(shù)的關系。

表1 蟻群-禁忌搜索算法和本文算法參數(shù)取值Table 1 Parameters of ant colony-tabu searchalgorithm and the algorithm proposed in this paper

表2 3種算法仿真測試結果對比Table 2 Contrast of 3 algorithm simulation test results

根據表2和圖4，對比本文算法與蟻群-禁忌搜索算法的結果可知：當成像點目標數(shù)較小(約為100個)時，蟻群-禁忌搜索算法的耗時與本文算法相當，平均約為12 s，成像點目標權值總和基本一致。當成像點目標數(shù)大于等于200時，蟻群-禁忌搜索算法的耗時為本文算法的1.5～3.0倍。隨著成像點目標數(shù)越來越多，蟻群-禁忌搜索算法的耗時將大幅增加，本文算法的時間優(yōu)勢更為明顯。從權值上看，本文算法有6個權值大于蟻群-禁忌搜索算法，3個小于蟻群-禁忌搜索算法，說明本文算法得到的權值總和略優(yōu)于蟻群-禁忌搜索算法。

全局搜索算法要對整個解空間進行遍歷求解，能夠遍歷所有可行解，因此得出的解對應的成像點目標權值總和較高；但其缺點是耗時較多，當成像點目標數(shù)較多時，采用該算法不能在可接受的時間范圍內得出結果。從成像點目標的權值總和來看，全局搜索算法略優(yōu)于本文算法；但從時間上看，本文算法的耗時只是全局搜索算法的10%～30%。圖4(a)中的曲線顯示，全局搜索算法的耗時隨著成像點目標數(shù)的增加呈指數(shù)式增長，極大限制了它的實際應用。

以上分析表明：與蟻群-禁忌搜索算法相比，本文算法的求解耗時明顯較短，且成像點目標權值總和略高；全局搜索算法雖然能得出成像點目標權值總和較高的規(guī)劃方案，但存在耗時過長的問題，本文算法在耗時方面具有較大的優(yōu)勢，且耗時并不會隨問題規(guī)模的增大而顯著增加。因此，本文算法能在較短的時間內求解模型，且得出較優(yōu)的解。本文模型適用性較強，能夠成功解決多星成像規(guī)劃問題。

3 結束語

本文對多星成像規(guī)劃問題進行研究，根據衛(wèi)星成像的實際情況，建立成像規(guī)劃模型，將求解分為成像點目標分配和單軌道圈次調度兩部分，減小搜索空間，在逐次迭代的過程中，將單軌道圈次調度結果作為反饋信息，不斷調整成像點目標分配方案，使規(guī)劃結果盡可能接近全局最優(yōu)解。成像點目標分配采用免疫算法，有較強的全局搜索能力，能夠很好地保持解的多樣性，避免搜索進入局部最優(yōu)解。單軌道圈次調度采用圖的最長路徑算法，能夠在考慮側擺次數(shù)約束的情況下輸出該軌道圈次所能成像點目標的最大權值，且具有較低的時間復雜度。測試結果表明：本文模型能夠得出相對較優(yōu)的規(guī)劃結果，且效率較高。尤其在問題規(guī)模較大的情況下，本文提出的模型求解算法效率優(yōu)勢更加明顯。

參考文獻(References)

[1] 陳克偉，安蓓，王炎娟，等.基于PDDL的成像衛(wèi)星任務規(guī)劃建模[J].兵工自動化,2008,27(12):41-44

Chen Kewei, An Bei, Wang Yanjuan, et al. Modeling of mission planning for imaging satellite based on PDDL [J]. Ordnance Industry Automation, 2008, 27(12): 41-44 (in Chinese)

[3] 賀川，孟憲貴，祝轉民，等.基于執(zhí)行時段滑動調整策略的中繼衛(wèi)星任務規(guī)劃算法設計[J].飛行器測控學報,2015,34(3):246-253

He Chuan, Meng Xiangui, Zhu Zhuanmin, et al. Design of mission programming algorithm for TDRS based on execution time slide adjustment strategy [J]. Journal of Spacecraft TT&C Technology, 2015, 34(3): 246-253 (in Chinese)

[4] 張倩，趙硯，徐梅.衛(wèi)星星座的空域覆蓋性能計算模型[J].飛行器測控學報,2011,30(1):6-10

Zhang Qian, Zhao Yan, Xu Mei. Computation model of constellation space coverage performance [J]. Journal of Spacecraft TT&C Technology, 2011, 30(1): 6-10 (in Chinese)

[5] 白保存，賀仁杰，李菊芳，等.面向點及區(qū)域目標的遙感衛(wèi)星任務調度[J].國防科技大學學報,2009,31(2):59-63

Bai Baocun, He Renjie, Li Jufang, et al. Remote sensing satellites observing scheduling toward spot and ploygon targets [J]. Journal of Nation University of Defense Technology, 2009, 31(2): 59-63 (in Chinese)

[6] 王智勇，王永強，王鈞，等.多星聯(lián)合任務規(guī)劃方法[J].中國空間科學技術,2012,32(1):8-14

Wang Zhiyong, Wang Yongqiang, Wang Jun, et al. Multi-satellite task scheduling method [J]. Chinese Space Science and Technology, 2012, 32(1): 8-14 (in Chinese)

[7] Gabrel V, Vanderpooten D. Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite [J]. European Journal of Operational Research, 2002, 139(3): 533-542

[8] 王建江，朱曉敏，吳朝波，等.面向應急條件的多星動態(tài)調度方法[J].航空學報,2013,34(5):1151-1164

Wang Jianjiang, Zhu Xiaomin, Wu Chaobo, et al. Multi-satellite dynamic scheduling method for emergency condition [J]. Acta Aeronautica et Astronautica Sinica, 2013, 34(5): 1151-1164 (in Chinese)

[9] Zhu K J, Li J F, Baoyin H X. Satellite scheduling considering maximum observation coverage time and minimum orbital transfer fuel cost [J]. Acta Astronautica, 2010, 66(1/2): 220-229

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

[11] Wang J J, Demeulemeester E, Qiu D, et al. A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds [J]. Computers & Operations Research, 2016, 74: 1-13

[12] Wang J, Zhu X, Zhu J, et al. Towards dynamic real-time scheduling for multiple earth observation satellites [J]. Journal of Computer & System Sciences, 2015, 81(1): 110-124

[13] 白保存，賀仁杰，李菊芳，等.衛(wèi)星單軌任務合成觀測問題及其動態(tài)規(guī)劃算法[J].系統(tǒng)工程與電子技術,2009,31(7):1738-1742

Bai Baocun, He Renjie, Li Jufang, et al. Satellite orbit task merging problem and its dynamic programming algorithm [J]. Systems Engineering and Electronics, 2009, 31(7): 1738-1742 (in Chinese)

[14] 余建軍，孫樹棟，吳秀麗，等.四種改進免疫算法及其比較[J].系統(tǒng)工程,2006,24(2):106-112

Yu Jianjun, Sun Shudong, Wu Xiuli, et al. Four modified immune algorithm and its compare [J]. Systems Engineering, 2006, 24(2): 106-112 (in Chinese)

[15] Bagheri A, Zandieh M, Mahdavi I, et al. An artificial immune algorithm for the flexible job-shop scheduling problem [J]. Future Generation Computer Systems, 2010, 26(4): 533-541

[16] Yang S, Wang M, Jiao L. Quantum-inspired immune clone algorithm andmultiscale bandelet based image representation [J]. Pattern Recognition Letters, 2010, 31(13): 1894-1902

[17] 李艷，孫樂，朱懷忠，等.網樹求解有向無環(huán)圖中具有長度約束的簡單路徑和最長路徑問題[J].計算機學報，2012，35(10):2193-2203

Li Yan, Sun Le, Zhu Huaizhong, et al. Anettree for simple paths with length constraint and the longest path in directed acyclic graphs [J]. Chinese Journal of Computers， 2012， 35(10): 2193-2203 (in Chinese)

[18] Chia W L, Chen P L, Hsieha S Y, et al. Weight-constrained and density-constrained paths in a tree:enumerating, counting, and k-maximum density paths [J]. Discrete Applied Mathematics, 2015, 180: 126-134

[19] 蔡德榮.基于蟻群算法的多星聯(lián)合成像任務規(guī)劃問題研究[D].成都:電子科技大學,2012

Cai Derong. Multi-satellite imaging task scheduling problem research based on ant algorithm [D]. Chengdu: University of Electronic Science and Technology of China, 2012 (in Chinese)

[20] 李菊芳，白保存，陳英武，等.多星成像調度問題基于分解的優(yōu)化算法[J].系統(tǒng)工程理論與實踐,2009,29(8):134-143

Li Jufang, Bai Baocun, Chen Yingwu, et al. Optimization algorithm based on decomposition for satellites observation scheduling problem [J]. Systems Engineering Theory & Practices, 2009, 29(8): 134-143 (in Chinese)