龍運軍，陳宇寧，陳英武，邢立寧

(國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)與管理學(xué)院，長沙 410073)

1 概述

多星成像調(diào)度問題已被證明是NP-hard問題[1]，人們至今未有較完善的解決方案。以往國內(nèi)外的學(xué)者主要采用數(shù)學(xué)規(guī)劃和圖論的方法建模[2]。Petri網(wǎng)既是圖形工具又是數(shù)學(xué)工具，具有圖形直觀、能描述沖突和并發(fā)、能以狀態(tài)分布矩陣表示等優(yōu) 點，是研究離散動態(tài)系統(tǒng)最有效的工具[3]。用Petri網(wǎng)表達具有多種約束和邏輯關(guān)系的優(yōu)化問題，再結(jié)合現(xiàn)代優(yōu)化方法求解，是一個值得研究的重要課 題。據(jù)目前掌握的資料，國內(nèi)外尚未有采用 Petri網(wǎng)對多星成像調(diào)度問題建模的公開成果。本文通過在普通 Petri網(wǎng)中引入指標信息來克服數(shù)學(xué)規(guī)劃模型直觀性差和圖論模型難以描述多星調(diào)度諸多約束的缺點，以直觀有效地形式描述多星成像調(diào)度問題，特別是衛(wèi)星資源爭用和多星并發(fā)觀測問題。

基于 Petri網(wǎng)調(diào)度問題的求解算法研究近年來受到了很多的關(guān)注。文獻[4]提出一種通過Petri網(wǎng)和A*算法生成可行調(diào)度的方法；文獻[5]探討了基于 Petri網(wǎng)變遷序列編碼的遺傳調(diào)度優(yōu)化算法；文獻[6-7]探討了 Petri網(wǎng)和混合算法相結(jié)合的優(yōu)化方法。本文利用多星成像調(diào)度問題的鄰域特性，在 Petri網(wǎng)中引入指標信息對多星成像調(diào)度問題進行描述，利用蟻群算法和局部搜索技術(shù)優(yōu)化變遷序列，對多星成像調(diào)度問題進行求解。

2 相關(guān)符號說明

多星成像調(diào)度問題研究M顆衛(wèi)星對N個任務(wù)實施偵察，已知各任務(wù)的時間窗口約束和相鄰任務(wù)之間的側(cè)擺轉(zhuǎn)換時間約束，要求將衛(wèi)星資源分配給各個任務(wù)使得觀測總的收益值達到最大。

相關(guān)符號說明如下：

(1)觀測任務(wù)集T={t1, t2,… ,tNT}，衛(wèi)星集合S={s1, s2,…,sNS}，NT和NS分別表示待觀測的任務(wù)總數(shù)和衛(wèi)星總數(shù)。

(2)衛(wèi)星sk對任務(wù)ti的時間窗為[W Ski,WEki]，觀測時間段為[Ski, Eki]。

(3)衛(wèi)星sk最大側(cè)擺Rk次，實際側(cè)擺次數(shù)為rk，其側(cè)擺速率為λ，側(cè)擺后穩(wěn)定時間為d。

(4)Okj表示衛(wèi)星sk的第 j個觀測活動，其觀測時間段為[O Skj, O Ekj]，側(cè)擺角為Gj，nk為衛(wèi)星sk觀測活動總數(shù)。

(5)決策變量集X={ x1, x2,… ,xNT}，且 ?i∈{1,2,… ,NT}，xi∈ {0,1}。 xi= 1表示任務(wù)ti被安排觀測，xi= 0表示任務(wù)ti不被安排觀測。

(6)任務(wù)集 T對應(yīng)的觀測收益集為P={ p1, p2,…,p NT}。

以最大化被安排觀測任務(wù)的總收益值為調(diào)度目標，則該問題的目標函數(shù)可以表示為：

式(2)表示觀測時間段必須在可見時間窗口內(nèi)；式(3)表示受能量和存儲量的限制，衛(wèi)星實際側(cè)擺次數(shù)不能大于其最大側(cè)擺次數(shù)；式(4)表示相鄰兩次觀測必須滿足側(cè)擺轉(zhuǎn)換時間約束。

3 多星成像調(diào)度

Petri網(wǎng)在描述和分析離散事件動態(tài)系統(tǒng)中具有重要作用，因此，在多星成像調(diào)度問題建模中得到采用。

3.1 一類綜合指標Petri網(wǎng)

