改進(jìn)差分進(jìn)化算法求解多成像衛(wèi)星調(diào)度問(wèn)題

彭 攀，白沐炎，陳長(zhǎng)春，陳曉宇

（1.上海衛(wèi)星工程研究所，上海 201109；2.上海航天技術(shù)研究院，上海 201109；3.中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430074）

0 引言

成像偵察衛(wèi)星調(diào)度問(wèn)題是一類(lèi)混合時(shí)間和資源分配的復(fù)雜調(diào)度問(wèn)題，且已被證明是一類(lèi)非確定多項(xiàng)式競(jìng)爭(zhēng)（Non-deterministic Polynomial Complete，NPC）問(wèn)題［1］，涉及了多學(xué)科交叉知識(shí)，是我國(guó)空天地一體化體系設(shè)計(jì)的基礎(chǔ)。作為空間信息網(wǎng)絡(luò)構(gòu)建和衛(wèi)星應(yīng)用控制領(lǐng)域的關(guān)鍵支撐技術(shù)，成像偵察衛(wèi)星調(diào)度問(wèn)題已成為實(shí)際應(yīng)用中的一個(gè)重要研究?jī)?nèi)容，受到學(xué)術(shù)界和工程界的高度重視［2］。

很多學(xué)者最初研究了單星調(diào)度規(guī)劃問(wèn)題，設(shè)計(jì)了高效的求解模型和算法。Jang等［3］通過(guò)對(duì)任務(wù)可見(jiàn)時(shí)間窗口離散化，并在此基礎(chǔ)上構(gòu)建了0/1 線(xiàn)性規(guī)劃模型。Wu等［4］提出了一種基于任務(wù)動(dòng)態(tài)劃分的自適應(yīng)模擬退火算法，并引入禁忌表求解了單星多軌道對(duì)地觀(guān)測(cè)調(diào)度規(guī)劃問(wèn)題。潘耀等［5］通過(guò)對(duì)遙感衛(wèi)星成像任務(wù)規(guī)劃中的點(diǎn)目標(biāo)進(jìn)行聚類(lèi)，構(gòu)建了任務(wù)聚類(lèi)圖模型，設(shè)計(jì)了一種改進(jìn)的單軌最優(yōu)團(tuán)劃分聚類(lèi)方法。這一系列的工作在單星調(diào)度規(guī)劃最優(yōu)可行解生成和問(wèn)題界限描述上均取得了顯著的進(jìn)展。

隨著航天任務(wù)的復(fù)雜化和要求的提高，在軌運(yùn)行衛(wèi)星數(shù)量和類(lèi)型逐漸增多，用戶(hù)需求不斷增加，且表現(xiàn)出復(fù)雜多樣的特性，由多顆星組成的衛(wèi)星網(wǎng)絡(luò)系統(tǒng)在通信、導(dǎo)航和遙感等領(lǐng)域都得到了重要的應(yīng)用。與單星調(diào)度規(guī)劃問(wèn)題相比，調(diào)度復(fù)雜任務(wù)約束下多顆協(xié)同運(yùn)作的衛(wèi)星需要考慮觀(guān)測(cè)資源選擇和執(zhí)行時(shí)間窗口選擇，以及更多的執(zhí)行操作約束［6］。考慮到傳統(tǒng)任務(wù)規(guī)劃算法不能適應(yīng)多衛(wèi)星資源的應(yīng)用特點(diǎn)，有學(xué)者將多星聯(lián)合調(diào)度規(guī)劃問(wèn)題劃分為任務(wù)到資源分配的主問(wèn)題和多個(gè)單星調(diào)度規(guī)劃的子問(wèn)題［7-8］。賀仁杰等［9］深入分析了成像衛(wèi)星任務(wù)規(guī)劃技術(shù)，將其看作是帶時(shí)間窗口約束的并行機(jī)調(diào)度問(wèn)題，并采用禁忌搜索算法求解了較大規(guī)模的任務(wù)協(xié)同規(guī)劃問(wèn)題。劉偉［10］提出了混合整數(shù)規(guī)劃模型和約束滿(mǎn)足模型相結(jié)合的調(diào)度規(guī)劃模型，研究了這兩種模型下的Lagrangian 松弛確定性?xún)?yōu)化方法和模擬退火算法隨機(jī)性?xún)?yōu)化方法。Salman等［11］提出了混合差分進(jìn)化的元啟發(fā)式隨機(jī)擴(kuò)散搜索算法，研究了多衛(wèi)星聯(lián)合廣播任務(wù)調(diào)度問(wèn)題。Xu等［12］提出了基于任務(wù)優(yōu)先級(jí)指標(biāo)的蟻群算法，研究了最大化收益值的多敏捷衛(wèi)星對(duì)地觀(guān)測(cè)調(diào)度規(guī)劃問(wèn)題。Zhang等［13］構(gòu)建了一個(gè)獨(dú)立的復(fù)雜沖突結(jié)構(gòu)圖模型，以最小化任務(wù)執(zhí)行時(shí)延為目標(biāo)，提出了蟻群優(yōu)化多星聯(lián)合調(diào)度問(wèn)題。Zheng等［14］提出一種改進(jìn)的混合動(dòng)態(tài)變異算子的遺傳算法求解多星聯(lián)合對(duì)地觀(guān)測(cè)調(diào)度規(guī)劃問(wèn)題，顯著提升了算法的性能。嚴(yán)珍珍等［15］提出一種加入精英策略的改進(jìn)蟻群算法的多敏捷衛(wèi)星成像調(diào)度方法。陳曉宇等［16］提出了基于任務(wù)優(yōu)先級(jí)和沖突消解的改進(jìn)差分進(jìn)化算法。Song等［17］采用帶局部搜索的改進(jìn)遺傳算法，求解了多星調(diào)度規(guī)劃問(wèn)題，提高了算法搜索效率。

