基于改進(jìn)DE算法的敏捷成像衛(wèi)星前攝式調(diào)度

李志亮, 李小將, 張東來(lái)

(1. 航天工程大學(xué)研究生院, 北京 101416; 2. 航天工程大學(xué)宇航科學(xué)與技術(shù)系, 北京 101416; 3. 酒泉衛(wèi)星發(fā)射中心, 甘肅 酒泉 732750)

0 引 言

敏捷成像衛(wèi)星與傳統(tǒng)成像衛(wèi)星相比具有滾動(dòng)、俯仰和偏航姿態(tài)機(jī)動(dòng)性能,對(duì)地觀測(cè)能力更強(qiáng),任務(wù)沖突的解決方式更多,已成為新型衛(wèi)星發(fā)展的重要方向[1]。有效的規(guī)劃和調(diào)度是敏捷成像衛(wèi)星發(fā)揮其優(yōu)勢(shì)的重要支撐,也是國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)問題。目前,多數(shù)研究[1-4]在確定條件下展開,即假設(shè)與調(diào)度相關(guān)的信息都是確定的。然而不確定因素在敏捷成像衛(wèi)星任務(wù)調(diào)度中時(shí)刻存在,并且影響調(diào)度方案的執(zhí)行。文獻(xiàn)[5]總結(jié)了4種典型的不確定因素,包括新任務(wù)的到達(dá)、目標(biāo)觀測(cè)和數(shù)傳機(jī)會(huì)的變化、衛(wèi)星資源狀態(tài)的不確定性、任務(wù)屬性的變化。為應(yīng)對(duì)不確定因素的影響,許多學(xué)者研究了前攝式調(diào)度方法,前攝式調(diào)度[6]是指在調(diào)度之初預(yù)先考慮不確定因素,將其作為先驗(yàn)知識(shí)引進(jìn)調(diào)度中,生成適應(yīng)性或魯棒性調(diào)度方案。有效地表示不確定因素并構(gòu)建魯棒性指標(biāo)是建立前攝式調(diào)度魯棒模型的關(guān)鍵。文獻(xiàn)[7]基于隨機(jī)云層預(yù)測(cè)模型研究了EO-1衛(wèi)星的魯棒性規(guī)劃問題。文獻(xiàn)[8]針對(duì)云層覆蓋的不確定因素,提出一種基于鄰域的魯棒性指標(biāo),建立了約束滿足模型并采用基于分級(jí)優(yōu)化策略的隨機(jī)變鄰域禁忌搜索算法進(jìn)行求解。文獻(xiàn)[9]在文獻(xiàn)[8]基礎(chǔ)上,增加了總?cè)蝿?wù)執(zhí)行時(shí)間指標(biāo),建立了多目標(biāo)魯棒調(diào)度模型,采用NSGA-Ⅱ算法求解。文獻(xiàn)[10]將總時(shí)間重疊度和總?cè)蝿?wù)執(zhí)行時(shí)間作為魯棒性指標(biāo),建立了多目標(biāo)魯棒性模型,同樣采用NSGA-Ⅱ算法求解。文獻(xiàn)[11]考慮將任務(wù)調(diào)度到多個(gè)可見窗口以增加觀測(cè)成功的概率,構(gòu)建了魯棒模型。文獻(xiàn)[12]考慮任務(wù)間衛(wèi)星姿態(tài)轉(zhuǎn)換約束和重要時(shí)間窗預(yù)留規(guī)則,提出一種基于資源預(yù)留的魯棒性任務(wù)規(guī)劃方法。

上述研究中,文獻(xiàn)[7-12]均沒有考慮衛(wèi)星資源失效對(duì)調(diào)度的影響,不能滿足衛(wèi)星資源狀態(tài)不確定條件下調(diào)度系統(tǒng)具有較強(qiáng)魯棒性的需求。此外,觀測(cè)任務(wù)的選擇、排序以及觀測(cè)時(shí)間的確定增加敏捷成像衛(wèi)星前攝式調(diào)度求解的復(fù)雜性,傳統(tǒng)求解算法[9-10]難以適用。

