靳 鵬, 唐曉茜,*

(1. 合肥工業(yè)大學(xué)管理學(xué)院, 安徽 合肥 230009; 2. 過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室, 安徽 合肥 230009)

0 引 言

對(duì)地觀測(cè)衛(wèi)星是空間范圍內(nèi)的一種成像資源,根據(jù)用戶對(duì)地球表面目標(biāo)的成像需求,利用星載傳感器,在滿足衛(wèi)星成像的約束條件下,對(duì)地球表面目標(biāo)進(jìn)行觀測(cè),獲取圖像信息。由于具有成像效果好、覆蓋區(qū)域廣且不受國(guó)界限制等優(yōu)點(diǎn),在環(huán)境監(jiān)測(cè)、資源探測(cè)、災(zāi)害預(yù)警、軍事偵探等領(lǐng)域發(fā)揮著重要作用。當(dāng)?shù)卣?、火?zāi)等緊急情況發(fā)生時(shí),充分利用衛(wèi)星資源對(duì)受災(zāi)區(qū)域成像已經(jīng)成為一種獲取圖像信息的重要手段,能夠?yàn)榫仍块T提供重要的決策信息支持。應(yīng)急任務(wù)的觀測(cè)會(huì)對(duì)原調(diào)度序列產(chǎn)生影響,如何設(shè)計(jì)高效的衛(wèi)星應(yīng)急任務(wù)調(diào)度方法,在保證觀測(cè)總收益的基礎(chǔ)上最小化對(duì)原調(diào)度序列的擾動(dòng)是多星應(yīng)急任務(wù)調(diào)度領(lǐng)域急需解決的問題。

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

衛(wèi)星對(duì)任務(wù)觀測(cè)成像需要滿足時(shí)間窗、姿態(tài)轉(zhuǎn)換時(shí)間、存儲(chǔ)限制等多方面約束。近年來,用戶的觀測(cè)需求量持續(xù)上漲,遠(yuǎn)大于衛(wèi)星資源負(fù)載能力,星上任務(wù)呈現(xiàn)飽和狀態(tài)。在盡量減少對(duì)初始調(diào)度序列擾動(dòng)的情況下完成應(yīng)急任務(wù)調(diào)度變得更加復(fù)雜。

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

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

應(yīng)用任務(wù)合成機(jī)制處理應(yīng)急任務(wù)的研究較少。文獻(xiàn)[7]側(cè)重于對(duì)應(yīng)急任務(wù)合成位置選擇的研究,不存在整體尋優(yōu)過程。文獻(xiàn)[32-34] 考慮應(yīng)急任務(wù)與常規(guī)任務(wù)合成的同時(shí)以最大化任務(wù)觀測(cè)收益和最小化序列擾動(dòng)為目標(biāo),設(shè)計(jì)啟發(fā)式算法完成應(yīng)急任務(wù)的動(dòng)態(tài)調(diào)度。這對(duì)原來任務(wù)序列的魯棒性要求較高,調(diào)度難度也較大。

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

1 問題描述

對(duì)地觀測(cè)衛(wèi)星應(yīng)急任務(wù)調(diào)度問題有以下描述。

給定一組衛(wèi)星,在調(diào)度周期內(nèi)存在軌道集合={,,…,,…,||},||為軌道數(shù)量。

本文以軌道作為資源的最小調(diào)度單元,任一衛(wèi)星軌道圈次的屬性可以用六元組<,span,,,,>表示。其中,表示軌道上傳感器視場(chǎng)角,span表示傳感器最長(zhǎng)開機(jī)時(shí)間,表示傳感器單位時(shí)間成像的存儲(chǔ)系數(shù),表示軌道最大存儲(chǔ)量,表示傳感器偏轉(zhuǎn)速率,表示傳感器姿態(tài)穩(wěn)定時(shí)間。

1.1 任務(wù)合成

衛(wèi)星以一定側(cè)擺角和時(shí)間窗對(duì)任務(wù)觀測(cè)成像時(shí)形成觀測(cè)條帶。在一個(gè)觀測(cè)條帶內(nèi),滿足某種約束條件下,將多個(gè)地理位置相近的任務(wù)同時(shí)觀測(cè)的過程為任務(wù)的合成觀測(cè)。如圖1所示,應(yīng)急任務(wù)和常規(guī)任務(wù)′滿足衛(wèi)星側(cè)擺角約束和傳感器單次最長(zhǎng)開機(jī)時(shí)間約束,可以在衛(wèi)星的一個(gè)觀測(cè)條帶內(nèi)合成觀測(cè)。

