考慮合成機制的多星應急任務調度

靳 鵬, 唐曉茜,*

(1. 合肥工業大學管理學院, 安徽 合肥 230009; 2. 過程優化與智能決策教育部重點實驗室, 安徽 合肥 230009)

0 引 言

對地觀測衛星是空間范圍內的一種成像資源,根據用戶對地球表面目標的成像需求,利用星載傳感器,在滿足衛星成像的約束條件下,對地球表面目標進行觀測,獲取圖像信息。由于具有成像效果好、覆蓋區域廣且不受國界限制等優點,在環境監測、資源探測、災害預警、軍事偵探等領域發揮著重要作用。當地震、火災等緊急情況發生時,充分利用衛星資源對受災區域成像已經成為一種獲取圖像信息的重要手段,能夠為救援部門提供重要的決策信息支持。應急任務的觀測會對原調度序列產生影響,如何設計高效的衛星應急任務調度方法,在保證觀測總收益的基礎上最小化對原調度序列的擾動是多星應急任務調度領域急需解決的問題。

應急任務具有兩大特點:① 及時性,希望任務越早成像越好。應急任務的到達伴隨著期望完成時間,但當任務實際完成時間比期望完成時間晚時,所獲得的圖像信息仍然有價值;② 隨機性,任務到達的時間和數量是不確定的。在軌衛星成像過程中存在衛星狀態改變、云層影響或用戶需求轉變等多種不確定性,導致用戶提交的應急任務呈現隨機性特點。雖然應急任務的到達是隨機的,但調度任務并給衛星上注觀測指令是統一完成的。本文在任務統一調度情況下研究多星應急任務調度問題。

衛星對任務觀測成像需要滿足時間窗、姿態轉換時間、存儲限制等多方面約束。近年來,用戶的觀測需求量持續上漲,遠大于衛星資源負載能力,星上任務呈現飽和狀態。在盡量減少對初始調度序列擾動的情況下完成應急任務調度變得更加復雜。

目前,國內外學者已經對多星應急任務調度問題展開大量研究。文獻[14-20]采用蟻群算法、局部迭代搜索算法、粒子群算法和遺傳算法等啟發式算法完成應急任務調度。文獻[21]以最大化任務觀測收益和數量為目標,提出直接插入或刪除插入(insert directly or insert by deleting,IDI)算法和直接插入、移位插入、刪除插入和被刪除任務重插入(insert directly, insert by shifting, insert by deleting, and reinsert the tasks deleted, ISDR)算法完成應急任務調度。文獻[22]以任務調度總權重最大和應急任務提前完成時間最長為目標,在ISDR算法的基礎上加入回溯算子,設計插入、移位、回溯、刪除和重插入(insertion, shifting, backtracking, deletion, and reinsertion,ISBDR)算法解決問題。兩種算法都以移位、重插入的方式處理常規任務,但都未考慮對初始調度序列的擾動情況。另外,上述文獻并未突出應急任務完成時間對觀測收益的影響,認為應急任務的觀測收益恒定不變。

現實中資源有限、任務繁多，任務以最佳側擺角獨立觀測時完成率低且資源利用不充分。因此,學者采用任務合成機制增大任務觀測數量和收益,提高衛星資源利用率。文獻[23-27]建立合成任務的調度模型,以最大化任務觀測收益為目標,采用模擬退火算法、蟻群算法和動態規劃算法等啟發式算法完成合成任務調度。文獻[28-30]應用最小派系劃分思想實現任務合成,基于圖論建立模型,設計啟發式算法求解問題。文獻[31]設計啟發式規則實現任務合成與動態調度,但未建立相關模型。上述文獻都是在常規任務間執行任務合成,并未考慮對應急任務的合成操作。

應用任務合成機制處理應急任務的研究較少。文獻[7]側重于對應急任務合成位置選擇的研究,不存在整體尋優過程。文獻[32-34] 考慮應急任務與常規任務合成的同時以最大化任務觀測收益和最小化序列擾動為目標,設計啟發式算法完成應急任務的動態調度。這對原來任務序列的魯棒性要求較高,調度難度也較大。

