基于改進(jìn)煙花算法的密集任務(wù)成像衛(wèi)星調(diào)度方法

張 銘，王晉東，衛(wèi) 波

(1.信息工程大學(xué)，鄭州 450001； 2.北京市遙感信息研究所，北京 100101)

0 引言

地球觀測成像衛(wèi)星由于在災(zāi)害監(jiān)測、目標(biāo)偵察和情報(bào)獲取方面具有許多明顯的優(yōu)勢(如視野廣闊，不受地域、時域限制)，已成為科學(xué)研究、軍事行動和民用活動中不可缺少的工具。而在區(qū)域作戰(zhàn)、反恐維穩(wěn)以及搶險救災(zāi)等應(yīng)急行動中，往往任務(wù)需求比較集中、空間密度比較高、時效性要求比較強(qiáng)，而現(xiàn)有觀測系統(tǒng)容納能力往往不能夠同時滿足多個用戶大量密集型任務(wù)請求。成像衛(wèi)星的觀測調(diào)度涉及到成像衛(wèi)星、時間窗口和側(cè)擺角度的合理安排。因此，如何利用稀缺的成像衛(wèi)星資源，針對大量密集型任務(wù)，在滿足相關(guān)約束的條件下制定合理有效的調(diào)度方案，最大限度地提高總體觀測效率是目前亟待解決的一個問題。

現(xiàn)有成像衛(wèi)星調(diào)度問題往往抽象為背包問題、整數(shù)規(guī)劃問題等經(jīng)典問題。文獻(xiàn)[1]對面向點(diǎn)目標(biāo)的成像衛(wèi)星調(diào)度問題進(jìn)行了研究，將多星聯(lián)合調(diào)度問題看作具有時間窗口約束的多機(jī)調(diào)度問題，并給出了基于整數(shù)規(guī)劃和約束滿足問題的模型求解。文獻(xiàn)[2]研究成像衛(wèi)星調(diào)度問題，將問題映射為低約束混合整數(shù)規(guī)劃模型，并提出一個迭代算法逐步收緊該模型的約束，從而獲得調(diào)度方案可行的一個最優(yōu)解；文獻(xiàn)[3]研究一個區(qū)域內(nèi)出現(xiàn)多個沖突任務(wù)的情況下如何根據(jù)調(diào)度使模型收益最大，為此建立了非線性規(guī)劃模型；文獻(xiàn)[4]建立了數(shù)學(xué)模型和無環(huán)有向圖模型，提出一種混合迭代局部搜索的蟻群優(yōu)化算法。以上理論大多是基于一些簡化的標(biāo)準(zhǔn)模型，往往忽略了實(shí)際問題中的某些關(guān)鍵因素，并沒有考慮成像衛(wèi)星存儲約束、能量約束以及成像衛(wèi)星姿態(tài)轉(zhuǎn)換時間窗口等實(shí)際約束條件，從而影響了問題的實(shí)用性；而且這些模型一般只適用于任務(wù)稀疏條件下任務(wù)調(diào)度規(guī)劃問題的研究，當(dāng)出現(xiàn)大量密集型任務(wù)需求時，以上模型不足以很好地解決該實(shí)際問題。

針對密集型任務(wù)調(diào)度問題，文獻(xiàn)[5]研究了成像衛(wèi)星任務(wù)合成問題，但并沒有將合成與調(diào)度結(jié)合起來。文獻(xiàn)[6]考慮了對相鄰任務(wù)在時間窗口上進(jìn)行聚類合成，沒有考慮不同側(cè)擺角任務(wù)之間的合成關(guān)系。文獻(xiàn)[7]考慮了成像衛(wèi)星遙感器采用固定角度觀測時，觀測條帶對多個目標(biāo)的覆蓋情況，但僅限于在側(cè)擺角度不變的情況下且沒有考慮時間窗口約束合成問題。文獻(xiàn)[8]在研究觀測時間和觀測角度的參數(shù)優(yōu)化時，考慮用相同側(cè)擺角和時間窗口對多個目標(biāo)統(tǒng)一觀測。文獻(xiàn)[9]分析了元任務(wù)之間的合成關(guān)系及合成約束條件，建立了單星成像偵察任務(wù)合成的團(tuán)劃分模型，給出了問題的求解算法；但該模型并沒有考慮多星協(xié)同工作條件下的合成問題研究，同時由于敏捷成像衛(wèi)星[10-13]可以通過俯仰、翻滾、偏轉(zhuǎn)等姿態(tài)變化，實(shí)現(xiàn)對目標(biāo)前方、后方、上方等立體式觀測，一次過境可以完成更多的任務(wù)，通常也可以用來解決密集型任務(wù)調(diào)度問題。但敏捷成像衛(wèi)星調(diào)度問題的研究相比一般成像衛(wèi)星更為復(fù)雜，其復(fù)雜的觀測過程和觀測約束條件均對調(diào)度方法和模型求解提出了更高的要求，在本文研究中主要針對一般成像衛(wèi)星，對敏捷成像衛(wèi)星不再考慮。

