灰色蟻群系統(tǒng)求解多目標(biāo)衛(wèi)星觀測調(diào)度問題

王海波，徐敏強(qiáng)，王日新，李玉慶

(哈爾濱工業(yè)大學(xué)深空探測基礎(chǔ)研究中心，哈爾濱150080，1021810103@163.com)

地球觀測衛(wèi)星的任務(wù)是根據(jù)用戶需求獲取指定區(qū)域的圖像信息.為了能夠最大限度的利用衛(wèi)星資源，有必要對衛(wèi)星的觀測活動進(jìn)行合理的規(guī)劃和調(diào)度.由于衛(wèi)星資源調(diào)度是一個典型的過載調(diào)度問題，在一定時間內(nèi)不可能完成所有用戶需求，這就需要根據(jù)成像需求的重要程度和云量信息，在滿足側(cè)視轉(zhuǎn)換時間、存儲容量等約束條件下，使盡可能重要、成像質(zhì)量好的成像需求獲得成像.目前，單顆衛(wèi)星的觀測調(diào)度以及多星聯(lián)合觀測調(diào)度問題，各國學(xué)者進(jìn)行了大量研究，并取得了一定的成果［1-4］.但是，國內(nèi)外對該問題的研究很少系統(tǒng)地考慮云層覆蓋對調(diào)度的影響，獲得的圖像可能因?yàn)樵茖拥挠绊懚貌坏接行У氖褂?，造成衛(wèi)星資源的極大浪費(fèi).衛(wèi)星觀測調(diào)度問題已被證明是NP-hard問題，這意味著當(dāng)問題規(guī)模很大時，不能在合理的時間內(nèi)窮舉出所有的成像路徑.蟻群優(yōu)化算法是一種元啟發(fā)式算法，雖然不能保證得到的是最優(yōu)解，但能在合理的時間內(nèi)得到問題較好的近優(yōu)解［5］.因此，本文提出了一種灰色蟻群系統(tǒng)算法來解決衛(wèi)星觀測調(diào)度問題，采用多個目標(biāo)函數(shù)評價成像路徑的質(zhì)量，實(shí)現(xiàn)觀測數(shù)據(jù)高效優(yōu)質(zhì)的獲取.

1 多目標(biāo)衛(wèi)星觀測調(diào)度優(yōu)化模型

1.1 基于區(qū)間灰數(shù)的云量描述

目前，主要通過兩種方法得到無云或者少云圖像:1)調(diào)度前利用云量預(yù)測模型進(jìn)行成像預(yù)調(diào)度;2)調(diào)度后基于拍攝圖像的云量評估進(jìn)行重調(diào)度.合理的成像預(yù)測調(diào)度模型能有效降低重調(diào)度的成本，減少衛(wèi)星資源的浪費(fèi).因此采用短期云量預(yù)報的衛(wèi)星成像預(yù)調(diào)度，其調(diào)度時間段為6 h，關(guān)于重調(diào)度研究本文不作討論.

云層覆蓋是影響衛(wèi)星拍攝圖像質(zhì)量最主要的因素.云量是有云天空占天空總面積的比例，我國云量計(jì)算單位采用10成制.天空無云，云量為0，天空完全為云所遮蔽，云量為10.由于現(xiàn)有的氣象預(yù)報技術(shù)還不能準(zhǔn)確地預(yù)測某地某時上空的云量，而往往給定一個云量信息的區(qū)間范圍，因此本文采用區(qū)間灰數(shù)來描述衛(wèi)星與成像需求觀測時間窗口內(nèi)的云量.灰數(shù)是指只知其大概范圍而不知其確切值的數(shù)，通常用“?”表示.既有下界a又有上界ˉa的灰數(shù)稱為區(qū)間灰數(shù)，記為?∈［］［6］.

定義1 設(shè)?1∈，且記L(?1)=，則稱p≥?(?12)=為?1≥?2的可能度［7］.

在算法的每次迭代中，當(dāng)蟻群系統(tǒng)中每只螞蟻都構(gòu)建一條完整的成像路徑之后，通過區(qū)間灰數(shù)的運(yùn)算法則以及區(qū)間數(shù)大小的可能度定義比較成像路徑之間的云量大小.由于缺乏區(qū)間灰數(shù)取值的分布信息，采用等權(quán)均值白化得到每條成像路徑的平均云量信息，進(jìn)而得到Pareto最優(yōu)解.

1.2 多目標(biāo)衛(wèi)星調(diào)度優(yōu)化模型

