劉 翔，雷明佳，陳韜亦，陳金勇，馮小恩

(1.中國電子科技集團公司 航天信息應(yīng)用技術(shù)重點實驗室，河北 石家莊 050081；2.哈爾濱工業(yè)大學(xué) 深空探測基礎(chǔ)研究中心，黑龍江 哈爾濱 150080)

0 引言

多星觀測任務(wù)優(yōu)化是指在一定的優(yōu)化目標指導(dǎo)下，對多個觀測任務(wù)進行排程，進一步確定需要擇優(yōu)執(zhí)行哪些任務(wù)，以及執(zhí)行這些任務(wù)的衛(wèi)星和時間窗口。隨著近幾十年航天事業(yè)的不斷進步與發(fā)展，我國在軌運行和規(guī)劃研制的觀測衛(wèi)星的數(shù)量和種類均在不斷增多，與此同時也對觀測衛(wèi)星的任務(wù)規(guī)劃提出了十分嚴峻的考驗[1-3]，因此研究高效、準確且有工程實踐價值的衛(wèi)星觀測任務(wù)優(yōu)化算法具有重要意義。

目前國內(nèi)外已有大量針對不考慮數(shù)據(jù)下傳的衛(wèi)星觀測任務(wù)優(yōu)化問題的研究。Mohamed等[4]將spot5衛(wèi)星的日調(diào)度問題直接轉(zhuǎn)化成對benchmark問題，并采用遺傳算法求解，文獻[5-7]則進一步提出了改進算法，在一定程度上提高了算法的求解精度和求解速度。Zhaojun Zhang[8]在研究多星控制資源規(guī)劃問題時提出一種復(fù)雜的獨立集合模型，并建立了基于蟻群優(yōu)化的規(guī)劃算法。陳英武等[9]建立了多星任務(wù)規(guī)劃模型，并設(shè)計了基于動態(tài)參數(shù)決策模型的演化學(xué)習(xí)型蟻群算法。文獻[10-11]則對分布式衛(wèi)星系統(tǒng)采用粒子群優(yōu)化算法求解其多任務(wù)數(shù)傳調(diào)度問題。Wang和Qiu等[12]首次建立了對分布式成像衛(wèi)星應(yīng)急任務(wù)的新型多目標動態(tài)調(diào)度模型，并將任務(wù)進行合并。文獻[13-15]分析了衛(wèi)星運行及觀測活動過程中的部分約束條件，并建立了相應(yīng)的數(shù)學(xué)模型。

以上文獻針對所研究問題提出的求解方法雖在一定程度上取得了較好的效果，但普遍存在著約束不全面或計算耗時長的問題，本文針對多星觀測任務(wù)的優(yōu)化問題，在基于對各種復(fù)雜約束分析的基礎(chǔ)上，提出了一種基于貪婪策略的遺傳算法，通過將貪婪算法的核心思想與遺傳算法有機結(jié)合，在保證算法求解精度的同時提高算法的收斂速度。

1 多星觀測任務(wù)規(guī)劃問題描述

1.1 衛(wèi)星觀測任務(wù)模型

多星觀測任務(wù)優(yōu)化的過程實際就是對衛(wèi)星觀測任務(wù)加以選擇的過程，而衛(wèi)星的觀測任務(wù)模型是根據(jù)工程實踐需要以及用戶需求建立的，可用如下模型描述：

tasknq

{

Datanq；xnq

}

1.2 觀測任務(wù)規(guī)劃模型

信息實時獲取條件下的多星觀測任務(wù)規(guī)劃(Multi-Satellite Observation Task Planning，MuSOTP)，就是假設(shè)在給定規(guī)劃時段內(nèi)的任務(wù)與觀測資源不變且星際鏈路穩(wěn)定的條件下，多顆能力異構(gòu)的對地觀測衛(wèi)星完成任務(wù)分配。將多星觀測任務(wù)規(guī)劃問題表述為：

MuSOTP={SAT，TGT，W，TASK，RES；STATE}，

其中，W表示所有可見窗口集合；TASK表示衛(wèi)星觀測任務(wù)集合，TASK={task11，…，task1r1；…；taskN1，…，taskNrN}；RES表示約束條件集合；STATE表示所有觀測任務(wù)的關(guān)系狀態(tài)集合。

同時做出如下假設(shè)：

① 各觀測任務(wù)之間具有獨立性；

② 每個目標至多只能被觀測一次；

③ 不考慮衛(wèi)星設(shè)備故障；

④ 極端工況和特殊工況不予考慮。

