面向應(yīng)急任務(wù)衛(wèi)星魯棒性規(guī)劃模型及算法

鄧潤，唐宏，單越，牛曉楠，劉穎慧

（北京師范大學(xué) 地表過程與資源生態(tài)國家重點(diǎn)實(shí)驗(yàn)室，北京 100875）

1 引 言

成像衛(wèi)星具有一次成像范圍大、成像成本低等特點(diǎn)，已廣泛應(yīng)用于國防、環(huán)保、農(nóng)業(yè)、氣象、災(zāi)害應(yīng)急等領(lǐng)域。然而，成像衛(wèi)星研制、發(fā)射和維護(hù)成本高，盡管隨著衛(wèi)星應(yīng)用技術(shù)的發(fā)展，越來越多的成像衛(wèi)星升入太空，但相對于人類日益增長的成像需求，衛(wèi)星資源仍然異常寶貴。為了最優(yōu)化地利用成像衛(wèi)星資源，衛(wèi)星任務(wù)規(guī)劃尤為重要。成像衛(wèi)星受到軌道限制僅在特定的時間窗口內(nèi)與地面目標(biāo)可見，衛(wèi)星任務(wù)規(guī)劃［1］即綜合考慮衛(wèi)星成像能力及任務(wù)需求等約束，以安排最大任務(wù)收益為優(yōu)化目標(biāo)，確定要執(zhí)行的任務(wù)及執(zhí)行這些任務(wù)的時間窗起止時間。現(xiàn)有研究［2－6］大多集中在衛(wèi)星靜態(tài)任務(wù)規(guī)劃，當(dāng)新的應(yīng)急成像任務(wù)到來時，采用完全重規(guī)劃算法對原問題重新建模求解。產(chǎn)生的新任務(wù)規(guī)劃方案與初始方案相差較大，導(dǎo)致衛(wèi)星重調(diào)度難度大。

針對衛(wèi)星動態(tài)任務(wù)規(guī)劃，Perberton等［7］總結(jié)了4種引起衛(wèi)星任務(wù)規(guī)劃方案調(diào)整的因素：任務(wù)觀測機(jī)會變化、資源變化、新任務(wù)插入、衛(wèi)星任務(wù)規(guī)劃問題參數(shù)變化，但并未提出具體的問題模型及求解算法。Verfaillie［8］和劉洋［9］提出基于動態(tài)約束滿足問題的衛(wèi)星動態(tài)任務(wù)規(guī)劃模型及求解算法，但并未考慮初始方案的可調(diào)整性。王軍民［10］將衛(wèi)星任務(wù)動態(tài)規(guī)劃問題分為魯棒性初始方案生成及調(diào)整兩個階段，在初始方案生成階段，引入基于鄰域的魯棒性指標(biāo)，得到更易于調(diào)整的初始方案，當(dāng)新任務(wù)與初始方案中的任務(wù)沖突時，能使初始方案中的任務(wù)安排到其他位置而不被刪除，但基于鄰域的魯棒性指標(biāo)不能衡量初始方案接受新任務(wù)直接插入而不影響已安排任務(wù)執(zhí)行的能力。

本文在衛(wèi)星魯棒性任務(wù)規(guī)劃模型目標(biāo)函數(shù)中引入總時間重疊度及總?cè)蝿?wù)執(zhí)行時長兩項(xiàng)魯棒性指標(biāo)，通過仿真模擬實(shí)驗(yàn)結(jié)果分析可知，在任務(wù)收益和相差不大的情況下，采用本文方法能得到總時間重疊度更小，總?cè)蝿?wù)執(zhí)行時長更短的衛(wèi)星魯棒性任務(wù)規(guī)劃方案。

2 衛(wèi)星魯棒性任務(wù)規(guī)劃模型

2.1 魯棒性指標(biāo)

對于給定的規(guī)劃方案，在面臨擾動時，應(yīng)用某種特定的動態(tài)調(diào)整方法既能保持良好的規(guī)劃方案收益，又能保持新老規(guī)劃方案的差異盡可能小，則稱之為魯棒性規(guī)劃方案［10］。