衛(wèi)星以一定的軌道繞地球運(yùn)行，當(dāng)衛(wèi)星飛臨目標(biāo)區(qū)域時，由于受成像幅寬的限制，只能選取某個目標(biāo)區(qū)域成像，而每個目標(biāo)區(qū)域都有嚴(yán)格的觀測時間窗口.由于衛(wèi)星的姿態(tài)控制能力以及星上的存儲容量有限，而且成像任務(wù)的觀測時間窗口之間往往有重疊區(qū)域，一個軌道圈次內(nèi)不能完成所有成像需求，需要考慮成像任務(wù)的重要程度、云量信息以及消耗的存儲器容量等各種因素選擇任務(wù)成像.在調(diào)度之前首先作如下假設(shè):

1)一顆衛(wèi)星任意時刻最多只能處理一個任務(wù);

2)用戶的成像需求為點(diǎn)目標(biāo)，若為區(qū)域目標(biāo)，可按照一定的規(guī)則分解為多個點(diǎn)目標(biāo);

3)任務(wù)在被執(zhí)行期間不能被中斷;

4)由于衛(wèi)星沿著一定的軌道高速運(yùn)行，在衛(wèi)星與成像需求的可見時間窗口內(nèi)，成像任務(wù)上空的云量不發(fā)生變化.

為了建立衛(wèi)星成像調(diào)度問題模型，首先給出以下成像參數(shù):調(diào)度的時間區(qū)間T;成像衛(wèi)星集合S;待成像的任務(wù)集合J;衛(wèi)星α對任務(wù)i的成像開始時間;衛(wèi)星α對任務(wù)i的成像結(jié)束時間;成像任務(wù)i的持續(xù)時間di;衛(wèi)星α對成像任務(wù)i的側(cè)視角度aαi;成像任務(wù)i的權(quán)重因子pi;衛(wèi)星α完成任務(wù)i所需的存儲容量qαi;衛(wèi)星α側(cè)視角的轉(zhuǎn)動速度rα;衛(wèi)星α固態(tài)存儲器的圖像存儲能力Mα;成像任務(wù)i與衛(wèi)星α可見時間窗口內(nèi)天空的云量［hαi，ˉhαi］;成像任務(wù)i允許的最大云量Hi;定義決策變量:γαi為二元變量，γαi=1表示衛(wèi)星α調(diào)度成像任務(wù)i，否則γαi=0;bi表示任務(wù)i成像的開始時間;ωαik為二元變量，ωαik=1表示在衛(wèi)星α的成像序列中，成像任務(wù)k與i相鄰，且在i后執(zhí)行，否則ωαik=0;

為了更全面的反映調(diào)度結(jié)果的質(zhì)量，采用多目標(biāo)函數(shù)評價成像路徑，目標(biāo)函數(shù)定義如下: 1)成像調(diào)度未完成成像任務(wù)的重要程度，

2)成像調(diào)度所有成像任務(wù)的平均云量，

成像調(diào)度過程中考慮的約束條件有:

1)初始成像任務(wù)的轉(zhuǎn)換約束.虛擬初始任務(wù)0和該衛(wèi)星所有可用任務(wù)都滿足側(cè)視約束，即

2)成像側(cè)視角約束.衛(wèi)星對一個任務(wù)成像之后，必須有足夠的時間完成側(cè)視動作，以對下一個任務(wù)成像，即

3)星上存儲容量約束.衛(wèi)星在成像任務(wù)過程中，存儲的數(shù)據(jù)總量不能超過其最大容量，即

2 灰色蟻群系統(tǒng)的多目標(biāo)優(yōu)化算法

求解多目標(biāo)優(yōu)化問題的常用方法有字典排序法、目標(biāo)加權(quán)法和基于Pareto最優(yōu)解方法.前兩種方法需要決策者已知目標(biāo)函數(shù)的先驗(yàn)信息，而在衛(wèi)星觀測調(diào)度問題中，很難得到目標(biāo)函數(shù)的相關(guān)信息.因此，本文采用基于Pareto最優(yōu)解的思想，將Pareto前端分為多個相等部分，將蟻群也分為多個種群，每個種群搜索Pareto前端的一部分，搜索方向能覆蓋整個解空間，且得到的Pareto最優(yōu)解具有良好的分布性.為保證解的收斂性，采用精英保留策略，下面對算法的主要步驟作詳細(xì)說明.

2.1 信息素的定義以及初始化