針對上述問題，本文提出了一種基于改進(jìn)煙花算法的密集任務(wù)成像衛(wèi)星調(diào)度方法。該方法首先對任務(wù)需求進(jìn)行分析，依據(jù)點(diǎn)目標(biāo)任務(wù)在偏轉(zhuǎn)角度和觀測時間上的相近性，進(jìn)行任務(wù)合成分析；然后利用合成任務(wù)和成像衛(wèi)星在觀測時間窗口、能量消耗、存儲空間上的約束構(gòu)建合成任務(wù)約束模型；最后利用改進(jìn)的煙花算法對合成任務(wù)進(jìn)行組合優(yōu)化調(diào)度求解，有效提高了任務(wù)調(diào)度的收益和效率等。

1 問題描述及模型建立

1.1 問題描述

成像衛(wèi)星偵查是指利用星載的可見光相機(jī)、紅外相機(jī)或合成孔徑雷達(dá)等遙感器信息來獲取地面信息，并將這些信息通過中繼衛(wèi)星或者地面觀測站傳遞回地面。成像偵查衛(wèi)星一般繞地球近地軌道進(jìn)行飛行，不同的衛(wèi)星軌道可被視為具有一定觀測能力的相同類型的資源。衛(wèi)星飛行軌跡沿一維向前飛行，星載遙感器側(cè)擺角度沿另一維側(cè)向運(yùn)動，最終產(chǎn)生一條二維的矩形掃描帶。成像衛(wèi)星掃描條帶平行于星下點(diǎn)軌跡，其寬度一般是固定的，其中覆蓋有多個點(diǎn)目標(biāo)。

成像衛(wèi)星任務(wù)調(diào)度是指在滿足用戶觀測任務(wù)需求(主要包括圖像類型、觀測有效時間、優(yōu)先級、圖像分辨率)的條件下，將任務(wù)分配給相應(yīng)成像衛(wèi)星對應(yīng)軌道的時間窗口。一個用戶可以有多個不同的任務(wù)，由于成像衛(wèi)星軌跡不同，一個任務(wù)可以在不同成像衛(wèi)星對應(yīng)的不同軌道上進(jìn)行觀測。為避免同一任務(wù)被不同成像衛(wèi)星資源反復(fù)觀測，一般將根據(jù)調(diào)度目標(biāo)利用智能算法對多個分配方案進(jìn)行篩選比較，最終找到一組最優(yōu)解。其任務(wù)調(diào)度流程如圖1所示。

本文主要針對點(diǎn)目標(biāo)比較密集的情況進(jìn)行研究。首先根據(jù)合成約束條件對可以合成的任務(wù)進(jìn)行合成；然后根據(jù)成像衛(wèi)星能量、容量約束、任務(wù)約束和成像衛(wèi)星時間窗口約束等條件建立密集任務(wù)多星多軌道約束模型，最后利用改進(jìn)的煙花算法對模型進(jìn)行求解，將任務(wù)合理分配給不同成像衛(wèi)星軌道的時間窗口。

圖1 多星多軌道任務(wù)調(diào)度流程示意圖

1.2 模型假設(shè)

由于成像衛(wèi)星資源調(diào)度涉及范圍比較廣、調(diào)度模型比較復(fù)雜，為方便問題求解，在不影響調(diào)度模型的前提下對問題作以下假設(shè)：

1)不考慮氣象條件對成像衛(wèi)星成像的影響。由于氣象等不確定性因素的影響，會對最終成像衛(wèi)星成像結(jié)果產(chǎn)生影響，本文假設(shè)氣象預(yù)報(bào)為確定性、高可信度因素。

2)需求任務(wù)為一次性到達(dá)，每一批存在多個任務(wù)。

3)不考慮成像衛(wèi)星所攜帶的遙感器以及成像衛(wèi)星運(yùn)行軌道的差異性，假設(shè)所有的成像衛(wèi)星都具有相同的性質(zhì)如能量和存儲容量。

1.3 模型分析

1.3.1 合成約束分析

1)合成約束必要性分析。

由于觀測區(qū)域比較密集，任務(wù)比較集中，成像衛(wèi)星屬于稀缺資源，受到自身存儲容量、能量消耗的影響，對成像衛(wèi)星進(jìn)行合成分析具有以下優(yōu)勢：