基于上述定義和假設(shè)，多星觀測任務(wù)規(guī)劃的目的就是從各衛(wèi)星的觀測任務(wù)集合中選擇一個子集，使得生成的規(guī)劃方案在滿足約束集合RES的前提下獲取最大的目標觀測收益。多星觀測任務(wù)規(guī)劃模型為：

(1)

(2)

式(1)表示在約束條件下的最大觀測收益；式(2)表示每個目標最多只能被觀測一次。

2 約束條件分析

本文綜合考慮載荷運行和平臺運行，既要研究與觀測任務(wù)相關(guān)的可見時間窗口的約束條件，還要考慮和平臺運行有關(guān)的衛(wèi)星軌道、熱控、能量和姿態(tài)等多方面的約束，并逐一建立數(shù)學(xué)模型。

2.1 觀測時間窗口約束

由于星載傳感器的錐角和衛(wèi)星側(cè)擺角的限制[16-17]，衛(wèi)星只有在位于目標上方一定范圍內(nèi)時，才可對其觀測。目標可被觀測的某一時段，稱為可見窗口。觀測任務(wù)必須在可見窗口內(nèi)完成，如圖1所示。

圖1 觀測任務(wù)時間窗口約束示意

本文利用Matlab和STK預(yù)先計算出所有衛(wèi)星對各目標的可見窗口，對于觀測任務(wù)tasknq，觀測時間窗口約束可表示為：

(3)

2.2 姿態(tài)調(diào)整約束

姿態(tài)調(diào)整沖突是針對衛(wèi)星觀測任務(wù)提出的，即衛(wèi)星觀測時姿態(tài)調(diào)整擺角不能超過設(shè)定值θ。目標在衛(wèi)星軌道坐標系下的位置坐標為xs，ys，zs，則衛(wèi)星俯仰和翻滾軸向的擺角θP，θR約束為：

(4)

2.3 觀測過渡時間約束

衛(wèi)星在執(zhí)行2個相鄰任務(wù)時，需考慮到一定的過渡時間，以保證在此期間內(nèi)調(diào)整好衛(wèi)星姿態(tài)和成像儀器的工作狀態(tài)，如圖2所示。

圖2 觀測過渡時間約束示意

以連續(xù)的任務(wù)a和任務(wù)a+1為例分析，設(shè)衛(wèi)星俯仰軸向的調(diào)姿角速度參數(shù)為ω、翻滾軸向的調(diào)姿角速度參數(shù)為ψ，衛(wèi)星完成前一觀測任務(wù)的觀測擺角為(θPB，θRB)，取其后某一時刻對后續(xù)任務(wù)的觀測擺角為(θP，θR)，在連續(xù)姿態(tài)調(diào)整模式下，衛(wèi)星的姿態(tài)機動時間Δta，a+1的計算公式為：

(5)

對于衛(wèi)星satn的任務(wù)序列，前一個任務(wù)結(jié)束到下一個任務(wù)開始之間的時間間隔應(yīng)該大于或等于一個過渡時間Ba，a+1，且過渡時間應(yīng)該大于或等于衛(wèi)星姿態(tài)調(diào)整時間Δta，a+1，觀測過渡時間約束可表示為：

(6)

Ba，a+1≥Δta，a+1，

(7)

2.4 光照及能量平衡約束

對衛(wèi)星電源系統(tǒng)有當(dāng)圈能量平衡約束[18-19]，即蓄電池組在地影期的放電量能在之后的光照期內(nèi)得到完全補充，且為保證蓄電池壽命，單次在地影期的放電深度不超過20%，則能量平衡約束如下：

tCs，tCe∈[Tg，Td] ，

(8)

Ed≤min{Ec，0.2*EB}，

(9)

式中，Tg，Td表示衛(wèi)星光照期的起始時間和結(jié)束時間；Ed，Ec表示電池組在地影期的放電量、光照期的充電能；EB表示蓄電池容量。

2.5 存儲資源約束

衛(wèi)星每次存儲的觀測數(shù)據(jù)的大小不能超過存儲設(shè)備當(dāng)前的剩余容量Datafree，存儲資源約束可表示為：

?tasknq∈TASK，Datanq≤Datafree。

(10)

3 基于貪婪策略的遺傳算法設(shè)計與實現(xiàn)

遺傳算法是從代表問題可能潛在解集的一個種群開始，按照適者生存、優(yōu)勝劣汰的原理，逐漸進化產(chǎn)生近似最優(yōu)解的智能算法[20-21]。

3.1 編碼

