應(yīng)用改進多種群遺傳算法的多星成像目標規(guī)劃方法

張曼利 章文毅 馬廣彬 樊慧晶

(1 中國科學(xué)院空天信息創(chuàng)新研究院，北京 100094)(2 中國科學(xué)院大學(xué)，北京 100049)

隨著近年來衛(wèi)星遙感應(yīng)用到各個領(lǐng)域[1-2]，人們對遙感影像數(shù)據(jù)的需求急劇增長。在衛(wèi)星資源相對有限的條件下，研究如何充分利用現(xiàn)有衛(wèi)星資源，給衛(wèi)星合理安排成像目標序列，對多顆衛(wèi)星協(xié)同規(guī)劃，充分利用每顆衛(wèi)星的觀測能力，對遙感應(yīng)用具有重要的作用。多星成像規(guī)劃問題是研究對于點目標或者區(qū)域目標來說，在一定的成像時間周期內(nèi)如何統(tǒng)籌多顆衛(wèi)星對目標區(qū)域進行觀測。對每顆衛(wèi)星來說，如果在指定的時間周期內(nèi)能飛過該目標區(qū)域，會對該目標區(qū)域產(chǎn)生一個或多個成像條帶(衛(wèi)星上帶有多個遙感器)，對于多星觀測區(qū)域會產(chǎn)生一個更大的條帶集合，在多星觀測的條帶集合中如何規(guī)劃出一個較優(yōu)的組合方案，就是多星成像規(guī)劃需要解決的問題。

目前，在衛(wèi)星成像目標規(guī)劃問題的模型和求解算法上已經(jīng)取得一定成果。求解模型有背包模型[3]，以最大化時間覆蓋率和最大化空間覆蓋率建立時間分辨率優(yōu)先、空間分辨率優(yōu)先兩種模型[4]，約束滿足問題模型[5-6]，以及將最大化成像目標數(shù)量和目標優(yōu)先級作為優(yōu)化目標建立的任務(wù)組合優(yōu)化模型[7]。求解算法有禁忌搜索算法[3,5，8]、貪婪算法[4]、遺傳算法[4-5]、模擬退火算法[5]、基于基因表達式的改進遺傳算法[6]和超啟發(fā)式算法[7]。這些算法大都是智能優(yōu)化算法[9]，容易陷入局部最優(yōu)解，且對于大區(qū)域目標及時間周期較長的情況不能盡快規(guī)劃出較優(yōu)的成像方案。同時，對于文獻[4-5]中使用的遺傳算法，當成像目標區(qū)域較小時，解空間的規(guī)模較小，遺傳算法比較適用；但是對大區(qū)域目標成像時，在解空間規(guī)模較大的情況下，遺傳算法不能有效地規(guī)劃出較優(yōu)的成像方案。

為了有效解決上述問題，本文提出改進多種群遺傳算法的多星成像目標規(guī)劃方法。根據(jù)目標函數(shù)和約束規(guī)則建立模型，利用改進的多種群遺傳算法對模型進行求解，采用移民算子種群在多種群之間關(guān)聯(lián)及更新種群；移民算子種群保留每一次進化中所有種群中的部分最優(yōu)成像方案，然后和每次進化中所有種群進行對比置換，保留每代進化中的最優(yōu)成像方案，防止算法每次進化過程中最優(yōu)成像方案丟失，從而針對多星區(qū)域目標能夠有效地規(guī)劃出目標函數(shù)較優(yōu)的成像方案。

1 模型設(shè)計

對于多目標來說，考慮衛(wèi)星的側(cè)擺能力，衛(wèi)星只有飛臨目標上空時才有可能對目標進行成像。對于2個目標，如果成像時間窗口發(fā)生重疊，因為1個時間窗口只能觀測1個目標，所以只能選擇1個目標成像。如圖1所示，對于觀測目標1，2，3，4來說，因為目標1和目標2、目標3和目標4成像時間窗口重疊，所以只能選擇其中的2個目標進行成像，例如目標1和目標3。

圖1 目標成像時間窗口Fig.1 Target imaging time windows