在基于規(guī)則的系統(tǒng)控制與調(diào)度中，基本 Petri網(wǎng)難以有效反映系統(tǒng)外部的基于規(guī)則控制等因素，因此需要對其進行擴展。本文在基本 Petri網(wǎng)的基礎(chǔ)上增加了能夠影響系統(tǒng)進程的指標，定義了一類綜合指標Petri網(wǎng)(Integrated Indexes Petri Net, IIPN)。

定義 綜合指標 Petri網(wǎng)為一個五元組IIPN=(P, T, F, M , P r)，其中：

(1)P為庫所集合，T為變遷集合，F(xiàn)為流關(guān)系集合，且：

為與變遷相關(guān)的指標集合。

3.2 綜合調(diào)度規(guī)則

以 IIPN為基礎(chǔ)，根據(jù)以下規(guī)則可以構(gòu)建多星成像調(diào)度問題的IIPN模型。

規(guī)則1 建立任務(wù)庫所集合 Task={T1, T2,…,TN}，其中，Ti是按照任務(wù)可見時間窗的先后順序排列的，N表示任務(wù)總數(shù)，當托肯到達某個任務(wù)庫所時代表該任務(wù)已完成成像活動。

規(guī)則2 任務(wù)庫所集合中增加一個虛任務(wù)Tstart，并且把Tstart作為T1的前序任務(wù)。

規(guī)則3 設(shè)置一個變遷預(yù)處理階段，在此階段中利用遙感器側(cè)擺轉(zhuǎn)換時間約束消除所有無效變遷。

規(guī)則4 建立一個變遷序列：

規(guī)則5 托肯代表當前觀測方案，初始時刻，觀測方案中沒有任務(wù)，每當托肯到達一個任務(wù)庫所，就把該任務(wù)添入觀測方案中。

規(guī)則6 從一個任務(wù)庫所到另外一個任務(wù)庫所需要經(jīng)過一個變遷，變遷的點火需要一個托肯和一個衛(wèi)星資源庫所的參與，變遷可包含多種指標，根據(jù)問題的特點和求解的需要設(shè)計指標信息。對指標的不同運用可以反映不同的調(diào)度需求，把指標綜合在一起則是一種綜合調(diào)度規(guī)則。

3.3 變遷指標設(shè)計

多星的短期調(diào)度具有2個重要特點：(1)多個任務(wù)競爭一顆衛(wèi)星資源；(2)一個任務(wù)具有多顆衛(wèi)星并發(fā)觀測?？梢姡斎蝿?wù)規(guī)模較大時，多星成像調(diào)度問題是一個組合爆炸問題。針對多星成像調(diào)度問題的特點，為有效降低解空間的復(fù)雜度，提高解搜索的效率，設(shè)計如下變遷指標。

指標1任務(wù)收益值p。任務(wù)收益值表示任務(wù)一旦被觀測可獲得的收益，它反映了任務(wù)的重要程度，采用該指標可以有效解決衛(wèi)星資源競爭問題，且本文將以觀測方案的總收益值作為評價方案優(yōu)劣的標準。

指標2 側(cè)擺角slewAngle。側(cè)擺角是衛(wèi)星觀測任務(wù)時星載遙感器偏離星下線的角度，側(cè)擺消耗衛(wèi)星能量，采用該指標可以有效解決多星并發(fā)觀測的問題。圖1所示為5個任務(wù)和2顆衛(wèi)星的實例應(yīng)用規(guī)則1～規(guī)則 5所構(gòu)建的 IIPN模型。經(jīng)過預(yù)處理階段得到各任務(wù)的可見時間窗，可以通過甘特圖來表示，衛(wèi)星與任務(wù)之間的可見關(guān)系如圖2所示。

圖1 2顆衛(wèi)星5個任務(wù)構(gòu)建的IIPN模型

圖2 衛(wèi)星與任務(wù)可見關(guān)系甘特圖

4 混合蟻群優(yōu)化算法

在基本蟻群算法中，人工螞蟻按照狀態(tài)轉(zhuǎn)移規(guī)則逐步構(gòu)建可行解，它們將一些隨機性引入到優(yōu)化結(jié)果中，因此，基本蟻群算法很難快速地找到待優(yōu)化問題的全局最優(yōu)解。為提高求解效率，采用局部搜索技術(shù)來輔助蟻群優(yōu)化過程。綜合蟻群優(yōu)化與局部搜索的方法已經(jīng)成功運用于作業(yè)車間調(diào)度問題和帶寬最小化問題等組合優(yōu)化問題[8]。本文將混合基本蟻群算法和局部搜索技術(shù)求解多星優(yōu)化問題。