算法將“某個成像任務(wù)i被執(zhí)行后立刻執(zhí)行任務(wù)j的期望度”定義為信息素τij.對每個目標(biāo)函數(shù)分別構(gòu)建一個信息素矩陣，本文研究的成像調(diào)度模型包含兩個目標(biāo)函數(shù)，故可記為矩陣τ和τ'，將這兩個信息素矩陣中的所有元素值初始化為τ0.

2.2 解的構(gòu)建

多種群策略能促進(jìn)蟻群系統(tǒng)中子種群的生成和保持，從而保護(hù)一些次優(yōu)解以維持種群多樣性，防止蟻群系統(tǒng)收斂到Pareto前端的單一點(diǎn).因此采用多種群搜索方式，將m只螞蟻分為大小相等的m'個種群，每個種群中含有m″只螞蟻，其中，m=m'×m″.每一代中，每只螞蟻都構(gòu)建一條完整的成像路徑，在構(gòu)建路徑過程中，使用偽隨機(jī)比例的狀態(tài)轉(zhuǎn)移規(guī)則選擇下個成像任務(wù)，如下式所示:

如果q≤q0:

否則，

其中，q0∈［0，1］，q是均勻分布在區(qū)間［0，1］中的一個隨機(jī)變量，choicek表示第k只螞蟻可選下一個成像任務(wù)的候選列表，候選列表是成像任務(wù)無圈有向圖［8］上，與i相鄰在i之后可成像的任務(wù)集合，可避免在成像任務(wù)i大規(guī)模的鄰域上搜索，減小了搜索空間，節(jié)省了程序的運(yùn)行時間.ξ和ζ分別是信息素和啟發(fā)式信息的權(quán)參數(shù).ηij和η'ij分別是邊e(i，j)相對于每一個目標(biāo)函數(shù)的啟發(fā)式值，如式(2)(3)所示.

為加強(qiáng)每個種群的螞蟻搜索Pareto前端不同的區(qū)域，每個種群都要由下式計(jì)算λ的范圍，