本文綜合考慮應急任務完成時間和觀測收益指標,建立有時間依賴性收益的數學規劃模型。將合成機制與遺傳算法融合解決多星應急任務調度問題,提出考慮合成機制的多星應急任務調度算法(genetic algorithm with task merging for emergency task scheduling,GA-TM-ETS)。算法以應急任務優先調度為原則,首先設計任務合成、插入、替換等3種算子完成向初始調度序列添加應急任務的操作;其次考慮任務觀測收益、序列擾動和最短觀測時間等因素設計適應度函數,提高算法搜索速度;最后設計基于組基因的交叉算子和變異算子,結合全局修復算子進行序列尋優。實驗表明所設計的GA-TM-ETS算法能夠顯著提高調度質量,適用于多對地觀測衛星應急任務調度。

1 問題描述

對地觀測衛星應急任務調度問題有以下描述。

給定一組衛星,在調度周期內存在軌道集合={,,…,,…,||},||為軌道數量。

本文以軌道作為資源的最小調度單元,任一衛星軌道圈次的屬性可以用六元組<,span,,,,>表示。其中,表示軌道上傳感器視場角,span表示傳感器最長開機時間,表示傳感器單位時間成像的存儲系數,表示軌道最大存儲量,表示傳感器偏轉速率,表示傳感器姿態穩定時間。

1.1 任務合成

衛星以一定側擺角和時間窗對任務觀測成像時形成觀測條帶。在一個觀測條帶內,滿足某種約束條件下,將多個地理位置相近的任務同時觀測的過程為任務的合成觀測。如圖1所示,應急任務和常規任務′滿足衛星側擺角約束和傳感器單次最長開機時間約束,可以在衛星的一個觀測條帶內合成觀測。

圖1 任務合成圖Fig.1 Diagram of task merging

111 側擺角約束

(1)

圖2 側擺角約束Fig.2 Swing angle constraint

(2)

112 單次最長開機時間約束

(3)

圖3 最長開機時間約束Fig.3 Maximum boot time constraint

如圖4所示,應急任務和常規任務′滿足任務合成條件,且合成任務與前后在軌任務滿足時間窗約束和姿態轉換約束,則任務以任務合成方式執行觀測。

圖4 任務合成Fig.4 Task merging

1.2 任務插入

(4)

(5)

如圖5所示,常規任務′和′+1之間存在足夠長的空閑時間片段,應急任務滿足任務插入式(4)和式(5),將其插入觀測。

圖5 任務插入Fig.5 Task insertion

1.3 任務替換

(6)

(7)

如圖6所示,任務滿足替換在軌任務′的式(6)和式(7),用替換′執行觀測。

圖6 任務替換Fig.6 Task replacement

2 調度模型

2.1 完成時間-收益函數

(8)

圖7 應急任務完成時間-收益Fig.7 Emergency task completion time-revenue

2.2 擾動

應急任務的插入可能會擾亂初始調度序列。本文對初始調度序列上的常規任務設計了兩種處理方式:刪除任務或更換任務執行位置。設(=1,2)為任務第種處理方式的影響權重,當刪除任務時取1,當更換任務執行位置時取2,并且>。

考慮常規任務調度序列Seq,應急任務插入后,軌道上的擾動表示為

(9)

其中,turb(′,)定義為

(10)

2.3 數學規劃模型

數學規劃模型以合成任務為描述對象。設任務集={,,…,},為待觀測的合成任務數量。當待觀測任務中只包含一個元任務時,該任務也被看作合成任務。

231目標函數

本文的調度目標優先考慮最大化任務觀測總收益:

(11)

(12)

另一個調度目標考慮對原任務調度序列擾動最小:

(13)

232 約束條件

每個任務只能被觀測一次:

(14)

任務的觀測結束時間一定不小于任務觀測開始時間:

(15)

