基于圖論模型的成像衛(wèi)星任務(wù)規(guī)劃方法研究

黃瀚　張曉倩

(成都理工大學(xué)工程技術(shù)學(xué)院　自動化工程系，四川　樂山　614000)

?

基于圖論模型的成像衛(wèi)星任務(wù)規(guī)劃方法研究

黃瀚*張曉倩

(成都理工大學(xué)工程技術(shù)學(xué)院自動化工程系，四川樂山614000)

成像衛(wèi)星是目前在各領(lǐng)域應(yīng)用極廣泛的一類對地觀測衛(wèi)星，任務(wù)規(guī)劃在其運(yùn)控系統(tǒng)中也起著主導(dǎo)作用。針對成像衛(wèi)星的任務(wù)規(guī)劃研究主要建立了其成像任務(wù)及數(shù)傳任務(wù)的圖論模型。在此基礎(chǔ)上研究了模擬退火算法對圖論模型的求解效果。針對經(jīng)典模擬退火算法的不足，加入了精英解保持策略和二次搜索過程。最后對比了改進(jìn)的模擬退火算法與經(jīng)典模擬退火算法應(yīng)用于圖論模型求解的效果。

成像衛(wèi)星；任務(wù)規(guī)劃；模擬退火算法

成像衛(wèi)星是一類利用攜帶的成像載荷并對地表成像完成數(shù)據(jù)傳輸?shù)膶Φ赜^測衛(wèi)星[1]。衛(wèi)星的任務(wù)規(guī)劃在整個衛(wèi)星運(yùn)行控制系統(tǒng)中處于中樞位置，對于成像衛(wèi)星的功能實(shí)現(xiàn)起著決定性的作用。

成像衛(wèi)星完成數(shù)據(jù)傳輸任務(wù)的途徑主要有三條，分別是衛(wèi)星與地面站完成數(shù)據(jù)傳輸、衛(wèi)星與中繼星完成數(shù)據(jù)傳輸和LEO星間數(shù)據(jù)傳輸。本文以成像衛(wèi)星的成像任務(wù)及數(shù)據(jù)傳輸任務(wù)問題為研究對象，研究其任務(wù)規(guī)劃的相關(guān)技術(shù)。

國內(nèi)外對成像衛(wèi)星任務(wù)規(guī)劃相關(guān)問題的研究主要集中于任務(wù)規(guī)劃預(yù)處理技術(shù)、任務(wù)規(guī)劃建模和任務(wù)規(guī)劃算法。

成像衛(wèi)星任務(wù)規(guī)劃預(yù)處理技術(shù)主要是根據(jù)用戶的需求和衛(wèi)星所攜帶資源的約束將原始任務(wù)分解為單次任務(wù)集合。對于任務(wù)分解技術(shù)集中與區(qū)域目標(biāo)成像任務(wù)的分解技術(shù)。Walton J[2]、Rivett C[3]等將區(qū)域分解轉(zhuǎn)化為集合覆蓋問題。Lemaitre M[4]將區(qū)域目標(biāo)按照成像模式分解為條帶集合但是沒有考慮到成像載荷的成像覆蓋范圍的重合性問題。

對于任務(wù)規(guī)劃模型主要集中于圖論模型、線性規(guī)劃模型、約束模型等方面。Gabrel V[5]等將成像衛(wèi)星任務(wù)規(guī)劃描述為一個時間序有向無圈圖模型，將任務(wù)規(guī)劃轉(zhuǎn)化為一個路徑尋優(yōu)問題。Vasquez M、Hao J K[6]等提出了以多維背包問題表示成像衛(wèi)星任務(wù)規(guī)劃，背包模型形式簡單，可以表示簡單的約束但是沒法表達(dá)復(fù)雜的約束，難以應(yīng)用于多星任務(wù)規(guī)劃中。

針對不同的任務(wù)規(guī)劃模型其求解算法也各不相同，主要有樹搜索、動態(tài)規(guī)劃法及各類優(yōu)化算法。在各類算法中智能優(yōu)化算法應(yīng)用的較為廣泛且規(guī)劃效果也較好。

1　成像衛(wèi)星任務(wù)規(guī)劃問題描述及建模

1.1成像衛(wèi)星任務(wù)規(guī)劃的問題描述

在成像衛(wèi)星的運(yùn)行過程中，由于衛(wèi)星的存儲器的容量有限，在占用比例較高時需要執(zhí)行數(shù)傳任務(wù)釋放空間。所以，以數(shù)傳任務(wù)執(zhí)行的起止時刻作為分段依據(jù)，把成像衛(wèi)星的執(zhí)行任務(wù)過程劃分為數(shù)傳段和成像段。