4.1 信息素的定義和初始化

將“給定變遷被選擇的概率”定義為方案空間上的信息素。用一個t×s維的矩陣Tao來記錄信息素，t代表所有任務(wù)的個數(shù)，s代表所有衛(wèi)星的個數(shù)。對于Tao中任意的元素τij，它的含義為選擇用第 j顆衛(wèi)星來觀測第i個任務(wù)的概率。初始化階段，信息素矩陣Tao中的元素都為0τ。

4.2 可行解的構(gòu)造

4.2.1 構(gòu)造機制

在構(gòu)造可行解之前首先要根據(jù)衛(wèi)星和任務(wù)的可見關(guān)系確定每個任務(wù)的變遷集合TR_set。然后將AntNum只螞蟻放在初始節(jié)點Tstart處，在每一個解構(gòu)造步，按照狀態(tài)轉(zhuǎn)移概率選擇一個變遷，變遷實施后得到下一個任務(wù)，從而完成螞蟻從當前任務(wù)到下一個任務(wù)的移動。每一只螞蟻將實施過的變遷以序列的形式存儲在當前路徑中，并且放置一定數(shù)量的信息素在所選擇的變遷上。當螞蟻到達終止標識也就是最后一個任務(wù)Te時，就可得到一個從初始標識到終止標識的變遷實施序列，此即該螞蟻找到的問題的可行解。

4.2.2 狀態(tài)轉(zhuǎn)移規(guī)則

從初始節(jié)點Tstart開始，對于每一任務(wù)Ti，按照以下的概率分布為該任務(wù)選擇下一個需要實施的變遷：

為[0, 1]之間均勻分布的隨機數(shù)；q0為選擇隨機性參數(shù)。當 q≤q0時，按照信息素選擇變遷；當q＞q0時，?按照如下的概率分布選擇變遷：

其中，Pr(j, s, t)為t時刻為任務(wù)Ti選擇變遷Trjs的概率。

4.2.3 啟發(fā)式信息

概率選擇是依據(jù)信息素強度τjs以及啟發(fā)式信息ηjs的指引。在多星成像調(diào)度的IIPN模型中，變遷包含任務(wù)收益值p和側(cè)擺角 slewAngle2個指標，本文將啟發(fā)式信息ηjs設(shè)計為這2個指標的函數(shù)如下：收益值和側(cè)擺角；、是本步驟可實施變遷集中所有可實施變遷的平均收益值和平均側(cè)擺角。

其中，pjs、sajs分別為可實施變遷集 j中變遷Trjs的

4.3 信息素的更新

4.3.1 信息素的局部更新

在每次迭代完成后，本次迭代獲得的最優(yōu)調(diào)度的螞蟻可應(yīng)用局部更新規(guī)則來更新當前的信息素水平。局部更新規(guī)則基于本次迭代所獲得的最優(yōu)調(diào)度來完成對信息素的更新。更新方式如下：

其中，ρlocal∈ (0,1)為局部信息素揮發(fā)系數(shù)。采用局部更新規(guī)則可以實現(xiàn)分化機制，避免算法過早陷入局部最優(yōu)。

4.3.2 信息素的全局更新

在蟻群優(yōu)化的迭代過程中，自開始迭代到當前迭代過程中獲得全局較優(yōu)調(diào)度的螞蟻可以應(yīng)用全局更新規(guī)則來更新當前的信息素水平。精英策略[9]選擇一次迭代中的最優(yōu)解完成信息素的更新，容易導(dǎo)致過早收斂。優(yōu)化排序策略[10]將一次迭代中的解進行排序，根據(jù)位次加權(quán)更新信息素。本文采用最優(yōu)解隊列(Best Solution Queue, BSQ)進行全局更新，最優(yōu)解隊列中始終保持當前若干個最優(yōu)解，若迭代過程中得到更優(yōu)的解，則進行替換。每完成一次迭代后，更新最優(yōu)解隊列，同時應(yīng)用全局更新規(guī)則更新信息素。全局更新方式如下：

其中， ρglobal∈ (0,1)這里；Δτjs為信息素增量，其定義如下：

其中， Pl為螞蟻l所走的變遷路徑總收益；為所有任務(wù)的總收益值。

4.4 蟻群混合局部搜索

