一種多目標變鄰域模擬退火算法及成像星座任務規劃方法

丁祎男，劉羽白，王淑一，雷擁軍

(1. 北京控制工程研究所，北京 100094； 2. 空間智能控制技術重點實驗室，北京 100094)

0 引 言

隨著對地觀測任務逐漸復雜，任務需求量不斷增加，各國競相發展敏捷成像衛星組成的星座，如美國的WorldView系列衛星，法國的Pleiades星座以及我國發射的“高景”系列衛星等[1]。

敏捷成像衛星可以沿三軸機動，有很強的對地觀測能力，成像星座可以進一步滿足大規模的觀測任務需求。相比于傳統成像衛星，敏捷衛星星座成像任務規劃問題的解空間更大[2]，因此選取能快速全面遍歷問題所有解的優化變量尤為重要。敏捷衛星拓寬了觀測時間窗口，但往往時間窗口邊緣的成像質量變差，難以滿足用戶需求，因此提高任務完成度的同時要兼顧成像質量，這是一個工程實踐中亟待解決的多約束多目標的優化問題，對模型構建和求解算法提出了更高的要求。

近年來國內外學者在衛星任務規劃方面進行了大量的研究。Chen等[3]和Xiao等[4]將任務規劃問題描述為混合整數線性規劃模型(MILP)，采用線性規劃求解器求解，可以得到穩定有效的優化結果。但MILP模型必須將約束和優化目標線性化，且優化中無法實時更新衛星和觀測目標以及地面站的相對位置信息，也無法記錄衛星的位置、速度、姿態信息，導致衛星在目標、地面站間的機動時間是預估的且不準確的，若任務密集則優化結果與實際情況差別較大。She等[5]針對此問題，在優化過程中周期性地更新約束條件，并用遺傳算法驗證求解結果，證明這是一種切實可行的方法。MILP的求解速度依賴于求解器的性能，面對大規模的觀測任務規劃問題，將會付出難以接受的時間代價。當前更多的研究將任務規劃問題描述為一般的約束滿足模型，采用元啟發式搜索算法求解，如遺傳算法[1-2,6-10]，模擬退火算法[11]、差分進化算法[12]，鄰域搜索算法[13-14]等。這些優化算法的思想已經非常成熟，因此如何針對存在的工程實踐問題設計約束條件和優化目標，以及如何構造模型和優化算法的聯系以提高求解效率，是近年來研究的核心。

優化對象是問題模型和求解算法間的橋梁，找到模型中能快速、全面遍歷問題所有解的變量是提高優化效果的關鍵。文獻[6,11]采用二進制編碼，以任務是否被選擇觀測為優化對象，該編碼方式搜索效率高，但不能主動調整任務的執行順序，搜索范圍有限。文獻[7-10,12-14]采用的是整數或實數編碼，可以優化任務觀測順序，但成像時刻需要先初始化為在時間窗口開始或中間的位置，然后在觀測順序確定的前提下根據星上資源或機動時間的約束進行調整。文獻[1]采用實數編碼，以相對成像時刻作為優化對象，文獻[2]采用二進制、整數、實數三種編碼，同時以任務選擇、任務順序和成像時刻為優化對象，可以充分遍歷解空間，發揮敏捷衛星的優勢。

單以最大化任務完成度為優化目標的任務規劃方法已經難以滿足日益復雜的觀測任務需求，但多目標優化問題比單目標優化問題的求解更為復雜。文獻[1,7,12-13]考慮了最大化完成任務總權重外的其它目標，如提高成像質量、最小化能源消耗等，但都是將多目標優化問題轉化為單目標優化問題，如將多個目標函數以加權的方式整合為單目標函數，或者將某幾個目標以約束的方式給出。單目標優化問題求解的計算量較小，可以在較短時間內得到較好的優化結果，但這樣得到的最優解是一個依賴加權系數或約束條件的平衡多個目標函數的解。這樣一來難以權衡新增的參數，二來若用戶需求發生變化，就需要調整參數重新規劃，耗費時間。文獻[9,14]采用的是Pareto多目標優化模型，分別采用多目標遺傳算法和局部搜索算法求解，得到的結果是問題的最優解集，使得優化過程中每一個目標函數的最優值都得以保留。

