基于貪婪策略的遺傳算法求解多星觀測任務優(yōu)化

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

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

0 引言

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

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

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

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

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

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

tasknq

{

Datanq；xnq

}

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

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

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

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

同時做出如下假設：

① 各觀測任務之間具有獨立性；

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

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

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

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

(1)

(2)

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

2 約束條件分析

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

2.1 觀測時間窗口約束

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

圖1 觀測任務時間窗口約束示意

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

(3)

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

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

(4)

2.3 觀測過渡時間約束

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

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

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

(5)

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

(6)

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

(7)

2.4 光照及能量平衡約束

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

tCs，tCe∈[Tg，Td] ，

(8)

Ed≤min{Ec，0.2*EB}，

(9)

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

2.5 存儲資源約束

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

?tasknq∈TASK，Datanq≤Datafree。

(10)

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

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

3.1 編碼

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

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

3.2 適應值函數(shù)

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

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

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

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

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

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

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

3.4 遺傳算子設計

3.4.1 復制選擇算子

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

3.4.2 交叉算子

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

Mcross=Pcross*M。

(11)

3.4.3 變異算子

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

Mmuta=Pmuta*M。

(12)

3.5 種群更新

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

3.6 算法實現(xiàn)

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

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

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

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

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

⑤ 算法結束，獲得最佳個體，輸出相應的觀測任務方案。

算法流程如圖4所示。

圖4 算法流程

4 算例及分析

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

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

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

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

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

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

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

衛(wèi)星ID目標ID開始時間/s結束時間/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ù)設置為：種群規(guī)模swarmNum=30，最大遺傳代數(shù)MaxRun=50，交叉概率Pcross=1，變異概率Pmuta=0.1，貪婪概率Pgreedy=0.7。由于遺傳算法本身具有一定的隨機性，因此通過對多次運算(10次)的結果進行統(tǒng)計，比較基于貪婪策略的遺傳算法和一般遺傳算法在算法收斂精度和收斂速度上的性能，結果如表2和圖5所示，基于貪婪策略的遺傳算法典型的規(guī)劃結果如圖6所示。

表 2 計算結果

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

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

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

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

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

5 結束語

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

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