考慮成像質(zhì)量的敏捷衛(wèi)星任務(wù)調(diào)度模型與算法

李志亮，李小將，孫 偉

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

?

考慮成像質(zhì)量的敏捷衛(wèi)星任務(wù)調(diào)度模型與算法

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

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

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

敏捷衛(wèi)星；任務(wù)調(diào)度；離散差分進(jìn)化；變鄰域搜索

0 引 言

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

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

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

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

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

1 敏捷衛(wèi)星任務(wù)調(diào)度時(shí)間約束描述

姿態(tài)機(jī)動(dòng)能力增加了敏捷衛(wèi)星對地觀測的自由度，同時(shí)，其任務(wù)調(diào)度的時(shí)間約束變得更加復(fù)雜，主要體現(xiàn)在成像、姿態(tài)轉(zhuǎn)換方面。在成像活動(dòng)中，當(dāng)一個(gè)地面目標(biāo)被選定后，其觀測時(shí)間是可見時(shí)間窗口內(nèi)的一個(gè)連續(xù)變量，不同觀測時(shí)間對應(yīng)的觀測姿態(tài)角不同，觀測姿態(tài)角直接影響衛(wèi)星對地面目標(biāo)的成像分辨率，而成像分辨率是成像質(zhì)量好壞的主要評價(jià)指標(biāo)，因此，觀測時(shí)間影響衛(wèi)星對地面目標(biāo)的成像質(zhì)量。此外，在姿態(tài)轉(zhuǎn)換活動(dòng)中，對于相鄰任務(wù)，衛(wèi)星需完成任務(wù)間的姿態(tài)轉(zhuǎn)換，姿態(tài)轉(zhuǎn)換時(shí)間取決于前后任務(wù)的結(jié)束和開始時(shí)間，當(dāng)衛(wèi)星資源有限而成像任務(wù)眾多時(shí)，姿態(tài)轉(zhuǎn)換時(shí)間主要受前一任務(wù)的結(jié)束時(shí)間影響，選擇不同的時(shí)間進(jìn)行姿態(tài)轉(zhuǎn)換，所需轉(zhuǎn)換時(shí)間也不同。

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

2 敏捷衛(wèi)星任務(wù)調(diào)度約束滿足模型

首先定義建立調(diào)度約束滿足模型所需參數(shù)，然后從決策變量、目標(biāo)函數(shù)、約束條件3個(gè)方面描述模型。

2.1 參數(shù)定義

本文模型相關(guān)參數(shù)定義如表1所示。

表1 相關(guān)參數(shù)定義Table 1 Definition of related parameters

2.2 模型描述

針對文獻(xiàn)[1]簡化姿態(tài)轉(zhuǎn)換約束的不足，本文通過計(jì)算不同時(shí)刻下衛(wèi)星對地面目標(biāo)的觀測姿態(tài)角，確定姿態(tài)機(jī)動(dòng)時(shí)間，使任務(wù)間姿態(tài)轉(zhuǎn)換約束更為合理。針對文獻(xiàn)[2-6]的研究均沒有考慮觀測時(shí)間對成像質(zhì)量影響的不足，本文在目標(biāo)函數(shù)中增加成像質(zhì)量評價(jià)函數(shù)，根據(jù)任務(wù)優(yōu)先級和觀測時(shí)間確定目標(biāo)函數(shù)值?？紤]上述改進(jìn)的目標(biāo)函數(shù)和增加的約束條件，多敏捷衛(wèi)星任務(wù)調(diào)度的約束滿足模型描述如下：

1)決策變量

2)目標(biāo)函數(shù)

在以往對敏捷衛(wèi)星任務(wù)調(diào)度的研究中，常見的目標(biāo)函數(shù)是最大化完成任務(wù)的優(yōu)先級之和[2-6]，其描述如下式：

(1)