在工程實踐中，成像質量逐漸成為用戶最重要的需求，而成像質量與衛星的成像時刻直接相關。文獻[13]考慮了成像質量，但將其作為約束條件給出，調整成像時刻的范圍不夠靈活，若用戶需求改變，就要修改約束重新規劃。文獻[12]提出了一種成像質量評價指標，并將提高成像質量與其它優化目標加權為單目標函數，取得了很好的優化效果，但其優化效果依賴于加權算法，且采用的是整數編碼，不能主動調整成像時刻。

多目標模擬退火算法可以有效地求解基于Pareto模型的多目標優化問題，其鄰域搜索的特性也可以很好地用于對成像時刻的優化。

綜合以上分析，本文首先考慮衛星的觀測時間窗口、姿態機動時間、星上資源等約束，以最大化完成任務總權重和滿足用戶成像質量要求為目標，建立多星多觀測目標的敏捷成像衛星任務規劃模型。進一步以成像時刻為優化對象，提出一種利用降溫過程調節搜索范圍的多目標變鄰域模擬退火算法，實現對任務成像時刻的滑動優化，得到問題的最優解集，兼顧最大化完成任務總權重和滿足用戶成像質量要求。最后通過工程實例仿真，比較了多種優化算法的仿真結果，驗證了模型構建的有效性和本文算法的優勢。

1 敏捷成像星座任務規劃模型

1.1 參數和變量定義

1)模型參數

P觀測目標集合，P={p1,p2,…,pNP}，其中NP為觀測目標數量。

S成像衛星集合，S={s1,s2,…,sNS}，其中NS為成像衛星數量。

M時間窗口(任務)集合，M={m1,m2,…,mN}，其中N為時間窗口數量。

ok目標pk的觀測時長。

ωk目標pk的權重。

ai任務mi的最早成像時刻。

bi任務mi的最晚成像時刻。

ui任務mi的權重。

2)模型變量

yi衛星執行任務mi時的成像時刻。

zi任務mi的執行情況，0表示不執行任務mi，1表示執行任務mi。

qjk衛星與目標的觀測關系，0表示目標pk未由衛星sj觀測，1表示目標pk由衛星sj觀測。

3)任務的表示

任務mi可以表示為：

(1)

1.2 多目標約束滿足模型

本文構建多目標約束滿足模型來描述敏捷成像衛星任務規劃問題，模型主要由約束條件、決策變量以及目標函數構成。

1)約束條件

本文主要考慮了時間窗口、姿態機動時間、星上資源、任務需求等4個方面的約束條件。

(1)衛星對目標的可見性約束

若任務mi確定被執行，則必須滿足

ai≤yi≤bi

(2)

(2)衛星姿態機動能力約束

衛星執行相鄰任務時受機動能力的約束，若衛星sj需要先后執行任務mi′和mi，設衛星在時刻ei′執行完任務mi′，接下來要在yi時刻執行任務mi，衛星所需的機動時間為di′i，需要滿足

yi-ei′≥di′i

(3)

(3)衛星星上資源約束

本文將星上能源、固存等約束都歸為星上資源約束。執行任務mi消耗的資源分為兩部分，一部分與衛星機動角度θi成正比，另一部分與成像時長ok成正比，比例系數分別為η1和η2，設衛星sj在執行任務mi之前的可用資源為Ej，若要執行任務mi需要滿足

Ej≥η1θi+η2ok

(4)

(4)觀測任務的唯一性約束

每個目標最多被觀測一次，且最多只被一顆衛星觀測，對于目標pk有

(5)

此約束條件可以協調衛星之間的觀測行為，與約束(3)結合可以防止出現某些衛星承擔了過多的觀測任務而其它衛星閑置的情況，發揮成像星座的觀測優勢。