在上述研究背景下，本文主要針對(duì)智能優(yōu)化算法求解多星聯(lián)合調(diào)度規(guī)劃問(wèn)題中存在的算法性能隨問(wèn)題規(guī)模增大而大大降低的問(wèn)題，旨在提出一種改進(jìn)差分進(jìn)化算法。首先建立了多星聯(lián)合調(diào)度規(guī)劃約束滿(mǎn)足最優(yōu)化模型，并在標(biāo)準(zhǔn)差分進(jìn)化算法的基礎(chǔ)上，通過(guò)分析成像衛(wèi)星的成像過(guò)程和工作原理，將成像衛(wèi)星調(diào)度過(guò)程分為調(diào)度預(yù)處理、任務(wù)規(guī)劃和調(diào)度優(yōu)化3 個(gè)階段。其中，調(diào)度預(yù)處理操作是根據(jù)用戶(hù)需求來(lái)篩選衛(wèi)星系統(tǒng)資源，確定每個(gè)觀(guān)測(cè)任務(wù)的可選資源以及可分配的時(shí)間窗口；在任務(wù)規(guī)劃過(guò)程中，采用基于啟發(fā)式思想的差分進(jìn)化算法對(duì)成像衛(wèi)星調(diào)度問(wèn)題進(jìn)行求解，重新定義了個(gè)體適應(yīng)度評(píng)估函數(shù)，設(shè)計(jì)了任務(wù)沖突消解方法；優(yōu)化過(guò)程是根據(jù)系統(tǒng)性能評(píng)估結(jié)果，主要對(duì)調(diào)度規(guī)劃結(jié)果中由于資源沖突而未完成的任務(wù)和因時(shí)間限制有時(shí)延的任務(wù)進(jìn)行進(jìn)一步的優(yōu)化。

1 問(wèn)題描述

多成像偵察衛(wèi)星調(diào)度問(wèn)題可以描述為在m個(gè)互不相同的遙感設(shè)備（資源集合R）安排n個(gè)觀(guān)測(cè)任務(wù)（活動(dòng)集合M）。對(duì)每個(gè)活動(dòng)Mi∈M，只有資源子集R(Mi)∈R可以滿(mǎn)足其執(zhí)行要求，該活動(dòng)完成需要占用資源Rj∈R，占用時(shí)間為[Begi，Endi]。此外，活動(dòng)Mi在占用資源Rj時(shí)具有一組互不相交的時(shí)間窗口集約束，且只能在其中的一個(gè)時(shí)間窗口內(nèi)不中斷地執(zhí)行完成。如果活動(dòng)Mi和活動(dòng)Mi'在執(zhí)行過(guò)程中占用同一個(gè)資源Rj，且活動(dòng)Mi在活動(dòng)Mi'之前執(zhí)行，那么活動(dòng)Mi執(zhí)行完成后，必須經(jīng)過(guò)一個(gè)轉(zhuǎn)換時(shí)間活 動(dòng)Mi'才能開(kāi)始執(zhí)行。由于資源 能力及時(shí)間的限制，活動(dòng)可能不被安排。因此，每個(gè)活動(dòng)Mi都有權(quán)值wi，代表該活動(dòng)安排時(shí)的效益值。