圖1 任務(wù)合成圖Fig.1 Diagram of task merging

111 側(cè)擺角約束

(1)

圖2 側(cè)擺角約束Fig.2 Swing angle constraint

(2)

112 單次最長(zhǎng)開機(jī)時(shí)間約束

(3)

圖3 最長(zhǎng)開機(jī)時(shí)間約束Fig.3 Maximum boot time constraint

如圖4所示,應(yīng)急任務(wù)和常規(guī)任務(wù)′滿足任務(wù)合成條件,且合成任務(wù)與前后在軌任務(wù)滿足時(shí)間窗約束和姿態(tài)轉(zhuǎn)換約束,則任務(wù)以任務(wù)合成方式執(zhí)行觀測(cè)。

圖4 任務(wù)合成Fig.4 Task merging

1.2 任務(wù)插入

(4)

(5)

如圖5所示,常規(guī)任務(wù)′和′+1之間存在足夠長(zhǎng)的空閑時(shí)間片段,應(yīng)急任務(wù)滿足任務(wù)插入式(4)和式(5),將其插入觀測(cè)。

圖5 任務(wù)插入Fig.5 Task insertion

1.3 任務(wù)替換

(6)

(7)

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

圖6 任務(wù)替換Fig.6 Task replacement

2 調(diào)度模型

2.1 完成時(shí)間-收益函數(shù)

(8)

圖7 應(yīng)急任務(wù)完成時(shí)間-收益Fig.7 Emergency task completion time-revenue

2.2 擾動(dòng)

應(yīng)急任務(wù)的插入可能會(huì)擾亂初始調(diào)度序列。本文對(duì)初始調(diào)度序列上的常規(guī)任務(wù)設(shè)計(jì)了兩種處理方式:刪除任務(wù)或更換任務(wù)執(zhí)行位置。設(shè)(=1,2)為任務(wù)第種處理方式的影響權(quán)重,當(dāng)刪除任務(wù)時(shí)取1,當(dāng)更換任務(wù)執(zhí)行位置時(shí)取2,并且>。

考慮常規(guī)任務(wù)調(diào)度序列Seq,應(yīng)急任務(wù)插入后,軌道上的擾動(dòng)表示為

(9)

其中,turb(′,)定義為

(10)

2.3 數(shù)學(xué)規(guī)劃模型

數(shù)學(xué)規(guī)劃模型以合成任務(wù)為描述對(duì)象。設(shè)任務(wù)集={,,…,},為待觀測(cè)的合成任務(wù)數(shù)量。當(dāng)待觀測(cè)任務(wù)中只包含一個(gè)元任務(wù)時(shí),該任務(wù)也被看作合成任務(wù)。

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

本文的調(diào)度目標(biāo)優(yōu)先考慮最大化任務(wù)觀測(cè)總收益:

(11)

(12)

另一個(gè)調(diào)度目標(biāo)考慮對(duì)原任務(wù)調(diào)度序列擾動(dòng)最小:

(13)

232 約束條件

每個(gè)任務(wù)只能被觀測(cè)一次:

(14)

任務(wù)的觀測(cè)結(jié)束時(shí)間一定不小于任務(wù)觀測(cè)開始時(shí)間:

(15)

兩連續(xù)觀測(cè)任務(wù)間的時(shí)間間隔至少滿足姿態(tài)轉(zhuǎn)換時(shí)間約束,其中,是一個(gè)很大的正數(shù):

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

(16)

應(yīng)急任務(wù)觀測(cè)完成時(shí)間具體表示為

(17)

軌道上任務(wù)成像的存儲(chǔ)空間不能超過單軌最大存儲(chǔ)限制:

(18)

因此,多星應(yīng)急任務(wù)調(diào)度問題可表示為上述具有時(shí)間依賴性收益的數(shù)學(xué)規(guī)劃模型。

3 算法設(shè)計(jì)

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

3.1 編碼方式

本文采用十進(jìn)制的編碼方式,以軌道為單元構(gòu)造組基因,用組基因矩陣表示任務(wù)調(diào)度方案。

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

圖8 編碼方式Fig.8 Encoding method

3.2 任務(wù)急切度

定義任務(wù)急切度確定應(yīng)急任務(wù)安排順序。

急切度

應(yīng)急任務(wù)的急切度urg反映任務(wù)等待觀測(cè)的迫切程度。使用任務(wù)觀測(cè)收益和從調(diào)度時(shí)刻開始到期望完成時(shí)間之內(nèi)的時(shí)間窗數(shù)量衡量任務(wù)急切度,表示為

urg=TWF

(19)