對于數(shù)據(jù)傳輸任務(wù)階段，根據(jù)數(shù)傳資源，其數(shù)傳任務(wù)執(zhí)行有兩種情況。第一種情況是成像衛(wèi)星與通信衛(wèi)星間進(jìn)行數(shù)據(jù)傳輸。第二種情況是成像衛(wèi)星與地面站進(jìn)行數(shù)據(jù)傳輸。需要注意的是成像衛(wèi)星與地面站的數(shù)傳方式可以是實(shí)傳或回放。實(shí)傳模式下成像衛(wèi)星同時執(zhí)行成像任務(wù)和數(shù)據(jù)傳輸任務(wù)?；胤拍Ｊ较?，只能執(zhí)行數(shù)據(jù)傳輸任務(wù)，將存儲器重的數(shù)據(jù)傳輸給地面站。兩者比較而言，實(shí)傳模式時效性更好，所以在建模時可以理解為實(shí)傳模式具有更高的優(yōu)先級。

對于成像任務(wù)階段，成像任務(wù)必須滿足成像時間窗口、成像條件等約束才能成功執(zhí)行。在建立起圖論模型時就需要給其附加各類約束。

1.2成像衛(wèi)星任務(wù)規(guī)劃的圖論模型

每個成像段對應(yīng)生成一個成像段頂點(diǎn)，每個數(shù)傳段根據(jù)數(shù)傳方式不同對應(yīng)生成三個頂點(diǎn)，這三個頂點(diǎn)在選擇路徑時只能選擇一個頂點(diǎn)通過。依照上述方式建立各頂點(diǎn)并按衛(wèi)星執(zhí)行任務(wù)的時間順序建立任務(wù)規(guī)劃的有向圖模型，如圖1(a)所示。

圖1　任務(wù)規(guī)劃圖論模型

圖中符號含義如下所述：

“O”——表示為成像任務(wù)執(zhí)行階段；

“S”——表示為執(zhí)行回放模式下的數(shù)傳任務(wù)；

“R”——表示為執(zhí)行實(shí)傳模式下的數(shù)傳任務(wù)；

“Q”——表示為僅執(zhí)行成像任務(wù)；

“s”、“e”——分別表示起始和結(jié)束。

有向圖中頂點(diǎn)“O”為成像任務(wù)階段，根據(jù)成像任務(wù)的約束條件等信息，構(gòu)成成像任務(wù)階段的無向互斥圖模型。將成像任務(wù)階段中的單個成像任構(gòu)成一個頂點(diǎn)。這一系列的頂點(diǎn)構(gòu)成的集合就是用戶所要求的成像任務(wù)集合。由于成像任務(wù)的各種約束條件使得某些成像任務(wù)出現(xiàn)沖突的情況，因此加入互斥關(guān)系構(gòu)成如圖1(b)所示的無向互斥圖模型。

對于成像任務(wù)階段的無向互斥圖模型，其含義如下所述。

定義1頂點(diǎn)的互斥集合NO(v)。頂點(diǎn)v的互斥集合為

NO(v)={u|(u,v)∈E(O),u∈V(O),v∈V(O)}，v為互斥圖中的任意頂點(diǎn)。

定義2頂點(diǎn)的度d(v)。頂點(diǎn)v的度為所有與頂點(diǎn)v具有互斥關(guān)系的其他頂點(diǎn)的個數(shù)，記為d(v)=|NO(v)|，v為互斥圖中的任意頂點(diǎn)。

定義3頂點(diǎn)的權(quán)值w(v)。對于互斥圖中的任意頂點(diǎn)v，頂點(diǎn)的權(quán)值是頂點(diǎn)所代表的成像任務(wù)的優(yōu)先級。

定義4邊的權(quán)值we(e)。邊的權(quán)值表示連接的兩個頂點(diǎn)的互斥關(guān)系。

無向圖模型描述了成像任務(wù)目標(biāo)之間的時間窗口約束關(guān)系，該模型簡潔形象且易于理解。將無向圖模型加入有向圖模型中構(gòu)成了成像衛(wèi)星任務(wù)規(guī)劃的圖論模型。

1.3成像衛(wèi)星任務(wù)規(guī)劃的目標(biāo)評價函數(shù)

根據(jù)成像衛(wèi)星的任務(wù)特點(diǎn)及約束，確定任務(wù)規(guī)劃的目標(biāo)評價函數(shù)為

(1)

(2)

vertex_qz=∑(vertex_qz～×vertex_hc)

(3)

式中vertex_qz——為成像任務(wù)的優(yōu)先級；

