基于遺傳禁忌算法的多星協同任務規劃方法

張澤華，張加友，張嘉凱，馬松靖，李宇哲

(哈爾濱工程大學 航天與建筑工程學院，黑龍江 哈爾濱 150001)

0 引言

對地觀測衛星利用星載傳感器觀測地面目標以獲取關鍵信息，在大地測繪和自然災害檢測等多種應用場景中具有關鍵作用。隨著對地觀測應用的不斷深入，任務需求量急劇攀升，同時多頻次、多模式、多傳感器等復雜觀測需求也逐漸增多，很多情況下單一衛星無法完成這些復雜的觀測需求。在此背景下，多星協同對地觀測成為當前對地觀測的主要方式[1-2]。

多星協同任務規劃問題是一個多維多選的組合優化問題，目前主要采用智能優化算法解決此類問題。文獻[3-5]基于蟻群算法對多星成像調度問題開展了研究，提出了一系列改進蟻群算法。文獻[6]基于遺傳算法引入向量編碼，研究了新的交叉和變異算子、新的計算適應度方法以及保持最優個體的新方法。文獻[7]設計了一種基于圈次進行交叉和變異的遺傳算法，并與蟻群算法進行仿真比對，驗證了其有效性。文獻[8]利用蒙特卡洛法和雙重停機條件對遺傳算法進行了改進，提出了一種改進型自適應遺傳算法，并通過實驗表明了該算法在全局搜索能力和算法收斂速度方面的提高。文獻[9]研究了雙遺傳算法與模擬退火算法、雙蟻群算法與禁忌搜索算法2類求解方法，并通過實驗數據證明了算法的有效性和適用性。文獻[10]基于遺傳算法設計了新的編碼方式，開發了一種新型遺傳算法進行求解對地觀測衛星的調度問題。文獻[11-12]提出了一種將高斯偽譜法與遺傳算法相結合的混合方法，通過遺傳算法生成規劃調度的可行解，再用高斯偽譜法優化能量和時間。該混合方法在能量效率、計算效率和姿軌平滑方面具有優越性。

本文在上述研究基礎上,提出了一種基于遺傳禁忌算法的多星協同任務規劃方法，該方法分為2個階段：第1階段為遺傳搜索階段，第2階段為禁忌搜索階段，兼具了遺傳算法較強的全局尋優能力和禁忌搜索算法較強的局部尋優能力。同時，通過仿真驗證了算法的穩定性和有效性。

1 多星協同任務規劃問題模型

多星協同任務規劃問題可概述為在指定場景時間內，根據用戶提出的需求任務集合和衛星資源信息，通過規劃調度給每個任務匹配滿足約束的衛星觀測時段，并保證衛星成像窗口不沖突。

由于一個任務可以被多顆衛星可見，且一顆衛星對一個任務的可見窗可能存在多個，即存在可見窗集合。假設衛星有n顆，任務有m個，那么可見窗個數為m×n，多星多任務可見窗集合如表1所示，衛星n對任務m的可見窗集合為Wmn。

多星協同任務規劃問題就是基于表1中的多星多任務可見窗集合，通過任務規劃得到合理的衛星觀測方案。

表1 多星多任務可見窗集合Tab.1 Visible window collection for multiple multi-satellite missions

1.1 基本假設

多星協同任務規劃問題涉及到的對象之間的關系復雜，并不能顧及到所有的具體細節和實際約束問題。在充分考慮到現實應用情況的基礎上，本文對實際問題做出了如下的基本假設和簡化：

① 假設觀測目標都是預處理后的固定點目標；

② 假設衛星存儲器的容量無限制；

③ 一般情況下，衛星能量約束用側擺次數和總開機時間等標準來描述，本文采用最大觀測任務數來描述；

④ 衛星姿態調整及穩定時間按照常數處理；

⑤ 假設每個任務只被觀測一次，且每個任務的觀測時長相同。

1.2 數學模型

多星協同任務規劃問題的數學模型如下：

f=α×maxf1+β×maxf2+γ×maxf3，

(1)

(2)

(3)

(4)

(5)

SEj≤SMaxEj，?j∈S，

(6)

STij,ETij∈Wij,?i∈T,?j∈S，

(7)

(8)

|CBij|≤SMaxCBj,?i∈T,?j∈S，

(9)

(10)

式(1)為優化目標函數，是由3個子目標加權建立。其中，α,β,γ分別為3個子目標的權重，且滿足0<α<1,0<β<1,0<γ<1,0<α+β+γ<1。3個權重值可以根據具體任務需求自定義，在本文中，取α=0.7，β=0.2，γ=0.1。式(2)為子目標1，表示觀測任務集合的總收益值最大；式(3)為子目標2，表示觀測任務集合的總完成度最大；式(4)為子目標3，表示衛星集合的側擺角之和最小，其中g(CBij)為側擺角歸一化函數，假設每顆衛星的最大成像側擺角均為60°，則可設g(CBij)=2cos(CBij)-1。