對于點目標來說，衛(wèi)星一次過境就可滿足成像，但是對于區(qū)域目標來說，單星的幅寬和分辨率很難在短時間周期內(nèi)完成對區(qū)域目標的成像覆蓋，而采用多星聯(lián)合對區(qū)域目標進行成像，則可以很好地滿足短時間周期內(nèi)對區(qū)域目標進行成像覆蓋的要求。文獻[4]模型約束條件中沒有考慮成像目標重復(fù)觀測的情況，文獻[5-6]模型約束條件中沒有考慮衛(wèi)星遙感器最大開機時長和開機次數(shù)限制約束條件，文獻[10]中對點目標進行研究，并沒有對區(qū)域目標進行分析。對于單個區(qū)域目標來說，如果衛(wèi)星的拍攝幅寬無法覆蓋觀測區(qū)域，就需要首先對區(qū)域進行劃分，分解成多個成像條帶，每個成像條帶相當于點目標，相當于對多個點目標進行成像規(guī)劃。對目標成像觀測來說，如果使用不同的衛(wèi)星，相同的分辨率，可能會出現(xiàn)對該目標中的條帶重復(fù)觀測，為了避免這種情況，設(shè)定每個條帶至多被成像1次，且必須在某顆衛(wèi)星的可見時間窗口內(nèi)成像。考慮軌道覆蓋會出現(xiàn)重復(fù)觀測，為了盡可能地均分軌道，設(shè)定單個軌道只能開機1次，即對于成像目標劃分的條帶來說，不同的條帶對應(yīng)的成像衛(wèi)星軌道不能相同?？紤]衛(wèi)星姿態(tài)轉(zhuǎn)換需要時間，設(shè)定姿態(tài)轉(zhuǎn)換時長限制。根據(jù)實際應(yīng)用中的衛(wèi)星測控規(guī)劃需求，考慮到衛(wèi)星能量和衛(wèi)星存儲容量的限制，采用衛(wèi)星遙感器最大開機時長和開機次數(shù)約束設(shè)計規(guī)則，使模型更具有實際應(yīng)用價值。本文針對單個區(qū)域目標的多星成像規(guī)劃問題進行研究，對于單個目標區(qū)域來說，衛(wèi)星遙感器開機時長比較短，開機次數(shù)也比較少，可以滿足最大開機時長和開機次數(shù)約束。

為了便于模型的建立及求解[10]，本文將成像條帶作為模型的數(shù)據(jù)輸入。它包含衛(wèi)星標志、軌道號、遙感器型號、成像范圍、成像模式、成像時間和側(cè)擺角等重要信息。在研究區(qū)域目標多星成像時，需要進行衛(wèi)星軌道的計算。本文衛(wèi)星星下點的位置和速度使用簡化常規(guī)攝動(SGP4)模型和衛(wèi)星的兩行軌道根數(shù)(TLE)計算。根據(jù)目標區(qū)域，通過衛(wèi)星軌道計算結(jié)合衛(wèi)星側(cè)擺角能力計算出所有可能的成像條帶。成像方案由條帶組成，在選取條帶組成成像方案時，需要考慮一定的約束條件。

問題優(yōu)化目標如式(1)～(3)所示。式(1)表示成像規(guī)劃方案周期最短；式(2)表示成像規(guī)劃方案覆蓋率最大；式(3)表示把成像規(guī)劃方案周期和覆蓋率采用加權(quán)和計算成像規(guī)劃方案綜合收益?？紤]到實際應(yīng)用中的用戶需求往往是近期盡快安排觀測，目標區(qū)域要盡快地滿足覆蓋?？紤]時間成本較低和任務(wù)完成率較高的情況，設(shè)置在時間周期較短、規(guī)劃方案覆蓋率較大情況下的合理規(guī)劃方案，即成像規(guī)劃方案中衛(wèi)星拍攝的周期最短，對觀測區(qū)域1次拍攝的覆蓋最大，這樣成像規(guī)劃方案綜合收益最佳。式(1)中成像規(guī)劃方案周期最短目標函數(shù)要保證周期最短，同時要考慮該方案的覆蓋率大小因素，如果只考慮周期最短為收益指標，可能會出現(xiàn)該成像規(guī)劃方案的覆蓋率非常低，因此采用方案覆蓋率作為一個權(quán)值來平衡成像周期最短目標函數(shù)的收益函數(shù)。