針對(duì)以往研究的不足,本文考慮衛(wèi)星資源失效、應(yīng)急任務(wù)加入兩類不確定因素,構(gòu)建了期望收益和松弛時(shí)間兩個(gè)魯棒性指標(biāo),將這兩類指標(biāo)作為優(yōu)化目標(biāo)構(gòu)建了前攝式調(diào)度魯棒模型,針對(duì)該模型的多目標(biāo)優(yōu)化特性,設(shè)計(jì)了一種多目標(biāo)離散差分進(jìn)化求解算法。并通過仿真計(jì)算驗(yàn)證了算法的優(yōu)越性。

1 前攝式調(diào)度魯棒模型

敏捷成像衛(wèi)星觀測(cè)任務(wù)的執(zhí)行伴隨著兩類主要的不確定因素:衛(wèi)星資源失效和應(yīng)急任務(wù)加入。前攝式調(diào)度是應(yīng)對(duì)不確定因素的重要方法,敏捷成像衛(wèi)星前攝式調(diào)度是指將衛(wèi)星資源失效概率、任務(wù)執(zhí)行主從窗口等信息作為先驗(yàn)知識(shí),構(gòu)建兼顧收益和魯棒性的優(yōu)化目標(biāo),同時(shí)結(jié)合衛(wèi)星資源和任務(wù)執(zhí)行約束條件,將有限的衛(wèi)星資源分配給多個(gè)觀測(cè)任務(wù),并確定任務(wù)執(zhí)行時(shí)間,生成魯棒性調(diào)度方案。本文首先構(gòu)建期望收益、松弛時(shí)間兩個(gè)魯棒性指標(biāo),進(jìn)而建立前攝式調(diào)度魯棒模型。

1.1 魯棒性指標(biāo)構(gòu)建

本文考慮的魯棒性指標(biāo)包括期望收益和松弛時(shí)間。

1.1.1 期望收益

衛(wèi)星資源失效具有很強(qiáng)的隨機(jī)性,其發(fā)生難以預(yù)測(cè)。文獻(xiàn)[13]假設(shè)某一時(shí)刻至多一顆衛(wèi)星失效,且失效事件相互獨(dú)立,但是沒有給出失效概率計(jì)算方法。文獻(xiàn)[14]假設(shè)機(jī)器故障概率與工作時(shí)間呈正相關(guān),對(duì)機(jī)器故障概率進(jìn)行了描述。借鑒該描述,本文增加空閑時(shí)間失效概率,假設(shè)衛(wèi)星資源失效滿足指數(shù)分布,采用下式計(jì)算衛(wèi)星失效概率:

(1)

式中,pn(t)表示t時(shí)刻衛(wèi)星sn失效的概率;rth表示衛(wèi)星sn第h次失效后維修結(jié)束時(shí)間,且rth≥0,調(diào)度初始時(shí)刻,記rth=0；FTl表示衛(wèi)星sn在[rth,t]內(nèi)的第l個(gè)空閑時(shí)間段;tsFTl和teFTl表示該時(shí)間段的起止時(shí)間;NFT表示[rth,t]內(nèi)空閑時(shí)間段的數(shù)量;AWTn表示衛(wèi)星sn的平均正常工作時(shí)間;ARTn表示衛(wèi)星sn的平均維修時(shí)間。

(2)

考慮了衛(wèi)星資源失效的概率,以及任務(wù)執(zhí)行的潛在可用從窗口,本文采用下式表示任務(wù)ti的期望收益:

(3)

1.1.2 松弛時(shí)間

研究表明調(diào)度方案中預(yù)留松弛時(shí)間能夠吸收任務(wù)變化帶來(lái)的擾動(dòng),增強(qiáng)調(diào)度的魯棒性[15]。借鑒文獻(xiàn)[15]對(duì)松弛時(shí)間的定義,本文將敏捷成像衛(wèi)星前攝式調(diào)度中的松弛時(shí)間定義為:設(shè)任務(wù)ti、tj為相鄰任務(wù),松弛時(shí)間是指從任務(wù)ti到tj的姿態(tài)轉(zhuǎn)換結(jié)束到任務(wù)tj開始觀測(cè)的時(shí)間段,描述如下式:

