朱政霖 馬廣彬 黃鵬 林友明

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

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

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

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

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

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

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

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

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

(1)

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

(2)

(3)

式中：Mj為軌道圈次Cj內(nèi)最大側(cè)擺次數(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內(nèi)衛(wèi)星遙感器對點目標(biāo)Ri成像結(jié)束時間；Tws,(i+1)j為軌道圈次Cj內(nèi)對點目標(biāo)Ri+1成像開始時間；Ttrans(i,i+1)為Twe,ij和Tws,(i+1)j的時間間隔，也就是衛(wèi)星遙感器的側(cè)擺轉(zhuǎn)換時間，見式(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內(nèi)衛(wèi)星遙感器的關(guān)閉時間、開啟時間和穩(wěn)定時間；|θ(i+1)j-θij|/Vsr,j為衛(wèi)星遙感器的側(cè)擺角度改變時間，其中，θ為側(cè)擺角，Vsr,j為衛(wèi)星遙感器的側(cè)擺轉(zhuǎn)換速率。

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

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

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

1.1 成像點目標(biāo)分配

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

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

1.2 單軌道圈次調(diào)度

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

(6)

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

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

(7)

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

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

(8)

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

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

(9)

1≤h1

(10)

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

(11)

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

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

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

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

(12)

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

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

2 測試結(jié)果與分析

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

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

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

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

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

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

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

3 結(jié)束語

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

參考文獻(References)

[1] 陳克偉，安蓓，王炎娟，等.基于PDDL的成像衛(wèi)星任務(wù)規(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] 賀川，孟憲貴，祝轉(zhuǎn)民，等.基于執(zhí)行時段滑動調(diào)整策略的中繼衛(wèi)星任務(wù)規(guī)劃算法設(shè)計[J].飛行器測控學(xué)報,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].飛行器測控學(xué)報,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ū)域目標(biāo)的遙感衛(wèi)星任務(wù)調(diào)度[J].國防科技大學(xué)學(xué)報,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)合任務(wù)規(guī)劃方法[J].中國空間科學(xué)技術(shù),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] 王建江，朱曉敏，吳朝波，等.面向應(yīng)急條件的多星動態(tài)調(diào)度方法[J].航空學(xué)報,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)星單軌任務(wù)合成觀測問題及其動態(tài)規(guī)劃算法[J].系統(tǒng)工程與電子技術(shù),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] 李艷，孫樂，朱懷忠，等.網(wǎng)樹求解有向無環(huán)圖中具有長度約束的簡單路徑和最長路徑問題[J].計算機學(xué)報，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)合成像任務(wù)規(guī)劃問題研究[D].成都:電子科技大學(xué),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] 李菊芳，白保存，陳英武，等.多星成像調(diào)度問題基于分解的優(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)