問題約束規(guī)如式(4)～(9)所示。式(4)表示當衛(wèi)星飛臨目標的時間段內(nèi)都可以對目標成像，為了避免不同的衛(wèi)星對該條帶重復(fù)觀測，限定每個觀測條帶至多被成像1次，即條帶i至多有1個成像時間窗口。式(5)表示觀測條帶如果被成像，任意條帶的成像時間區(qū)間必須在某顆衛(wèi)星的可見時間窗口內(nèi)。式(6)表示不同的條帶對應(yīng)的成像衛(wèi)星軌道不能相同。式(7)表示對于不同的觀測條帶來說，衛(wèi)星遙感器成像需要轉(zhuǎn)換姿態(tài)角，即2個相鄰條帶的成像時間間隔需要大于姿態(tài)轉(zhuǎn)換時長,成像規(guī)劃方案里所有條帶按照成像時間窗口的開始時間排序，參考圖1，對于相鄰條帶來說，成像時間窗口不能重疊，因此1個時間窗口只能觀測1個條帶。式(8)表示遙感器開機的持續(xù)總時間要小于最大開機時長。式(9)表示遙感器開機次數(shù)要小于最大開機次數(shù)。

(1)

(2)

(3)

yijr≤1

(4)

(5)

Oi≠Ok

(6)

fi+ti,i+1

(7)

(8)

npt

(9)

模型中式(1)～(9)的符號釋義如下。條帶序號i=1,2,3,…,nb，nb為條帶總數(shù)；Ci為成像條帶Bi的覆蓋率，其中，Bi為成像規(guī)劃方案里的所有條帶集合B(所有條帶按照成像時間窗口的開始時間排序)里面的任意條帶；Tstart和Tend分別為成像規(guī)劃輸入的起始時間和結(jié)束時間，Ttstart和Ttend分別為成像規(guī)劃方案的實際起始時間和實際結(jié)束時間；v1和v2分別為成像周期和成像區(qū)域覆蓋率對應(yīng)的權(quán)值；成像條帶Bi在衛(wèi)星Sj的第r個時間窗口成像時，yijr取值為1，否則為0，其中，Sj為衛(wèi)星集合S里面的任意衛(wèi)星，衛(wèi)星序號j=1,2,3,…,ns，ns為衛(wèi)星總數(shù)，成像窗口序號r=1,2,3,…,nij，nij為衛(wèi)星Sj對成像條帶Bi的可行成像時間窗口總數(shù)；bi和fi分別為條帶Bi的實際成像開始時間和實際成像結(jié)束時間；wijr,s和wijr,e分別為條帶Bi在衛(wèi)星Sj的第r個時間窗口的開始時間和結(jié)束時間；Oi為條帶Bi對應(yīng)的軌道號，Ok為條帶Bk對應(yīng)的軌道號，其中，i≠k，k=1,2,3,…,nb；ti,i+1為條帶Bi到后續(xù)條帶Bi+1的姿態(tài)轉(zhuǎn)換時長；bi+1為條帶Bi+1的實際開始成像時間；tm,ps和tm,pe分別為遙感器第m次開機時間和關(guān)機時間，其中，m=1,2,3,…,npt，npt為遙感器開機總數(shù)；lpt為遙感器最大開機時間；NPT為遙感器最大開機次數(shù)。

2 改進的多種群遺傳算法求解過程

2.1 算法框架

改進的多種群遺傳算法源于遺傳算法，設(shè)置生成多種群協(xié)同進化，每個種群隨機生成不同的交叉概率和變異概率，提高對觀測目標最優(yōu)成像方案的搜索能力，避免算法的進化過程較早收斂。同時，加入移民算子種群在多種群之間進行關(guān)聯(lián)及更新種群，移民算子種群保留每次進化中所有種群中的部分最優(yōu)成像方案，然后和每次進化中所有種群進行對比置換，保留每代進化中的最優(yōu)成像方案。利用精華種群中適應(yīng)度最大的成像方案的最少保持代數(shù)作為終止判據(jù)，比遺傳算法中設(shè)定1個最大進化代數(shù)作為終止判據(jù)更加有效，使收斂速度得到提高。