其中:h∈{1，2，…，m'}.

2.3 精英保留策略

加會產(chǎn)生越來越多的優(yōu)良個體，但由于狀態(tài)轉(zhuǎn)移規(guī)則的隨機(jī)性，有可能破壞本屬于Pareto前端的個體，影響蟻群系統(tǒng)的搜索效率和收斂性.精英保留策略的思想是在每個種群中，將當(dāng)前Pareto前端的個體保留到下一代群體，參與信息素的更新操作.該策略可以明顯加速蟻群算法的搜索過程，并且在找到優(yōu)良解后可以防止它的丟失.因此，存儲至今每個種群得到的Pareto最優(yōu)解的成像路徑Tbs，允許這些路徑進(jìn)行信息素的更新操作.

2.4 全局信息素更新規(guī)則

為了加強(qiáng)算法對Pareto前端各個部分的探索度，使用了一種區(qū)域更新規(guī)則，即每只螞蟻只在它所屬的種群中更新信息素矩陣.只有在當(dāng)前迭代中得到的Pareto前端的路徑Tis與該種群中至今最優(yōu)路徑Tbs才能釋放信息素，且只有這些螞蟻進(jìn)行信息素的蒸發(fā)動作，如下式所示.

其中:

τ'信息素矩陣更新類似.

2.5 局部信息素更新規(guī)則

除了全局信息素更新規(guī)則外，灰色蟻群系統(tǒng)還使用了一個局部信息素更新規(guī)則如下式:

其中:參數(shù)ρl是局部信息素的蒸發(fā)速率，τ0是信息素的初始值.

在成像路徑構(gòu)建過程中，若螞蟻經(jīng)過邊e(i，j)，則調(diào)用這條規(guī)則更新該邊上的信息素.

局部更新規(guī)則能增加螞蟻探索未調(diào)度的成像任務(wù)的機(jī)會，使得算法不會陷入停滯狀態(tài).

3 仿真試驗(yàn)及結(jié)果分析

為了說明前文所建立的模型以及算法的有效性，對3顆太陽同步軌道地球觀測衛(wèi)星進(jìn)行成像調(diào)度，假設(shè)衛(wèi)星具有相同的軌道參數(shù)，如表1所示.星上CCD相機(jī)的側(cè)擺能力為±32°，固態(tài)存儲器容量274 Gb.所有任務(wù)的調(diào)度起止時間為2009-01-01T0/T6.

蟻群系統(tǒng)在進(jìn)化過程中，雖然隨迭代次數(shù)的增

表1 軌道參數(shù)

由于算法的參數(shù)較多，且各參數(shù)對算法的影響較大，因此采用多次試驗(yàn)比較的方式，最終確定各參數(shù)如表2所示時，運(yùn)行結(jié)果較為理想.

表2 灰色蟻群系統(tǒng)的參數(shù)

為了對比算法的性能，應(yīng)用多目標(biāo)蟻群優(yōu)化算法中廣泛采用的Pareto ant colony optimization (PACO)［9］算法和本文提出的灰色蟻群系統(tǒng)優(yōu)化(GACS)算法對500個成像需求進(jìn)行調(diào)度，比較結(jié)果如圖1所示.由圖1可以看出，GACS得到的Pareto最優(yōu)解支配大部分PACO算法求得的Pareto最優(yōu)解，PACO算法雖然可以獲得一定數(shù)目的最優(yōu)解，但是獲得的最優(yōu)解數(shù)目較少，且分布性不如GACS均勻.兩種算法的運(yùn)行時間都滿足運(yùn)行時間限制，均不超過1 200 s.

圖1 500個任務(wù)時算法的性能比較

為分析GACS算法的收斂性，用文獻(xiàn)［10］中定義的信息熵來衡量式(1)中節(jié)點(diǎn)轉(zhuǎn)移概率pkij的分布程度的信息量，熵值越趨近于0，表明節(jié)點(diǎn)轉(zhuǎn)移規(guī)則更有確定性.所有節(jié)點(diǎn)熵值的平均值稱為平均熵，平均熵隨迭代次數(shù)變化情況如圖2所示.

圖2 GACS算法的收斂性分析

由圖可知，隨迭代次數(shù)的增加，平均熵值由初始的5.19逐步遞減為1.90，表明當(dāng)進(jìn)化成熟時，非支配路徑上的信息素濃度遠(yuǎn)大于支配路徑上的信息素濃度，從而節(jié)點(diǎn)的概率分布也更穩(wěn)定.

實(shí)際應(yīng)用中，在得到衛(wèi)星成像調(diào)度的Pareto最優(yōu)解后需根據(jù)具體情況對這些成像序列進(jìn)行選擇，生成衛(wèi)星的動作指令指導(dǎo)衛(wèi)星完成成像任務(wù).

4 結(jié)論

多目標(biāo)衛(wèi)星觀測調(diào)度問題相比傳統(tǒng)的衛(wèi)星觀測調(diào)度更符合實(shí)際的調(diào)度情況，也是新出現(xiàn)的一類復(fù)雜的問題.本文采用灰色蟻群系統(tǒng)對該問題進(jìn)行了優(yōu)化求解，仿真結(jié)果表明所建立的數(shù)學(xué)模型以及算法的可行性和合理性.

［1］BENSANA E，LEMAITRE M，VERFAILLIE G.Earth observation satellite management［J］.Constraints，1999，4(3):293-299.

［2］WOLFE W J，SORENSEN S E.Three scheduling algorithms applied to the earth observing systems domain［J］.Management Science，2000，46(1):148-168.

［3］LEMAITRE M，VERFAILLIE G，JOUHAUD F，et al.Selecting and scheduling observations of agile satellites［J］. Aerospace Science and Technology，2002，6:367-381.

［4］BIANCHESSI N，CORDEAU J，DESROSIERS J，et al. A heuristic for the multi-satellite，multi-orbit and multiuser management of Earth observation satellites［J］.European Journal of Operational Research，2007，117 (2):750-762.

［5］DORIGO M，STUTZLE T.Ant colony optimization［M］.Cambridge，MA:MIT Press，2004.

［6］劉思峰，黨耀國，方志耕.灰色系統(tǒng)理論及其應(yīng)用［M］.第3版.北京:科學(xué)出版社，2004.

［7］王堅(jiān)強(qiáng)，任世昶.基于期望值的灰色隨機(jī)多準(zhǔn)則決策方法［J］.控制與決策，2009，24(1):39-43.

［8］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: 533-542.

［9］DOERNER K，GUTJAHR W，HARTL R，et al.Pareto ant colony optimization:A metaheuristic approach to multiobjective portfolio selection［J］.Annals of Operations Research，2004，131:79-99.

［10］YIN PengYeng，WANG JingYu.Ant colony optimization for the nonlinear resource allocation problem［J］. Applied Mathematics and Computation，2006，174: 1438-1453.