slackij=otj-oti-di-trij-tst

(4)

式中,oti、otj分別表示ti、tj的開始觀測(cè)時(shí)間;di表示ti的觀測(cè)時(shí)長(zhǎng);trij表示衛(wèi)星從ti到tj的姿態(tài)機(jī)動(dòng)時(shí)間;tst表示衛(wèi)星姿態(tài)機(jī)動(dòng)穩(wěn)定時(shí)間。

1.2 魯棒模型描述

本文在敏捷成像衛(wèi)星調(diào)度領(lǐng)域經(jīng)典文獻(xiàn)[1]的基礎(chǔ)上進(jìn)行合理擴(kuò)展,考慮多顆衛(wèi)星多個(gè)軌道圈次、任務(wù)間姿態(tài)轉(zhuǎn)換、以及星上存儲(chǔ)和能量等現(xiàn)實(shí)條件,從以下4個(gè)方面描述模型。

1.2.1 參數(shù)定義

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

表1 相關(guān)參數(shù)定義

1.2.2 決策變量

本文采用的決策變量包括兩個(gè):任務(wù)ti是否被觀測(cè),任務(wù)ti和tj是否為相鄰任務(wù),描述如下式:

(6)

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

根據(jù)文中提出的期望收益和松弛時(shí)間指標(biāo),敏捷成像衛(wèi)星前攝式調(diào)度魯棒模型的優(yōu)化目標(biāo)為最大化調(diào)度期望收益和總松弛時(shí)間,其表達(dá)式為

(7)

(8)

式中,F1表示最大化調(diào)度期望收益;F2表示最大化總松弛時(shí)間。

1.2.4 約束條件

考慮任務(wù)間姿態(tài)轉(zhuǎn)換約束、星上存儲(chǔ)和能量約束等,本文模型包括以下5方面的約束條件:

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

(9)

(10)

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

(11)

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

?ti,tj∈T,i≠j:

(12)

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

(13)

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

?sn∈S,?k∈OBn,?ti,tj∈T,i≠j:

(14)

上述模型將調(diào)度期望收益和總松弛時(shí)間作為優(yōu)化目標(biāo),同時(shí)考慮了衛(wèi)星資源和觀測(cè)任務(wù)的多重復(fù)雜約束,是較為復(fù)雜的多目標(biāo)優(yōu)化模型,本文采用多目標(biāo)離散差分進(jìn)化算法進(jìn)行求解。

2 MDDE求解算法

敏捷成像衛(wèi)星前攝式調(diào)度魯棒模型的求解是一個(gè)多目標(biāo)優(yōu)化問題。NSGA-Ⅱ算法在多目標(biāo)優(yōu)化上取得了不錯(cuò)的效果[9,16],同時(shí),NSGA-Ⅱ算法在尋優(yōu)中容易陷入局部最優(yōu),而且基于擁擠距離的多樣性評(píng)價(jià)準(zhǔn)則沒有考慮目標(biāo)函數(shù)值階數(shù)的差別,容易出現(xiàn)多個(gè)解聚集的情況。本文考慮差分進(jìn)化的全局探索優(yōu)勢(shì)[17]和擾動(dòng)操作的局部搜索能力,從離散差分進(jìn)化、外部存檔更新策略、Pareto解集的評(píng)價(jià)方面設(shè)計(jì)MDDE求解算法,并給出了算法的實(shí)現(xiàn)步驟。

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

離散差分進(jìn)化基本思路是首先采用離散形式對(duì)解進(jìn)行編碼,然后生成算法的初始種群,進(jìn)而采用變異、交叉、選擇算子得到下一代個(gè)體,通過競(jìng)爭(zhēng)獲得解空間內(nèi)更好的解。

解的編碼和初始種群生成是離散差分進(jìn)化的基礎(chǔ)。對(duì)于解的編碼,本文根據(jù)任務(wù)執(zhí)行順序采用自然數(shù)編碼方式,建立衛(wèi)星與任務(wù)的對(duì)應(yīng)關(guān)系,例如,x=[3 5 1 0 2 4 9 0 6 8 7],其中數(shù)字0用以區(qū)分不同的衛(wèi)星。對(duì)于初始種群的生成,本文在貪婪算法[1]的基礎(chǔ)上,增加兩個(gè)隨機(jī)因素:隨機(jī)選擇衛(wèi)星軌道圈次、輪盤賭法選擇候選任務(wù),采用隨機(jī)貪婪算法(random greedy algorithm,RGA)生成規(guī)模為NP的初始種群。