其中,TWF為任務(wù)從調(diào)度時(shí)刻開始到期望完成時(shí)間之間的時(shí)間窗數(shù)量。在應(yīng)急任務(wù)調(diào)度過程中,更傾向于優(yōu)先調(diào)度收益更大或時(shí)間窗數(shù)量更少的任務(wù)。

3.3 任務(wù)合成算子

應(yīng)急任務(wù)首先以任務(wù)合成的方式完成調(diào)度。任務(wù)合成算子操作步驟如下:

根據(jù)應(yīng)急任務(wù)在各軌道上的觀測(cè)機(jī)會(huì),將對(duì)有時(shí)間窗的軌道放入的候選軌道集COS中;

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

若CMTS不為空,轉(zhuǎn)步驟4;若為空,轉(zhuǎn)步驟6,考慮任務(wù)插入算子;

從CMTS中隨機(jī)選擇并刪除任務(wù),將選中常規(guī)任務(wù)與應(yīng)急任務(wù)執(zhí)行合成操作,獲得合成任務(wù);

判斷與在軌任務(wù)的沖突情況。若與前后任務(wù)不存在沖突,則直接將以任務(wù)合成方式插入;若存在沖突且沖突任務(wù)為常規(guī)任務(wù)時(shí),將常規(guī)任務(wù)刪除后合成,更新調(diào)度序列;若存在沖突且沖突任務(wù)為應(yīng)急任務(wù),不執(zhí)行合成,轉(zhuǎn)步驟3;

任務(wù)合成算子操作終止。

3.4 任務(wù)插入算子

當(dāng)任務(wù)不能以合成方式插入時(shí),利用任務(wù)插入算子完成調(diào)度。任務(wù)插入算子操作步驟如下：

在COS中的各個(gè)軌道中根據(jù)任務(wù)時(shí)間窗確定任務(wù)的可插入位置,獲得候選插入任務(wù)集CITS;

若CITS不為空,轉(zhuǎn)步驟3;若為空,轉(zhuǎn)步驟5,考慮任務(wù)替換算子;

從CITS中隨機(jī)選擇并刪除任務(wù),執(zhí)行任務(wù)插入操作,轉(zhuǎn)步驟4;

判斷與在軌任務(wù)的沖突情況。若與前后任務(wù)不存在沖突,則直接將插入;若存在沖突且沖突任務(wù)為常規(guī)任務(wù),將常規(guī)任務(wù)刪除后再插入,并更新調(diào)度序列;若存在沖突且沖突任務(wù)為應(yīng)急任務(wù),不執(zhí)行插入,轉(zhuǎn)步驟2;

任務(wù)插入算子操作終止。

3.5 任務(wù)替換算子

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

從COS中隨機(jī)選擇并刪除可觀測(cè)任務(wù)的軌道,執(zhí)行任務(wù)替換,轉(zhuǎn)步驟2;

判斷與在軌任務(wù)的沖突情況。若與前后任務(wù)不存在沖突,則直接將以任務(wù)替換方式插入;若存在沖突且沖突任務(wù)為常規(guī)任務(wù)時(shí),將常規(guī)任務(wù)刪除后替換,并更新調(diào)度序列;若存在沖突且沖突任務(wù)為應(yīng)急任務(wù),不執(zhí)行替換;

任務(wù)替換算子操作終止。

3.6 適應(yīng)度函數(shù)

遺傳算法中種群個(gè)體的優(yōu)劣由適應(yīng)度衡量。本文聯(lián)合任務(wù)觀測(cè)收益、序列擾動(dòng)和最短觀測(cè)時(shí)間3個(gè)指標(biāo)構(gòu)造適應(yīng)度函數(shù),評(píng)判個(gè)體優(yōu)劣。為說明最短觀測(cè)時(shí)間指標(biāo),定義無效觀測(cè)和有效重復(fù)觀測(cè)。

無效觀測(cè)

任務(wù)合成觀測(cè)時(shí),各元任務(wù)時(shí)間窗間可能存在時(shí)間間隔。執(zhí)行觀測(cè)時(shí),傳感器在該時(shí)間間隔內(nèi)成像并存儲(chǔ)數(shù)據(jù),產(chǎn)生無效觀測(cè),如圖9所示。

圖9 無效觀測(cè)Fig.9 Ineffective observation

有效重復(fù)觀測(cè)

任務(wù)合成觀測(cè)時(shí),各元任務(wù)的時(shí)間窗間可能存在重疊。執(zhí)行觀測(cè)時(shí),衛(wèi)星一次掃描可以完成對(duì)多個(gè)元任務(wù)片段的觀測(cè),最大化利用衛(wèi)星資源,產(chǎn)生有效重復(fù)觀測(cè),如圖10所示。