①任務(wù)合成可以使成像衛(wèi)星以較少的傳感器打開時間為代價完成更多的任務(wù)。成像衛(wèi)星在每次開始觀測之前必須首先打開傳感器，但由于受到自身存儲容量和能量的限制，成像衛(wèi)星在每個軌道周期的觀測次數(shù)也是有限的。通過任務(wù)合成可以使成像衛(wèi)星以更少的觀測完成更多的任務(wù)。如圖2所示，傳統(tǒng)上傳感器需要打開6次來執(zhí)行6個觀察任務(wù)。相比之下，任務(wù)合成使成像衛(wèi)星能夠在3個傳感器打開時間內(nèi)完成6項(xiàng)任務(wù)。

②任務(wù)合成可以使一些本來相互排斥的任務(wù)同時完成。當(dāng)成像衛(wèi)星連續(xù)完成兩個任務(wù)時，衛(wèi)星需要足夠的轉(zhuǎn)換時間來打開其傳感器并將傳感器偏轉(zhuǎn)到適當(dāng)?shù)慕嵌纫灾赶蛱囟繕?biāo)。如果兩個連續(xù)任務(wù)的時間窗口之間沒有足夠的持續(xù)時間，它們將是互斥的。如圖2所示，本文假設(shè)元任務(wù)t4、t5和t6是互斥的，則傳統(tǒng)上t4、t5或t6將不能被同時調(diào)度。而在考慮任務(wù)合成之后，t4、t5和t6可以被合成并一起完成。

圖2 成像衛(wèi)星任務(wù)合成示意圖

③任務(wù)合成可以使成像衛(wèi)星通過減少傳感器回轉(zhuǎn)時間和減少成像衛(wèi)星角度偏轉(zhuǎn)次數(shù)，從而降低衛(wèi)星能量消耗。

2)相關(guān)術(shù)語。

定義1 元任務(wù)。成像衛(wèi)星一次過境可以觀測的任務(wù)。

定義2 合成任務(wù)。當(dāng)若干個元任務(wù)滿足一定約束條件時，成像衛(wèi)星在同一軌道圈次內(nèi)通過調(diào)整觀測角度可以在一次過境時間內(nèi)進(jìn)行觀測的任務(wù)，合成任務(wù)包括一個或多個元任務(wù)。

定義3β-合成任務(wù)。合成任務(wù)包含的元任務(wù)個數(shù)，如2-合成任務(wù)表示該合成任務(wù)包含兩個元任務(wù)，特殊的當(dāng)β=1時即為元任務(wù)。

定義4 (n,l,m)-合成任務(wù)。表示在第n個成像衛(wèi)星的第l個軌道圈次中包含m個元任務(wù)的合成任務(wù)，特殊的當(dāng)m=1時即為元任務(wù)。

3)合成約束分析。

將多個任務(wù)組合成合成任務(wù)的前提條件是它們可以以相同的偏轉(zhuǎn)角度和時間窗口完成。

①偏轉(zhuǎn)角度約束。

圖3 成像衛(wèi)星視場角和偏轉(zhuǎn)角示意圖

推而廣之，對于多個元任務(wù)目標(biāo)t1,t2,…,tLT可以合成的條件是：

②觀測時間約束。

本文需計(jì)算出每個合成任務(wù)的時間窗口，從而允許成像衛(wèi)星在其公共的時間窗口內(nèi)完成對各個元任務(wù)的觀測。

圖4 合成時間窗口示意圖

4)合成算法步驟。

步驟1 判斷任務(wù)與成像衛(wèi)星是否有可視窗口，若有則轉(zhuǎn)步驟2，若無則轉(zhuǎn)步驟7；

步驟2 對第1顆成像衛(wèi)星在衛(wèi)星第1軌道圈次中具有可視窗口的元任務(wù)兩兩比較，若同時滿足合成偏轉(zhuǎn)角度和觀測時間約束，則將兩元任務(wù)合并為(1,1,2)-合成任務(wù)，若不滿足則合并為(1,1,1)-合成任務(wù)；

步驟3 將步驟2中(1,1,2)-合成任務(wù)再依次與第1軌道圈次中剩余的其他元任務(wù)進(jìn)行比較，若滿足合成條件則合并為(1,1,3)-合成任務(wù)，若不滿足轉(zhuǎn)步驟5；

步驟4 依次將合成后的任務(wù)與軌道圈次中其他元任務(wù)進(jìn)行合成條件判斷，直至為n-合成任務(wù)，若不滿足轉(zhuǎn)步驟5；

步驟5 依次遍歷該成像衛(wèi)星中其他軌道圈次；

步驟6 依次遍歷所有成像衛(wèi)星；

步驟7 合成結(jié)束。

1.3.2 成像衛(wèi)星資源約束分析