一個(gè)最優(yōu)調(diào)度方案應(yīng)滿(mǎn)足以下條件：1）每個(gè)活動(dòng)只能在自己的時(shí)間窗口內(nèi)執(zhí)行，否則，認(rèn)為該活動(dòng)未安排；2）每個(gè)活動(dòng)只能占用滿(mǎn)足其要求的資源集合中的一個(gè)資源，且執(zhí)行過(guò)程不能中斷；3）每個(gè)資源在任何時(shí)候只能同時(shí)滿(mǎn)足一個(gè)活動(dòng)的需求；4）安排活動(dòng)的總權(quán)值最大。

2 約束滿(mǎn)足最優(yōu)化模型

2.1 符號(hào)定義

2.1.1 集合

M：活動(dòng)集合。M={M1，M2，…，Mn}，其中第i個(gè)任務(wù)用Mi表示。

R：資源集合。R={R1，R2，…，Rm}，其中第j個(gè)資源用Rj表示。

M(Rj)：所有可以被安排在資源Rj上被執(zhí)行的活動(dòng)集合。Rj∈R，M(Rj)∈M。

R(Mi)：滿(mǎn)足觀(guān)測(cè)活動(dòng)Mi要求的資源集合。Mi∈M，R(Mi)∈R。

TWij：活動(dòng)Mi占用資源Rj是所允許的時(shí)間窗口集合。Nij表示活動(dòng)Mi占用資源Rj時(shí)所允許的可見(jiàn)時(shí)間窗口數(shù)目。其中，代表在活動(dòng)Mi占用資源Rj時(shí)所允許的第k個(gè)時(shí)間窗口開(kāi)始時(shí)間，代表活動(dòng)Mi占用資源Rj時(shí) 所允許的第k個(gè)時(shí)間窗口結(jié)束時(shí)間。

RTWj：資源Rj的有效執(zhí)行區(qū)間段集合，表示資源在哪些時(shí)間段內(nèi)可用。

2.1.2 參數(shù)

RPj：表示資源的圖像類(lèi)型。RPj=1 表示可見(jiàn)光成像，RPj=2 表示紅外線(xiàn)成像，RPj=3 表示多光譜成像，RPj=4 表示雷達(dá)成像。

Δj：表示資源Rj成像前的穩(wěn)定時(shí)長(zhǎng)。

Aj：表示資源Rj在整個(gè)仿真周期內(nèi)的最大執(zhí)行時(shí)長(zhǎng)。

wi：活動(dòng)Mi的權(quán)值。Mi∈M，wi＞0。

Di：活動(dòng)Mi完成所需要的持續(xù)時(shí)間。Mi∈M，TDi＞0。

TPi：活動(dòng)Mi成像所要求的圖像類(lèi)型。TPi=0表示成像類(lèi)型無(wú)要求，TPi=1 表示可見(jiàn)光成像，TPi=2 表示紅外線(xiàn)成像，TPi=3 表示多光譜成像，TPi=4 表示雷達(dá)成像。

SCBeg：場(chǎng)景開(kāi)始時(shí)間。

SCEnd：場(chǎng)景結(jié)束時(shí)間。

Begi：活動(dòng)Mi的開(kāi)始執(zhí)行時(shí)間約束。其中，Mi∈M，Begi≥SCBeg。

Endi：活動(dòng)Mi的執(zhí)行結(jié)束時(shí)間約束。其中，Mi∈M，Endi≤SCEnd。

2.2 復(fù)雜操作約束形式化描述

2.2.1 優(yōu)化變量

dsti：表示活動(dòng)Mi被安排時(shí)的開(kāi)始執(zhí)行時(shí)間。

2.2.2 優(yōu)化目標(biāo)

最大化任務(wù)執(zhí)行總效益

2.2.3 約束條件

1）每個(gè)任務(wù)Mi最多只被執(zhí)行一次，且只能在一個(gè)時(shí)間窗口內(nèi)執(zhí)行，或即使被執(zhí)行多次也只計(jì)算一次的收益，即

2）資源最大使用時(shí)長(zhǎng)。該約束用于表示在一個(gè)軌道周期或給定時(shí)長(zhǎng)內(nèi)的總側(cè)擺次數(shù)和開(kāi)機(jī)工作時(shí)長(zhǎng)不能超過(guò)其允許的上限范圍，即

3）任務(wù)執(zhí)行時(shí)間約束。每個(gè)任務(wù)都需要被分配在其所屬規(guī)劃時(shí)間區(qū)間內(nèi)，該條件多用于表示周期性覆蓋或者受光照等約束的應(yīng)急任務(wù)或通信任務(wù)中。即，如果