本文提出兩項(xiàng)魯棒性指標(biāo)：①總?cè)蝿?wù)執(zhí)行時長，衡量規(guī)劃方案接受新任務(wù)直接插入而不影響已安排任務(wù)執(zhí)行的能力；②總時間重疊度，衡量規(guī)劃方案中已安排任務(wù)與新任務(wù)沖突時，能被重新安排在其他時間窗口執(zhí)行的能力。

定義1總?cè)蝿?wù)執(zhí)行時長：各衛(wèi)星安排執(zhí)行任務(wù)時間之和。

（上式中涉及的變量、函數(shù)意義見2.2節(jié)模型中涉及的變量、參數(shù)及函數(shù)部分）

總?cè)蝿?wù)執(zhí)行時長算例：

表1 各任務(wù)收益及衛(wèi)星a與任務(wù)可見時間窗口

表1列舉出衛(wèi)星a與4個待執(zhí)行任務(wù)間的可見時間窗口、任務(wù)收益及衛(wèi)星完成各拍攝任務(wù)需要的時長。其中，任務(wù)收益根據(jù)各任務(wù)的重要性設(shè)定，任務(wù)越重要，衛(wèi)星執(zhí)行任務(wù)獲得的收益越高，衛(wèi)星任務(wù)規(guī)劃方案的任務(wù)收益和即方案中所有已安排執(zhí)行任務(wù)的收益和。由圖1可知，方案1中衛(wèi)星a最終執(zhí)行任務(wù)1和任務(wù)2；圖2顯示方案2中衛(wèi)星a執(zhí)行任務(wù)3和任務(wù)4，兩方案任務(wù)的收益和均為4，方案1總?cè)蝿?wù)執(zhí)行時長＝2＋5＝7，方案2總?cè)蝿?wù)執(zhí)行時長＝3＋1＝4。在規(guī)劃時段0～10內(nèi)，顯然方案2的空余時間窗口更多，接受新任務(wù)直接插入能力更強(qiáng)。此外方案2總執(zhí)行時長短，衛(wèi)星能量消耗更低，因此任務(wù)收益和指標(biāo)相同的情況下，總?cè)蝿?wù)執(zhí)行時長越短的方案性能越好。

定義2 總時間重疊度：各衛(wèi)星執(zhí)行任務(wù)時間窗口與衛(wèi)星其余可見時間窗口的時間重疊度乘以任務(wù)權(quán)重的和。

（上式中涉及的變量、函數(shù)意義見2.2節(jié)模型中涉及的變量、參數(shù)及函數(shù)部分）

總時間重疊度算例：

表2 各任務(wù)收益及其與衛(wèi)星a，b可見時間窗口

由圖3、圖4可知，方案A、方案B的任務(wù)收益和指標(biāo)均為11，方案A總時間重疊度＝3×3＋2×1＝11，方案B總時間重疊度為0，當(dāng)新應(yīng)急任務(wù)到來要占用任務(wù)1或者任務(wù)3的時間窗口時，方案A總時間重疊度較高，能重新安排任務(wù)1的潛在時間窗口［3 5］與任務(wù)4重疊，能重新安排任務(wù)3的潛在時間窗口［3 6］與任務(wù)2重疊，導(dǎo)致任務(wù)1、任務(wù)3都無法重新安排。而方案B總時間重疊度為0，能重新安排任務(wù)的潛在時間窗口都與方案中的其他任務(wù)沒有重疊，故當(dāng)新應(yīng)急任務(wù)插入引起沖突時，沖突位置的任務(wù)能重新安排到其他時間窗口執(zhí)行，無需刪除，因此任務(wù)收益和指標(biāo)相同的情況下，總時間重疊度小的任務(wù)規(guī)劃方案更優(yōu)。

2.2 面向應(yīng)急任務(wù)衛(wèi)星魯棒性任務(wù)規(guī)劃模型

本文引入總?cè)蝿?wù)執(zhí)行時長、總時間重疊度兩項(xiàng)魯棒性指標(biāo)，建立的衛(wèi)星魯棒性任務(wù)規(guī)劃約束滿足問題模型如下：

以上各式表達(dá)的含義如下：

式（1）表示任務(wù)收益和最大；

式（2）表示總時間重疊度最?。?/p>