1)資源能量約束。目前成像衛(wèi)星常用供電形式主要為蓄電池/太陽能電池供電，在光照期間太陽能向蓄電池充電，在地影期間蓄電池向成像衛(wèi)星供電。由于成像衛(wèi)星繞地飛行近似為圓形，光照時間和地影時間大致相等，因此可以近似認(rèn)為成像衛(wèi)星繞地飛行在單個軌道的能量為定值。成像衛(wèi)星對目標(biāo)任務(wù)成像時，需要消耗一定的電能。其消耗形式包括成像衛(wèi)星成像能量消耗、成像衛(wèi)星姿態(tài)調(diào)整能量消耗以及成像衛(wèi)星開關(guān)機(jī)能量消耗等。

2)資源存儲容量約束。成像偵察成像衛(wèi)星對目標(biāo)任務(wù)進(jìn)行觀測后，一般將信息存儲在自身存儲器內(nèi)。由于成像衛(wèi)星同地面站和中繼衛(wèi)星之間的數(shù)據(jù)傳輸速度有限，一旦數(shù)據(jù)信息量超過一定限制，成像衛(wèi)星在一次傳輸中將很難將信息傳輸完畢，因此，成像衛(wèi)星觀測活動受到衛(wèi)星資源自身存儲容量約束。

1.3.3 任務(wù)約束分析

1)任務(wù)唯一性約束。在任一時刻，由于成像衛(wèi)星存儲容量和能量的限制，為避免任務(wù)被重復(fù)觀測帶來額外的能量消耗，一個任務(wù)只能由至多一個衛(wèi)星完成，一個衛(wèi)星只能完成最多一個任務(wù)。

2)任務(wù)調(diào)度的不可中斷約束。調(diào)度任務(wù)一旦開始執(zhí)行就必須執(zhí)行完畢，否則認(rèn)為該任務(wù)無效。

1.3.4 時間窗口約束分析

兩個任務(wù)之間的過渡時間由它們的視角和遙感器的旋轉(zhuǎn)速率決定。如果兩個觀測活動之間的過渡時間超過它們的間隔時間，將放棄一個活動。對于合成任務(wù)Cu和Cv，兩次聯(lián)合觀測之間的間隔時間應(yīng)足夠長，以便成像衛(wèi)星能夠調(diào)整其姿態(tài)。

1.4 模型建立

1.4.1 模型參數(shù)及決策變量定義

1)模型參數(shù)定義如下：

U={u1,u2,…,uLU}為用戶集，LU表示用戶的個數(shù)。

T={t1,t2,…,tLT}為元任務(wù)集，LT表示元任務(wù)的個數(shù)。

S={s1,s2,…,sLS}為成像衛(wèi)星資源集，LS表示成像衛(wèi)星的個數(shù)。

C={C1,C2,…,CLC}為合成任務(wù)集，LC表示合成任務(wù)的個數(shù)。

p={p1,p2,…,pLM}為元任務(wù)的優(yōu)先級集，其中pi表示第i個元任務(wù)的優(yōu)先級。

CP={cp1,cp2,…,cpLC}為合成任務(wù)優(yōu)先級，其中cpi表示第i個合成任務(wù)的優(yōu)先級，其計(jì)算方式為包含的元任務(wù)優(yōu)先級之和。

et為衛(wèi)星成像單位時間所消耗的能量。

ec為成像衛(wèi)星姿態(tài)調(diào)整單位時間所消耗的能量。

es為成像衛(wèi)星單次姿態(tài)調(diào)整固有的能量消耗。

ev為一次開關(guān)機(jī)所消耗的能量。

En為成像衛(wèi)星sn單個軌道的最大可用能量。

ct為衛(wèi)星成像單位時長所占用的存儲容量。

Cn為成像衛(wèi)星sn單個軌道圈次最大存儲容量。

2)決策變量定義如下。

1.4.2 多星密集任務(wù)調(diào)度模型

從上述定義，以收益最大作為任務(wù)規(guī)劃的目標(biāo)，可以建立基于任務(wù)合成的成像衛(wèi)星資源規(guī)劃約束滿足問題(Constraint Satisfaction Problem, CSP)模型：

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

(1)

約束條件：

(2)

(3)

(4)

?u∈[1,LC],?n∈[1,LS],?j∈[1,LO]

(5)

(6)

其中，式(1)為目標(biāo)函數(shù)，即求調(diào)度模型的最大收益；式(2)為衛(wèi)星單個軌道圈次能量約束；式(3)為衛(wèi)星單個軌道圈次存儲容量約束；式(4)為任務(wù)唯一性約束；式(5)為合成任務(wù)的不可中斷約束；式(6)為合成任務(wù)間調(diào)整時間約束。

2 標(biāo)準(zhǔn)煙花算法

2.1 煙花算法概述

煙花算法(FireWorks Algorithm, FWA)[14-15]是根據(jù)煙花爆炸這種現(xiàn)象演變而來的一種智能尋優(yōu)算法，利用煙花爆炸中心產(chǎn)生以一定距離為半徑的均勻火花空間，爆炸過程相當(dāng)于尋優(yōu)，產(chǎn)生的均勻火花空間則是最優(yōu)解的空間范圍。煙花算法自2010年提出以后，受到各界廣泛關(guān)注，學(xué)者在多目標(biāo)煙花算法求解[16-17]、基于改進(jìn)煙花算法研究[18-19]和煙花算法在實(shí)際問題中的應(yīng)用[20-22]等方面作了大量研究。