2.2 算法調(diào)度流程

改進的多種群遺傳算法中種群的個體代表每個成像方案，個體的適應(yīng)度函數(shù)代表模型中的目標函數(shù)，種群是由若干個個體組成，個體中的基因代表相對應(yīng)的過境軌道產(chǎn)生的條帶集中被選中的條帶。每個過境軌道集包含多個過境軌道，且過境軌道相互沖突，所以選擇其一參與成像。采用二進制編碼方式，1位二進制編碼代表1個成像條帶，編碼為0時表示該條帶沒有被選中，編碼為1時表示選擇該條帶加入成像方案，成像方案由1個二進制串組成。算法詳細設(shè)計求解流程見圖2。

圖2 算法流程Fig.2 Algorithm flow

(1)每次隨機生成的成像方案需要判斷方案中的所有條帶是否滿足約束規(guī)則式(4)～(9)，滿足所有的約束規(guī)則后該方案才會被保留下來。

(2)初始化移民算子種群，即從n個種群中選擇適應(yīng)度最大的成像方案復(fù)制到初始移民算子種群中。

(3) 對n個種群隨機產(chǎn)生交叉概率(Pc)和變異概率(Pm)。不同的Pc和Pm值對算法的搜索能力不同。

(4)采用輪盤賭選擇個體。2個個體進行交叉時，被選中交換的二進制編碼位代表1個條帶，交換時不僅要把二進制編碼段進行交換，還要把二進制碼代表的條帶信息進行交換。

(5)移民算子種群在多種群之間進行關(guān)聯(lián)及更新種群，n個種群經(jīng)過選擇、交叉、變異后，把迭代過程中的每個種群Ax(x=1,2,3,…,n)和移民算子種群B比較成像方案的適應(yīng)度值。若發(fā)現(xiàn)種群Ax中最優(yōu)成像方案優(yōu)于移民算子種群B中的最優(yōu)成像方案，則把種群Ax中所有優(yōu)于移民算子種群B中最優(yōu)成像方案的成像方案加入到移民算子種群B中；否則，把移民算子種群B中所有優(yōu)于種群Ax中的成像方案置換掉種群Ax中的最差成像方案。該過程可以保證每次產(chǎn)生的較優(yōu)染色體被保留下來[6]，保證多種群共同進化。

(6)通過人工選擇算子模塊保存每個種群中適應(yīng)度最大的成像方案及編碼，放到精華種群中。

(7)最后判斷精華種群中適應(yīng)度最大成像方案的保持代數(shù)是否滿足收斂條件，如果滿足收斂條件，則輸出精華種群中適應(yīng)度最大的成像方案，否則，轉(zhuǎn)到(4)。

3 試驗驗證與分析

本文使用NetBeans軟件及Java語言編程實現(xiàn)衛(wèi)星成像任務(wù)規(guī)劃方法。改進的多種群遺傳算法設(shè)置3個種群進行尋優(yōu)求解，在[0.7,0.9]內(nèi)隨機產(chǎn)生Pc，在[0.001,0.300]內(nèi)隨機產(chǎn)生Pm。

為驗證改進的多種群遺傳算法進化過程的收斂效率，分別對遺傳算法和改進的多種群遺傳算法進行進化過程對比試驗，對同一個目標區(qū)域分別進行5次試驗，選擇成像規(guī)劃方案覆蓋率最大目標函數(shù)收益值作為對比標準。目標函數(shù)收益值范圍區(qū)間是[0,1]，最大收益值為1，試驗設(shè)置GA進化500代，設(shè)置MPGA進化50代，試驗對比結(jié)果如圖3和圖4所示。

