一種多目標(biāo)變鄰域模擬退火算法及成像星座任務(wù)規(guī)劃方法

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

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

0 引 言

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

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

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

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

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

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

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

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

1 敏捷成像星座任務(wù)規(guī)劃模型

1.1 參數(shù)和變量定義

1)模型參數(shù)

P觀測目標(biāo)集合，P={p1,p2,…,pNP}，其中NP為觀測目標(biāo)數(shù)量。

S成像衛(wèi)星集合，S={s1,s2,…,sNS}，其中NS為成像衛(wèi)星數(shù)量。

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

ok目標(biāo)pk的觀測時長。

ωk目標(biāo)pk的權(quán)重。

ai任務(wù)mi的最早成像時刻。

bi任務(wù)mi的最晚成像時刻。

ui任務(wù)mi的權(quán)重。

2)模型變量

yi衛(wèi)星執(zhí)行任務(wù)mi時的成像時刻。

zi任務(wù)mi的執(zhí)行情況，0表示不執(zhí)行任務(wù)mi，1表示執(zhí)行任務(wù)mi。

qjk衛(wèi)星與目標(biāo)的觀測關(guān)系，0表示目標(biāo)pk未由衛(wèi)星sj觀測，1表示目標(biāo)pk由衛(wèi)星sj觀測。

3)任務(wù)的表示

任務(wù)mi可以表示為：

(1)

1.2 多目標(biāo)約束滿足模型

本文構(gòu)建多目標(biāo)約束滿足模型來描述敏捷成像衛(wèi)星任務(wù)規(guī)劃問題，模型主要由約束條件、決策變量以及目標(biāo)函數(shù)構(gòu)成。

1)約束條件

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

(1)衛(wèi)星對目標(biāo)的可見性約束

若任務(wù)mi確定被執(zhí)行，則必須滿足

ai≤yi≤bi

(2)

(2)衛(wèi)星姿態(tài)機動能力約束

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

yi-ei′≥di′i

(3)

(3)衛(wèi)星星上資源約束

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

Ej≥η1θi+η2ok

(4)

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

每個目標(biāo)最多被觀測一次，且最多只被一顆衛(wèi)星觀測，對于目標(biāo)pk有

(5)

此約束條件可以協(xié)調(diào)衛(wèi)星之間的觀測行為，與約束(3)結(jié)合可以防止出現(xiàn)某些衛(wèi)星承擔(dān)了過多的觀測任務(wù)而其它衛(wèi)星閑置的情況，發(fā)揮成像星座的觀測優(yōu)勢。

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

2)決策變量

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

3)目標(biāo)函數(shù)

在以往研究中，多以最大化完成任務(wù)總權(quán)重作為優(yōu)化的目標(biāo)，但成像質(zhì)量也是成像任務(wù)執(zhí)行好壞的重要評價指標(biāo)，本文將提高成像質(zhì)量也作為優(yōu)化目標(biāo)。

(1)最大化完成任務(wù)總權(quán)重

(6)

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

(2)成像質(zhì)量最優(yōu)化

在同一個時間窗口中，成像時刻越靠近中心，由目標(biāo)到衛(wèi)星的仰角越大，成像質(zhì)量越高[15]，因此在優(yōu)化過程中應(yīng)盡可能將觀測窗口移向時間窗口中心，尤其是權(quán)重高的目標(biāo)，構(gòu)造目標(biāo)函數(shù)

(7)

為方便優(yōu)化算法的求解，將目標(biāo)函數(shù)式(7)轉(zhuǎn)化為最大化問題

(8)

式中：α為一個正數(shù)。

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

設(shè)多目標(biāo)優(yōu)化問題包含L個目標(biāo)函數(shù)、H個決策變量，其優(yōu)化目標(biāo)為

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

(9)

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

(10)

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

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

2 多目標(biāo)變鄰域模擬退火算法

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

2.1 成像時刻的編碼解碼

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

1)解的編碼

對于任務(wù)mi，隨機生成yi：

yi=ai+ε·(bi-ai)

(11)

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

2)解的解碼

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

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

(12)

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

(3)設(shè)衛(wèi)星在時刻ei′執(zhí)行完上一任務(wù)mi′，姿態(tài)矩陣為Rboi′，預(yù)計在時刻yi執(zhí)行該任務(wù)，姿態(tài)矩陣為Rboi，計算機動角度