煙花算法利用爆炸算子(即煙花產(chǎn)生爆炸火花的過程)和變異算子(即煙花產(chǎn)生高斯變異火花的過程)增強(qiáng)了算法在鄰域搜索和擴(kuò)大種群多樣性方面的能力，同時煙花算法按照一定選擇策略(即選擇下一代煙花的過程)來平衡資源分配和信息融合交互使得整個種群在全局搜索和局部搜索中達(dá)到一種平衡。

2.2 爆炸算子

在煙花算法的可行域內(nèi)初始化一定的煙花數(shù)量，每個煙花的位置代表一個可行解。假定待求解的優(yōu)化問題形式表示為maxf(x),x∈Ω，即在可行域Ω尋找一點(diǎn)x，使得該點(diǎn)為全局最大適應(yīng)值。為了兼顧開采性能和勘探性能，煙花算法的爆炸半徑和爆炸火花數(shù)目是根據(jù)相對于種群中其他煙花適應(yīng)度值來設(shè)計(jì)的。對于煙花xi，初始化種群個數(shù)為N，其爆炸半徑ri和爆炸火花數(shù)目mi計(jì)算公式如下所示：

(7)

(8)

其中：ymax=max(f(xi))(i=1,2,…,N)為當(dāng)前種群中適應(yīng)度最大值；ymin=min(f(xi))(i=1,2,…,N)為當(dāng)前種群中適應(yīng)度最小值；r為常數(shù)，用以調(diào)節(jié)煙花爆炸半徑；m為常數(shù)，用以調(diào)節(jié)煙花爆炸產(chǎn)生的數(shù)目；ε表示無窮小實(shí)數(shù)。從式(8)中可以看出函數(shù)適應(yīng)度值越接近目標(biāo)，爆炸產(chǎn)生的火花數(shù)目越多，產(chǎn)生的爆炸半徑越小，符合勘探性要求；相反函數(shù)適應(yīng)度值越遠(yuǎn)離目標(biāo)，爆炸產(chǎn)生的火花數(shù)目越少，產(chǎn)生的爆炸半徑越大，符合開采性要求。

為了避免較好煙花數(shù)目過多，較差煙花數(shù)目過少，對煙花i的火花數(shù)目作以下分析：

(9)

其中：a、b表示兩個常數(shù)，round為按照四舍五入規(guī)則進(jìn)行取整操作。一般取a=0.1，b=0.2。

根據(jù)產(chǎn)生的爆炸半徑和產(chǎn)生的爆炸火花數(shù)目，煙花xi生成mi個爆炸火花，其實(shí)現(xiàn)過程為隨機(jī)選擇z個維度，對其中隨機(jī)選擇出的維度k∈{1,2,…,z}按照式(10)進(jìn)行位置的偏移，生成相應(yīng)的爆炸火花。

(10)

(11)

式(11)中l(wèi)b、ub分別為k維解空間上的下邊界和上邊界，mod為取余函數(shù)。

2.3 變異算子

為了增加種群的多樣性，煙花算法中引入了高斯變異，產(chǎn)生高斯變異火花。在煙花種群中隨機(jī)選擇G個煙花，對其每一個煙花隨機(jī)選擇z個維度進(jìn)行高斯變異操作。

(12)

2.4 選擇策略

為了保證優(yōu)良個體能夠很好的傳遞給下一代，從種群候選集合(煙花、爆炸煙花、高斯變異火花)K中，隨機(jī)選擇N個個體作為下一代計(jì)算的煙花種群，候選集合中適應(yīng)度值最大的個體作為下一代N個個體中的一個，剩下N-1個個體通過輪盤賭方法選擇，對于候選者xi其被選中的概率為：

(13)

(14)

式(13)、(14)中R(xi)為當(dāng)前個體與候選者集合K中每個個體之間的距離和，同時可以看出，如果個體密度較高，則該個體被選中的幾率會大大降低。

3 密集任務(wù)成像衛(wèi)星資源調(diào)度算法

基于基本的FWA算法的選擇策略是一種基于距離的選擇策略，一個個體與其他個體相距越遠(yuǎn)，其被選中的幾率越大。這種選擇方案擴(kuò)展了種群選擇結(jié)果的多樣性，但同時也帶來了算法在每代執(zhí)行時間上的消耗。對于密集任務(wù)成像衛(wèi)星調(diào)度問題而言，一般為緊急性、對時間時效性要求較高任務(wù)，因此如果能夠在煙花算法上對其效率改進(jìn)則具有一定的現(xiàn)實(shí)意義。基于密集任務(wù)的成像衛(wèi)星資源調(diào)度問題是離散空間的非數(shù)值優(yōu)化問題，針對該調(diào)度問題特征，本文建立連續(xù)空間粒子與離散空間調(diào)度求解的一種對應(yīng)關(guān)系，提出一種改進(jìn)的煙花算法(Improved FireWorks Algorithm, IFWA)用于求解該組合優(yōu)化問題。