敏捷衛(wèi)星對地面目標(biāo)的觀測時(shí)間是可見時(shí)間窗口內(nèi)的一個(gè)連續(xù)變量，觀測時(shí)間離可見時(shí)間窗口的中心時(shí)刻越近，對應(yīng)的觀測姿態(tài)角越小，成像質(zhì)量也越好；反之離中心時(shí)刻越遠(yuǎn)，對應(yīng)的觀測姿態(tài)角越大，成像質(zhì)量則越差。在敏捷衛(wèi)星任務(wù)調(diào)度模型中考慮觀測時(shí)間對成像質(zhì)量的影響，通過合理安排任務(wù)的觀測時(shí)間提高成像質(zhì)量，具有一定的現(xiàn)實(shí)意義。

當(dāng)采用P1作為目標(biāo)函數(shù)，且任務(wù)ti被選擇觀測時(shí)，無論任務(wù)ti的觀測時(shí)間處于其可見時(shí)間窗口內(nèi)的哪一時(shí)刻，計(jì)算所得目標(biāo)函數(shù)值均為wi，而實(shí)際上，衛(wèi)星在不同觀測時(shí)間對目標(biāo)的成像質(zhì)量有一定差異。因此，有必要構(gòu)建觀測時(shí)間與成像質(zhì)量之間的函數(shù)關(guān)系式。

(2)

(3)

(4)

(5)

3)約束條件

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

(1)任務(wù)執(zhí)行的唯一性約束

(6)

(7)

(2)任務(wù)執(zhí)行的時(shí)間窗口約束

(8)

(3)相鄰任務(wù)間姿態(tài)轉(zhuǎn)換時(shí)間約束

(9)

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

(10)

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

(11)

上述模型通過引入成像質(zhì)量評價(jià)函數(shù)改進(jìn)目標(biāo)函數(shù)，同時(shí)考慮了任務(wù)間姿態(tài)轉(zhuǎn)換、星上存儲和能量等約束，是較為復(fù)雜的約束滿足模型，本文采用離散差分進(jìn)化與變鄰域搜索相結(jié)合的算法進(jìn)行求解。

3 DDE-VNS求解算法

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

3.1 離散差分進(jìn)化設(shè)計(jì)

1)解的編碼

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

2)初始種群的生成

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

步驟1：通過預(yù)處理獲得每顆衛(wèi)星在可用軌道圈次上的候選任務(wù)，隨機(jī)選擇一個(gè)軌道圈次，計(jì)算該軌道圈次上候選任務(wù)的優(yōu)先級之和Wsum、最早可觀測時(shí)間的最小值Bmin和最早可觀測時(shí)間的最大值Bmax。

步驟2：計(jì)算每個(gè)候選任務(wù)的選擇概率ai，計(jì)算式如下：

(12)

式中：σ是一個(gè)很小的正數(shù)。

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

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

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

3)變異算子

(13)

式中：r1、r2、r3為隨機(jī)選擇的三個(gè)個(gè)體，且r1≠r2≠r3≠i，F(xiàn)為縮放因子。應(yīng)用于敏捷衛(wèi)星任務(wù)調(diào)度問題，“⊕”和“?”運(yùn)算通過下式計(jì)算得到

(14)

式中：rand(·)為(0,1)的隨機(jī)數(shù)，mod(·)為取模運(yùn)算，NT為任務(wù)數(shù)量。

通過上述操作得到變異個(gè)體不一定是合理的任務(wù)序列，但是考慮到變異的作用是對目標(biāo)個(gè)體產(chǎn)生擾動(dòng)，因此可以在交叉算子中設(shè)計(jì)輔助算子得到合理的任務(wù)序列。

4)交叉算子

根據(jù)DDE的機(jī)理[9]，試驗(yàn)個(gè)體由變異個(gè)體和目標(biāo)個(gè)體通過交叉操作產(chǎn)生：

(15)

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

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

經(jīng)過交叉得到試驗(yàn)個(gè)體，一部分來自目標(biāo)個(gè)體，另一部分來自變異個(gè)體，并且通過輔助算子(步驟2～3)確保了試驗(yàn)個(gè)體的合理性。

5)選擇算子

采用一對一貪婪競爭機(jī)制選擇適應(yīng)度值較大的個(gè)體作為子代個(gè)體