式(5)表示每個任務最多被觀測一次；式(6)表示衛星觀測任務數應小于最大觀測任務數，即本文中描述的能量約束；式(7)表示衛星觀測任務的觀測時段應在可見窗內；式(8)表示衛星觀測任務集合中相鄰觀測任務之間應滿足過渡時間約束；式(9)表示衛星進行任務觀測時應滿足衛星最大成像側擺角約束；式(10)主要針對光學衛星，光學衛星觀測任務時應滿足太陽高度角約束。

2 遺傳禁忌算法

2.1 基本思想

遺傳算法[13-14]是于1975年基于進化生物學提出的，主要由初始化種群、遺傳算子和適應度函數組成，遺傳算子中包括交叉、變異和選擇等。遺傳算法具備較強的全局擇優能力，但容易過早收斂。禁忌搜索算法[15-16]于1986年基于局部鄰域搜索提出，主要由鄰域結構、禁忌表和藐視準則等組成。禁忌搜索算法具有較好的局部搜索能力，但初始解的質量對其影響較大。

多星協同任務規劃問題中任務成像觀測時間解集搜索空間很大，本文綜合遺傳算法和禁忌搜索算法的優勢，分2個階段進行問題求解。第1階段，利用遺傳算法搜索效率較高的特點，采用遺傳算法進行問題的初步求解；第2階段，發揮禁忌搜索算法較強的局部搜索能力，并考慮初始解對禁忌搜索的影響，以遺傳算法的優化結果為初始解，利用禁忌搜索算法對規劃問題進行再次求解，從而得到更優的結果。

2.2 編碼與個體可行性處理

2.2.1 編碼

依據表1，將可見窗集合用一個矩陣M來表示，即：

(11)

基于式(11)中的矩陣，創建每個任務目標所對應的可見窗有序集合：M1,M2,…,MN,其中Mi=W1i∪W2i∪…∪Wni。給每顆衛星進行編號排序，每顆衛星的可見窗按照可見開始時間排序，在整個計算過程中順序固定不變。由此，可以令個體染色體的維度為二維，第一維表示觀測任務的衛星，第二維表示該衛星觀測任務的觀測開始時間，并且分別用衛星序號和觀測開始時間位置序號進行表示。由于衛星觀測任務的可見窗可能由多個不連續的可見弧段組成，所以需要將可見窗連續化進而得到衛星觀測任務的觀測開始時間位置序號，如圖1所示。

圖1 可見窗連續化示意Fig.1 Visible window continuity

假設衛星對目標的可見窗有3個，第1個開始時間為0，結束時間為2，可見時長為2；第2個開始時間為5，結束時間為10，可見時長為5；第3個開始時間為15，結束時間為18，可見時長為3。根據可見時長的比例進行連續化，若觀測開始時間位置為4，則對應第2個窗口的時間位置為7。

根據上面的描述，通過編碼產生的染色體可以表示為：

D={(x1,y1),(x2,y2),…,(xm,ym)}，

(12)

式中，xi= 0,1,2,…,n表示對任務Ti進行觀測的衛星序號；yi=0,1,2,…,l表示該衛星觀測任務Ti的觀測開始時間位置序號。根據前述假設可知，每個任務最多被觀測一次，所以若xi取值為0，就表示該任務不被觀測。

2.2.2 個體可行性處理

為保證個體滿足約束條件，需要對其進行可行性處理，該處理是針對個體中的每一個任務進行如下操作：

① 衛星能量約束判斷。判斷該任務所選觀測衛星是否滿足式(6)，若不滿足，則進行衛星序號突變，再重新判斷，直至挑選出滿足該約束的衛星。若所有可見衛星都不滿足該約束，則將該任務的觀測衛星序號置為0。

② 衛星相鄰任務時間窗口沖突判斷。判斷該任務的觀測時段是否滿足式(8)，若不滿足，則進行觀測開始時間位置序號突變，再重新判斷。可見窗長度遠大于成像時長，因此存在大量觀測開始時間位置序號突變結果，本文設定觀測開始時間位置序號突變次數上限，若其突變次數達到該上限仍未找到滿足約束的觀測時段，則進行衛星序號突變。若所有可見衛星的可見窗突變在達到突變次數上限時都未找到滿足約束的觀測時段，則將該任務的觀測衛星序號置為0。