式（3）表示總?cè)蝿?wù)執(zhí)行時長最短；

式（4）表示每個任務(wù)最多被執(zhí)行一次；

式（5）表示每顆衛(wèi)星的執(zhí)行任務(wù)序列中不存在重疊的時間段，即各衛(wèi)星同一時間僅執(zhí)行一個任務(wù)；

式（6）表示衛(wèi)星執(zhí)行任務(wù)必須在兩者可見時間窗口內(nèi)進(jìn)行；

式（7）表示任意單圈時間段內(nèi)，衛(wèi)星執(zhí)行任務(wù)的總時長必須小于衛(wèi)星單圈最長執(zhí)行任務(wù)時長。

模型中涉及的變量、參數(shù)及函數(shù)：

（1）決策變量：

Task［s］［t］：時間區(qū)間變量（interval），表示衛(wèi)星s執(zhí)行任務(wù)t的時間窗口；

Satellites：將衛(wèi)星s執(zhí)行任務(wù)的時間窗按時間順序排序得到的任務(wù)序列，表示衛(wèi)星s的執(zhí)行任務(wù)序列。

（2）其他參數(shù)：

ω（t）：成像任務(wù)t的收益；

tw：衛(wèi)星與任務(wù)間可見時間窗口四元組＜s，t，start，end＞，對應(yīng)信息＜衛(wèi)星，任務(wù)，開始時間，結(jié)束時間＞；

TW：可見時間窗口集合；

TWs：衛(wèi)星s的可見時間窗口集合；

TWst：衛(wèi)星s對任務(wù)t的可見時間窗口集合；

S：參與成像衛(wèi)星集合；

T：成像任務(wù)集合；

maxdurations：衛(wèi)星s單圈最長執(zhí)行任務(wù)時長；

orbittimes：衛(wèi)星s單軌運(yùn)行時間。

（3）函數(shù)：

presenceOf（interval a）：若a在調(diào)度方案中出現(xiàn)則返回1，否則返回0；

sizeOf（interval a）：返回a的大?。?/p>

overlapLength（interval a，int b，int c）：返回a與［b c］間重疊時間長度；

startOf（interval a）：返回時間區(qū)間變量的開始時間。

3 衛(wèi)星魯棒性任務(wù)規(guī)劃算法

3.1 基于NSGA－П衛(wèi)星魯棒性任務(wù)規(guī)劃算法

衛(wèi)星魯棒性任務(wù)規(guī)劃問題是典型的多目標(biāo)優(yōu)化問題，目前求解多目標(biāo)優(yōu)化問題大多采用多目標(biāo)進(jìn)化算法。針對上述衛(wèi)星魯棒性任務(wù)規(guī)劃模型，本文基于經(jīng)典多目標(biāo)優(yōu)化算法 NSGA－П［11－12］框架（圖5）設(shè)計了衛(wèi)星魯棒性任務(wù)規(guī)劃算法。

算法流程如下：

（1）設(shè)計解的遺傳編碼，設(shè)置種群大小M，最大迭代次數(shù)T，當(dāng)前迭代次數(shù)t＝0，并初始化種群Pt；

（2）對種群Pt進(jìn)行選擇，交叉，變異遺傳操作，產(chǎn)生新種群Qt；

（3）對新種群Rt＝（Pt∪Qt）進(jìn)行非支配排序（Non－dominated sorting）得到Rt的非支配前沿F＝（F1，F(xiàn)2，…）；

（4）令Pt＋1＝?，i＝1，Pt＋1＝Pt＋1∪Fi；

（5）i＝i＋1，若｜Pt＋1｜＋｜Fi｜＜M，轉(zhuǎn)（4），若｜Pt＋1｜＋｜Fi｜＝M，轉(zhuǎn)（7）；

（6）計算Fi中個體的擁擠距離，并按擁擠距離選出最好的｜M－｜Pt＋1｜｜個體，Pt＋1＝Pt＋1∪Fi［1∶｜M－｜Pt＋1｜｜］；

（7）t＝t＋1，若t＋1＜T且Pt＋1∩Pt≠Pt，重復(fù)（2）；

（8）輸出Pt中的非支配pareto解并解碼。