在實際的觀測任務中，還存在衛星數傳窗口、數傳時機、太陽能帆板供電等因素，但這些約束在形式上都可以歸到以上四種約束中，本文不再贅述。

2)決策變量

本文選取任務mi中的成像時刻yi作為決策變量，其可以唯一確定衛星執行該任務時的觀測起止時間和機動軌跡，通過設定任務間的沖突處理原則，進一步可以確定整個任務序列中哪些任務可以執行和執行順序，間接確定變量zi和qjk的值，得到可執行任務序列。因此yi可以以一個變量遍歷問題的整個解空間，在搜索范圍和效率方面都有一定的優勢。

3)目標函數

在以往研究中，多以最大化完成任務總權重作為優化的目標，但成像質量也是成像任務執行好壞的重要評價指標，本文將提高成像質量也作為優化目標。

(1)最大化完成任務總權重

(6)

ui一般情況下與任務包含的目標pk的權重ωk相同，即ui=ωk，但若完成的任務為紅外相機在陽照區成像，令ui=μωk，其中μ∈(0,1)為懲罰系數，引導優化算法優先考慮在陽照區采用可見光成像。

(2)成像質量最優化

在同一個時間窗口中，成像時刻越靠近中心，由目標到衛星的仰角越大，成像質量越高[15]，因此在優化過程中應盡可能將觀測窗口移向時間窗口中心，尤其是權重高的目標，構造目標函數

(7)

為方便優化算法的求解，將目標函數式(7)轉化為最大化問題

(8)

式中：α為一個正數。

這兩個目標函數是有沖突的，由于時間窗口有重疊，目標函數式(8)會使任務開始執行時間盡可能安排在時間窗口中心，這樣會使部分任務因時間沖突無法被觀測。傳統的單目標優化算法將兩個目標函數加權為一個目標函數，通過調整加權系數來引導優化過程側重優化其中一個目標，加權系數會對優化效果產生較大的影響，選擇不當會丟失一些較優解。本文采用基于Pareto模型的多目標優化算法，引入非受支配解和非受支配解集的概念[16]：

設多目標優化問題包含L個目標函數、H個決策變量，其優化目標為

maxg(x)=[g1(x),g2(x),…,gL(x)]

(9)

式中：x為H維決策向量，稱為問題的解；g(x)定義了L個由解空間向目標空間的映射函數。若有

(10)

則稱解x1支配解x2或解x2受解x1支配，記作x1?x2。若一個解不受問題的解集中任一解支配，稱此解關于該解集為非受支配解。

多目標優化問題的本質在于各目標往往是相互沖突的，同時使多個目標均達到最優是不可能的[16]。多目標優化算法的目標就是在迭代過程中尋找盡可能多的非受支配解，最終得到問題的非受支配解集，這樣可以保留所有對各目標函數不同程度側重的解，不會丟失任一目標函數的最優值。優化結束后按用戶需求從非受支配解集中選取合適的解作為最終優化結果。

2 多目標變鄰域模擬退火算法

成像衛星任務規劃問題已經被證明是一個非確定多項式難問題，不存在有效算法求得最優解，現有的研究都傾向于采用智能優化算法求得近似最優解，如遺傳算法、蟻群算法、模擬退火算法等。其中模擬退火算法可以實現鄰域搜索，且優化過程中搜索精度不斷提高，很適合對成像時刻的優化。本文以成像時刻為優化對象，設計了解的編碼解碼和變鄰域搜索策略，提出一種多目標模擬退火算法，實現對任務成像時刻的滑動優化，以達到同時優化完成任務總權重和成像質量的目的。

2.1 成像時刻的編碼解碼

解的編碼是將任務序列表示為可被優化算法操作的對象(解)的過程，解碼則是將解轉化為任務序列的過程。根據1.2節對決策變量的討論，本文設計了一種針對成像時刻的實數編碼和解碼方法。

1)解的編碼

對于任務mi，隨機生成yi：

yi=ai+ε·(bi-ai)

(11)

式中：ε∈[0,1]為隨機數。式(11)可以保證yi∈[ai,bi]。將所有任務的預計成像時刻序列S=[y1,y2,…,yn]T作為優化問題的解，通過調整該時間序列達到優化任務序列的目的。