3.1 精英選擇策略

為了能夠加快選擇到下一代的速度，本文采用一種精英選擇策略，使候選集K中的每個個體根據(jù)自身的適應(yīng)度值都有可能以一定概率被選擇為下一代，候選集K按照以下概率進(jìn)行選擇：

(15)

候選集中每個個體的適應(yīng)度值越大，其被選為下一代的幾率越大，特殊的當(dāng)候選集中個體適應(yīng)度值最大時，將會以概率1被選擇到下一代，從而保證了算法的最優(yōu)性質(zhì)得以在下一代中體現(xiàn)。根據(jù)式(15)計(jì)算每個個體的適應(yīng)度值并依概率從大到小排序，選擇出排序前N/2的個體作為下一代煙花，剩下N/2個體從種群中隨機(jī)選擇，從而在一定程度上既保證了種群的多樣性，同時提高了算法的求解效率。

3.2 編碼和解碼

基于煙花算法是隨機(jī)產(chǎn)生一個N維粒子空間，本文用3n個位置值表示每個煙花的位置矢量，即所有任務(wù)調(diào)度方案的一個排列。在這種調(diào)度方案排列中前n個表示對應(yīng)的任務(wù)編號，中間n個表示對應(yīng)的成像衛(wèi)星編號，最后n個表示成像衛(wèi)星軌道圈次，即第i(1≤i≤n)個位置第n+i個位置和第2n+i個位置的數(shù)值共同構(gòu)成了一個調(diào)度方案，第i個任務(wù)分配給了第n+i位置上對應(yīng)數(shù)值編號的衛(wèi)星所對應(yīng)的第2n+i個位置上數(shù)值編號的軌道圈次。例如：一個煙花個體可以表示為X={x1,…,xi,…xn,xn+1,…,xn+i,…,x2n,x2n+1,…,x2n+i,…,x3n}，則其對應(yīng)的調(diào)度方案初始排列可以為 1,2,…,n,1,2,…,n,1,2,…,n其含義為第1個任務(wù)分配給了第1顆成像衛(wèi)星所對應(yīng)的第1個軌道圈次，第2個任務(wù)分配給了第2顆成像衛(wèi)星的第2個軌道圈次，第n個任務(wù)分配給第n顆成像衛(wèi)星的第n個軌道圈次。在解碼過程中，先將3n維煙花的位置矢量轉(zhuǎn)化為一個一維的有序排列，根據(jù)排列中相應(yīng)的位置數(shù)值對應(yīng)相應(yīng)的調(diào)度方案。

3.3 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)是整個煙花算法中的關(guān)鍵部分。在用煙花算法尋優(yōu)之前，要根據(jù)實(shí)際問題確定目標(biāo)函數(shù)(適應(yīng)度函數(shù))。與數(shù)學(xué)中純粹的優(yōu)化問題不同，適應(yīng)度函數(shù)求取結(jié)果為極大值，其值具有非負(fù)性。在基于任務(wù)合成的密集任務(wù)成像衛(wèi)星調(diào)度問題的研究中，任務(wù)規(guī)劃的目標(biāo)是實(shí)現(xiàn)總服務(wù)的收益最大即任務(wù)的優(yōu)先級最大，因而可以定義煙花算法適應(yīng)度函數(shù)如下：

(16)

其中：pi表示任務(wù)的總收益，εi表示懲罰值，表示約束違規(guī)的總和，主要是根據(jù)煙花位置對應(yīng)的調(diào)度方案是否符合資源約束、任務(wù)約束和時間窗口約束最終統(tǒng)計(jì)得到的，從適應(yīng)度求解公式可以看出，其懲罰值越小，則適應(yīng)度函數(shù)值越大，表示方案越合理。

對于煙花算法的每一個煙花矢量信息，計(jì)算其懲罰值時需要考慮其約束信息：對每個任務(wù)分別進(jìn)行資源約束、任務(wù)約束和時間窗口約束判斷，如果其中任一約束不滿足，則懲罰值記為1；如果煙花位置第n+i或2n+i個位置為0，表示第i個任務(wù)單元沒有分配成像衛(wèi)星資源窗口，則懲罰值為1，最終εi為n個任務(wù)判定后懲罰值之和。

3.4 算法描述

通過對基于密集任務(wù)成像衛(wèi)星資源調(diào)度問題的模型建立，本文提出一種改進(jìn)煙花算法，其流程如圖5所示。