兩連續觀測任務間的時間間隔至少滿足姿態轉換時間約束,其中,是一個很大的正數:

=1,2,…,-1；=1,2,…,||

(16)

應急任務觀測完成時間具體表示為

(17)

軌道上任務成像的存儲空間不能超過單軌最大存儲限制:

(18)

因此,多星應急任務調度問題可表示為上述具有時間依賴性收益的數學規劃模型。

3 算法設計

遺傳算法是基于自然選擇和生物進化理論的演化算法,因其具有較強的廣域搜索能力而被廣泛應用于解決組合優化問題。本文以遺傳算法為基礎設計GA-TM-ETS算法求解問題。以應急任務優先調度為原則,首先,設計任務合成、插入和替換算子完成應急任務向常規調度序列的插入過程;其次,考慮任務觀測收益、序列擾動和最短觀測時間等因素設計適應度函數,提高算法搜索速度;最后,根據編碼方式,設計基于組基因的交叉算子和變異算子,結合全局修復算子完成序列尋優。

3.1 編碼方式

本文采用十進制的編碼方式,以軌道為單元構造組基因,用組基因矩陣表示任務調度方案。

首先在調度周期內為衛星劃分軌道并編號,每個軌道編號后存放在該軌道上執行的任務序列,每條軌道及其任務序列組成一個組基因。所有組基因組成組基因矩陣,一個組基因矩陣代表一個完整的衛星調度方案。如圖8所示,調度周期內衛星共存在條軌道,在軌道2上最先執行任務16,最后執行任務47;在軌道上依次執行任務18、任務19和任務39。

圖8 編碼方式Fig.8 Encoding method

3.2 任務急切度

定義任務急切度確定應急任務安排順序。

急切度

應急任務的急切度urg反映任務等待觀測的迫切程度。使用任務觀測收益和從調度時刻開始到期望完成時間之內的時間窗數量衡量任務急切度,表示為

urg=TWF

(19)

其中,TWF為任務從調度時刻開始到期望完成時間之間的時間窗數量。在應急任務調度過程中,更傾向于優先調度收益更大或時間窗數量更少的任務。

3.3 任務合成算子

應急任務首先以任務合成的方式完成調度。任務合成算子操作步驟如下:

根據應急任務在各軌道上的觀測機會,將對有時間窗的軌道放入的候選軌道集COS中;

在COS中的軌道上確定能夠與合成觀測的在軌任務,獲得任務的候選合成任務集CMTS;

若CMTS不為空,轉步驟4;若為空,轉步驟6,考慮任務插入算子;

從CMTS中隨機選擇并刪除任務,將選中常規任務與應急任務執行合成操作,獲得合成任務;

判斷與在軌任務的沖突情況。若與前后任務不存在沖突,則直接將以任務合成方式插入;若存在沖突且沖突任務為常規任務時,將常規任務刪除后合成,更新調度序列;若存在沖突且沖突任務為應急任務,不執行合成,轉步驟3;

任務合成算子操作終止。

3.4 任務插入算子

當任務不能以合成方式插入時,利用任務插入算子完成調度。任務插入算子操作步驟如下：

在COS中的各個軌道中根據任務時間窗確定任務的可插入位置,獲得候選插入任務集CITS;

若CITS不為空,轉步驟3;若為空,轉步驟5,考慮任務替換算子;

從CITS中隨機選擇并刪除任務,執行任務插入操作,轉步驟4;

判斷與在軌任務的沖突情況。若與前后任務不存在沖突,則直接將插入;若存在沖突且沖突任務為常規任務,將常規任務刪除后再插入,并更新調度序列;若存在沖突且沖突任務為應急任務,不執行插入,轉步驟2;

任務插入算子操作終止。

3.5 任務替換算子

當任務合成算子和任務插入算子不能完成任務調度時,考慮任務替換算子。任務替換的目的是完成觀測收益更高的任務,被替換的任務暫時存放到該染色體的未完成任務集(unscheduled tasks list, UTL)中,等待重插入。任務替換算子操作步驟如下:

從COS中隨機選擇并刪除可觀測任務的軌道,執行任務替換,轉步驟2;

判斷與在軌任務的沖突情況。若與前后任務不存在沖突,則直接將以任務替換方式插入;若存在沖突且沖突任務為常規任務時,將常規任務刪除后替換,并更新調度序列;若存在沖突且沖突任務為應急任務,不執行替換;

任務替換算子操作終止。

3.6 適應度函數

遺傳算法中種群個體的優劣由適應度衡量。本文聯合任務觀測收益、序列擾動和最短觀測時間3個指標構造適應度函數,評判個體優劣。為說明最短觀測時間指標,定義無效觀測和有效重復觀測。

無效觀測

任務合成觀測時,各元任務時間窗間可能存在時間間隔。執行觀測時,傳感器在該時間間隔內成像并存儲數據,產生無效觀測,如圖9所示。

圖9 無效觀測Fig.9 Ineffective observation

有效重復觀測

任務合成觀測時,各元任務的時間窗間可能存在重疊。執行觀測時,衛星一次掃描可以完成對多個元任務片段的觀測,最大化利用衛星資源,產生有效重復觀測,如圖10所示。

圖10 有效重復觀測Fig.10 Effective repeated observation

當任務合成觀測時,應急任務對合成位置的選擇會直接影響衛星的成像時長。如圖11所示,應急任務可以和軌道上的任務或軌道上的任務合成觀測,合成后任務的觀測時長分別為和。因為<,則選擇與任務合成,在最短觀測時間內執行觀測,從而最小化無效觀測,最大化有效重復觀測,充分利用衛星資源。

圖11 最短觀測時間說明圖Fig.11 Diagram of minimum observation time

綜上,適應度函數設置下式所示：

Fitness=

(20)

兩條染色體比較時,總觀測時間更短,序列擾動更小,觀測總收益更大的染色體序列更優。

3.7 交叉算子

針對本文的編碼方式,設計組基因片段單點交叉方式執行染色體交叉操作。交叉策略是將選中的兩條父代染色體根據隨機選擇的軌道編號分為兩部分,交換后半部分組基因矩陣片段后刪除重復任務,并執行任務重插入操作,獲得子代染色體，如圖12所示。

圖12 染色體交叉Fig.12 Chromosome crossover

具體交叉步驟如下:

計算種群中各染色體的適應度值,將種群中染色體根據適應度值非升序排序,更新種群中染色體順序;

從種群的前半部分隨機選取待交叉的父代染色體F1,從整體種群中隨機選取待交叉的父代染色體F2;

隨機生成軌道編號;

以軌道為分割點,將F1分為矩陣片段F11和F12,將F2分為矩陣片段F21和F22;

在矩陣片段F22中刪除F11中已存在的任務,在F12中刪除F21中已存在的任務;

依次拼接矩陣片段F11和F22,獲得子代染色體z1;依次拼接矩陣片段F21和F12,獲得子代染色體z2;

從z1、z2的UTL中分別向染色體z1、z2中重新插入任務,最終獲得子代染色體Z1、Z2;

采用精英策略從四條染色體F1、F2、Z1、Z2中選擇適應度函數較小的兩條染色體放回種群中。

3.8 變異算子

基于軌道組基因設計變異算子。隨機選擇軌道圈次,將該圈次的任務進行變異。變異策略是將選中組基因上的所有任務重新放入該染色體的UTL中,與未完成任務一起重新插入,如圖13所示。

圖13 染色體變異Fig.13 Chromosome mutation

具體變異步驟如下:

在種群中隨機選取染色體F,在F中確定變異軌道編號;

將選中軌道上的任務放至該染色體的UTL中,清空選中軌道;

從UTL中向染色體中重新插入任務,獲得子代染色體Z;

采用精英策略從兩條染色體F和Z中選擇適應度函數較小的染色體放回種群中。

3.9 全局修復算子