圖10 有效重復(fù)觀測(cè)Fig.10 Effective repeated observation

當(dāng)任務(wù)合成觀測(cè)時(shí),應(yīng)急任務(wù)對(duì)合成位置的選擇會(huì)直接影響衛(wèi)星的成像時(shí)長(zhǎng)。如圖11所示,應(yīng)急任務(wù)可以和軌道上的任務(wù)或軌道上的任務(wù)合成觀測(cè),合成后任務(wù)的觀測(cè)時(shí)長(zhǎng)分別為和。因?yàn)?,則選擇與任務(wù)合成,在最短觀測(cè)時(shí)間內(nèi)執(zhí)行觀測(cè),從而最小化無效觀測(cè),最大化有效重復(fù)觀測(cè),充分利用衛(wèi)星資源。

圖11 最短觀測(cè)時(shí)間說明圖Fig.11 Diagram of minimum observation time

綜上,適應(yīng)度函數(shù)設(shè)置下式所示：

Fitness=

(20)

兩條染色體比較時(shí),總觀測(cè)時(shí)間更短,序列擾動(dòng)更小,觀測(cè)總收益更大的染色體序列更優(yōu)。

3.7 交叉算子

針對(duì)本文的編碼方式,設(shè)計(jì)組基因片段單點(diǎn)交叉方式執(zhí)行染色體交叉操作。交叉策略是將選中的兩條父代染色體根據(jù)隨機(jī)選擇的軌道編號(hào)分為兩部分,交換后半部分組基因矩陣片段后刪除重復(fù)任務(wù),并執(zhí)行任務(wù)重插入操作,獲得子代染色體，如圖12所示。

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

具體交叉步驟如下:

計(jì)算種群中各染色體的適應(yīng)度值,將種群中染色體根據(jù)適應(yīng)度值非升序排序,更新種群中染色體順序;

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

隨機(jī)生成軌道編號(hào);

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

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

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

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

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

3.8 變異算子

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

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

具體變異步驟如下:

在種群中隨機(jī)選取染色體F,在F中確定變異軌道編號(hào);

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

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

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

3.9 全局修復(fù)算子

前面任務(wù)的調(diào)度過程主要考慮各任務(wù)間時(shí)間窗的沖突關(guān)系,并未根據(jù)衛(wèi)星軌道的全局約束對(duì)任務(wù)分配進(jìn)行限制,可能存在不符合軌道存儲(chǔ)限制的不可行解。全局修復(fù)算子考慮衛(wèi)星軌道整體約束,最終尋找最優(yōu)解時(shí),當(dāng)在軌任務(wù)與軌道最大存儲(chǔ)限制出現(xiàn)沖突時(shí),優(yōu)先刪除具有更小收益的常規(guī)任務(wù)來消除沖突。

3.10 算法主要流程

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

3.10.1 初始種群生成

應(yīng)用任務(wù)合成、插入和替換算子將集合TE中的任務(wù)插入到初始調(diào)度序列可得到染色體,重復(fù)此過程即可獲得初始種群population。設(shè)初始種群數(shù)量為pop,初始調(diào)度序列為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 種群序列尋優(yōu)

初始種群經(jīng)過交叉變異尋優(yōu)和全局修復(fù)算子修復(fù)過程獲得最終調(diào)度序列Chromosome*。設(shè)種群最大迭代次數(shù)為maxiter,種群序列尋優(yōu)的算法如算法2所示。

種群序列尋優(yōu)算法

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 仿真實(shí)驗(yàn)

本節(jié)通過對(duì)比實(shí)驗(yàn)驗(yàn)證GA-TM-ETS算法的有效性。實(shí)驗(yàn)在Intel(R) Core(TM) i5-6500CPU處理器、16.0G內(nèi)存、64 位 Windows7 環(huán)境運(yùn)行,基于myeclipse2017編程環(huán)境采用java語(yǔ)言實(shí)現(xiàn)。

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

表1 衛(wèi)星參數(shù)信息Table 1 Satellite parameter information

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

4.1 算法有效性實(shí)驗(yàn)

GA-ETS算法和IDI算法的共同點(diǎn)在于,兩算法中都不存在合成機(jī)制。為驗(yàn)證基礎(chǔ)的GA-ETS算法的有效性,將GA-ETS算法和IDI算法對(duì)比,實(shí)驗(yàn)結(jié)果如表2及圖14所示。