2.1.1 變異算子

(15)

對(duì)于變異個(gè)體的產(chǎn)生,DesCons[18]、InsertMut[19]等操作取得了不錯(cuò)的尋優(yōu)效果,但是這些操作所針對(duì)的調(diào)度問題沒有任務(wù)執(zhí)行的時(shí)間窗口約束,不能被本文直接采用。因此,本文提出適用于敏捷成像衛(wèi)星調(diào)度問題的DC操作和F操作。

DC操作的基本思路是首先從每顆衛(wèi)星的任務(wù)序列中隨機(jī)刪除比例為dps的任務(wù),dps∈(0,1),然后從未安排的任務(wù)集合中隨機(jī)選擇比例為cps的任務(wù),將選擇的任務(wù)按照調(diào)度約束條件插入到現(xiàn)有序列中,得到變異個(gè)體。

F操作的基本思路是判斷相鄰任務(wù)間的松弛時(shí)間是否大于閾值MinD·slc,MinD表示所有任務(wù)的最小觀測(cè)時(shí)長(zhǎng),slc表示擾動(dòng)強(qiáng)度,slc∈[1,10],如果小于MinD·slc,則刪除相鄰任務(wù)中wi/di較小的任務(wù),得到變異個(gè)體。

2.1.2 交叉算子

根據(jù)離散差分進(jìn)化的機(jī)理,試驗(yàn)個(gè)體可采用下式獲得[19]:

(16)

基于塊結(jié)構(gòu)的整體移動(dòng)策略[19]是一種有效的試驗(yàn)個(gè)體產(chǎn)生操作。在敏捷成像衛(wèi)星調(diào)度問題中,由于時(shí)間窗口約束,任務(wù)序列同樣具有塊結(jié)構(gòu)特征,但是塊結(jié)構(gòu)的整體移動(dòng)容易產(chǎn)生不可行解。為此,本文提出一種考慮局部修復(fù)的CR操作,基本思路是對(duì)于每顆衛(wèi)星的任務(wù)序列,隨機(jī)選擇一個(gè)切點(diǎn),計(jì)算切點(diǎn)處任務(wù)的觀測(cè)結(jié)束時(shí)間,將滿足姿態(tài)轉(zhuǎn)換的切點(diǎn)右側(cè)任務(wù)序列進(jìn)行交換,然后刪除交換后任務(wù)序列中重復(fù)的任務(wù),得到試驗(yàn)個(gè)體。

2.1.3 選擇算子

(17)

2.2 外部存檔更新策略

為保留算法進(jìn)化中優(yōu)質(zhì)解,本文采用外部存檔保存搜索到的非支配解,設(shè)外部存檔為EA,EA={ea1,ea2,…,eaNE},NE表示EA的規(guī)模,每進(jìn)化一代,EA根據(jù)當(dāng)前新解y進(jìn)行更新。同時(shí),為避免EA中非支配解過于集中,引進(jìn)個(gè)體間的歸一化鄰域距離,當(dāng)EA的規(guī)模大于NP時(shí),根據(jù)歸一化鄰域距離刪除擁擠的解,以保持解的多樣性。

對(duì)于兩個(gè)目標(biāo)函數(shù)的多目標(biāo)優(yōu)化問題,設(shè)兩個(gè)目標(biāo)函數(shù)分別為f1(·)和f2(·),根據(jù)Pareto解集的定義,EA中任意兩個(gè)解互相不構(gòu)成支配關(guān)系,即對(duì)于?eak,eak+1∈EA,若f1(eak)f2(eak+1),因此將EA中所有解按照f1(·)函數(shù)值升序排列時(shí),其f2(·)函數(shù)值為降序排列。y與EA的相對(duì)關(guān)系如圖1所示。

