應用改進多種群遺傳算法的多星成像目標規劃方法

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

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

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

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

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

1 模型設計

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

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

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

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

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

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

(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為條帶總數；Ci為成像條帶Bi的覆蓋率，其中，Bi為成像規劃方案里的所有條帶集合B(所有條帶按照成像時間窗口的開始時間排序)里面的任意條帶；Tstart和Tend分別為成像規劃輸入的起始時間和結束時間，Ttstart和Ttend分別為成像規劃方案的實際起始時間和實際結束時間；v1和v2分別為成像周期和成像區域覆蓋率對應的權值；成像條帶Bi在衛星Sj的第r個時間窗口成像時，yijr取值為1，否則為0，其中，Sj為衛星集合S里面的任意衛星，衛星序號j=1,2,3,…,ns，ns為衛星總數，成像窗口序號r=1,2,3,…,nij，nij為衛星Sj對成像條帶Bi的可行成像時間窗口總數；bi和fi分別為條帶Bi的實際成像開始時間和實際成像結束時間；wijr,s和wijr,e分別為條帶Bi在衛星Sj的第r個時間窗口的開始時間和結束時間；Oi為條帶Bi對應的軌道號，Ok為條帶Bk對應的軌道號，其中，i≠k，k=1,2,3,…,nb；ti,i+1為條帶Bi到后續條帶Bi+1的姿態轉換時長；bi+1為條帶Bi+1的實際開始成像時間；tm,ps和tm,pe分別為遙感器第m次開機時間和關機時間，其中，m=1,2,3,…,npt，npt為遙感器開機總數；lpt為遙感器最大開機時間；NPT為遙感器最大開機次數。

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

2.1 算法框架

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

2.2 算法調度流程

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

圖2 算法流程Fig.2 Algorithm flow

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

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

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

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

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

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

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

3 試驗驗證與分析

本文使用NetBeans軟件及Java語言編程實現衛星成像任務規劃方法。改進的多種群遺傳算法設置3個種群進行尋優求解，在[0.7,0.9]內隨機產生Pc，在[0.001,0.300]內隨機產生Pm。

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

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

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

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

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

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

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

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

4 結束語

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