3.2 遺傳算子設(shè)計

3.2.1 遺傳編碼

由于衛(wèi)星任務(wù)規(guī)劃問題中，個體遺傳操作（交叉、變異）涉及到大量的基因位置移動，本文采用實(shí)數(shù)鏈狀編碼，將衛(wèi)星按編號順序排列，每顆衛(wèi)星任務(wù)序列包含一對虛擬起始、終止節(jié)點(diǎn)，兩者之間所夾節(jié)點(diǎn)為該衛(wèi)星執(zhí)行的任務(wù)節(jié)點(diǎn)，相鄰衛(wèi)星間通過虛擬的起始節(jié)點(diǎn)與終止節(jié)點(diǎn)連接。為便于遺傳個體的解碼及任務(wù)插入的可行性分析，本文設(shè)計的任務(wù)節(jié)點(diǎn)包含以下信息：任務(wù)號、占用的可用時間窗口開始時間、占用的時間窗口終止時間、最早開始執(zhí)行時間、最晚開始執(zhí)行時間、關(guān)鍵任務(wù)序列編號、后向能量負(fù)荷、指向下一任務(wù)節(jié)點(diǎn)的指針、指向前一任務(wù)節(jié)點(diǎn)的指針。具體遺傳編碼示例如圖6所示。

3.2.2 選擇算子

采用二元錦標(biāo)賽選擇，從種群中隨機(jī)選取2個個體，比較這2個個體在非支配排序中的順序，選取位置靠前的個體。

3.2.3 交叉算子

根據(jù)上述遺傳編碼，設(shè)計交叉算子（圖7）：在兩個父個體上，隨機(jī)選擇同一顆衛(wèi)星的任務(wù)序列互相替換；在父個體其他衛(wèi)星的任務(wù)序列上刪除與新替換的衛(wèi)星任務(wù)序列重復(fù)的任務(wù)；并嘗試插入新替換的衛(wèi)星任務(wù)序列相比原始任務(wù)序列丟失的任務(wù)。

3.2.4 變異算子

根據(jù)成像任務(wù)多時間窗口特性，設(shè)計單點(diǎn)變異算子，具體工作流程如下：

①對原始任務(wù)序列（1，2，3，4…nt）進(jìn)行隨機(jī)排序，初始化任務(wù)序列號i＝1；

②計算任務(wù)Ti對應(yīng)的時間窗口數(shù)量nitw；

③若nitw＝0，i＝i＋1，轉(zhuǎn)到（2）；

④若待變異染色體中不存在Ti，嘗試插入任務(wù)Ti。若插入成功，更新染色體，結(jié)束變異；若插入失敗，i＝i＋1，轉(zhuǎn)到（2）；

⑤判斷Ti在染色體中的位置能否改變，若能，改變Ti位置，更新染色體，結(jié)束變異；否則，刪除Ti，更新染色體，結(jié)束變異。

3.3 種群初始化

①初始化任務(wù)序列號i＝1，個體編號j＝1，種群大小M；

②初始化調(diào)度方案任務(wù)鏈Schedulej＝φ，對原始任務(wù)序列（1，2，3，4…nt）進(jìn)行隨機(jī)排序；

③選取任務(wù)Ti插入，設(shè)任務(wù)Ti對應(yīng)的時間窗口數(shù)量nitw；

④若nitw＝0，轉(zhuǎn)到（7）；否則將任務(wù)Ti對應(yīng)的時間窗口進(jìn)行隨機(jī)排序，k＝1；

⑤選取時間窗口TWk，若任務(wù)Ti在時間窗口TWk能夠插入到調(diào)度方案中而不引起沖突，更新Schedulej，轉(zhuǎn)到（7）；

⑥k＝k＋1，若k≤nitw，轉(zhuǎn)（5）；

⑦i＝i＋1，若i＞nt，轉(zhuǎn)（8）；否則，轉(zhuǎn)到（3）；

⑧j＝j(luò)＋1，若j≤M，i＝1，轉(zhuǎn)到（2）；否則，種群初始化結(jié)束。

4 實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)方案設(shè)計