圖1 新解y與外部存檔EA的相對(duì)關(guān)系Fig.1 Relative relationship between new solution y and external archive EA

由圖1可知,EA的更新包括4種情況:①當(dāng)y與EA的每個(gè)解均互不支配時(shí),將y加入EA;②當(dāng)y支配EA的部分解時(shí),將被支配的解從EA刪除,并將y加入EA;③當(dāng)y支配EA的全部解時(shí),將EA的所有解刪除,并將y加入EA;④當(dāng)y被EA的任一解支配時(shí),則不更新EA。

為保持EA中非支配解的多樣性,需量化評(píng)價(jià)解之間的擁擠程度,文獻(xiàn)[16]提出一種擁擠距離計(jì)算公式,該公式具有簡(jiǎn)單高效的計(jì)算特點(diǎn),但是沒有考慮目標(biāo)函數(shù)值階數(shù)的差別,容易出現(xiàn)多個(gè)解聚集的情況。為此,本文在計(jì)算相鄰解的距離時(shí)對(duì)目標(biāo)函數(shù)值進(jìn)行歸一化處理,稱之為歸一化鄰域距離,其計(jì)算公式為

(18)

當(dāng)外部存檔超過一定規(guī)模時(shí),需根據(jù)歸一化鄰域距離計(jì)算出外部存檔中最擁擠的解,將EA中所有解的歸一化鄰域距離記為集合ND,ND={nd1,nd2,…,ndNE-1},設(shè)ND中最小的距離為ndk,比較ndk左側(cè)和右側(cè)的鄰域,若ndk-1ndk+1,則eak+1為最擁擠的解,若ndk-1=ndk+1,則需進(jìn)一步向兩側(cè)擴(kuò)展,直至確定最擁擠的解,并將最擁擠的解從外部存檔刪除。

2.3 Pareto解集的評(píng)價(jià)

MDDE算法的求解過程就是不斷構(gòu)造Pareto解集,并向解空間的最優(yōu)前沿靠近的過程。因此,對(duì)多目標(biāo)差分進(jìn)化算法性能評(píng)價(jià)的重要依據(jù)是Pareto解集的優(yōu)劣。不同于單目標(biāo)優(yōu)化,多目標(biāo)優(yōu)化很難用單一的指標(biāo)來(lái)衡量,通常會(huì)考慮3方面的性能指標(biāo)[20]:收斂性、均勻性和多樣性。針對(duì)這3方面的性能指標(biāo),本文結(jié)合敏捷成像衛(wèi)星前攝式調(diào)度的特點(diǎn),對(duì)文獻(xiàn)[20]提出的指標(biāo)進(jìn)行了改進(jìn),采用以下3個(gè)量化指標(biāo)對(duì)Pareto解集進(jìn)行評(píng)價(jià),這里記待評(píng)價(jià)的Pareto解集為SP,其規(guī)模為NS,初始種群的非劣解集為InitS。

2.3.1 世代距離

世代距離[20](generational distance,GD)用于評(píng)價(jià)求解所得Pareto解集與真實(shí)Pareto最優(yōu)解集的接近程度,該指標(biāo)需要參考Pareto最優(yōu)解集才能確定,而現(xiàn)實(shí)中調(diào)度問題解空間的最優(yōu)解集難以獲得。本文將初始種群的非劣解集作為參考集合以評(píng)價(jià)Pareto解集的收斂性,GD計(jì)算公式為

(19)

(20)

式中,rdk為非支配解xk(xk∈SP)到InitS的最小歐式距離;GD表示SP相對(duì)InitS的進(jìn)化距離,與文獻(xiàn)[20]不同,本文中GD越大,SP越接近Pareto最優(yōu)前沿;當(dāng)GD=0時(shí),SP即為InitS。

2.3.2 分散間距

分散間距(spacing,SP)[20]用于評(píng)價(jià)Pareto解集中各個(gè)解分布的均勻性和多樣性,與文獻(xiàn)[20]不同的是,本文考慮目標(biāo)函數(shù)值階數(shù)的差別,采用歸一化鄰域距離計(jì)算相鄰解之間的距離,SP計(jì)算公式為