vertex_qz～——為與該成像任務(wù)沖突的成像任務(wù)的優(yōu)先級；

vertex_hc——為兩個成像任務(wù)之間互斥程度；

vertex_qz——為總互斥程度；

vertex_value——為成像任務(wù)的評價值；

dl_value——為數(shù)傳任務(wù)的評價值；

value——為任務(wù)規(guī)劃的總評價值。

2　改進(jìn)的模擬退火算法及其仿真

2.1模擬退火算法及其改進(jìn)算法簡述

物質(zhì)經(jīng)由熔化狀態(tài)逐漸冷卻達(dá)到結(jié)晶狀態(tài)的物理過程中，物質(zhì)的內(nèi)能隨之衰減直至最低[7]。而優(yōu)化問題求解的過程與物質(zhì)的退火過程相似，所以在最優(yōu)問題的求解過程中加入內(nèi)能函數(shù)，利用Metropolis準(zhǔn)則，確保在溫度趨于收斂時，有更大的概率接受最優(yōu)解。模擬退火算法已經(jīng)由數(shù)學(xué)方式證明其有一定概率搜索到最優(yōu)解。

對于經(jīng)典模擬退火算法，若溫度更新函數(shù)的參數(shù)選擇偏小會導(dǎo)致降溫過程過快，最終搜索不到全局最優(yōu)解；若該參數(shù)選擇偏大，則需花費(fèi)大量時間去搜索全局最優(yōu)解，使得算法的收斂性變差。所以對其作了適當(dāng)?shù)母倪M(jìn)，改進(jìn)的模擬算法如圖2所示。

圖2　改進(jìn)的模擬退火算法程序流程圖

改進(jìn)的模擬退火算法相比于經(jīng)典的模擬退火算法，增加了精英解保持策略和二次搜索過程。在模擬退火算法的退火過程中保持精英解可以避免因溫度更新參數(shù)選擇過大導(dǎo)致收斂性變差的后果。在結(jié)束模擬退火算法后再次執(zhí)行二次搜索可以避免因溫度更新參數(shù)選擇過小導(dǎo)致降溫過程過快的后果。

2.2基于MATLAB的仿真與結(jié)果分析

在應(yīng)用模擬退火算法的時候，目標(biāo)評價函數(shù)值f即為內(nèi)能函數(shù)E，溫度T則是控制整個算法收斂的參數(shù)t，由初始可行解S0和控制參數(shù)初值t開始，進(jìn)行“產(chǎn)生新解-計算新狀態(tài)-更新狀態(tài)”的迭代過程，直到其滿足算法收斂條件。在模擬退火過程中，由算法收斂準(zhǔn)則決定是否得到最終解，由抽樣穩(wěn)定準(zhǔn)則決定是否更新控制參數(shù)，由Metropolis準(zhǔn)則決定更新的狀態(tài)。

仿真中初始溫度為t0=100 ℃，溫度更新函數(shù)為tk+1=0.93tk。

算法收斂準(zhǔn)則采用設(shè)置溫度控制參數(shù)的閾值，當(dāng)溫度控制參數(shù)到達(dá)該閾值，停止搜索。這種收斂準(zhǔn)則普遍適合于各種應(yīng)用背景，溫度控制參數(shù)閾值為t=1e-5。

抽樣穩(wěn)定準(zhǔn)則采用設(shè)置內(nèi)循環(huán)迭代次數(shù)的方式，當(dāng)滿足條件時，更新控制參數(shù)。

仿真中對于新狀態(tài)的更新方式與任務(wù)類型息息相關(guān)。針對成像任務(wù)有以下兩種更新方式：

(1)互換操作是指隨機(jī)將成像任務(wù)序列中的一個頂點(diǎn)換成該頂點(diǎn)的互斥集合中某一個頂點(diǎn)；

(2)插入操作是在成像任務(wù)序列中插入與任務(wù)序列中現(xiàn)有頂點(diǎn)都不互斥(即邊的權(quán)值為0)的某個頂點(diǎn)。

對于數(shù)據(jù)傳輸任務(wù)，則通過改變數(shù)傳任務(wù)的通信模式來更新其狀態(tài)。

由于成像衛(wèi)星任務(wù)規(guī)劃為組合優(yōu)化問題，狀態(tài)編碼可以是0-1編碼方式和整數(shù)編碼方式。分析了在算法處理中兩種編碼方式帶來的差異，發(fā)現(xiàn)0-1二進(jìn)制編碼方式處理起來更為簡單。將狀態(tài)編碼為0-1二進(jìn)制碼，采用取反操作代替插入操作和替換操作進(jìn)行狀態(tài)的更新。