假設(shè)有2顆衛(wèi)星，分別選取50，100，200個點(diǎn)目標(biāo)成像，通過STK軟件計算衛(wèi)星與觀測目標(biāo)間的可見時間窗口，并隨機(jī)模擬各觀測目標(biāo)要求的成像時長及任務(wù)收益。

常規(guī)衛(wèi)星任務(wù)規(guī)劃往往僅以任務(wù)收益和最大為優(yōu)化目標(biāo)，不考慮魯棒性指標(biāo)。魯棒性任務(wù)規(guī)劃研究中王軍民［12］提出基于鄰域的魯棒性指標(biāo)。針對上述不同觀測目標(biāo)數(shù)量的3組輸入數(shù)據(jù)，將本文提出的基于總時間重疊度及總?cè)蝿?wù)執(zhí)行時長指標(biāo)的魯棒性任務(wù)規(guī)劃方案，分別與常規(guī)衛(wèi)星任務(wù)規(guī)劃方案和基于鄰域指標(biāo)的魯棒性任務(wù)規(guī)劃方案對比分析。

4.2 基于總時間重疊度和總?cè)蝿?wù)執(zhí)行時長指標(biāo)的魯棒性衛(wèi)星任務(wù)規(guī)劃方案與常規(guī)方案對比

針對上述不同觀測目標(biāo)數(shù)量的3組輸入數(shù)據(jù)，僅以任務(wù)收益和最大為優(yōu)化目標(biāo)建立衛(wèi)星任務(wù)規(guī)劃模型，采用遺傳算法求解；同時以任務(wù)收益和最大、總時間重疊度最小、總?cè)蝿?wù)執(zhí)行時長最短為優(yōu)化目標(biāo)建立衛(wèi)星魯棒性任務(wù)規(guī)劃模型，采用本文提出的基于NSGA－П的衛(wèi)星魯棒性任務(wù)規(guī)劃算法求解。比較每組數(shù)據(jù)在兩種情況下得到的最優(yōu)規(guī)劃方案任務(wù)收益和、總時間重疊度、總?cè)蝿?wù)執(zhí)行時長3項(xiàng)指標(biāo)（圖8～圖10，表3～表5），考慮三優(yōu)化目標(biāo)得到的Pareto最優(yōu)解數(shù)量較多，僅列出收益指標(biāo)與單優(yōu)化目標(biāo)得到的任務(wù)收益和相差10以內(nèi)的規(guī)劃方案指標(biāo)函數(shù)值。

表3 50個觀測任務(wù)3指標(biāo)高收益區(qū)具體數(shù)值列表

表4 100個觀測任務(wù)3指標(biāo)高收益區(qū)具體數(shù)值列表

表5 200個觀測任務(wù)3指標(biāo)高收益區(qū)具體數(shù)值列表

分析圖8～圖10，及表3～表5可知，相比單優(yōu)化目標(biāo)思想的常規(guī)衛(wèi)星任務(wù)規(guī)劃，本文提出的三優(yōu)化目標(biāo)方法能得到任務(wù)收益和相差不大，但總時間重疊度及總?cè)蝿?wù)執(zhí)行時長都有大幅度減小的規(guī)劃方案。此外，三優(yōu)化目標(biāo)方法不容易陷入局部最優(yōu)，能進(jìn)化得到任務(wù)收益和更大的規(guī)劃方案，以及多個高收益、總時間重疊度和總?cè)蝿?wù)執(zhí)行時長較小的規(guī)劃方案供決策者選擇。

4.3 基于總時間重疊度、總?cè)蝿?wù)執(zhí)行時長指標(biāo)與基于鄰域指標(biāo)的魯棒性任務(wù)規(guī)劃方案對比

針對上述3組實(shí)驗(yàn)數(shù)據(jù)，分別求解基于鄰域指標(biāo)與基于總時間重疊度、總?cè)蝿?wù)執(zhí)行時長指標(biāo)的兩種衛(wèi)星魯棒性任務(wù)規(guī)劃模型，并比較兩種規(guī)劃方案的任務(wù)收益和、總?cè)蝿?wù)執(zhí)行時長、方案中可調(diào)整的任務(wù)收益和指標(biāo)（圖11～圖16）。