對于蟻群算法這樣的群智能優(yōu)化算法，全局搜索能力較強是因為每次迭代螞蟻的搜索不是基于某種鄰域結(jié)構(gòu)的搜索，螞蟻不需要被某種鄰域結(jié)構(gòu)所束縛。而缺點是一旦螞蟻找到一個較好的鄰域結(jié)構(gòu)，一個較優(yōu)的解甚至最優(yōu)的解也許就在領(lǐng)域結(jié)構(gòu)中，但螞蟻卻沒有珍惜，從而導(dǎo)致迭代次數(shù)的大量增加。為此，本文在算法的每次迭代中加入局部搜索策略，混合局部搜索的算法取名為ACO-LS算法。

4.4.1 局部搜索

算法每次迭代完以后，對最優(yōu)解隊列 BSQ進行局部搜索。局部搜索基于給定解的鄰域結(jié)構(gòu)，采用插入未安排任務(wù)變遷和替換任務(wù)變遷的方法。插入未安排任務(wù)變遷就是將一個未安排任務(wù)變遷插入到某個已安排的任務(wù)變遷之后；替換任務(wù)變遷就是用未安排任務(wù)變遷來替換已安排任務(wù)變遷。用局部搜索后的最優(yōu)解來更新最優(yōu)解隊列BSQ。

4.4.2 動態(tài)隨機性參數(shù)

局部搜索可以有效加速收斂。蟻群算法的主要任務(wù)在于提高全局搜索能力，以發(fā)現(xiàn)更好的鄰域結(jié)構(gòu)。本文給隨機性參數(shù)q0設(shè)定一個閾值。如果當前最優(yōu)解連續(xù)σ次迭代沒有改進，隨機性參數(shù)取0lq，以增大其對變遷選擇的隨機性，直到其出現(xiàn)更優(yōu)的解，隨機性參數(shù)取q0h，以輔助加速收斂。

4.4.3 混合蟻群算法的優(yōu)化流程

蟻群混合局部搜索的優(yōu)化流程如圖3所示。

圖3 蟻群混合局部搜索的優(yōu)化流程

4.5 終止條件

多星成像調(diào)度問題的目前還沒有標準的測試實例，而且在實際的工程應(yīng)用中問題規(guī)模是隨機的，因此問題的最優(yōu)調(diào)度解通常是未知的。本文以預(yù)設(shè)的最大迭代次數(shù)作為算法的終止條件。

5 仿真實例與分析

目前，在衛(wèi)星調(diào)度領(lǐng)域，還沒有公認的測試集，常見的做法是采用隨機生成任務(wù)方法驗證算法，仿真實例生成規(guī)則如下：

(1)在區(qū)域(北緯[20°, 50°]，東經(jīng)[70°, 130°])內(nèi)按照均勻分布生成點目標，并忽略任務(wù)對遙感器的類型要求及分辨率要求。目標數(shù)量 M取值為{100,200,300}。

(2)衛(wèi)星數(shù)量取值為{3,4,5}。

(3)任務(wù)收益值從[1,10]之間隨機生成。

(4)任務(wù)與衛(wèi)星的時間窗口采用STK軟件生成。

ACO-LS算法的參數(shù)設(shè)置如表1所示，算法均采用C#實現(xiàn)，編譯環(huán)境為VS.net 2005，實例在配置為Core(TM)i3 2.93 GHz CPU，2 GB內(nèi)存的計算機上運行。

表1 ACO-LS算法的參數(shù)設(shè)置

5.1 模型與算法有效性測試

以多星成像調(diào)度問題的約束滿足模型為基礎(chǔ)，文獻[11]采用禁忌搜索算法求解。為驗證本文模型和算法性能，將本文求解結(jié)果與其進行比較。每個算例在2種算法上各運行10次，結(jié)果取10次的均值，計算結(jié)果如表 2所示。其中，算例名稱表示目標數(shù)-衛(wèi)星數(shù)；OBS為經(jīng)軌道預(yù)報后，算例中任務(wù)的總時間窗口數(shù)量；RESULT為計算結(jié)果；CPU為計算時間，GAP為運行結(jié)果與TS算法相比提高的效率。

從各測試算例的計算結(jié)果來看，本文將 Petri網(wǎng)和 ACO-LS相結(jié)合的方法均對基于約束滿足模型的TS算法的結(jié)果有所改善。當問題規(guī)模增大時，本文方法對求解結(jié)果改善更可觀。但第3個算例的求解結(jié)果沒有改善，究其原因是衛(wèi)星資源豐富，可見時間窗口很多，任務(wù)完成率高，采用本文方法的優(yōu)勢不明顯。通過算例比較，表明基于Petri網(wǎng)和ACO- LS的多星成像調(diào)度方法可行，且求解結(jié)果較優(yōu)。