由圖3遺傳算法的5次進化過程試驗可以看出：5次試驗的平均收益值都不相同，進化過程不穩(wěn)定，且第1次試驗和第5次試驗進化500代后仍然沒有穩(wěn)定下來，收斂速度比較慢，第2～4次試驗雖然在200代附近收斂，但是收斂值并不理想，導(dǎo)致過早的收斂。觀察5次試驗進化過程曲線可以看出：遺傳算法得出的收益值并不是逐漸增長的曲線，這是因為遺傳算法在進化過程中沒有保留每代進化中的最優(yōu)成像方案，容易丟失最優(yōu)解。由圖4改進的多種群遺傳算法的5次試驗結(jié)果可以看出：進化過程比較穩(wěn)定，平均在20代以內(nèi)收斂，并且5次收斂時的收益值都比較理想，5次試驗曲線呈現(xiàn)穩(wěn)定上升，這是因為移民算子種群模塊保留了每代進化中的最優(yōu)成像方案，子代種群進化是在父代種群的最優(yōu)值基礎(chǔ)上繼續(xù)尋優(yōu)，所以最終收斂值比較理想?？梢?，綜合比較分析，改進的多種群遺傳算法比遺傳算法收斂進程快，且收斂值更優(yōu)。

圖3 遺傳算法進化過程試驗Fig.3 Genetic algorithm evolution process test

圖4 改進的多種群遺傳算法進化過程試驗Fig.4 Improved multi-population genetic algorithm evolution process test

為驗證改進的多種群遺傳算法求解模型中成像規(guī)劃方案周期最短、覆蓋率最大目標函數(shù)的性能，與遺傳算法[5]作對比分析。選取5個目標區(qū)域,成像衛(wèi)星為昴宿星-1a，1b(Pleiades-1a,1b),成像時間在2020-04-01T00:00:00-2020-04-15T00:00:00?？紤]到遺傳算法的不穩(wěn)定性，改進的多種群遺傳算法和遺傳算法均對每個區(qū)域做10次試驗，最后取平均值作為收益結(jié)果進行對比。選擇成像規(guī)劃方案覆蓋率最大和成像方案周期最短2個目標函數(shù)收益值作為對比標準，為了更直觀地對比不同目標區(qū)域調(diào)用2種算法得出的成像方案的覆蓋率和成像周期目標函數(shù)，分別將結(jié)果整理為圖5和圖6。

圖5 成像方案覆蓋率收益對比Fig.5 Benefit comparison of imaging scheme coverage

圖6 成像方案周期收益對比Fig.6 Benefit comparison of imaging scheme time period

從圖5和圖6可以看出：改進的多種群遺傳算法在成像規(guī)劃方案覆蓋率和成像周期目標函數(shù)上都優(yōu)于遺傳算法。在改進的多種群遺傳算法的迭代計算過程中，因為設(shè)置生成多種群進行進化，每個種群隨機生成不同的交叉概率和變異概率，每次進化過程中的所有種群和移民算子種群進行置換更新，在保留較優(yōu)成像方案編碼方案時，多個種群協(xié)同進化尋優(yōu)；遺傳算法則容易出現(xiàn)過早的收斂，收斂結(jié)果并不理想(參見圖3和圖4)，因此，改進的多種群遺傳算法得出的規(guī)劃方案結(jié)果優(yōu)于遺傳算法。本文多星成像目標規(guī)劃方法能夠較好地適應(yīng)對模型的求解，在有效的成像時間內(nèi)規(guī)劃出比較理想的成像方案，適用于多星成像目標規(guī)劃問題。

4 結(jié)束語

衛(wèi)星成像規(guī)劃問題的研究對于遙感應(yīng)急應(yīng)用等方面具有重要意義。本文面向區(qū)域目標進行求解，以目標成像時間周期最小和目標成像覆蓋率最大為目標函數(shù)建立模型，加入移民算子種群，保證各個種群之間進行對比關(guān)聯(lián)及協(xié)同尋優(yōu)，以保留較優(yōu)的成像方案。試驗結(jié)果表明，改進的多種群遺傳算法求解精度優(yōu)于遺傳算法，穩(wěn)定性較佳，能較好地解決衛(wèi)星成像任務(wù)規(guī)劃問題。后續(xù)會進一步改進算法的性能，更加全面地考慮衛(wèi)星實際約束情況，以及對于緊急任務(wù)的插入處理規(guī)則；同時，針對具備俯仰角姿態(tài)機動能力的衛(wèi)星，研究在具有更加靈活的觀測角情況下如何更好地協(xié)同多顆衛(wèi)星進行規(guī)劃成像。