(21)

2.3.3 最大分布廣度

最大分布廣度(maximum spread,MS)[20]用于衡量Pareto解集的散布范圍,本文在MS的計(jì)算時(shí)將初始解集的非劣解集作為參考集合,計(jì)算公式為

(22)

2.4 算法實(shí)現(xiàn)步驟

綜合上述的分析和設(shè)計(jì),MDDE算法實(shí)現(xiàn)的具體步驟如下:

步驟1初始化算法的相關(guān)參數(shù):種群規(guī)模NP、最大迭代次數(shù)Itermax、變異概率Pm、交叉概率Pc;采用隨機(jī)貪婪算法生成初始種群。

步驟2對(duì)初始種群進(jìn)行基于Pareto的非支配排序,將排序后初始種群的最優(yōu)前沿作為外部存檔EA。

步驟5判斷是否達(dá)到最大迭代次數(shù)Itermax,如果達(dá)到,則輸出外部存檔EA作為Pareto非劣解集,并對(duì)解集的收斂性、均勻性、多樣性進(jìn)行評(píng)價(jià),如果沒有達(dá)到,則重復(fù)步驟步驟3和步驟4。

3 仿真驗(yàn)證

首先設(shè)置敏捷成像衛(wèi)星、成像任務(wù)和MDDE算法的相關(guān)參數(shù),然后采用Matlab R2010b實(shí)現(xiàn)MDDE算法,并對(duì)比分析MDDE與NSGA-Ⅱ[9,16]算法的求解結(jié)果。

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

仿真算例中敏捷成像衛(wèi)星的主要參數(shù)參考Pleiades衛(wèi)星[1],成像任務(wù)采取隨機(jī)生成的方式獲得,考慮到點(diǎn)目標(biāo)是成像的基本單元,條帶目標(biāo)可以看作具有一定觀測(cè)時(shí)長(zhǎng)的點(diǎn)目標(biāo),區(qū)域目標(biāo)通過分解可由點(diǎn)目標(biāo)和條帶目標(biāo)組成,本文選擇在一定范圍內(nèi)隨機(jī)生成不同規(guī)模的點(diǎn)目標(biāo)任務(wù)集[21]。衛(wèi)星和任務(wù)的主要參數(shù)如表2所示。

表2 衛(wèi)星和任務(wù)的主要參數(shù)

表2中,rand([x,y])表示x和y之間服從均勻分布的隨機(jī)數(shù)。通過組合產(chǎn)生5組算例(衛(wèi)星數(shù)～任務(wù)數(shù)):2～50、3～100、4～200、5～300、6～600。

算法參數(shù)設(shè)置如下:種群規(guī)模NP=100,進(jìn)化代數(shù)Itermax=100,變異概率Pm=0.7,交叉概率Pc=0.5,解構(gòu)的擾動(dòng)強(qiáng)度dps=0.4,重構(gòu)的擾動(dòng)強(qiáng)度cps=0.6,插入松弛時(shí)間的擾動(dòng)強(qiáng)度slc=2。

3.2 算法實(shí)現(xiàn)與結(jié)果分析

采用Matlab實(shí)現(xiàn)MDDE算法,計(jì)算機(jī)配置為Intel Core i7-3770 CPU @3.4GHz、8核4GB內(nèi)存,操作系統(tǒng)為Windows 7、編程環(huán)境為Matlab R2010b。為驗(yàn)證MDDE的優(yōu)越性,將MDDE與NSGA-Ⅱ算法[9,16]在5組算例上進(jìn)行對(duì)比,以世代距離、分散間距、最大分布廣度作為算法性能對(duì)比的指標(biāo),需要說明的是,這3個(gè)指標(biāo)均無(wú)量綱。為避免隨機(jī)因素的影響,每種算法在每組算例上獨(dú)立運(yùn)行20次并取平均值,對(duì)比如表3所示。

表3 MDDE與NSGA-Ⅱ算法的性能對(duì)比