(16)

3.2 變鄰域搜索設(shè)計(jì)

在搜索過程中，充分利用問題信息增強(qiáng)離散差分進(jìn)化的局部搜索能力是提高其優(yōu)化性能的有效途徑。鑒于目標(biāo)種群的最優(yōu)個(gè)體往往攜帶有價(jià)值的信息，因此對每次迭代的最優(yōu)個(gè)體進(jìn)行局部搜索，以獲得更好的鄰域解[7]。

為了減小鄰域搜索的范圍，提高搜索效率，本文結(jié)合敏捷衛(wèi)星特點(diǎn)設(shè)計(jì)了三種鄰域結(jié)構(gòu)：插入鄰域、替換鄰域、移位鄰域。插入鄰域是將未選中執(zhí)行的任務(wù)插入到衛(wèi)星的任務(wù)序列中；替換鄰域是指當(dāng)插入鄰域不滿約束條件時(shí)，根據(jù)優(yōu)先級關(guān)系替換任務(wù)序列中已安排的任務(wù)；移位鄰域是指根據(jù)每顆衛(wèi)星的負(fù)載，從負(fù)載最大的衛(wèi)星任務(wù)序列中隨機(jī)選擇一個(gè)任務(wù)，將其插入到負(fù)載最小的衛(wèi)星任務(wù)序列中。衛(wèi)星的負(fù)載通過下式計(jì)算：

變鄰域搜索的步驟如下：

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

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

步驟3：采用移位鄰域?qū)Χ囝w衛(wèi)星的任務(wù)序列進(jìn)行調(diào)整，產(chǎn)生新的鄰域解。

步驟4：評價(jià)新解的適應(yīng)度值，若大于當(dāng)前最優(yōu)解，則用新解替換當(dāng)前最優(yōu)解。

步驟5：判斷當(dāng)前是否滿足終止條件，若滿足最大迭代次數(shù)或最優(yōu)解不變連續(xù)迭代次數(shù)，則結(jié)束搜索，否則轉(zhuǎn)向步驟1。

3.3 算法實(shí)現(xiàn)流程

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

圖1 DDE-VNS算法實(shí)現(xiàn)流程圖Fig.1 Algorithm flowchart of DDE-VNS

4 仿真校驗(yàn)

采用Matlab R2010b對敏捷衛(wèi)星任務(wù)調(diào)度約束滿足模型的有效性和DDE-VNS算法的優(yōu)越性進(jìn)行仿真校驗(yàn)。

4.1 參數(shù)設(shè)置

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

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

4.2 調(diào)度約束滿足模型仿真結(jié)果分析

圖2 成像質(zhì)量隨觀測時(shí)間的變化Fig.2 Change of imaging quality with observation time

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

表2 不同目標(biāo)函數(shù)下調(diào)度方案對比Table 2 Comparison of schedule schemes under different objective function

4.3 DDE-VNS求解算法仿真結(jié)果分析

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

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

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

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

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

5 結(jié) 論

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

[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] 王凌,錢斌.混合差分進(jìn)化與調(diào)度算法[M].北京: 清華大學(xué)出版社, 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] 薛羽, 莊毅, 顧晶晶, 等. 自適應(yīng)離散差分進(jìn)化算法策略的選擇[J]. 軟件學(xué)報(bào), 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] 張春美,陳杰,辛斌. 武器目標(biāo)分配問題的離散差分進(jìn)化算法[J]. 北京理工大學(xué)學(xué)報(bào), 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] 皮本杰, 翟淑寶. 信號采集系統(tǒng)星地資源快速調(diào)度優(yōu)化方法[J]. 宇航學(xué)報(bào), 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] 陳錦偉. 敏捷衛(wèi)星遙感圖像配準(zhǔn)和拼接技術(shù)研究[D]. 杭州: 浙江大學(xué), 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.

通信地址：北京市懷柔區(qū)八一路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-)，男，博士生，主要從事航天任務(wù)分析與設(shè)計(jì)研究。