4）為每個(gè)任務(wù)分配的觀(guān)測(cè)窗口需要滿(mǎn)足成像資源的可用性約束和任務(wù)的觀(guān)測(cè)時(shí)長(zhǎng)約束。在調(diào)度過(guò)程中，如果為任務(wù)Mi分配了資源Rj以及相應(yīng)的可見(jiàn)時(shí)間窗口，則該任務(wù)的觀(guān)測(cè)時(shí)間段必須完全落在分配的可見(jiàn)時(shí)間窗口內(nèi)。該約束表示如下：

對(duì)于任意的Mi∈M，以及任意的Rj∈R(Mi)，k∈{1，2，…，Ni，j}，如果，則

5）同一資源上的連續(xù)兩個(gè)觀(guān)測(cè)任務(wù)間的最小轉(zhuǎn)換時(shí)長(zhǎng)約束。上述分析可知，衛(wèi)星在執(zhí)行任務(wù)的過(guò)程中，星載傳感器的側(cè)擺角和旋轉(zhuǎn)角隨著不同開(kāi)始執(zhí)行時(shí)間變化，因此，安排在同一資源上相鄰的兩個(gè)任務(wù)，需要考慮任務(wù)間的最小轉(zhuǎn)換時(shí)長(zhǎng)，從而使得衛(wèi)星或者星載傳感器調(diào)整到正確的姿態(tài)。同時(shí)考慮到兩個(gè)任務(wù)的不同執(zhí)行先后順序，該約束表示如下：

對(duì)于任意的Rj∈R和分配在該資源上的任意兩個(gè)連續(xù) 觀(guān)測(cè)任務(wù)序列Mi，Mi'∈M(Rj)，如 果且同時(shí)成 立，則

6）成像資源類(lèi)型選擇約束。當(dāng)任務(wù)Mi選定資源Rj以及相應(yīng)的可見(jiàn)時(shí)間窗口時(shí)，必須滿(mǎn)足當(dāng)前情況下資源Rj是可用的，并且資源Rj對(duì)應(yīng)的載荷圖像類(lèi)型能夠滿(mǎn)足活動(dòng)要求的成像類(lèi)型要求。即，如果，則

7）優(yōu)化變量取值約束。對(duì)于任意的Mi∈M、資源Rj∈R(Mi)，以及所有的k∈{1，2，…，Ni，j}，有如下約束：

3 改進(jìn)差分進(jìn)化算法

針對(duì)成像衛(wèi)星調(diào)度這一NP 完全問(wèn)題的求解，為提高問(wèn)題的求解效率，首先可以對(duì)該問(wèn)題進(jìn)行分類(lèi)，然后再采用相應(yīng)的算法進(jìn)行求解。考慮在通常情況下，當(dāng)問(wèn)題求解規(guī)模較大時(shí)，該問(wèn)題往往很難得到一組可行解，此時(shí)，只能通過(guò)一些典型的智能算法進(jìn)行求解。而差分進(jìn)化（Differential Evolu?tion，DE）算法是一種用于最優(yōu)化問(wèn)題的后設(shè)啟發(fā)式算法，是一種基于實(shí)數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法。在相關(guān)已有工作中，大量研究表明DE 是一種性能非常好的求解實(shí)數(shù)編碼優(yōu)化問(wèn)題的啟發(fā)式方法。為了提高調(diào)度方案解的優(yōu)越性及算法的運(yùn)行效率，本文是在標(biāo)準(zhǔn)DE 基礎(chǔ)上，加入調(diào)度預(yù)處理操作和一些啟發(fā)式思想對(duì)成像衛(wèi)星調(diào)度問(wèn)題進(jìn)行求解。同樣，當(dāng)采用近似算法對(duì)問(wèn)題進(jìn)行求解后，往往還存在很多未完成的任務(wù)，這時(shí)可通過(guò)再次運(yùn)用確定性算法，為未完成的任務(wù)在剩余的時(shí)間窗口內(nèi)嘗試重新選取時(shí)間窗口，從而進(jìn)一步達(dá)到問(wèn)題最優(yōu)解的定義。

在演化的過(guò)程中，算法中涉及的幾項(xiàng)重要操作（調(diào)度預(yù)處理、沖突消除、效益值計(jì)算、可行解二次優(yōu)化）如下。

3.1 調(diào)度預(yù)處理

