基于改進煙花算法的密集任務成像衛星調度方法

張 銘，王晉東，衛 波

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

0 引言

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

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

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

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

1 問題描述及模型建立

1.1 問題描述

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

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

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

圖1 多星多軌道任務調度流程示意圖

1.2 模型假設

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

1)不考慮氣象條件對成像衛星成像的影響。由于氣象等不確定性因素的影響，會對最終成像衛星成像結果產生影響，本文假設氣象預報為確定性、高可信度因素。

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

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

1.3 模型分析

1.3.1 合成約束分析

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

由于觀測區域比較密集，任務比較集中，成像衛星屬于稀缺資源，受到自身存儲容量、能量消耗的影響，對成像衛星進行合成分析具有以下優勢：

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

②任務合成可以使一些本來相互排斥的任務同時完成。當成像衛星連續完成兩個任務時，衛星需要足夠的轉換時間來打開其傳感器并將傳感器偏轉到適當的角度以指向特定目標。如果兩個連續任務的時間窗口之間沒有足夠的持續時間，它們將是互斥的。如圖2所示，本文假設元任務t4、t5和t6是互斥的，則傳統上t4、t5或t6將不能被同時調度。而在考慮任務合成之后，t4、t5和t6可以被合成并一起完成。

圖2 成像衛星任務合成示意圖

③任務合成可以使成像衛星通過減少傳感器回轉時間和減少成像衛星角度偏轉次數，從而降低衛星能量消耗。

2)相關術語。

定義1 元任務。成像衛星一次過境可以觀測的任務。

定義2 合成任務。當若干個元任務滿足一定約束條件時，成像衛星在同一軌道圈次內通過調整觀測角度可以在一次過境時間內進行觀測的任務，合成任務包括一個或多個元任務。

定義3β-合成任務。合成任務包含的元任務個數，如2-合成任務表示該合成任務包含兩個元任務，特殊的當β=1時即為元任務。

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

3)合成約束分析。

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

①偏轉角度約束。

圖3 成像衛星視場角和偏轉角示意圖

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

②觀測時間約束。

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

圖4 合成時間窗口示意圖

4)合成算法步驟。

步驟1 判斷任務與成像衛星是否有可視窗口，若有則轉步驟2，若無則轉步驟7；

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

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

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

步驟5 依次遍歷該成像衛星中其他軌道圈次；

步驟6 依次遍歷所有成像衛星；

步驟7 合成結束。

1.3.2 成像衛星資源約束分析

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

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

1.3.3 任務約束分析

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

2)任務調度的不可中斷約束。調度任務一旦開始執行就必須執行完畢，否則認為該任務無效。

1.3.4 時間窗口約束分析

兩個任務之間的過渡時間由它們的視角和遙感器的旋轉速率決定。如果兩個觀測活動之間的過渡時間超過它們的間隔時間，將放棄一個活動。對于合成任務Cu和Cv，兩次聯合觀測之間的間隔時間應足夠長，以便成像衛星能夠調整其姿態。

1.4 模型建立

1.4.1 模型參數及決策變量定義

1)模型參數定義如下：

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

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

S={s1,s2,…,sLS}為成像衛星資源集，LS表示成像衛星的個數。

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

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

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

et為衛星成像單位時間所消耗的能量。

ec為成像衛星姿態調整單位時間所消耗的能量。

es為成像衛星單次姿態調整固有的能量消耗。

ev為一次開關機所消耗的能量。

En為成像衛星sn單個軌道的最大可用能量。

ct為衛星成像單位時長所占用的存儲容量。

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

2)決策變量定義如下。

1.4.2 多星密集任務調度模型

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

目標函數：

(1)

約束條件：

(2)

(3)

(4)

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

(5)

(6)

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

2 標準煙花算法

2.1 煙花算法概述

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

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

2.2 爆炸算子

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

(7)

(8)

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

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

(9)

其中：a、b表示兩個常數，round為按照四舍五入規則進行取整操作。一般取a=0.1，b=0.2。

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

(10)

(11)

式(11)中lb、ub分別為k維解空間上的下邊界和上邊界，mod為取余函數。

2.3 變異算子

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

(12)

2.4 選擇策略

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

(13)

(14)

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

3 密集任務成像衛星資源調度算法

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

3.1 精英選擇策略

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

(15)

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

3.2 編碼和解碼

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

3.3 適應度函數設計

適應度函數是整個煙花算法中的關鍵部分。在用煙花算法尋優之前，要根據實際問題確定目標函數(適應度函數)。與數學中純粹的優化問題不同，適應度函數求取結果為極大值，其值具有非負性。在基于任務合成的密集任務成像衛星調度問題的研究中，任務規劃的目標是實現總服務的收益最大即任務的優先級最大，因而可以定義煙花算法適應度函數如下：

(16)

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

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

3.4 算法描述

通過對基于密集任務成像衛星資源調度問題的模型建立，本文提出一種改進煙花算法，其流程如圖5所示。

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

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

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

圖5 IFWA流程

4 實驗仿真與結果分析

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

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

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

設計仿真對比實驗：當任務規模分別為100，200，300，400，500，600時考慮任務合成和不考慮任務合成條件下用FWA求解該模型問題，得到實際任務完成對比實驗圖、收益值對比實驗圖、時間對比實驗，實驗結果如圖6所示。

圖6 FWA考慮任務、收益值、時間對比

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

同時，從圖6(c)中可以發現，隨著任務數的增多，考慮合成條件的消耗時間比沒有考慮合成條件的消耗時間多，這是因為當任務數為100時，由于任務相對比較分散，任務相互合成的機會比較小，資源之間發生沖突的可能性比較小。當任務數越來越多時，任務之間合成機會變多，資源之間競爭急劇增加，衛星調度時間也隨之增長較快。

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

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

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

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

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

由圖8可知，當任務數為100和600時，同等條件下改進煙花算法可以通過更少的迭代次數達到穩定，說明改進煙花算法具有更高的收斂速度，這是因為改進煙花算法通過調整其適應度值和改進其選擇策略，其性能得到優化，收斂速度更高。

由圖8也可以看出，當迭代次數為40次以后，各個算法基本達到穩定值，取迭代次數為40次，在考慮任務合成的前提下，分別用遺傳算法、蟻群算法和改進煙花算法進行求解，其平均收益值如表1所示。

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

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

5 結語

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

由于本文主要考慮的是靜態條件下任務一次性到達的情況，在實際應用中往往會出現如高優先級任務加入、成像衛星資源失效等動態情況，下一步將針對動態環境下成像衛星任務調度展開研究。