(13)

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

(14)

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

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

2.2 解的變鄰域搜索

為實現(xiàn)成像時刻在時間窗口內(nèi)的滑動搜索，本文設(shè)計了一個位移算子，用于調(diào)整成像時刻在時間窗口的位置。

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

(15)

γ=tn/Tn

(16)

式中：Tn和tn分別為目標(biāo)函數(shù)fn對應(yīng)的初始溫度和當(dāng)前溫度。在本文算法中，所有目標(biāo)函數(shù)對應(yīng)的溫度采用同樣的衰減系數(shù)，因此γ與n的取值無關(guān)?？梢钥闯?，γ∈(0,1]，且隨溫度降低不斷減小。下面介紹初始溫度的計算方法：

(17)

根據(jù)模擬退火算法解的接受準(zhǔn)則[17]，可以認(rèn)為在溫度Tn下，任意兩個解之間都有相同的轉(zhuǎn)化概率。

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

(18)

實現(xiàn)了成像時刻在時間窗口內(nèi)的變鄰域搜索。

2.3 非受支配解集的構(gòu)造

本節(jié)給出多目標(biāo)模擬退火算法中解的選拔淘汰機制以及非受支配解集的構(gòu)造方法。

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

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

(19)

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

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

(20)

如果新解被接受，令Scur=Snew，否則保留當(dāng)前解。

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

以上步驟如圖1所示。

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

3 仿真校驗與結(jié)果分析

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

3.1 模型和算法參數(shù)設(shè)置

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

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

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

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

3.2 算法的可行性校驗

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

圖2 多目標(biāo)變鄰域模擬退火算法優(yōu)化過程Fig.2 Optimization process of multi-objective variable-neighborhood simulated annealing algorithm

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

表1 非受支配解的目標(biāo)函數(shù)值Table 1 Objective function values of the non-dominated solutions

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

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

3.3 多種算法的比較和分析

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

1)滑動優(yōu)化與順序優(yōu)化

VNSA是以成像時刻為優(yōu)化對象，采用實數(shù)編碼實現(xiàn)對成像時刻的滑動優(yōu)化的變鄰域模擬退火算法，而GA是以觀測順序為優(yōu)化對象，采用整數(shù)編碼的遺傳算法。VNSA和GA都是以最大化完成任務(wù)總權(quán)重為目標(biāo)的單目標(biāo)優(yōu)化算法，其目標(biāo)函數(shù)為：

(21)

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

(22)

表2 VNSA和GA優(yōu)化結(jié)果對比Table 2 Comparison of optimization results between VNSA and GA

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

2)多目標(biāo)優(yōu)化與單目標(biāo)優(yōu)化

MOVNSA是采用基于Pareto模型的多目標(biāo)變鄰域模擬退火算法，WOVNSA是多目標(biāo)加權(quán)的單目標(biāo)變鄰域模擬退火算法，其目標(biāo)函數(shù)為：

(23)

λ取值越大，成像質(zhì)量對優(yōu)化函數(shù)的影響就越小，經(jīng)過多次仿真，取λ=1.5，可以得到滿足用戶需求的優(yōu)化效果。優(yōu)化結(jié)果如表3所示。

WOVNSA相比于MOVNSA對成像質(zhì)量優(yōu)化效果更好，而完成任務(wù)總權(quán)重較差，這是由于其每次迭代保留的都是兩個目標(biāo)函數(shù)的折中解，丟失了滿足

表3 MOVNSA和WOVNSA優(yōu)化結(jié)果對比Table 3 Comparison of optimization results between MOVNSA and WOVNSA

用戶需求的前提下的最大任務(wù)總權(quán)重的解。MOVNSA的優(yōu)化結(jié)果給決策者提供了多個選擇，即使用戶對成像質(zhì)量的需求發(fā)生變化，仍可在非受支配解集中選取最優(yōu)解。

3)變鄰域與定鄰域搜索

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

表4 MOVNSA和MOSA優(yōu)化結(jié)果對比Table 4 Comparison of optimization results between MOVNSA and MOSA

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

圖4 多目標(biāo)定鄰域模擬退火算法優(yōu)化過程Fig.4 Optimization process of multi-objective fixed-neighborhood simulated annealing algorithm

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

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

4 結(jié) 論

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