首先，對(duì)衛(wèi)星系統(tǒng)資源及用戶(hù)需求進(jìn)行分析，優(yōu)先處理多星聯(lián)合對(duì)地覆蓋過(guò)程中只與其靜態(tài)覆蓋性能相關(guān)的約束，計(jì)算所有滿(mǎn)足星地觀(guān)測(cè)需求的可見(jiàn)時(shí)間窗口集合。只有當(dāng)觀(guān)測(cè)需求同時(shí)具有可用資源和可用時(shí)間時(shí)，才認(rèn)為該觀(guān)測(cè)需求可能被完成，需要通過(guò)進(jìn)一步調(diào)度來(lái)確定其是否被執(zhí)行、執(zhí)行該觀(guān)測(cè)需求的衛(wèi)星和為其分配的成像時(shí)間段。其次，當(dāng)任務(wù)至少存在一個(gè)可見(jiàn)時(shí)間窗口且在調(diào)度過(guò)程中可能被執(zhí)行時(shí)，分析該任務(wù)的可見(jiàn)時(shí)間窗口區(qū)間上的資源爭(zhēng)用沖突度，考慮優(yōu)先安排含有空閑資源的任務(wù)，旨在降低問(wèn)題的搜索空間，提高算法求解效率。

針對(duì)某一假定調(diào)度規(guī)劃場(chǎng)景，經(jīng)過(guò)調(diào)度預(yù)處理操作，可生成衛(wèi)星與目標(biāo)之間的可見(jiàn)時(shí)間窗口約束集，如圖1 所示。

種群中個(gè)體上每個(gè)基因位編碼為一個(gè)任務(wù)的執(zhí)行狀態(tài)（包括任務(wù)屬性、是否被安排執(zhí)行、被安排的觀(guān)測(cè)資源和觀(guān)測(cè)時(shí)間窗口），種群中的每個(gè)個(gè)體對(duì)應(yīng)一個(gè)調(diào)度可行解。個(gè)體的初始化主要分為兩個(gè)方面：1）采用基于任務(wù)執(zhí)行時(shí)間優(yōu)先或基于任務(wù)執(zhí)行收益優(yōu)先的貪心算法得到的可行解，對(duì)個(gè)體中的部分任務(wù)進(jìn)行編碼，調(diào)度方案中未能完成的剩余任務(wù)則在其可見(jiàn)時(shí)間窗口集中隨機(jī)選擇進(jìn)行編碼；2）首先對(duì)擁有空閑時(shí)間區(qū)間的任務(wù)進(jìn)行編碼，其次為剩余的任務(wù)在其所有可見(jiàn)時(shí)間窗口中隨機(jī)選擇進(jìn)行編碼。

圖1 調(diào)度預(yù)處理Fig.1 Scheduling preprocessing

3.2 沖突消除

當(dāng)個(gè)體中的多個(gè)任務(wù)爭(zhēng)用資源產(chǎn)生資源沖突情況時(shí)，如何消除資源沖突，通常情況下是采用其中一個(gè)個(gè)體的沖突基因位重新隨機(jī)選擇時(shí)間窗口，而對(duì)于這類(lèi)資源沖突較大的情況，重新選擇的時(shí)間窗口往往會(huì)引起與其他任務(wù)更多的資源沖突情況，因此，對(duì)于發(fā)生資源沖突的基因位選擇新的資源和執(zhí)行時(shí)間窗口也是至關(guān)重要的。運(yùn)用啟發(fā)式的思想，當(dāng)為個(gè)體中兩個(gè)成像任務(wù)分配的資源和執(zhí)行時(shí)間不滿(mǎn)足約束條件，則需要消除一個(gè)任務(wù)，為其重新分配資源和執(zhí)行時(shí)間。為了使得該優(yōu)化序列的效益值最大，可通過(guò)以下方式選擇消除的基因位：1）沖突基因位的沖突效益值；2）沖突基因位的可見(jiàn)時(shí)間窗口長(zhǎng)度和時(shí)間窗口的沖突度。

在 同一資源上 執(zhí)行的任 務(wù)M1、Mi、Mj、Mk，有任務(wù)Mi、Mj、Mk執(zhí)行時(shí)間 窗口相互沖突，如 圖1 所示。其中，任務(wù)Mi和Mk的沖突度均為1，而任務(wù)Mj的沖突度為2，且該任務(wù)的可見(jiàn)時(shí)間窗口長(zhǎng)度最大，故為任務(wù)Mj重新選擇時(shí)間窗口。在重新選擇的時(shí)間窗口時(shí)，任務(wù)Mj的第一個(gè)時(shí)間窗口又可能會(huì)引起任務(wù)Mi和Mk的沖突，故為任務(wù)Mj重新分配的執(zhí)行時(shí)間窗口為第3 個(gè)可見(jiàn)時(shí)間窗口。