在初始化階段，煙花種群數(shù)量為N，爆炸半徑調(diào)節(jié)常數(shù)為r，爆炸火花數(shù)調(diào)節(jié)常數(shù)為m。對于n個任務(wù)組成的其中一種調(diào)度方案初始化一個煙花位置，隨機(jī)產(chǎn)生N個這樣的煙花位置。由式(16)根據(jù)任務(wù)收益和懲罰值計(jì)算煙花的適應(yīng)度值。由式(7)計(jì)算爆炸火花產(chǎn)生的煙花個數(shù)，由式(8)計(jì)算煙花爆炸的半徑大小，由式(10)生成相應(yīng)的爆炸火花，對于超出邊界的煙花由式(11)進(jìn)行映射操作。

根據(jù)高斯變異火花常數(shù)G，隨機(jī)選擇G個煙花，由式(12)對煙花隨機(jī)選擇z個維度進(jìn)行高斯變異操作。若超出邊界，則由式(11)進(jìn)行相應(yīng)的映射操作。

隨后，采用精英選擇策略，由式(15)選出N/2個個體作為下一代煙花，剩下N/2個個體從種群中隨機(jī)選擇，根據(jù)迭代次數(shù)判斷是否終止計(jì)算。最后，按照結(jié)果將任務(wù)分配給相應(yīng)成像衛(wèi)星對應(yīng)的軌道圈次的時間窗口。

圖5 IFWA流程

4 實(shí)驗(yàn)仿真與結(jié)果分析

為了驗(yàn)證算法的可行性，本文設(shè)計(jì)了兩類對比實(shí)驗(yàn)：1)IFWA和FWA算法在考慮任務(wù)合成和未考慮任務(wù)合成條件下的性能對比；2)在考慮任務(wù)合成的前提下，改進(jìn)煙花算法(IFWA)與傳統(tǒng)的遺傳算法(Genetic Algorithm, GA)、蟻群優(yōu)化(Ant Colony Optimization, ACO)算法性能對比。仿真實(shí)驗(yàn)參數(shù)環(huán)境設(shè)計(jì)如下：在緯度-30°～40°，經(jīng)度80°～120°的范圍內(nèi)隨機(jī)均勻生成不同數(shù)量規(guī)模的點(diǎn)目標(biāo)，元任務(wù)優(yōu)先級則為[1,10]的隨機(jī)數(shù)，衛(wèi)星s1為美國空間成像公司發(fā)射的IKONOS-2衛(wèi)星，衛(wèi)星s2為美國軌道成像公司發(fā)射的ORBVIEW衛(wèi)星，衛(wèi)星s3為法國發(fā)射的SPOT-5衛(wèi)星，衛(wèi)星s4為美國DigitalGlobe公司發(fā)射的Quickbird衛(wèi)星，4顆成像衛(wèi)星均經(jīng)過該區(qū)域范圍。觀測時間段為2017- 05- 06T12:00—2017- 05- 07T12:00，成像衛(wèi)星的視場角分別為3°、5°、8°和6°，可行的側(cè)擺角范圍為±45°、±30°、±33°和±25°，成像衛(wèi)星單次開機(jī)最長時間分別為200 s、150 s、180 s和160 s。任務(wù)的地理坐標(biāo)決定了其與成像衛(wèi)星之間的可見窗口以及觀測角度，由STK軟件計(jì)算獲得。由于任務(wù)為隨機(jī)生成，因此可能出現(xiàn)某些任務(wù)沒有觀測機(jī)會。

算法測試實(shí)驗(yàn)環(huán)境為Windows 7操作系統(tǒng)，在Pentium 1.70 GHz CPU,512 MB內(nèi)存的微機(jī)上運(yùn)行，采用Matlab R2014b實(shí)現(xiàn)編程。FWA和IFWA的控制參數(shù)為：煙花種群數(shù)量N=120，爆炸半徑調(diào)節(jié)常數(shù)r=1 000，爆炸火花數(shù)調(diào)節(jié)常數(shù)m=200，解空間下邊界為lb=1，上邊界為ub=20，高斯變異火花數(shù)目G=60，迭代次數(shù)為20。

1)IFWA和FWA算法在考慮任務(wù)合成和未考慮任務(wù)合成條件下的性能對比。

設(shè)計(jì)仿真對比實(shí)驗(yàn)：當(dāng)任務(wù)規(guī)模分別為100，200，300，400，500，600時考慮任務(wù)合成和不考慮任務(wù)合成條件下用FWA求解該模型問題，得到實(shí)際任務(wù)完成對比實(shí)驗(yàn)圖、收益值對比實(shí)驗(yàn)圖、時間對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 FWA考慮任務(wù)、收益值、時間對比