③ 衛星側擺角約束判斷。判斷該任務所選觀測衛星是否滿足式(9)，若不滿足，則依照第②步中的先突變觀測開始時間位置序號后突變衛星序號的方法進行處理。

2.3 遺傳搜索階段

基于式(6)染色體結構，隨機初始化種群，并對種群中個體進行可行性處理。設定迭代次數，對種群進行遺傳迭代，每代種群的個體都需進行可行性處理，直至達到迭代次數，輸出最優個體，即為遺傳搜索階段優化結果。遺傳搜索階段流程如圖2所示，圖中符號Pm表示變異概率。

圖2 遺傳搜索階段流程Fig.2 Genetic search phases

2.3.1 交叉算子

將種群中的個體進行兩兩隨機配對形成父代和母代染色體，父代和母代染色體通過部分基因片段的交叉產生子代個體。染色體交叉示意圖如圖3所示，隨機選取2個整數index1和index2，并滿足0

圖3 染色體交叉示意Fig.3 Chromosomal crossover

2.3.2 變異算子

根據本文的編碼方式，變異算子包括衛星序號突變和觀測開始時間位置序號突變2種。

觀測開始時間位置序號突變示意圖如圖4所示，若個體染色體在index1和index2處發生觀測開始時間位置序號突變，則從連續化可見窗結果中隨機突變新的觀測開始時間位置序號。

圖4 觀測開始時間位置序號突變示意Fig.4 Observation start time position sequence number mutation

衛星序號突變示意圖如圖5所示，若個體染色體在index1和index2處發生衛星序號突變，首先判斷突變處基因是否還存在其他可見衛星，若存在，選擇新的可見衛星，同時選擇新的觀測開始時間位置序號，若不存在，將衛星序號置為0，即該任務不被觀測。

圖5 衛星序號突變示意Fig.5 Satellite number mutation

2.3.3 選擇算子

本文采用錦標賽方法與雙敗淘汰制的結合進行選擇。假設子代與父代個體形成的混合種群個體總數為N0，選擇后新一代種群個體數為N。將所有個體隨機分成10組，每組采用錦標賽方法將前N/10名判定獲勝進入勝者組，其余個體進入敗者組。敗者組中采用錦標賽方法將前N/2名判定復活進入復活組，其余個體判定最終失敗進行淘汰。勝者組中同樣采用錦標賽方法將前N/2名判定最終勝利進入勝利組，后N/2名進入復活組。最后，復活組的所有個體爭搶最后的N/2個名額，爭奪方式依舊是錦標賽方法，將前N/2名判定最終勝利進入勝利組。至此，選擇算子操作結束，勝利組即為新一代種群，具體操作流程如圖6所示。

圖6 選擇算子操作流程Fig.6 Selection operator workflow

2.4 禁忌搜索階段

禁忌搜索算法的初始解可以隨機產生，但其初始解的優劣對搜索的性能影響較大。因此，本文將遺傳搜索階段的優化結果作為初始解進行禁忌搜索。禁忌搜索階段流程如圖7所示。

圖7 禁忌搜索階段流程Fig.7 Tabu search phases

2.4.1 鄰域結構

鄰域結構是指由當前解通過鄰域函數產生另一個解的方式，通過鄰域函數產生的解會有多個，這些解構成當前解的鄰域解集。鄰域結構的設計方法有很多，并且針對不同的問題會有不同的鄰域結構設計方法。在本文中以遺傳算法中的染色體為初始解的結構，由此設計出一種類似于遺傳算法中變異算子的鄰域結構，如圖8所示。

圖8 鄰域結構示意Fig.8 Neighborhood structure

首先隨機選擇變異任務編號，其次選擇變異該任務的可見衛星編號，最后選擇變異該可見衛星的觀測開始時間位置序號。

試驗地設在建三江勝利農場科技園區；土壤情況為草甸白漿土；土壤養分含量：速氮：182m/kg，速磷：32.2mg/kg，速鉀：67mg/kg，有機質 35.5mg/kg，PH 值 5.4.

2.4.2 禁忌表

本文中鄰域結構設計時考慮了變異任務編號、變異任務的可見衛星編號、變異可見衛星的觀測開始時間位置序號，因此本文基于禁忌長度和上述3個變異序號進行設計禁忌表，禁忌表結構如下：

TabuL={(a1,b1,c1,d1),(a2,b2,c2,d2),…,(aL,bL,cL,dL)}，

(13)

式中，L表示禁忌表中存儲的禁忌解的個數；ai=1,2,3，…，T表示當前禁忌解的禁忌長度，T為初始禁忌長度；bi=1,2,…,m表示染色體上選擇變異的任務位置編號，m為任務個數，即染色體上的基因個數；ci=1,2,…,nvs表示所選定任務選擇變異后的衛星編號，nvs為任務的可見衛星個數；di=1,2,…,l表示所選定衛星選擇變異后的觀測開始時間位置編號。