3.3 效益值計(jì)算

通常情況下，效益值的計(jì)算是直接與任務(wù)完成個(gè)數(shù)或個(gè)體沖突度相關(guān)聯(lián)的［18］，即適應(yīng)度函數(shù)值的計(jì)算與個(gè)體效益值無(wú)關(guān)，只與完成個(gè)數(shù)和沖突度相關(guān)，即沖突個(gè)數(shù)相等的兩個(gè)個(gè)體效益值相等，同樣對(duì)于如下情況計(jì)算得到的效益值也是相等的。

假設(shè)任務(wù)Mi、Mj、Mk有相同的效益值，顯然，對(duì)于圖2 所示任務(wù)執(zhí)行狀態(tài)1，在調(diào)度方案中只需要消除任務(wù)Mj，就可完成Mi和Mk兩項(xiàng)任務(wù)，而對(duì)于圖3所示任務(wù)執(zhí)行狀態(tài)2，無(wú)論如何消除沖突，調(diào)度方案中最終只有一個(gè)任務(wù)可以被完成。

對(duì)于上述情況，可以采取一種個(gè)體任務(wù)沖突度的方式消除沖突。個(gè)體適應(yīng)度評(píng)估函數(shù)為

圖2 任務(wù)執(zhí)行沖突1Fig.2 Mission execution conflict of case 1

圖3 任務(wù)執(zhí)行沖突2Fig.3 Mission execution conflict of case 2

式中：任 務(wù)Mi、Mj、Mk的效益值分別為wi、wj、wk，故任務(wù)Mi、Mj、Mk的沖突度分別為Vi、Vj、Vk，Vi=wj+wk，Vj=wi+wk，Vk=wi+wj，按任務(wù)沖 突度降序排序，依次刪除任務(wù)，直到個(gè)體中無(wú)任務(wù)沖突為止，此時(shí)再計(jì)算個(gè)體中的所有分配時(shí)間窗口的任務(wù)的效益之總和。這樣可以更大限度地保留效益值或權(quán)重較大的任務(wù)，從而更有效地選出效益值較大的個(gè)體，生成較優(yōu)的調(diào)度方案。

3.4 可行解二次優(yōu)化

當(dāng)采用近似算法求解該衛(wèi)星星座調(diào)度問(wèn)題時(shí)，對(duì)于每次求解生成的調(diào)度方案，針對(duì)性地用確定性算法對(duì)調(diào)度結(jié)果進(jìn)行二次優(yōu)化。針對(duì)某一次的調(diào)度結(jié)果，主要從任務(wù)完成率、資源利用率和時(shí)效性3個(gè)方面對(duì)指定衛(wèi)星系統(tǒng)的本次調(diào)度方案進(jìn)行評(píng)估。對(duì)于當(dāng)前調(diào)度結(jié)果，如果存在由于資源沖突而未能完成的任務(wù)，或者為任務(wù)分配的時(shí)間段對(duì)其要求的時(shí)間限有延遲，則通過(guò)調(diào)度優(yōu)化操作可以在任務(wù)完成率、資源利用率和時(shí)效性3 個(gè)方面都能夠進(jìn)行優(yōu)化，從而進(jìn)一步解決并優(yōu)化調(diào)度結(jié)果，使得調(diào)度結(jié)果更優(yōu)，并能夠滿(mǎn)足用戶(hù)的需求。

1）對(duì)調(diào)度結(jié)果中的所有已分配時(shí)間窗口的任務(wù)進(jìn)行時(shí)間優(yōu)化。找出已分配時(shí)間窗口的任務(wù)，結(jié)合預(yù)處理結(jié)果，將所有任務(wù)的分配時(shí)間窗口前移，且主要針對(duì)有時(shí)間延遲的任務(wù)，嘗試為其選擇更好的執(zhí)行時(shí)間窗口。

2）為調(diào)度方案中因資源沖突未完成的任務(wù)重新搜索時(shí)間窗口。針對(duì)上一步操作，對(duì)經(jīng)過(guò)時(shí)間優(yōu)化后的調(diào)度結(jié)果進(jìn)行分析，找出所有因資源沖突而未能安排的任務(wù)，遍歷其所有可見(jiàn)時(shí)間窗口，嘗試為其重新選擇執(zhí)行時(shí)間窗口。

4 仿真試驗(yàn)及結(jié)果分析

