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

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

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

0 引言

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

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

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

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

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

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

tasknq

{

Datanq；xnq

}

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

信息實(shí)時(shí)獲取條件下的多星觀測任務(wù)規(guī)劃(Multi-Satellite Observation Task Planning，MuSOTP)，就是假設(shè)在給定規(guī)劃時(shí)段內(nèi)的任務(wù)與觀測資源不變且星際鏈路穩(wěn)定的條件下，多顆能力異構(gòu)的對(duì)地觀測衛(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í)做出如下假設(shè)：

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

② 每個(gè)目標(biāo)至多只能被觀測一次；

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

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

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

(1)

(2)

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

2 約束條件分析

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

2.1 觀測時(shí)間窗口約束

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

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

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

(3)

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

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

(4)

2.3 觀測過渡時(shí)間約束

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

圖2 觀測過渡時(shí)間約束示意

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

(5)

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

(6)

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

(7)

2.4 光照及能量平衡約束

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

tCs，tCe∈[Tg，Td] ，

(8)

Ed≤min{Ec，0.2*EB}，

(9)

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

2.5 存儲(chǔ)資源約束

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

?tasknq∈TASK，Datanq≤Datafree。

(10)

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

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

3.1 編碼

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

圖3 遺傳算法二進(jìn)制編碼方式

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

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

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

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

① 將染色體按觀測目標(biāo)編號(hào)重新排序；

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

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

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

3.4 遺傳算子設(shè)計(jì)

3.4.1 復(fù)制選擇算子

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

3.4.2 交叉算子

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

Mcross=Pcross*M。

(11)

3.4.3 變異算子

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

Mmuta=Pmuta*M。

(12)

3.5 種群更新

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

3.6 算法實(shí)現(xiàn)

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

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

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

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

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

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

算法流程如圖4所示。

圖4 算法流程

4 算例及分析

為了驗(yàn)證基于貪婪策略的遺傳算法能在保證算法精度的前提下有效提高算法的收斂速度，采用模擬數(shù)據(jù)建立仿真算例，所有算法和程序用MATLABR2014a編程軟件實(shí)現(xiàn)。對(duì)于目標(biāo)、衛(wèi)星的模型建立，時(shí)間窗口和衛(wèi)星光照地影時(shí)段的預(yù)處理都通過STK9.2仿真軟件實(shí)現(xiàn)，運(yù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來共同完成目標(biāo)觀測任務(wù)，其軌道建立參考了Orbview、Landsat、資源三號(hào)、風(fēng)云一號(hào)和天繪一號(hào)等衛(wèi)星的軌道參數(shù)；

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

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

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

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

衛(wèi)星ID目標(biāo)ID開始時(shí)間/s結(jié)束時(shí)間/s持續(xù)時(shí)間/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。由于遺傳算法本身具有一定的隨機(jī)性，因此通過對(duì)多次運(yùn)算(10次)的結(jié)果進(jìn)行統(tǒng)計(jì)，比較基于貪婪策略的遺傳算法和一般遺傳算法在算法收斂精度和收斂速度上的性能，結(jié)果如表2和圖5所示，基于貪婪策略的遺傳算法典型的規(guī)劃結(jié)果如圖6所示。

表 2 計(jì)算結(jié)果

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

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

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

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

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

5 結(jié)束語

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

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