2)解的解碼

將所有任務按解S表示的預計成像時刻升序排列，按時間優先的原則進行沖突處理，得到可執行任務序列。具體步驟為：

(1)將所有任務按解表示的預計成像時刻升序排列，將zi都置為1，qjk都置為0。

(12)

跳過該任務，令zi=0，重新執行步驟(2)。

(3)設衛星在時刻ei′執行完上一任務mi′，姿態矩陣為Rboi′，預計在時刻yi執行該任務，姿態矩陣為Rboi，計算機動角度

(13)

根據機動角度計算衛星所需的機動時間和執行該任務所需的資源消耗。若滿足約束條件式(3)和約束條件式(4)則表示衛星可以在時刻yi觀測到目標，以yi作為此任務的成像時刻，將qjk置為1，并計算衛星執行完任務mi的時間ei、更新衛星的可用資源Ej：

(14)

(4)重復步驟(2)～(3)，直到遍歷完所有任務。zi為1的任務組成可執行任務序列。

對解S的解碼完成后，根據式(6)和式(8)計算該解的目標函數f1和f2。

2.2 解的變鄰域搜索

為實現成像時刻在時間窗口內的滑動搜索，本文設計了一個位移算子，用于調整成像時刻在時間窗口的位置。

根據模擬退火算法中接受準則的特性，溫度最高時，任意兩個解之間都有相同的轉化概率，此時應使搜索鄰域最大，使預計成像時刻可以通過位移算子到達時間窗口的任意位置，這在優化初期起到了避免陷入局部最優的“爬山”作用。隨著溫度的降低，模擬退火算法對差解的接受概率逐漸降低，最優解的區域也基本固定，過大的搜索鄰域會使算法的優化陷入停滯。本文利用算法中的溫度參數設計了一個變鄰域系數來逐漸縮小搜索鄰域，通過對解的微調，可以顯著提高時間窗口的利用率，加快算法的收斂速度。

(15)

γ=tn/Tn

(16)

式中：Tn和tn分別為目標函數fn對應的初始溫度和當前溫度。在本文算法中，所有目標函數對應的溫度采用同樣的衰減系數，因此γ與n的取值無關。可以看出，γ∈(0,1]，且隨溫度降低不斷減小。下面介紹初始溫度的計算方法：

(17)

根據模擬退火算法解的接受準則[17]，可以認為在溫度Tn下，任意兩個解之間都有相同的轉化概率。

綜上，可以得到解的更新算法：

(18)

實現了成像時刻在時間窗口內的變鄰域搜索。

2.3 非受支配解集的構造

本節給出多目標模擬退火算法中解的選拔淘汰機制以及非受支配解集的構造方法。

1)建立非受支配解集Nd，初始化為空集。

2)按式(17)計算目標函數f1和f2對應的初始溫度T1和T2，通過調整式(8)中的α使得T1和T2在同一個數量級。

(19)

將解Sr移出Nd集，并在遍歷Nd集中所有解后將解Snew加入Nd集；若有Sr?Snew，則不改變Nd集；若Snew和Nd中的所有解都沒有支配關系，直接將Snew加入Nd集。

5)若Snew?Scur，令Scur=Snew，否則按如下概率判斷是否接受新解[18]：

(20)

如果新解被接受，令Scur=Snew，否則保留當前解。

6)每執行完步驟4)～ 5)視為循環一次，若在當前溫度下循環次數已經達到K，更新當前溫度tn=β·tn,n=1,2，其中衰減系數β∈(0,1)。若有max{t1,t2}≤Tmin，停止優化算法，輸出非受支配解集Nd，否則返回步驟4)。

以上步驟如圖1所示。

圖1 非受支配解集更新算法流程圖Fig.1 Flow chart of the non-dominated solution set update algorithm

3 仿真校驗與結果分析

為校驗本文模型的有效性和算法的優勢，開展對工程實例的仿真。仿真平臺為：Windows 10操作系統下的Matlab，計算機配置為Intel(R) Core i7-7700HQ@ CPU 2.8 GHz處理器，16GB內存。