本文遺傳算法采用二進制方式編碼，如圖3所示。染色體的每一位代表某一目標對應(yīng)的某一時間窗口，取值為0或1，0表示該窗口不執(zhí)行，1表示該窗口執(zhí)行，染色體長度即為所有目標對于所有衛(wèi)星的可見時間窗口數(shù)量。

圖3 遺傳算法二進制編碼方式

3.2 適應(yīng)值函數(shù)

適應(yīng)值是遺傳算法選擇的方向和標志，直接影響算法解決實際問題的性能和效率。適應(yīng)值函數(shù)通常根據(jù)問題的優(yōu)化目標來建立，通過評價種群中個體的適應(yīng)度來選擇個體。本文的適應(yīng)值函數(shù)即為式(1)。

3.3 基于貪婪策略的種群初始化

由于遺傳算法的搜索性能與種群的分布狀態(tài)密切相關(guān)，而種群在遺傳算法執(zhí)行過程中的分布變化直接受其初始狀態(tài)的影響，現(xiàn)有的方法大多通過隨機產(chǎn)生初始種群，本文為了提高遺傳算法的收斂速度和計算精度，采用基于貪婪策略[22]的賦值方法生成規(guī)模為M的初始化種群，具體方法如下：

① 將染色體按觀測目標編號重新排序；

② 設(shè)置貪婪概率Pgreedy，計算需要置1的基因位數(shù)量T*Pgreedy；

③ 設(shè)置數(shù)組aT，亂序存放整數(shù)1，2，…，T，取前T*Pgreedy個數(shù)，即為染色體上需要被置1的基因位對應(yīng)的目標編號；

④ 找到染色體上對應(yīng)③中各目標編號的基因位，并在每個目標對應(yīng)的基因位中隨機選擇一個置為1，剩余全部基因位置為0。

3.4 遺傳算子設(shè)計

3.4.1 復(fù)制選擇算子

選擇算子主要實現(xiàn)父代種群中優(yōu)秀個體和良好基因的保存，本文采用如下選擇機制：對新產(chǎn)生的種群，按適應(yīng)值從高到低排序，最高的個體直接進入交配池，剩余的個體按輪盤賭的機制進行選擇，以提高適應(yīng)值高的個體進入交配池的概率，盡可能淘汰適應(yīng)值低的個體，且進入交配池的個體數(shù)量與種群數(shù)量相等。

3.4.2 交叉算子

由于雙點交叉和三點交叉的方式在增加種群多樣性的同時也增加了搜索的隨機性，會導(dǎo)致算法收斂速度下降，因此選用單點交叉方法。隨機選擇交配池中的2個個體，隨機選擇一個交叉點，將2條染色體上位于交叉點之后的片段互換，即完成交叉操作。設(shè)交叉概率為Pcross，則執(zhí)行交叉操作的個體數(shù)Mcross為：

Mcross=Pcross*M。

(11)

3.4.3 變異算子

變異算子能在種群個體間適應(yīng)值區(qū)別較小時，增加種群的多樣性，防止進化停滯，陷入局部最優(yōu)。對進入交配池的個體，按一定的變異概率對染色體選擇是否進行變異操作。當(dāng)染色體被選中時，隨機選擇10%*T個基因位，改變該基因位原來的值，即由1變?yōu)?，或由0變?yōu)?。設(shè)變異概率為Pmuta，則執(zhí)行變異操作的個體數(shù)Mmuta為：

Mmuta=Pmuta*M。

(12)

3.5 種群更新

對經(jīng)過約束沖突處理的新個體計算適應(yīng)值，若新個體的適應(yīng)值比原個體的適應(yīng)值高，則用新個體替換原個體進入到下一代種群中，否則保留原個體進入下一代。逐代優(yōu)化，得到最優(yōu)解。

3.6 算法實現(xiàn)

采用Matlab編程實現(xiàn)算法，步驟如下：

① 設(shè)置算法最大迭代次數(shù)MaxRun基于貪婪策略的種群初始化：采用3.3節(jié)中的初始化方法，對種群中的每條染色體按(0，1)編碼方式進行編碼；

② 沖突處理：對染色體上的基因位逐一進行沖突檢查，沒有通過沖突檢查的基因位置為0；

③ 完成沖突檢查和處理后，計算各個體的適應(yīng)值，記錄適應(yīng)值最高的個體；

④ 判斷算法停止條件，若滿足停止條件，轉(zhuǎn)向步驟⑤；否則按選擇機制選擇個體進入交配池，完成變異、交叉操作產(chǎn)生新個體，并進行種群更新得到下一代種群，返回步驟②；