為使IDI算法更加適用于本文的研究背景,將算法做出如下修改:將衛(wèi)星對(duì)任務(wù)的可見時(shí)間窗作為觀測(cè)時(shí)間窗,將應(yīng)急任務(wù)根據(jù)優(yōu)先級(jí)非降序排序并依次選擇任務(wù),遍歷選中任務(wù)的時(shí)間窗,插入任務(wù)。

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

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

圖14 GA-ETS算法和IDI算法實(shí)驗(yàn)結(jié)果對(duì)比Fig.14 Comparison of the experimental results of GA-ETS algorithm and IDI algorithm

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

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

4.2 驗(yàn)證合成機(jī)制的重要作用

GA-ETS算法融合任務(wù)合成機(jī)制后得到GA-TM-ETS算法。本節(jié)將GA-TM-ETS算法和GA-ETS算法對(duì)比,驗(yàn)證合成機(jī)制在GA-TM-ETS算法中的重要作用,實(shí)驗(yàn)結(jié)果如表3及圖15所示。

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

圖15 GA-TM-ETS算法和GA-ETS算法實(shí)驗(yàn)結(jié)果對(duì)比Fig.15 Comparison of experimental results of GA-TM-ETS algorithm and GA-ETS algorithm

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

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

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

分析表3中兩算法運(yùn)行時(shí)間列可知,9組任務(wù)規(guī)模下,GA-TM-ETS算法的最長(zhǎng)運(yùn)行時(shí)間不超過86 s,且算法調(diào)度的任務(wù)數(shù)量和獲得的觀測(cè)收益明顯好于GA-ETS算法,說明該算法可以在應(yīng)急任務(wù)開始調(diào)度的較短時(shí)間內(nèi)及時(shí)高質(zhì)量完成調(diào)度。

4.3 參數(shù)敏感性分析

不同參數(shù)值的設(shè)置會(huì)直接影響算法性能。GA-TM-ETS算法以傳統(tǒng)遺傳算法為設(shè)計(jì)基礎(chǔ),其中涉及少量參數(shù),如交叉概率、種群規(guī)模等。不同的參數(shù)組合會(huì)獲得不同的調(diào)度結(jié)果,但各參數(shù)間存在多種參數(shù)組合,所有參數(shù)最優(yōu)組合很難被找到。

啟發(fā)式算法可以獲得問題的較優(yōu)解或以一定概率獲得問題的最優(yōu)解,在求解的過程中,最好狀態(tài)是達(dá)到問題目標(biāo)和時(shí)間成本之間的平衡狀態(tài),犧牲大量的時(shí)間獲得更好的解的做法往往是不科學(xué)的。本文在9組任務(wù)規(guī)模下,采用控制變量法,在不同的參數(shù)組合下進(jìn)行大量的實(shí)驗(yàn),分析不同任務(wù)規(guī)模下的參數(shù)敏感性,試圖找到任務(wù)觀測(cè)收益和消耗時(shí)間之間的平衡狀態(tài)。

圖16展示3種不同應(yīng)急任務(wù)規(guī)模下,5種不同交叉概率和種群規(guī)模的組合實(shí)驗(yàn)結(jié)果。分析圖16可知,無論在何種任務(wù)規(guī)模下,程序運(yùn)行時(shí)間隨著種群規(guī)模的增大幾乎呈現(xiàn)線性增長(zhǎng),各個(gè)交叉概率的設(shè)置值對(duì)程序運(yùn)行時(shí)間不會(huì)產(chǎn)生明顯影響。在不同的交叉概率下,隨著種群規(guī)模的增大,適應(yīng)度值出現(xiàn)峰值。經(jīng)實(shí)驗(yàn)結(jié)果分析, GA-TM-ETS算法中參數(shù)最終設(shè)置為:應(yīng)急任務(wù)規(guī)模為20時(shí),交叉概率為0.80,種群規(guī)模為60;應(yīng)急任務(wù)規(guī)模為40時(shí),交叉概率為0.85,種群規(guī)模為80;應(yīng)急任務(wù)規(guī)模為60時(shí),交叉概率為0.80,種群規(guī)模為80。

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

5 結(jié) 論

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

在未來工作中依舊存在許多待解決的問題:① 優(yōu)化數(shù)學(xué)模型,比如增加用戶對(duì)成像衛(wèi)星類型的要求約束和考慮成像質(zhì)量的約束;② 考慮現(xiàn)實(shí)情況,在任務(wù)可見時(shí)間窗內(nèi)考慮觀測(cè)時(shí)間窗的提前或延遲策略,增強(qiáng)任務(wù)調(diào)度的魯棒性。