3.1 模型和算法參數設置

成像衛星星座有兩個軌道面，每個軌道面有4顆衛星，采用太陽同步軌道。降交點地方時分別為10∶30和13∶30，以保證在降交點觀測時有較好的光照條件。仿真時間為一天，即86400 s。

種子衛星軌道參數：軌道高度為500 km，偏心率為0，軌道傾角為97.4°，近地點幅角為0°，升交點赤經為160°。為保證充分利用星座的覆蓋能力，每個軌道面內相鄰兩顆衛星相位差為90°，相鄰軌道第一顆衛星相位差為45°，每個軌道面有一顆衛星為紅外成像衛星，其余為可見光成像衛星。衛星最大側擺角為45°，地面覆蓋角為9.4°，星座對赤道上的點的最大重訪周期約為2.95 h。考慮20個目標，總權重為60的工況，目標點隨機分布在114°E～117°E、37°N～42°N之間。用戶對于成像質量要求為觀測時間窗口必須包含于可見時間窗口的1/4-3/4。

對于模擬退火算法，溫度衰減系數β越接近1、每個溫度迭代次數K越大、終止溫度Tmin越低，算法的總迭代次數就越多，得到的優化結果越接近最優解，但需要的優化時間也會增加。

經過多次仿真測試，取β=0.8,K=50,Tmin=0.1時，可以在較短時間獲得較好的解。

3.2 算法的可行性校驗

本節通過展示單次規劃的過程和結果，校驗本文算法的可行性。在優化過程中，每一次降溫時記錄非受支配解集中的所有解對應的目標函數值，表示在二維空間中，稱為每個溫度下的近似Pareto面，如圖2所示。圖中橫軸表示目標函數f1，表示任務的總權重，正方向為權重增大方向，最大值為60；縱軸表示目標函數f2，表示任務的成像質量，正方向為成像質量提高，最大值為0(對于本算例，取α=0.004，可以使兩個目標函數對應的初始溫度在同一數量級)。點越靠近右上，其代表的解就越優。可以看出近似Pareto面呈現向右上角層層包絡的趨勢，且隨著溫度降低，相鄰溫度的近似Pareto面越來越緊密，這是由于隨著溫度下降，搜索鄰域逐漸變小，且接受差解的概率不斷降低。

圖2 多目標變鄰域模擬退火算法優化過程Fig.2 Optimization process of multi-objective variable-neighborhood simulated annealing algorithm

最終優化結果為最低溫度下的非受支配解集，按f1降序排列，如表1所示。最終得到的非受支配解集有5個非受支配解，這5個解表示的觀測時間窗口在可見時間窗口的位置如圖3所示。

表1 非受支配解的目標函數值Table 1 Objective function values of the non-dominated solutions

圖3 非受支配解觀測時間窗口位置示意圖Fig.3 Observation time window represented by non-dominated solutions

可以看出由于重疊的時間窗口中執行的任務可能會相互沖突，若要使目標函數f1達到最大，將會降低一部分時間窗口的成像質量。對于每次優化得到的非受支配解集，在所有觀測時間窗口必須包含于可見時間窗口1/4-3/4位置的前提下，選取任務權重最高的解作為優化的最終解。以本次優化結果為例，按完成任務總權重排序后，S1的總權重雖然最大，但有多個目標的觀測窗口不符合成像質量要求(圖示中的紅色段)，因此舍棄S1，在剩余解中按照上述原則選擇S2作為本次優化的最終解。

3.3 多種算法的比較和分析

為展示滑動優化、多目標優化、變鄰域搜索在優化考慮成像質量的成像衛星任務規劃問題上的優越性，將本文算法與將成像質量作為約束條件的單目標變鄰域模擬退火算法(VNSA)和單目標遺傳算法(GA)、考慮成像質量的單目標變鄰域模擬退火算法(WOVNSA)、固定鄰域的多目標模擬退火算法(MOSA)進行對比，每種算法進行20次仿真，下面用三組對比數據作進一步說明。

