基于Petri網和混合蟻群算法的多星成像調度

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

(國防科學技術大學信息系統與管理學院，長沙 410073)

1 概述

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

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

2 相關符號說明

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

相關符號說明如下：

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

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

(3)衛星sk最大側擺Rk次，實際側擺次數為rk，其側擺速率為λ，側擺后穩定時間為d。

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

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

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

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

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

3 多星成像調度

Petri網在描述和分析離散事件動態系統中具有重要作用，因此，在多星成像調度問題建模中得到采用。

3.1 一類綜合指標Petri網

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

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

(1)P為庫所集合，T為變遷集合，F為流關系集合，且：

為與變遷相關的指標集合。

3.2 綜合調度規則

以 IIPN為基礎，根據以下規則可以構建多星成像調度問題的IIPN模型。

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

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

規則3 設置一個變遷預處理階段，在此階段中利用遙感器側擺轉換時間約束消除所有無效變遷。

規則4 建立一個變遷序列：

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

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

3.3 變遷指標設計

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

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

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

圖1 2顆衛星5個任務構建的IIPN模型

圖2 衛星與任務可見關系甘特圖

4 混合蟻群優化算法

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

4.1 信息素的定義和初始化

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

4.2 可行解的構造

4.2.1 構造機制

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

4.2.2 狀態轉移規則

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

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

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

4.2.3 啟發式信息

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

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

4.3 信息素的更新

4.3.1 信息素的局部更新

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

其中，ρlocal∈ (0,1)為局部信息素揮發系數。采用局部更新規則可以實現分化機制，避免算法過早陷入局部最優。

4.3.2 信息素的全局更新

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

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

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

4.4 蟻群混合局部搜索

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

4.4.1 局部搜索

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

4.4.2 動態隨機性參數

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

4.4.3 混合蟻群算法的優化流程

蟻群混合局部搜索的優化流程如圖3所示。

圖3 蟻群混合局部搜索的優化流程

4.5 終止條件

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

5 仿真實例與分析

目前，在衛星調度領域，還沒有公認的測試集，常見的做法是采用隨機生成任務方法驗證算法，仿真實例生成規則如下：

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

(2)衛星數量取值為{3,4,5}。

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

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

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

表1 ACO-LS算法的參數設置

5.1 模型與算法有效性測試

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

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

表2 2種算法的求解結果比較

5.2 變遷指標對結果的影響

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

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

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

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

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

圖4 2個實例的最佳結果進化情況

6 結束語

多星成像調度問題是一個典型的NP-Hard問題，國內外學者從不同角度對其進行了建模和求解。本文針對多星成像調度問題的特點，提出基于綜合指標Petri網和混合蟻群算法的多星成像調度策略，并給出一種ACO-LS算法。仿真結果表明，將本文策略運用于求解多星成像調度問題是有效的，優于文獻[11]所采用方法的求解結果。在衛星和任務數量相對較多時，當前基于 Petri網的方法對多星成像調度問題的描述相對復雜。后續研究中需要對該策略進行改進或尋求新的描述方法，以對問題進行更簡潔、直觀的描述。

[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]賀仁杰, 李菊芳, 姚 鋒, 等.成像衛星任務規劃技術[M].北京: 科學出版社, 2011.

[3]袁崇義.Petri網原理與應用[M].北京: 電子工業出版社,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網與 GA 算法的FMS調度優化[J].計算機學報, 2005, 28(2): 201-208.

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

[7]潘全科, 朱劍英.基于Petri網和混合算法的作業車間優化[J].計算機集成制造系統, 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]賀仁杰.成像偵察衛星調度問題研究[D].長沙: 國防科學技術大學, 2004.