⑤ 算法結(jié)束，獲得最佳個體，輸出相應(yīng)的觀測任務(wù)方案。

算法流程如圖4所示。

圖4 算法流程

4 算例及分析

為了驗證基于貪婪策略的遺傳算法能在保證算法精度的前提下有效提高算法的收斂速度，采用模擬數(shù)據(jù)建立仿真算例，所有算法和程序用MATLABR2014a編程軟件實現(xiàn)。對于目標、衛(wèi)星的模型建立，時間窗口和衛(wèi)星光照地影時段的預(yù)處理都通過STK9.2仿真軟件實現(xiàn)，運行環(huán)境為Windows10 教育版，Intel Core i3-3220 CPU@3.30 GHz，8 GB RAM。

模擬數(shù)據(jù)產(chǎn)生過程如下：

① 在STK仿真場景中設(shè)定衛(wèi)星數(shù)量為10顆，建立遙感衛(wèi)星模型S1～S10來共同完成目標觀測任務(wù)，其軌道建立參考了Orbview、Landsat、資源三號、風(fēng)云一號和天繪一號等衛(wèi)星的軌道參數(shù)；

② 利用Matlab隨機在全球范圍內(nèi)建立50個地面觀測目標點，并隨機設(shè)定每個目標的收益值；

③ 設(shè)定多星觀測任務(wù)規(guī)劃周期為24 h；

④ 在STK中計算10顆衛(wèi)星對50個地面目標的所有可見窗口W，部分觀測窗口的數(shù)據(jù)如表1所示。

表 1 觀測窗口數(shù)據(jù)表

衛(wèi)星ID目標ID開始時間/s結(jié)束時間/s持續(xù)時間/s收益值137 288.3977 571.286282.889961313 190.56213 469.606279.0449211913 567.78913 825.651257.862801261 179.0711 370.923191.8529………………103766 109.48466 249.141139.65790104665 869.82466 105.537235.71333104971 704.16571 896.477192.31277

算法的主要參數(shù)設(shè)置為：種群規(guī)模swarmNum=30，最大遺傳代數(shù)MaxRun=50，交叉概率Pcross=1，變異概率Pmuta=0.1，貪婪概率Pgreedy=0.7。由于遺傳算法本身具有一定的隨機性，因此通過對多次運算(10次)的結(jié)果進行統(tǒng)計，比較基于貪婪策略的遺傳算法和一般遺傳算法在算法收斂精度和收斂速度上的性能，結(jié)果如表2和圖5所示，基于貪婪策略的遺傳算法典型的規(guī)劃結(jié)果如圖6所示。

表 2 計算結(jié)果

算法 最小值最大值平均值找到最大值的平均次數(shù)收斂時的平均迭代次數(shù)平均時間/sGreedy-GA1 3042 2422 206.574010224.156 3GA7712 2422 032.462525275.868 8

由表2可知，基于貪婪策略的遺傳算法求解的任務(wù)規(guī)劃方案與一般遺傳算法求解的方案的收益值相同，說明基于貪婪策略的遺傳算法能保證遺傳算法原有的求解精度，同時，基于貪婪策略的遺傳算法達到收斂狀態(tài)的平均迭代次數(shù)為10，計算耗時224.156 3 s，而一般遺傳算法達到收斂狀態(tài)的平均迭代次數(shù)為25，計算耗時275.868 8 s，說明貪婪策略能有效提高遺傳算法的收斂速度，減少計算時間。

(a)基于貪婪策略的遺傳算法

(b)一般遺傳算法圖5 10次計算進化曲線

圖6 Greedy-GA的典型觀測任務(wù)規(guī)劃結(jié)果

5 結(jié)束語

針對一類觀測任務(wù)具有優(yōu)先級約束的多資源觀測任務(wù)優(yōu)化問題，建立了觀測任務(wù)模型和觀測任務(wù)規(guī)劃模型，通過對各類復(fù)雜約束的深入分析和數(shù)學(xué)建模，設(shè)計了一種基于貪婪策略的遺傳算法。仿真算例結(jié)果表明，該方法求解此類問題是合理且有效的，并且能在保證算法原有精度的前提下提高算法的收斂速度。

當(dāng)然，目前對于如何更好地將貪婪策略與遺傳算法有機結(jié)合方面的研究尚不充分，本文的研究也只是在提高算法求解速度方面取得了成果，今后的研究重點將放在如何將貪婪策略應(yīng)用到遺傳算法的選擇、交叉與變異的過程中，以進一步提高算法的尋優(yōu)能力和尋優(yōu)速度。