在仿真中假定任務(wù)規(guī)劃的圖論模型有兩個成像段和兩個數(shù)傳段，兩個成像任務(wù)段分別有16和9個成像任務(wù)。采用經(jīng)典模擬退火算法解算該模型，其程序運(yùn)行時間為2.194 250 s，其目標(biāo)評價值變化如圖3所示。

圖3　基于經(jīng)典模擬退火算法的評價值變化圖

由圖3可以看出模擬退火算法在運(yùn)行過程中有一定的概率接受較差的解，這擴(kuò)大了搜索可行解的范圍。最終規(guī)劃結(jié)果為：

成像段A的方案為[1,0,1,1,1,1,1,0,1,1,0,0,0,1,1,1]；

成像段B的方案為[0,1,1,1,1,0,0,0,1]；

兩個數(shù)傳頂點(diǎn)的工作模式均為回放模式；

最終的目標(biāo)評價值為42.19。

規(guī)劃結(jié)果中“1”表示該成像任務(wù)被選定在任務(wù)規(guī)劃的最終方案中，“0”則表示不選擇該任務(wù)。從圖3中解的更新可知，應(yīng)用經(jīng)典模擬退火算法時，不會只限于更好的解的周圍去搜索，而是以一定的概率接受次優(yōu)解。但是由于經(jīng)典模擬退火算法的自身缺陷，丟失了搜索過程中得到的一個最優(yōu)解。

采用改進(jìn)的模擬退火算法解算該圖論模型，其程序運(yùn)行時間為2.015 32 s，其目標(biāo)評價值如圖4所示。

圖4　基于改進(jìn)的模擬退火算法的評價值變化圖

其規(guī)劃結(jié)果：成像段A為[1,0,1,1,1,1,1,0,1,1,0,0,0,1,1,1]，成像段B為[0,1,1,1,0,1,0,0,1]，兩個數(shù)傳頂點(diǎn)的工作模式均為回放模式，任務(wù)方案的目標(biāo)評價值為42.67。

對比經(jīng)典模擬退火算法和改進(jìn)的模擬退火算法的規(guī)劃結(jié)果后，可以看出當(dāng)增加了精英解保持環(huán)節(jié)后，能夠保證不丟失搜索過程中的最優(yōu)解。改進(jìn)了任務(wù)序列編碼方式之后，也使得程序的執(zhí)行時間大大減少，能夠很快的搜索到全局最優(yōu)解。而經(jīng)典模擬退火算法由于Metropolis準(zhǔn)則接受新解的隨機(jī)性，難以快速收斂到最優(yōu)解。

3　結(jié)束語

成像衛(wèi)星的任務(wù)規(guī)劃在其運(yùn)行中有著舉足輕重的作用，研究其任務(wù)規(guī)劃技術(shù)對成像衛(wèi)星的發(fā)展有著重要意義。通過成像衛(wèi)星的任務(wù)規(guī)劃圖論模型可以簡潔明了的驗(yàn)證各類優(yōu)化算法的應(yīng)用效果。仿真結(jié)果表明對模擬退火算法適當(dāng)改進(jìn)之后可以明顯改善其算法的收斂性和尋最優(yōu)解的能力。改進(jìn)的模擬退火算法在成像衛(wèi)星任務(wù)規(guī)劃中取得不錯的效果，對于實(shí)際的成像衛(wèi)星任務(wù)規(guī)劃也具有指導(dǎo)意義。

[1]葛榜軍, 廖春發(fā). 總裝備部衛(wèi)星有效載荷及應(yīng)用技術(shù)專業(yè)組應(yīng)用技術(shù)分組[M]. 衛(wèi)星應(yīng)用現(xiàn)狀與發(fā)展，北京: 中國科學(xué)技術(shù)出版社, 2001: 124-130.

[2]Walton J T. Models for the management of satellite-based sensors[D]. Massachusetts Institute of Technology, 1993.

[3]Rivett C, Pontecorvo C. Improving satellite surveillance through optimal assignment of assets[R]. Defence Science and Technology Organisation Edinburgh (Australia) Intelligence Surveillance Reconn Div, 2003.

[4]Lemaitre M, Verfaillie G. Earth Observation Satellite Management[J]. Constraints, 1999,4(3):293-299.

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

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

[7]江加和, 宋子善. 模擬退火算法在連續(xù)變量全局優(yōu)化問題中應(yīng)用[J]. 北京航空航天大學(xué)學(xué)報, 2001, 27(5): 556-559.

(責(zé)任編輯陳葵晞)

黃瀚，男，江西吉安人。助教，碩士。研究方向：控制理論與控制工程。

TP273

A

2095-4859(2016)02-0155-04