4.1 場(chǎng)景管理

成像偵察衛(wèi)星需要包括觀(guān)測(cè)衛(wèi)星及其所載傳感器。為了使本文設(shè)計(jì)的成像偵察衛(wèi)星系統(tǒng)資源更加切合實(shí)際，從國(guó)外衛(wèi)星應(yīng)用強(qiáng)國(guó)發(fā)射并投入使用的觀(guān)測(cè)衛(wèi)星中選取了5 顆構(gòu)造了一個(gè)成像偵察衛(wèi)星 網(wǎng)，分別 是SPOT-5、MTI、ORBVIEW-3、IKO?NOS-2、EO-1，衛(wèi)星軌道參數(shù)可查詢(xún)AGI 公司發(fā)布的全球衛(wèi)星軌道數(shù)據(jù)庫(kù)。隨著衛(wèi)星應(yīng)用的深入，衛(wèi)星星上載荷類(lèi)型不斷豐富，從傳感器角度看，包括可見(jiàn)光、紅外、多光譜、高光譜、合成孔徑雷達(dá)（Syn?thetic Aperture Radar，SAR）等多種傳感器類(lèi)型。為體現(xiàn)成像類(lèi)型約束，本文中星載傳感器的性能參數(shù)設(shè)置見(jiàn)表1。場(chǎng)景仿真周期為2018-01-01 00∶00∶00—2018-01-01 18∶00∶00

表1 傳感器參數(shù)Tab.1 Sensor parameters

地面目標(biāo)即觀(guān)測(cè)目標(biāo)，它是生成觀(guān)測(cè)任務(wù)的基本要素。本文在地球陸地范圍內(nèi)隨機(jī)選取了100 個(gè)地面目標(biāo)以及中國(guó)境內(nèi)的35 個(gè)城市作為目標(biāo)。這個(gè)地面目標(biāo)集合具有一定的代表性，基本上能夠以一定的密度覆蓋地球陸地。地面目標(biāo)的具體分布如圖4 所示（軟件STK 提供的二維平面地圖）。圖4中，紅色圓點(diǎn)表示待成像的地面目標(biāo)，陰影部分表示星載傳感器在當(dāng)前時(shí)刻對(duì)地面的覆蓋范圍。在實(shí)際應(yīng)用中，經(jīng)常會(huì)對(duì)某一個(gè)地區(qū)比較集中的若干點(diǎn)目標(biāo)進(jìn)行觀(guān)測(cè)，從而引起任務(wù)對(duì)資源的爭(zhēng)用沖突，因此，在地面目標(biāo)集也設(shè)計(jì)了幾組位置比較集中的點(diǎn)目標(biāo)，這種目標(biāo)比較集中的觀(guān)測(cè)任務(wù)往往會(huì)帶來(lái)對(duì)衛(wèi)星資源的需求沖突問(wèn)題，采用手工計(jì)算很難解決，必須依靠計(jì)算機(jī)來(lái)解決。

圖4 二維地面目標(biāo)分布圖Fig.4 2D ground-target distribution

4.2 規(guī)劃結(jié)果

對(duì)于上述測(cè)試實(shí)例計(jì)算可得，任務(wù)完成理論上限為135 個(gè)。分別采用標(biāo)準(zhǔn)DE 和基于啟發(fā)式思想的改進(jìn)DE 進(jìn)行求解，實(shí)驗(yàn)生成的調(diào)度方案結(jié)果對(duì)比見(jiàn)表2 和表3。

表2 標(biāo)準(zhǔn)DE 任務(wù)完成情況Tab.2 Mission completion status with the standard DE

4.3 結(jié)果分析

1）標(biāo)準(zhǔn)DE 和改進(jìn)DE 對(duì)該問(wèn)題的求解，算法性能對(duì)比分析。

測(cè)試方案的任務(wù)完成率和任務(wù)完成效益比值分別如圖5 和圖6 所示。圖中，紅線(xiàn)表示任務(wù)完成上限，綠線(xiàn)表示采用改進(jìn)DE 得到的結(jié)果，藍(lán)線(xiàn)表示采用標(biāo)準(zhǔn)DE 得到的結(jié)果。

由圖5 和圖6 可知：本文在問(wèn)題的求解過(guò)程中，采用啟發(fā)式思想消除個(gè)體沖突和計(jì)算適應(yīng)值，可以有效地生成較好的任務(wù)規(guī)劃結(jié)果，生成調(diào)度方案的任務(wù)完成率和任務(wù)完成效益非常接近于任務(wù)完成理論上限值，并且對(duì)于每一組調(diào)度方案，任務(wù)的完成效益都大于任務(wù)的完成率。

