黃瀚　張曉倩

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

?

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

黃瀚*張曉倩

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

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

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

成像衛(wèi)星是一類利用攜帶的成像載荷并對地表成像完成數據傳輸的對地觀測衛(wèi)星[1]。衛(wèi)星的任務規(guī)劃在整個衛(wèi)星運行控制系統中處于中樞位置，對于成像衛(wèi)星的功能實現起著決定性的作用。

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

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

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

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

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

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

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

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

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

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

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

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

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

圖中符號含義如下所述：

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

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

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

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

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

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

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

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

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

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

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

定義4邊的權值we(e)。邊的權值表示連接的兩個頂點的互斥關系。

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

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

根據成像衛(wèi)星的任務特點及約束，確定任務規(guī)劃的目標評價函數為

(1)

(2)

vertex_qz=∑(vertex_qz～×vertex_hc)

(3)

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

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

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

vertex_qz——為總互斥程度；

vertex_value——為成像任務的評價值；

dl_value——為數傳任務的評價值；

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

2　改進的模擬退火算法及其仿真

2.1模擬退火算法及其改進算法簡述

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

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

圖2　改進的模擬退火算法程序流程圖

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

2.2基于MATLAB的仿真與結果分析

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

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

算法收斂準則采用設置溫度控制參數的閾值，當溫度控制參數到達該閾值，停止搜索。這種收斂準則普遍適合于各種應用背景，溫度控制參數閾值為t=1e-5。

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

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

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

(2)插入操作是在成像任務序列中插入與任務序列中現有頂點都不互斥(即邊的權值為0)的某個頂點。

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

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

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

圖3　基于經典模擬退火算法的評價值變化圖

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

成像段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]；

兩個數傳頂點的工作模式均為回放模式；

最終的目標評價值為42.19。

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

采用改進的模擬退火算法解算該圖論模型，其程序運行時間為2.015 32 s，其目標評價值如圖4所示。

圖4　基于改進的模擬退火算法的評價值變化圖

其規(guī)劃結果：成像段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]，兩個數傳頂點的工作模式均為回放模式，任務方案的目標評價值為42.67。

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

3　結束語

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

[1]葛榜軍, 廖春發(fā). 總裝備部衛(wèi)星有效載荷及應用技術專業(yè)組應用技術分組[M]. 衛(wèi)星應用現狀與發(fā)展，北京: 中國科學技術出版社, 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)化問題中應用[J]. 北京航空航天大學學報, 2001, 27(5): 556-559.

(責任編輯陳葵晞)

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

TP273

A

2095-4859(2016)02-0155-04