如圖6(a)所示，當(dāng)觀測任務(wù)數(shù)較少情況下，考慮合成條件和不考慮合成條件差別并不是很明顯，隨著任務(wù)數(shù)的增加，考慮合成條件的明顯比沒有考慮合成條件的觀測數(shù)要多。當(dāng)任務(wù)數(shù)達(dá)到500和600以后，考慮合成條件的要比沒有考慮的觀測任務(wù)數(shù)分別增加30.77%和34.48%。由于收益和任務(wù)數(shù)量正相關(guān)，由圖6(b)可以看出，在考慮合成條件后，任務(wù)收益明顯增加。

同時，從圖6(c)中可以發(fā)現(xiàn)，隨著任務(wù)數(shù)的增多，考慮合成條件的消耗時間比沒有考慮合成條件的消耗時間多，這是因?yàn)楫?dāng)任務(wù)數(shù)為100時，由于任務(wù)相對比較分散，任務(wù)相互合成的機(jī)會比較小，資源之間發(fā)生沖突的可能性比較小。當(dāng)任務(wù)數(shù)越來越多時，任務(wù)之間合成機(jī)會變多，資源之間競爭急劇增加，衛(wèi)星調(diào)度時間也隨之增長較快。

為解決考慮合成任務(wù)以后帶來的時間上的開銷，本文在原有煙花算法的基礎(chǔ)上針對選擇策略進(jìn)行了改進(jìn)，采用精英選擇策略，提高了算法的收斂速度，縮短了算法求解的時間，其實(shí)驗(yàn)對比如圖7所示。

圖7 考慮任務(wù)合成時FWA與IFWA在時間上對比

從圖7可以看出，用改進(jìn)后的煙花算法(IFWA)求解該模型時，雖然在時間上仍然比沒有考慮合成任務(wù)時FWA要多一些，但相比考慮任務(wù)合成時FWA時間上則平均減少了32%～45%，在時間和效率綜合考慮的情況下，其求解結(jié)果可以接受。

2)在考慮任務(wù)合成的前提下，改進(jìn)煙花算法(IFWA)與傳統(tǒng)的遺傳算法(GA)、蟻群算法(ACO)性能對比。迭代次數(shù)分別為10、20、30、40、50、60，選取任務(wù)數(shù)為100和600時其平均收益值隨迭代次數(shù)更新曲線如圖8所示。

圖8 任務(wù)數(shù)為100、600時幾種算法收益值更新曲線

由圖8可知，當(dāng)任務(wù)數(shù)為100和600時，同等條件下改進(jìn)煙花算法可以通過更少的迭代次數(shù)達(dá)到穩(wěn)定，說明改進(jìn)煙花算法具有更高的收斂速度，這是因?yàn)楦倪M(jìn)煙花算法通過調(diào)整其適應(yīng)度值和改進(jìn)其選擇策略，其性能得到優(yōu)化，收斂速度更高。

由圖8也可以看出，當(dāng)?shù)螖?shù)為40次以后，各個算法基本達(dá)到穩(wěn)定值，取迭代次數(shù)為40次，在考慮任務(wù)合成的前提下，分別用遺傳算法、蟻群算法和改進(jìn)煙花算法進(jìn)行求解，其平均收益值如表1所示。

表1 三種算法平均收益值對比

由表1可以看出，在不同目標(biāo)任務(wù)下，IFWA的尋優(yōu)性能總比其他兩個算法尋找到的平均收益值要大，即IFWA相對尋優(yōu)性能最好，ACO次之，GA最差。綜上所述，考慮任務(wù)合成的IFWA可以有效解決多星密集任務(wù)調(diào)度問題。

5 結(jié)語

針對多用戶大量密集型任務(wù)請求，考慮成像衛(wèi)星自身能量、容量限制等因素，本文首先根據(jù)密集型任務(wù)特點(diǎn)分析了任務(wù)合成的條件，建立了基于合成任務(wù)約束的多星密集任務(wù)調(diào)度模型，可以有效節(jié)約資源，提高完成任務(wù)的數(shù)量和收益。在算法求解上采用一種新穎的智能算法——IFWA，不僅增加了種群搜索空間，在每一次迭代過程中都會產(chǎn)生多個個體，而且基于精英的選擇策略有效減少了模型求解的時間，能夠有效地解決該問題。實(shí)驗(yàn)結(jié)果表明，該方法可以有效提高成像衛(wèi)星觀測效率，具有很強(qiáng)的實(shí)用價值。

由于本文主要考慮的是靜態(tài)條件下任務(wù)一次性到達(dá)的情況，在實(shí)際應(yīng)用中往往會出現(xiàn)如高優(yōu)先級任務(wù)加入、成像衛(wèi)星資源失效等動態(tài)情況，下一步將針對動態(tài)環(huán)境下成像衛(wèi)星任務(wù)調(diào)度展開研究。