前面任務的調度過程主要考慮各任務間時間窗的沖突關系,并未根據衛星軌道的全局約束對任務分配進行限制,可能存在不符合軌道存儲限制的不可行解。全局修復算子考慮衛星軌道整體約束,最終尋找最優解時,當在軌任務與軌道最大存儲限制出現沖突時,優先刪除具有更小收益的常規任務來消除沖突。

3.10 算法主要流程

GA-TM-ETS算法主要由初始種群的生成和種群序列尋優兩部分組成。

3.10.1 初始種群生成

應用任務合成、插入和替換算子將集合TE中的任務插入到初始調度序列可得到染色體,重復此過程即可獲得初始種群population。設初始種群數量為pop,初始調度序列為Seq。初始種群生成的算法如算法1所示。

初始種群生成算法

1 Initialize the set TE,pop,Seq;

2 Set popnum=1;

3 Calculateurgfor∈TE and sort TE by it from high to low;

4 for popnum=1 to pop do

5 for eachin TE do

6 ifand′in Seq satisfy the constraints (1)～(3) then

7 Merge task by task merging operator;

8 else ifand′in Seq satisfy

the constraints (4) and (5) then

9 Insert task by task insertion operator;

10 else ifand′in Seq satisfy the constraints (6) and (7) then

11 Replace task by task replacement operator;

12 end if

13 end for

14 end for

3.10.2 種群序列尋優

初始種群經過交叉變異尋優和全局修復算子修復過程獲得最終調度序列Chromosome*。設種群最大迭代次數為maxiter,種群序列尋優的算法如算法2所示。

種群序列尋優算法

1 Initialize the set population;

2 Set iter=0;

3 for iter=0 to maxiter do

4 Cross by crossover operator;

5 Mutate by mutation operator;

6 iter++;

7 end for

8 Repair by global repair operator;

9 Select and return Chromosome*

4 仿真實驗

本節通過對比實驗驗證GA-TM-ETS算法的有效性。實驗在Intel(R) Core(TM) i5-6500CPU處理器、16.0G內存、64 位 Windows7 環境運行,基于myeclipse2017編程環境采用java語言實現。

實驗中,初始調度序列采用遺傳算法生成。實驗利用仿真軟件模擬真實環境生成3顆衛星,調度周期為24小時,衛星參數設置如表1所示。隨機生成100、200、400個常規任務集合和20、40、60個應急任務集合,常規任務觀測收益在區間[0，1]內隨機生成,應急任務觀測收益在區間[1，2]內隨機生成。為避免數據偶然性,每種數據規模下分別對應生成3組數據執行實驗,每組數據算例運行30次并取平均值作為該組數據實驗結果,每種規模下的3個數據實驗結果取平均值得到最終該規模實驗結果,最終得到9組實驗。

表1 衛星參數信息Table 1 Satellite parameter information

由于多星調度問題的多變性和復雜性,各個科研團體在考慮不同的實際應用下進行研究,目前在該領域沒有公認的benchmark測試集。為驗證算法的有效性,本文進行3組對比實驗。首先,將不考慮合成機制的應急任務調度算法(genetic algorithm for emergency task scheduling,GA-ETS)與IDI算法對比,驗證本文設計的基礎算法的有效性;其次,將GA-TM-ETS算法和GA-ETS算法對比,證明合成策略在算法中的重要作用;最后,進行參數敏感性分析,確定各規模實驗中各參數值的最優組合。

4.1 算法有效性實驗

GA-ETS算法和IDI算法的共同點在于,兩算法中都不存在合成機制。為驗證基礎的GA-ETS算法的有效性,將GA-ETS算法和IDI算法對比,實驗結果如表2及圖14所示。

為使IDI算法更加適用于本文的研究背景,將算法做出如下修改:將衛星對任務的可見時間窗作為觀測時間窗,將應急任務根據優先級非降序排序并依次選擇任務,遍歷選中任務的時間窗,插入任務。