表2 2種算法的求解結(jié)果比較

5.2 變遷指標對結(jié)果的影響

多星成像調(diào)度的 IIPN模型中的變遷包含任務(wù)收益值p和側(cè)擺角slewAngle 2個指標，在ACO-LS算法中2個指標通過啟發(fā)式信息ηjs發(fā)揮作用。

為測試2個指標對算法性能的影響，針對實例5和實例9，分別在取一個指標和取2個指標的情況下計算，各次迭代得到的最佳結(jié)果的進化情況如圖 4所示。

可以看出，啟發(fā)式信息若只考慮側(cè)擺角，則收斂速度很慢，且解的質(zhì)量很差，那是因為算法著重處理了多星并發(fā)觀測的情況卻忽略了對競爭情況的處理。

若只考慮任務(wù)收益值，雖然解得質(zhì)量比只考慮側(cè)擺角時要好，但是收斂速度仍然很慢，其原因同樣是缺乏系統(tǒng)的考慮，偏重處理競爭情況。

若同時考慮這2個指標，算法的性能則有很大的改善，同時可以看出，2個實例分別在第 50次和第80次迭代時就已經(jīng)取得最優(yōu)解了。

圖4 2個實例的最佳結(jié)果進化情況

6 結(jié)束語

多星成像調(diào)度問題是一個典型的NP-Hard問題，國內(nèi)外學(xué)者從不同角度對其進行了建模和求解。本文針對多星成像調(diào)度問題的特點，提出基于綜合指標Petri網(wǎng)和混合蟻群算法的多星成像調(diào)度策略，并給出一種ACO-LS算法。仿真結(jié)果表明，將本文策略運用于求解多星成像調(diào)度問題是有效的，優(yōu)于文獻[11]所采用方法的求解結(jié)果。在衛(wèi)星和任務(wù)數(shù)量相對較多時，當前基于 Petri網(wǎng)的方法對多星成像調(diào)度問題的描述相對復(fù)雜。后續(xù)研究中需要對該策略進行改進或?qū)で笮碌拿枋龇椒?，以對問題進行更簡潔、直觀的描述。

[1]Bensana E, Verfaillie G, Bataellie N, et al.Exact and Approximate Methods for the Daily Management of an Earth Observing Satelete[C]//Proc.of SpaceOPS’96.Munich, Germany: [s.n.], 1996.

[2]賀仁杰, 李菊芳, 姚 鋒, 等.成像衛(wèi)星任務(wù)規(guī)劃技術(shù)[M].北京: 科學(xué)出版社, 2011.

[3]袁崇義.Petri網(wǎng)原理與應(yīng)用[M].北京: 電子工業(yè)出版社,2005.

[4]Lee D Y.Scheduling FMS Using Petri Nets and Heuristic Search[J].IEEE Trans.on Robotics and Automation, 1994,10(2): 123-132.

[5]郝 東, 蔣昌俊, 林 琳.基于 Petri網(wǎng)與 GA 算法的FMS調(diào)度優(yōu)化[J].計算機學(xué)報, 2005, 28(2): 201-208.

[6]肖良清, 樂曉波.時間Petri網(wǎng)與遺傳蟻群算法相結(jié)合的并行測試研究[J].系統(tǒng)仿真學(xué)報, 2009, 21(23): 7648-7654.

[7]潘全科, 朱劍英.基于Petri網(wǎng)和混合算法的作業(yè)車間優(yōu)化[J].計算機集成制造系統(tǒng), 2007, 12(3): 580-584.

[8]Blum C.Beam-ACO Hybridizing Ant Colony Optimization with Beam Search: An Application to Open Shop Scheduling[J].Computers and Operations Research, 2005,32(6): 1565-1591.

[9]Dorigo M, Stuzle T.Ant Colony Optimization[M].[S.l.]:MIT Press, 2004.

[10]Bullnheimer B, Hard R R, Strauss C.A New Rand-based Version of the Ant System: A Computational Study[J].Central European Journal for Operations Research and Economics, 1999, 7(1): 25-38.

[11]賀仁杰.成像偵察衛(wèi)星調(diào)度問題研究[D].長沙: 國防科學(xué)技術(shù)大學(xué), 2004.