分析圖11～圖16可知，在任務(wù)收益和指標(biāo)值較大時，基于總時間重疊度、總?cè)蝿?wù)執(zhí)行時長指標(biāo)與基于鄰域指標(biāo)的魯棒性任務(wù)規(guī)劃方案相比，兩種規(guī)劃方案的任務(wù)收益和、可調(diào)整任務(wù)收益和指標(biāo)都相差不大，基于總時間重疊度、總?cè)蝿?wù)執(zhí)行時長指標(biāo)得到的規(guī)劃方案總?cè)蝿?wù)執(zhí)行時長更小。

5 結(jié)束語

本文提出總?cè)蝿?wù)執(zhí)行時長、總時間重疊度兩項(xiàng)新魯棒性指標(biāo)，建立成像衛(wèi)星魯棒性任務(wù)規(guī)劃模型，并設(shè)計基于NSGA－П的衛(wèi)星魯棒性任務(wù)規(guī)劃算法求解該模型。實(shí)驗(yàn)表明，在考慮任務(wù)收益和最大化的基礎(chǔ)上，引入總時間重疊度及總?cè)蝿?wù)執(zhí)行時長的三優(yōu)化目標(biāo)模型、僅考慮任務(wù)收益和指標(biāo)的單優(yōu)化目標(biāo)模型（常規(guī)衛(wèi)星任務(wù)規(guī)劃方案）、基于鄰域魯棒性指標(biāo)的多目標(biāo)優(yōu)化模型，三者得到的任務(wù)總收益高且相差不大的規(guī)劃方案相比，本文方法得到的衛(wèi)星任務(wù)規(guī)劃方案總時間重疊度、總?cè)蝿?wù)執(zhí)行時長往往更小，當(dāng)新應(yīng)急任務(wù)到來時，將有更長的空余時間段接受其直接插入而不引起沖突，且與其沖突的原始任務(wù)能調(diào)整到其他時間窗重新安排而不被刪除的概率也更大。此外，總?cè)蝿?wù)時長越短，衛(wèi)星能量消耗越小，采用本文方法得到的衛(wèi)星任務(wù)規(guī)劃方案，在降低衛(wèi)星能量損耗方面也具有重要實(shí)踐意義。

［1］王沛，譚躍進(jìn).衛(wèi)星對地觀測任務(wù)規(guī)劃問題簡明綜述［J］.計算機(jī)應(yīng)用研究，2008，25（10）：2893－2897.

［2］VASQUEZ M，HAO J K.A “l(fā)ogic－constrained”knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite［J］.Computational Optimization and Applications，2001，20（2）：137－157.

［3］BENSANA E，VERFAILLIE G，LEMAITRE M.Earth observing satellite［J］.Managements Constraints，1999，4（3）：293－299.

［4］FRANK J，SMITH D E.Planning and scheduling for fleets of earth observing satellites［C］.Proceedings of the Sixth International Symposium on Artificial Intelligence，Robotics，Automation and Space，2001.

［5］WOLFE W J，SORENSEN S E.Three scheduling algorithms applied to the earth observing systems domain［J］.Management Science，2000，46（4）：148－168.

［6］GABREL V，VANDERPOOTEN D.Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite［J］.European Journal of Operational Research，2002，139（3）：533－542.

［7］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.

［8］VERFAILLIE G，SCHIEX T.Solution reuse in dynamic constraint satisfaction problems［C］.AAAI，1994，94：307－312.

［9］劉洋，陳英武，譚躍進(jìn).一種有新任務(wù)到達(dá)的多衛(wèi)星動態(tài)調(diào)度模型與方法［J］.系統(tǒng)工程理論與實(shí)踐，2005，25（4）：35－41.

［10］王軍民，王鵬，李菊芳，等.成像衛(wèi)星魯棒性調(diào)度策略研究［J］.系統(tǒng)工程與電子技術(shù)，2010，32（1）：109－114.

［11］DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multi－objective genetic algorithm：NSGA－II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182－197.

［12］DEBK，AGRAWAL S，PRATAP A，et al.A fast elitist non－dominated sorting genetic algorithm for multi－objective optimization：NSGA－II［J］.Lecture Notes in Computer Science，2000，19（17）：849－858.