黃瀚　張曉倩

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

?

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

黃瀚*張曉倩

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

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

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

成像衛(wèi)星是一類利用攜帶的成像載荷并對(duì)地表成像完成數(shù)據(jù)傳輸?shù)膶?duì)地觀測(cè)衛(wèi)星[1]。衛(wèi)星的任務(wù)規(guī)劃在整個(gè)衛(wèi)星運(yùn)行控制系統(tǒng)中處于中樞位置，對(duì)于成像衛(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èn)題為研究對(duì)象，研究其任務(wù)規(guī)劃的相關(guān)技術(shù)。

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

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

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

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

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

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

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

對(duì)于數(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)星同時(shí)執(zhí)行成像任務(wù)和數(shù)據(jù)傳輸任務(wù)?；胤拍Ｊ较?，只能執(zhí)行數(shù)據(jù)傳輸任務(wù)，將存儲(chǔ)器重的數(shù)據(jù)傳輸給地面站。兩者比較而言，實(shí)傳模式時(shí)效性更好，所以在建模時(shí)可以理解為實(shí)傳模式具有更高的優(yōu)先級(jí)。

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

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

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

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

圖中符號(hào)含義如下所述：

“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ú)向互斥圖模型。將成像任務(wù)階段中的單個(gè)成像任構(gòu)成一個(gè)頂點(diǎn)。這一系列的頂點(diǎn)構(gòu)成的集合就是用戶所要求的成像任務(wù)集合。由于成像任務(wù)的各種約束條件使得某些成像任務(wù)出現(xiàn)沖突的情況，因此加入互斥關(guān)系構(gòu)成如圖1(b)所示的無(wú)向互斥圖模型。

對(duì)于成像任務(wù)階段的無(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)的個(gè)數(shù)，記為d(v)=|NO(v)|，v為互斥圖中的任意頂點(diǎn)。

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

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

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

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

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

(1)

(2)

vertex_qz=∑(vertex_qz～×vertex_hc)

(3)

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

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

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

vertex_qz——為總互斥程度；

vertex_value——為成像任務(wù)的評(píng)價(jià)值；

dl_value——為數(shù)傳任務(wù)的評(píng)價(jià)值；

value——為任務(wù)規(guī)劃的總評(píng)價(jià)值。

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

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

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

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

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

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

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

在應(yīng)用模擬退火算法的時(shí)候，目標(biāo)評(píng)價(jià)函數(shù)值f即為內(nèi)能函數(shù)E，溫度T則是控制整個(gè)算法收斂的參數(shù)t，由初始可行解S0和控制參數(shù)初值t開(kāi)始，進(jìn)行“產(chǎn)生新解-計(jì)算新?tīng)顟B(tài)-更新?tīng)顟B(tài)”的迭代過(guò)程，直到其滿足算法收斂條件。在模擬退火過(guò)程中，由算法收斂準(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í)，更新控制參數(shù)。

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

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

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

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

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

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

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

由圖3可以看出模擬退火算法在運(yùn)行過(guò)程中有一定的概率接受較差的解，這擴(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]；

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

最終的目標(biāo)評(píng)價(jià)值為42.19。

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

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

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

其規(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]，兩個(gè)數(shù)傳頂點(diǎn)的工作模式均為回放模式，任務(wù)方案的目標(biāo)評(píng)價(jià)值為42.67。

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

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

成像衛(wèi)星的任務(wù)規(guī)劃在其運(yùn)行中有著舉足輕重的作用，研究其任務(wù)規(guī)劃技術(shù)對(duì)成像衛(wèi)星的發(fā)展有著重要意義。通過(guò)成像衛(wèi)星的任務(wù)規(guī)劃圖論模型可以簡(jiǎn)潔明了的驗(yàn)證各類優(yōu)化算法的應(yīng)用效果。仿真結(jié)果表明對(duì)模擬退火算法適當(dāng)改進(jìn)之后可以明顯改善其算法的收斂性和尋最優(yōu)解的能力。改進(jìn)的模擬退火算法在成像衛(wèi)星任務(wù)規(guī)劃中取得不錯(cuò)的效果，對(duì)于實(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ā)展，北京: 中國(guó)科學(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)化問(wèn)題中應(yīng)用[J]. 北京航空航天大學(xué)學(xué)報(bào), 2001, 27(5): 556-559.

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

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

TP273

A

2095-4859(2016)02-0155-04