1)滑動優化與順序優化

VNSA是以成像時刻為優化對象，采用實數編碼實現對成像時刻的滑動優化的變鄰域模擬退火算法，而GA是以觀測順序為優化對象，采用整數編碼的遺傳算法。VNSA和GA都是以最大化完成任務總權重為目標的單目標優化算法，其目標函數為：

(21)

成像質量要求以約束條件的方式給出，以保證觀測時間窗口包含于可見時間窗口的1/4～3/4。其時間窗口為：

(22)

表2 VNSA和GA優化結果對比Table 2 Comparison of optimization results between VNSA and GA

可以看到，采用滑動優化方法的模擬退火算法從優化時間到優化效果都好于優化任務執行順序的遺傳算法，這是由于以執行順序為優化對象的編碼方式不能直接對成像時刻進行搜索，只能采用初始化的固定時刻或在沖突消解中確定，考慮到敏捷成像衛星時間窗口長，這樣勢必會浪費可觀測時間段。

2)多目標優化與單目標優化

MOVNSA是采用基于Pareto模型的多目標變鄰域模擬退火算法，WOVNSA是多目標加權的單目標變鄰域模擬退火算法，其目標函數為：

(23)

λ取值越大，成像質量對優化函數的影響就越小，經過多次仿真，取λ=1.5，可以得到滿足用戶需求的優化效果。優化結果如表3所示。

WOVNSA相比于MOVNSA對成像質量優化效果更好，而完成任務總權重較差，這是由于其每次迭代保留的都是兩個目標函數的折中解，丟失了滿足

表3 MOVNSA和WOVNSA優化結果對比Table 3 Comparison of optimization results between MOVNSA and WOVNSA

用戶需求的前提下的最大任務總權重的解。MOVNSA的優化結果給決策者提供了多個選擇，即使用戶對成像質量的需求發生變化，仍可在非受支配解集中選取最優解。

3)變鄰域與定鄰域搜索

MOVNSA是采用變鄰域搜索的多目標模擬退火算法，而MOSA是采用定鄰域(γ=0.5)搜索的多目標模擬退火算法，優化結果如表4所示。

表4 MOVNSA和MOSA優化結果對比Table 4 Comparison of optimization results between MOVNSA and MOSA

定鄰域的模擬退火算法的效果不佳，這是由于溫度較高時搜索范圍過小，無法跳出局部最優，而溫度較低時，接受差解的概率變低，過大的搜索范圍難以改善當前解，因此定鄰域模擬退火算法在優化過程中存在停滯的現象。定鄰域模擬退火算法的優化過程如圖4所示。

圖4 多目標定鄰域模擬退火算法優化過程Fig.4 Optimization process of multi-objective fixed-neighborhood simulated annealing algorithm

將圖4與圖2 (c)對比可以看出，隨著優化的不斷進行，定鄰域模擬退火算法的相鄰溫度近似Pareto面趨于重合，不能有效改善非受支配解集。

綜上所述，以成像時刻為優化對象的變鄰域模擬退火算法相比于以任務順序為優化對象的遺傳算法，大大提高了優化效率，并且可以有效的優化成像質量；其中多目標模擬退火算法既可以兼顧最大化完成任務總權重和提高成像質量，還可以給決策者多種選擇，根據用戶需求選擇最優解。

4 結 論

本文以最大化任務完成度和滿足用戶成像質量為目標，建立了多星協同的敏捷成像衛星觀測任務模型。設計了一種以成像時刻為優化對象的滑動優化策略，迭代過程中對每個任務的成像時刻進行鄰域搜索，可以兼顧優化單任務觀測時間段在可見時間窗口的位置和優化相鄰任務的觀測順序。采用多目標模擬退火算法求解該多目標優化問題，利用模擬退火算法中的降溫過程不斷縮小搜索范圍，顯著改善了算法的優化效果。仿真結果表明本文算法收斂速度快，優化效果好，可以在滿足用戶需求的前提下最大化完成任務總權重。