表3 改進(jìn)DE 任務(wù)完成情況Tab.3 Mission completion status with the improved DE

圖5 測(cè)試方案的任務(wù)完成率Fig.5 Mission completion rate of the test scheme

圖6 測(cè)試方案的任務(wù)完成效益率Fig.6 Mission completion benefit rate of the test scheme

2）采用調(diào)度優(yōu)化模塊對(duì)調(diào)度方案的結(jié)果影響分析。

采用標(biāo)準(zhǔn)DE 生成調(diào)度方案的任務(wù)完成率和任務(wù)完成效益比值分別如圖7 和圖8 所示。圖中，紅線(xiàn)表示任務(wù)完成上限，藍(lán)線(xiàn)表示直接采用標(biāo)準(zhǔn)DE得到的結(jié)果，綠線(xiàn)表示在調(diào)度方案的基礎(chǔ)上采用調(diào)度優(yōu)化模塊后得到的結(jié)果。

圖7 標(biāo)準(zhǔn)DE 生成調(diào)度方案的任務(wù)完成率Fig.7 Mission completion rate of the scheduling scheme generated by the standard DE algorithm

圖8 標(biāo)準(zhǔn)DE 生成調(diào)度方案的任務(wù)完成效益Fig.8 Mission completion benefit rate of the scheduling scheme generated by the standard DE algorithm

采用DE 生成調(diào)度方案的任務(wù)完成率和任務(wù)完成效益比值分別如圖9 和圖10 所示。圖中，紅線(xiàn)表示任務(wù)完成上限，藍(lán)線(xiàn)表示直接采用改進(jìn)DE 得到的結(jié)果，綠線(xiàn)表示在調(diào)度方案的基礎(chǔ)上采用調(diào)度優(yōu)化模塊后得到的結(jié)果。

由調(diào)度優(yōu)化模塊對(duì)調(diào)度方案的影響結(jié)果分析圖可知，當(dāng)采用近似算法求解該衛(wèi)星星座調(diào)度問(wèn)題時(shí)，對(duì)于每次求解生成的調(diào)度方案，具有針對(duì)性地用確定性算法對(duì)調(diào)度結(jié)果進(jìn)行二次優(yōu)化。對(duì)于存在由于資源沖突而未能完成的任務(wù)，或者為任務(wù)分配的時(shí)間段對(duì)其要求的時(shí)間限有延遲，則通過(guò)調(diào)度優(yōu)化操作可以在任務(wù)完成率、資源利用率和時(shí)效性3 個(gè)方面都能夠進(jìn)行優(yōu)化，從而進(jìn)一步解決并優(yōu)化調(diào)度結(jié)果，使得調(diào)度結(jié)果更優(yōu)，并能夠滿(mǎn)足用戶(hù)的需求。

圖9 改進(jìn)DE 生成調(diào)度方案的任務(wù)完成率Fig.9 Mission completion rate of the scheduling scheme generated by the improved DE algorithm

圖10 改進(jìn)DE 生成調(diào)度方案的任務(wù)完成效益Fig.10 Mission completion benefit rate of the scheduling scheme generated by the improved DE algorithm

5 結(jié)束語(yǔ)

本文通過(guò)分析成像衛(wèi)星的成像過(guò)程和工作原理，建立了多成像衛(wèi)星的約束滿(mǎn)足最優(yōu)化調(diào)度規(guī)劃模型。在此基礎(chǔ)上，采用啟發(fā)式算法思想，設(shè)計(jì)了成像衛(wèi)星聯(lián)合任務(wù)規(guī)劃問(wèn)題的改進(jìn)DE 求解方案。通過(guò)測(cè)試實(shí)例發(fā)現(xiàn)，在改進(jìn)DE 迭代過(guò)程中采用啟發(fā)式算法思想，消除個(gè)體中任務(wù)的沖突并計(jì)算個(gè)體適應(yīng)值，可以快速地生成較優(yōu)的調(diào)度方案。調(diào)度優(yōu)化操作的實(shí)現(xiàn)對(duì)每一次調(diào)度結(jié)果進(jìn)行優(yōu)化，可以進(jìn)一步提高本次調(diào)度方案的任務(wù)完成率、資源利用率和時(shí)效性。同時(shí)，調(diào)度優(yōu)化操作的實(shí)現(xiàn)，同樣也可以應(yīng)用到應(yīng)急調(diào)度中，從而生成較優(yōu)的調(diào)度方案。