表2 GA-ETS算法和IDI算法結果Table 2 Results of GA-ETS algorithm and IDI algorithm

通過分析表2中兩算法收益列和圖14(a)可知,當常規任務規模分別為100、200、400時,隨著應急任務規模的增加,GA-ETS算法和IDI算法的觀測總收益都逐漸增加,且變化趨勢相同,說明GA-ETS算法作為GA-TM-ETS算法的基礎設計算法是有效的。表2最后一欄表示收益差值相對值,其計算公式為:收益差值相對值=(GA-ETS觀測收益-IDI觀測收益)/IDI觀測收益。依據計算結果可知,常規任務規模為100時,應急任務規模為20、40、60情況下GA-ETS算法的觀測收益比IDI算法分別提高12.57%、14.03%、14.30%,最高提高14.30%;常規任務規模為200時,應急任務規模為20情況下GA-ETS算法的觀測收益比IDI算法提高最多,最高提高10.41%;常規任務規模為400時,應急任務規模為20的情況下GA-ETS算法的觀測收益比IDI算法提高最多,最高提高9.55%。實驗結果表明GA-ETS算法優于IDI算法。

圖14 GA-ETS算法和IDI算法實驗結果對比Fig.14 Comparison of the experimental results of GA-ETS algorithm and IDI algorithm

擾動度量時,分別將任務刪除和任務移位的干擾量設置為1和0.5。根據表2中兩算法擾動列和圖14(b)分析可得, GA-ETS算法的調度擾動量不小于IDI算法,但擾動差值在區間(0,5.5)之內。在GA-ETS算法的觀測收益明顯大于IDI算法的條件下,擾動量的少量增加是可以接受的。

分析表2中兩算法運行時間列可知,IDI算法運行很快,大規模實驗下完成調度僅需約20 s。GA-ETS算法的交叉變異過程需要判斷各任務時間窗之間的沖突,消耗一定的時間成本,運行相對較慢,大規模實驗下完成調度需82.190 s。但在GA-ETS算法的觀測收益明顯大于IDI算法的條件下,運行時間的少量增加是可以接受的。

4.2 驗證合成機制的重要作用

GA-ETS算法融合任務合成機制后得到GA-TM-ETS算法。本節將GA-TM-ETS算法和GA-ETS算法對比,驗證合成機制在GA-TM-ETS算法中的重要作用,實驗結果如表3及圖15所示。

表3 GA-ETS算法和GA-TM-ETS算法結果Table 3 Results of GA-ETS algorithm and GA-TM-ETS algorithm

圖15 GA-TM-ETS算法和GA-ETS算法實驗結果對比Fig.15 Comparison of experimental results of GA-TM-ETS algorithm and GA-ETS algorithm

分析表3中兩算法收益列和圖15(a)可知,9組任務規模下,GA-TM-ETS算法獲得的觀測收益都明顯高于GA-ETS算法。其次,當常規任務規模為100時,應急任務規模為20、40、60情況下,GA-TM-ETS算法觀測收益分別超出GA-ETS算法43.66、68.25、118.12;當常規任務規模為200時,應急任務規模為20、40、60情況下,GA-TM-ETS算法觀測收益分別超出GA-ETS算法80.72、115.1、162.34;當常規任務規模為400時,應急任務規模為20、40、60情況下,GA-TM-ETS算法觀測收益分別超出GA-ETS算法151.59、196.80、238.92,即當常規任務規模不變時,隨著應急任務規模增大,GA-TM-ETS算法超出GA-ETS算法的觀測收益差值增大,說明任務合成機制在越大應急任務規模下效果越明顯。

分析表3中兩算法擾動列和圖15(b)可知,當常規任務數量為100和200時,GA-TM-ETS算法的擾動量大于GA-ETS算法,但差值在區間(0,3)內;當常規任務數量為400時,GA-TM-ETS算法的擾動量小于GA-ETS算法,且差值最大為5.9。此現象出現的原因可以解釋為:當任務間存在沖突時,任務合成機制的存在可以將沖突的常規任務與應急任務在原位置合成觀測或在其他位置合成觀測,減少對常規任務的拒絕或移位,有效減少對原序列的擾動量。但當常規任務數量為100和200時,任務合成機制對于減小擾動量的作用效果不明顯,當常規任務數量為400時減小擾動量的效果較明顯。