2.4.3 藐視準則

當通過鄰域結構生成的候選解屬于禁忌表中的禁忌解時，需要進行藐視準則判斷。判斷準則如下：若該禁忌解優于當前最佳解則視為該禁忌解藐視禁忌準則，可以將其解禁，并將其更新為當前解和當前最佳解；否則該禁忌解無法藐視禁忌準則，無法解禁。

3 仿真驗證

3.1 仿真場景設置

本文仿真場景中仿真時長為1 d。設置了4顆衛星，4顆衛星除了軌道傾角不同外，其他參數一致，具體參數值如表2所示。設置了7種觀測任務群規模，任務群規模分別為100，150，200，250，300，350，400，不同規模任務群均為在全球范圍內隨機生成。

表2 衛星參數Tab.2 Satellite parameters

3.2 算法穩定性測試

針對規模為300的任務群，本文通過種群數分別為150，200，250的3種情況進行算法求解來對算法的穩定性進行測試，得到3種情況下種群最優個體適應度曲線，測試結果如圖9所示。

由圖9可以看出，種群數分別為150，200，300三種情況下，最優個體適應度收斂的迭代次數不同，隨著種群數增加，收斂的迭代次數增加，但均在50次迭代之內收斂。同時，在迭代過程中每次迭代的適應度值不同，但3種情況下最終收斂的適應度值相近。由此可以說明,不同種群數下，算法求解的種群最優個體適應度相近，驗證了算法的穩定性。

圖9 不同種群數適應度曲線Fig.9 The fitness curve of different population numbers

3.3 不同任務群規模仿真比對

本文對7種不同規模的任務群進行仿真測試，測試中種群數量為200，迭代次數為400，得到每一種規模下種群最優個體適應度曲線、最優個體總收益值曲線、最優個體總完成度曲線以及最優個體總側擺角曲線，仿真結果如圖10～圖13所示。

圖10 不同任務群規模適應度曲線Fig.10 The fitness curve of different task group scales

圖11 不同任務群規模總收益值曲線Fig.11 The total revenue value curve of different task group scales

圖12 不同任務群規模總完成度曲線Fig.12 The total completion degree curve of different task group scales

圖13 不同任務群規模總側擺角曲線Fig.13 The total roll angle curve of different task group scales

本文中數學模型的優化目標函數由總收益值、總完成度以及總側擺角值3個子目標組成，為了對上述適應度曲線的分析結果進行進一步驗證，對不同任務群規模的總收益值、總完成度以及總側擺角值進行分析。該仿真場景中衛星最大側擺角為60°，因此式(4)中側擺角歸一化函數設為g(CBij)=2cos(CBij)-1。

圖11、圖12和圖13分別為不同任務群規模總收益值曲線、總完成度曲線和總側擺角曲線。

由圖11和圖12可以看出，前3種任務群規模的總收益值和總完成度相近，且大于后4種任務群規模。因此，圖10中前3種任務群規模的最終收斂適應度值相近，且大于后4種任務群規模，與前面采用場景可完成任務數閾值分析的結果一致。由這3幅圖可以看出其曲線變化趨勢與圖10一致，7種任務群規模均在迭代150次后達到最優，且隨著任務群規模增大，總收益值、總完成度和總側擺角遞減。

由此，將規模為300的任務群的優化目標函數值及其3個子目標函數值進行分析，如圖14所示。由圖14可以看出,3個子目標函數值變化趨勢及適應度值的變化趨勢一致，同時適應度曲線較靠近總收益值曲線，該結果主要由于本文中子目標總收益值的權重占比較大。

圖14 任務群規模300的優化目標值曲線Fig.14 The optimization objective function value curve of the task group size of 300

4 結束語

任務規劃是多星協同對地觀測研究中的關鍵點，規劃結果的優劣直接關系著衛星資源的利用效率和觀測任務的執行質量。針對多星協同對地觀測中的任務規劃問題，提出了一種基于遺傳算法和禁忌搜索算法的多星協同任務規劃算法。該方法利用遺傳算法實現優化問題的初步求解，完成全局解空間的搜索；將遺傳算法求得的初步解作為輸入，利用禁忌搜索算法實現優化問題的進一步求解，完成局部解空間的細致搜索。所提出的方法綜合了遺傳算法全局尋優和禁忌搜索算法局部尋優的優勢，解決了多星協同對地觀測的任務規劃問題。通過不同種群數下的仿真測試驗證了算法的穩定性，通過不同任務群規模的仿真驗證了算法的有效性。