由表3可知,在GD指標(biāo)上,MDDE比NSGA-Ⅱ高14.32%左右,說明MDDE算法求解得到的Pareto解集更接近真實(shí)最優(yōu)前沿;在SP指標(biāo)上,MDDE比NSGA-Ⅱ低5.17%左右,說明MDDE算法求解得到的Pareto解集中各個(gè)解的分布更均勻;在MS指標(biāo)上,MDDE比NSGA-Ⅱ高11.79%左右,說明MDDE算法求解得到的Pareto解集的最大分布范圍更廣。

以算例4～200為例,MDDE與NSGA-Ⅱ算法的Pareto求解結(jié)果對(duì)比如圖2所示。圖2中,RGA表示采用隨機(jī)貪婪算法求解得到的初始種群非劣解集,NSGA-Ⅱ-100表示采用NSGA-Ⅱ算法迭代100次求解得到的Pareto解集,MDDE-1、MDDE-50、MDDE-100分別表示采用MDDE算法迭代1、50、100次求解得到的Pareto解集。

圖2 MDDE與NSGA-Ⅱ算法Pareto求解結(jié)果對(duì)比Fig.2 Pareto solution comparison of MDDE with NSGA-Ⅱ algorithm

由圖2可知,MDDE算法從初始種群開始,通過多次迭代,不斷向解空間最優(yōu)前沿靠近,且MDDE算法經(jīng)過100次迭代求解所得解集優(yōu)于NSGA-Ⅱ算法經(jīng)過100次迭代求解所得解集。

在運(yùn)行時(shí)間方面,MDDE與NSGA-Ⅱ算法在5個(gè)算例上的結(jié)果對(duì)比如圖3所示。由圖3可知,MDDE的運(yùn)行時(shí)間在5個(gè)算例上比NSGA-Ⅱ平均降低了9.72%左右,說明MDDE比NSGA-Ⅱ的求解效率更高。同時(shí)可以看出,從算例2～50到6～600,隨著算例規(guī)模的變大,算法的運(yùn)行時(shí)間大幅增長(zhǎng),這是由于敏捷成像衛(wèi)星前攝式調(diào)度問題具有NP-Hard特性,解空間隨問題規(guī)模呈指數(shù)級(jí)增大,算法運(yùn)行時(shí)間也大幅增長(zhǎng)。

圖3 MDDE與NSGA-Ⅱ算法運(yùn)行時(shí)間對(duì)比Fig.3 Average CPU time comparison of MDDE and NSGA-Ⅱ algorithm

綜上結(jié)果分析,MDDE算法在求解結(jié)果和求解效率上均優(yōu)于NSGA-Ⅱ算法,驗(yàn)證了MDDE算法的優(yōu)越性。

4 結(jié) 論

本文針對(duì)敏捷成像衛(wèi)星前攝式調(diào)度中存在的衛(wèi)星資源失效、應(yīng)急任務(wù)加入兩類不確定因素,構(gòu)建了以期望收益和松弛時(shí)間為優(yōu)化目標(biāo)的調(diào)度魯棒模型,針對(duì)該模型的多目標(biāo)優(yōu)化特性,提出了一種MDDE求解算法,仿真結(jié)果表明3個(gè)Pareto解集評(píng)價(jià)指標(biāo)上MDDE比NSGA-Ⅱ提高了10.42%左右,在運(yùn)行時(shí)間上降低了9.72%左右,驗(yàn)證了MDDE算法的優(yōu)越性。同時(shí),本文研究沒有考慮擾動(dòng)事件發(fā)生后如何對(duì)方案進(jìn)行調(diào)整,在后續(xù)工作中,可進(jìn)一步研究反應(yīng)式調(diào)度模型和算法,以期采用較小幅度的方案調(diào)整應(yīng)對(duì)多種擾動(dòng)事件的影響。

[2] HABET D, VASQUEZ M, VIMONT Y. Bounding the optimum for the problem of scheduling the photographs of an agile earth observing satellite[J]. Computational Optimization and Applications, 2010, 47(2): 307-333.

[3] 姜維, 龐秀麗, 郝會(huì)成. 成像衛(wèi)星協(xié)同任務(wù)規(guī)劃模型與算法[J]. 系統(tǒng)工程與電技術(shù), 2013, 35(10): 2093-2101.