如表3中兩算法常規任務和應急任務完成數量列及圖15(c)和圖15(d)所示,同等任務規模下,GA-TM-ETS算法的常規任務和應急任務完成數量都遠大于GA-ETS算法。GA-TM-ETS算法能夠表現出良好性能的原因在于,合成策略有效避免了任務時間窗之間的沖突,將原本因存在時間窗沖突或姿態轉換時間不足而拒絕的任務合成觀測,且合成觀測具有聯合收益,最終在增加了任務觀測數量的基礎上,大大提高了任務觀測收益。

分析表3中兩算法運行時間列可知,9組任務規模下,GA-TM-ETS算法的最長運行時間不超過86 s,且算法調度的任務數量和獲得的觀測收益明顯好于GA-ETS算法,說明該算法可以在應急任務開始調度的較短時間內及時高質量完成調度。

4.3 參數敏感性分析

不同參數值的設置會直接影響算法性能。GA-TM-ETS算法以傳統遺傳算法為設計基礎,其中涉及少量參數,如交叉概率、種群規模等。不同的參數組合會獲得不同的調度結果,但各參數間存在多種參數組合,所有參數最優組合很難被找到。

啟發式算法可以獲得問題的較優解或以一定概率獲得問題的最優解,在求解的過程中,最好狀態是達到問題目標和時間成本之間的平衡狀態,犧牲大量的時間獲得更好的解的做法往往是不科學的。本文在9組任務規模下,采用控制變量法,在不同的參數組合下進行大量的實驗,分析不同任務規模下的參數敏感性,試圖找到任務觀測收益和消耗時間之間的平衡狀態。

圖16展示3種不同應急任務規模下,5種不同交叉概率和種群規模的組合實驗結果。分析圖16可知,無論在何種任務規模下,程序運行時間隨著種群規模的增大幾乎呈現線性增長,各個交叉概率的設置值對程序運行時間不會產生明顯影響。在不同的交叉概率下,隨著種群規模的增大,適應度值出現峰值。經實驗結果分析, GA-TM-ETS算法中參數最終設置為:應急任務規模為20時,交叉概率為0.80,種群規模為60;應急任務規模為40時,交叉概率為0.85,種群規模為80;應急任務規模為60時,交叉概率為0.80,種群規模為80。

圖16 GA-TM-ETS算法不同種群規模和交叉概率的參數敏感性分析Fig.16 Parameter sensitivity analysis of GA-TM-ETS algorithm with different population sizes and crossover probability

5 結 論

本文主要研究多星應急任務調度問題。首先,根據應急任務特點,考慮應急任務完成時間和觀測收益的關系,建立具有時間依賴性收益的合成任務數學規劃模型。其次,以遺傳算法為基礎設計GA-TM-ETS算法求解問題。算法以應急任務優先調度為原則,首先設計任務合成、插入和替換算子完成應急任務向常規調度序列的插入操作。再次，考慮任務觀測收益、序列擾動和最短觀測時間等因素設計適應度函數,提高算法搜索速度。然后，根據編碼方式,設計基于組基因的交叉算子和變異算子,結合全局修復算子完成序列尋優。最后,通過對比實驗對算法的性能進行分析和比較,結果表明GA-TM-ETS算法可以在保證觀測總收益且最小化對原調度序列的擾動的基礎上解決多星應急任務調度問題。

在未來工作中依舊存在許多待解決的問題:① 優化數學模型,比如增加用戶對成像衛星類型的要求約束和考慮成像質量的約束;② 考慮現實情況,在任務可見時間窗內考慮觀測時間窗的提前或延遲策略,增強任務調度的魯棒性。