JIANG W, PANG X L, HAO H C. Collaborative scheduling model and algorithm for imaging satellite network[J]. Systems Engineering and Electronics, 2013, 35(10): 2093-2101.

[4] 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(C): 195-206.

[5] PEMBERTON J C, GREENWALD L G. On the need for dynamic scheduling of imaging satellites[J]. International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences, 2002, 34(1): 165-171.

[6] LAMBRECHTS O, DEMEULEMEESTER E, HERROELEN W. Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities[J]. Journal of Scheduling, 2008, 11(2): 121-136.

[7] ABRAMSON M, CARR F, CARR D, et al. Robust planning for the Earth Observing-1 (EO-1) mission[C]∥Proc.of the AIAA Aerospace Conference, 2013: 33-36.

[8] 王軍民,李菊芳,譚躍進(jìn).不確定條件下衛(wèi)星魯棒性調(diào)度問題[J].系統(tǒng)工程,2007,25(12): 94-99.

WANG J M, LI J F, TAN Y J. The robust satellite scheduling problem under uncertainty[J].Systems Engineering,2007,25(12): 94-99.

[9] NIU X, TANG H, WU L, et al. Imaging-duration embedded dynamic scheduling of earth observation satellites for emergent events[J].Mathematical Problems in Engineering,2015,4:1-31.

[10] 鄧潤(rùn), 唐宏, 單越, 等. 面向應(yīng)急任務(wù)衛(wèi)星魯棒性規(guī)劃模型及算法[J]. 遙感信息, 2014, 29(5): 25-31.

DENG R, TANG H, SHAN Y, et al. Emergency task oriented satellite robust mission planning model and algorithm[J]. Remote Sensing Information, 2014, 29(5): 25-31.

[11] WANG J, DEMEULEMEESTER E, QIU D. A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds[J]. Computers & Operations Research, 2016,74(C):1-13.

[12] 張忠山, 譚躍進(jìn), 義余江, 等. 基于資源預(yù)留的成像衛(wèi)星魯棒性任務(wù)規(guī)劃方法[J]. 系統(tǒng)工程理論與實(shí)踐, 2016, 36(6): 1544-1554.

ZHANG Z S, TAN Y J, YI Y J, et al. A robustness task planning method for imaging satellite based on resources reservation[J]. Systems Engineering Theory & Practice, 2016, 36(6): 1544-1554.

[13] ZHU X, WANG J, QIN X, et al. Fault-tolerant scheduling for real-time tasks on multiple earth observation satellites[J]. IEEE Trans.on Parallel & Distributed Systems, 2014, 26(1): 1-15.

[14] 何偉. 機(jī)器故障下柔性Job Shop調(diào)度研究[D]. 重慶: 重慶大學(xué), 2012.

HE W. Study on flexible job shop scheduling with machine breakdown[D]. Chongqing: Chongqing University, 2012.

[15] DAVENPORT A J, BECK J C. Slack-based techniques for robust schedules[C]∥Proc.of the 6th European Conference on Planning, 2001: 43-49.

[16] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ[J]. IEEE Trans.on Evolutionary Computation, 2002, 6(2): 182-197.

[17] 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.

[18] TASGETIREN M F, SUGANTHAN P N, PAN Q K. An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem[J]. Applied Mathematics and Computation, 2010, 215(9): 3356-3368.

[19] PAN Q K, TASGETIREN M F, LIANG Y C. A discrete differential evolution algorithm for the permutation flow shop scheduling problem[J]. Computers & Industrial Engineering, 2008, 55(4): 795-816.

[20] ZITZLER E, DEB K, THIELE L. Comparison of multi-objective evolutionary algorithms: empirical results[J]. Evolutionary Computation, 2000, 8(2): 173-195.

[21] 李志亮, 李小將, 孫偉. 考慮成像質(zhì)量的敏捷衛(wèi)星任務(wù)調(diào)度模型與算法[J]. 宇航學(xué)報(bào), 2017, 38(6): 590-597.

LI Z L, LI X J, SUN W. Task scheduling model and algorithm for agile satellite considering imaging quality[J]. Journal of Astronautics, 2017, 38(6): 590-597.