丁祎男，田科豐，王淑一

0 引 言

對地觀測成像衛(wèi)星是一類利用衛(wèi)星遙感器對地球表面、地形地貌、能源礦藏，以及低層大氣進行探測從而獲取有用信息的一類衛(wèi)星[1].隨著敏捷機動技術的發(fā)展，敏捷技術在成像衛(wèi)星中廣泛應用，如美國的WorldView系列衛(wèi)星，法國的Pleiades星座等.

敏捷成像衛(wèi)星是斷續(xù)工作方式，因此需要根據(jù)用戶需求進行任務規(guī)劃.衛(wèi)星任務規(guī)劃在整個對地觀測過程中起著關鍵作用，其結果直接影響到對地觀測衛(wèi)星系統(tǒng)的觀測效率.

目前，國外在衛(wèi)星任務規(guī)劃領域的研究持續(xù)時間長，技術比較成熟，且相關技術已應用到一些實際的航天任務中，其中，由NASA研制的ASPEN(Automated scheduling and planning environment)是一種地面任務規(guī)劃系統(tǒng)，使用局部搜索算法，應用范圍廣、擴展性良好[2].法國LEMAITRE等[3]針對敏捷衛(wèi)星Pleiades星座的任務規(guī)劃，提出了約束規(guī)劃模型，并分析比較了約束規(guī)劃、貪婪、動態(tài)規(guī)劃以及局部搜索等四種算法.TANGPATTANAKUL等[4]提出了一種基于指標的多目標局部搜索算法，解決多目標觀測任務規(guī)劃問題.國內(nèi)研究中，黃生俊等[5]針對多星任務規(guī)劃，綜合蟻群算法的反饋特性和模擬退火算法的局部搜索特性，設計了一種基于知識的改進模擬退火算法.郝會成等人針對新一代對地觀測敏捷衛(wèi)星任務規(guī)劃問題，提出了一種免疫遺傳-蟻群混合算法[6].李菊芳等[7]探討了一類涉及多星、多地面站的成像衛(wèi)星系統(tǒng)集成調(diào)度問題，并提出了一種變鄰域禁忌搜索算法.趙萍等[8]對衛(wèi)星自主任務調(diào)度問題構建了基于目標收益及多約束的任務調(diào)度模型，并設計了一種改進的自適應遺傳算法進行求解.韓傳奇等[9]提出了基于成像任務時間及任務均衡度的多指標優(yōu)化函數(shù)，針對所建模型，采用改進的遺傳算法，引入資源隨機分配的解碼策略及精英保留策略，保證了算法的全局收斂性，提高了算法的性能.

以上研究都針對敏捷成像衛(wèi)星任務規(guī)劃問題的特點設計了智能優(yōu)化算法進行求解，得到了較好的優(yōu)化結果，可以看出智能優(yōu)化算法在求解衛(wèi)星任務規(guī)劃問題上有很大優(yōu)勢.但現(xiàn)有的研究中任務規(guī)劃模型都較為簡單，存在一定的局限性.其中ASPEN系統(tǒng)是面向單顆衛(wèi)星的任務規(guī)劃，沒有涉及多星的協(xié)同調(diào)度； LEMAITRE等人的研究中應用的智能優(yōu)化算法都有各自的缺點，沒有使用混合算法來互補；黃生俊等和李菊芳等的研究面向的是非敏捷衛(wèi)星，沒有考慮任務間衛(wèi)星的姿態(tài)轉換約束；韓傳奇等的研究沒有考慮衛(wèi)星機動能力和能量約束；并且在衛(wèi)星成像系統(tǒng)多樣化的如今，上述提到的研究都沒有考慮到多載荷的任務協(xié)同調(diào)度.

針對這些問題，本文對多星自主任務協(xié)同中涉及的任務建模及優(yōu)化算法進行研究，采用了一種遺傳禁忌混合算法，解決多載荷敏捷衛(wèi)星在星上資源約束條件下的任務優(yōu)化問題，解決多星多載荷的任務協(xié)同分配問題.

1 問題描述

敏捷衛(wèi)星任務規(guī)劃可以被描述為約束優(yōu)化問題.衛(wèi)星進行成像時必須滿足一定的約束條件，以保證成像衛(wèi)星安全、準確地執(zhí)行任務.記衛(wèi)星數(shù)量為S，目標點數(shù)量為P.

1.1 約束條件

本文考慮的約束包括：

(1) 衛(wèi)星對目標點的可見性約束

若第p個目標點對第s顆衛(wèi)星可見，衛(wèi)星質(zhì)心指向該目標點的矢量和衛(wèi)星與地心連線矢量的夾角αsp不能超過衛(wèi)星的最大偏置能力αsmax.可以表示為：

αsp≤αsmax

(1)

(2) 衛(wèi)星對目標點的觀測時長約束

若第i個可見時間窗口包含第p個目標點，則時間窗口的長度不能小于此目標點需要被觀測的時長dp，可以表示為：

Tei-Tsi≥dp

(2)

其中Tsi表示第i個可見時間窗口開始時刻，Tei表示第i個可見時間窗口結束時刻.

(3) 星載傳感器類型的約束

本文主要考慮可見光相機和紅外相機兩種對地觀測載荷.其中，配置可見光相機的衛(wèi)星只能在陽照區(qū)觀測，配置紅外傳感器的衛(wèi)星可以在全軌道周期觀測，陽照區(qū)優(yōu)先采用可見光相機觀測.

在滿足(1)～(3)三個約束的前提下，可以計算出所有衛(wèi)星對所有目標點的時間窗口.每一個時間窗口可以作為一個元任務，是任務規(guī)劃模型的基本單位，記元任務數(shù)量為N.

(4) 衛(wèi)星姿態(tài)機動能力約束

衛(wèi)星進行姿態(tài)轉移的時間受機動能力的約束：

Toei-Tos(i+1)≥Tdimin

(3)

其中Toei表示前一次任務觀測結束時間，Tos(i+1)表示此次任務最晚開始觀測時間，Tdimin為兩次觀測姿態(tài)轉移所需最短時間.

(5) 衛(wèi)星的星上能源約束

將星上能源簡化為觀測能量，假設在一個觀測周期內(nèi)第s顆衛(wèi)星的總觀測能量maxEs是有限的.若要執(zhí)行元任務mi，需要有足夠的能量去執(zhí)行此任務，可以表示為：

(4)

Ei=k1φi+k2dpi

(5)

其中φi、dpi分別為衛(wèi)星觀測元任務mi需要的機動角度、成像時長，k1為機動角度到觀測能量的轉換系數(shù)，k2為觀測時長到觀測能量的轉換系數(shù).

(6) 衛(wèi)星存儲器容量約束

衛(wèi)星對目標成像時生成成像數(shù)據(jù)，儲存在星載存儲器中，經(jīng)過地面站會向地面站傳輸之前儲存的觀測數(shù)據(jù)，釋放存儲器空間.假設第s顆衛(wèi)星存儲器容量為maxCs，若要執(zhí)行元任務mi，需要有足夠的存儲器可用容量去儲存此任務產(chǎn)生的數(shù)據(jù)，表示為：

(6)

(7)

(8)

每次成像生成的數(shù)據(jù)大小和成像時長成正比，每次釋放的數(shù)據(jù)大小和數(shù)傳時間成正比，可以表示為：

Ci=k3dpi

(9)

Csg=k4dsg

(10)

其中dpi為衛(wèi)星觀測元任務mi的成像時長，dsg為第s顆衛(wèi)星與第g個地面站的數(shù)傳時長，k3為成像時長到成像數(shù)據(jù)的轉換系數(shù)，k4為數(shù)傳時長與釋放空間大小的轉換系數(shù).

(7) 衛(wèi)星數(shù)傳約束

若第s顆衛(wèi)星要向第g個地面站傳輸數(shù)據(jù)，則地面站與衛(wèi)星之間的視線方向在當?shù)氐难鼋铅聅g不能小于衛(wèi)星對地面站可見的最小仰角βmin，可以表示為：

βsg≥βmin

(11)

根據(jù)衛(wèi)星數(shù)傳約束可以計算出衛(wèi)星經(jīng)過地面站的數(shù)傳時長.

(8) 目標點任務約束

每個目標點都需要被觀測一次，且只被一顆衛(wèi)星觀測，對于第p個目標點有：

(12)

其中mis(s,p)為第s顆衛(wèi)星對第p個目標點的執(zhí)行情況，1表示執(zhí)行，0表示不執(zhí)行.此約束條件是為防止在一個觀測周期中某一個目標點被多次觀測，浪費衛(wèi)星資源.

由于一個目標點對應多個元任務，且元任務間不可避免的存在時間窗口沖突，再考慮到(4)～(8)約束條件的限制，需要任務分配算法來確定最終的任務序列.

1.2 性能指標

每一個元任務mi包含的目標點pmi都有不同的權重ωi，任務規(guī)劃的性能指標M為任務序列中所有完成任務對應目標點的權重和.為引導優(yōu)化算法優(yōu)先考慮在陽照區(qū)采用可見光成像，設定若完成的任務為紅外相機在陽照區(qū)成像(下文稱為載荷不匹配)，此任務對應的權重將乘以懲罰系數(shù)μ(0<μ<1).本課題選取μ=0.5.性能指標可以表示為：

(13)

其中

2 求解算法

多星多載荷任務規(guī)劃問題是典型的NP困難問題，沒有有效的確定性求解算法，傳統(tǒng)解決此類問題的主要方法包括遺傳算法、禁忌算法等智能優(yōu)化方法.

遺傳算法是基于自然選擇和基因遺傳學原理的搜索算法，其適用范圍廣、廣域搜索能力強，但也因種群間有很高的局部相似性，存在收斂速度慢，求解時間長的缺點.

禁忌算法模仿人類的記憶功能，使用禁忌表來避免重復搜索，并通過藐視原則來留下優(yōu)良解，從而保證搜索的多樣性，達到全局優(yōu)化的目的.禁忌算法收斂速度快，求解時間短，但其搜索性能對初始解依賴較大且廣域搜索能力不足.

由上可知，遺傳算法和禁忌算法有較強的互補性，本文結合兩者的優(yōu)點，使用遺傳禁忌混合算法進行求解.求解步驟如下：

1) 對于多星對多目標的觀測任務，元任務數(shù)量巨大，需要先對元任務進行聚類處理.

2)按照一定的順序?qū)λ芯垲愐来螒没旌纤惴ㄟM行優(yōu)化運算，得到每個聚類的最優(yōu)任務序列.

3) 將所有聚類的最優(yōu)任務序列合并可以得到整個任務規(guī)劃問題的最優(yōu)任務序列.

2.1 元任務聚類方法

本文根據(jù)元任務的時間窗口進行聚類，具體步驟為：

1) 設定最小聚類間隔mindt.將元任務序列按照時間窗口開始時刻從前到后排列，遍歷所有元任務，如果元任務mi和元任務mi-1的開始時間tsi和結束時間tei-1滿足tsi-tei-1>mindt，并且對任意jtej,即兩個元任務之間相隔超過最小聚類間隔，就記錄一個分割點bj=i-1.

2) 得到分割點集合[b1,b2,…bn-1,bn]，根據(jù)分割點集合可以將元任務序列分割成n+1個聚類.分割成的聚類包含元任務序號分別為為1～b1，b1+1～b2,…,bn+1～N.(N為元任務的總數(shù)).

3) 按照所處時間區(qū)間的先后順序處理第l個聚類：

①若l>1，類的種群初始化都是在完成上一個聚類的任務規(guī)劃后進行的.首先將包含之前類中已經(jīng)觀測過的目標點的元任務去除.

②然后對剩余的元任務進行0-1編碼，生成的染色體對應一個任務序列，每一個編碼對應一個元任務，0代表該元任務不執(zhí)行，1代表執(zhí)行.隨機產(chǎn)生多條染色體，構成初始種群，

③進行任務規(guī)劃運算，生成并存儲優(yōu)化后的任務序列，繼續(xù)處理下一個聚類.

4) 完成所有聚類的任務規(guī)劃后，將每個聚類的最優(yōu)任務序列按處理順序首尾相連，可以得到整個任務規(guī)劃的最優(yōu)序列.

2.2 遺傳禁忌混合算法

本文采用嵌入禁忌搜索的混合遺傳算法，核心思想是針對遺傳算法變異的無序性，使用禁忌搜索代替遺傳運算中的變異算子，一般稱為禁忌搜索變異算子，記為TSM(tabu search mutation)算子.

基本流程如圖1所示，具體如下：

(1) 對染色體對應的任務序列進行沖突處理，根據(jù)1.2節(jié)計算其性能指標(在優(yōu)化算法中稱為適配值).進而計算種群中每一條染色體的適配值.

(2) 基于輪盤賭的選擇運算

設種群大小為n，計算出個體i的適配值為Fi，輪盤賭具體過程如下：

1) 計算個體i被選中遺傳到下一代群體的概率為：

(14)

2) 計算個體i的累計概率：

(15)

3) 在[0,1]區(qū)間內(nèi)產(chǎn)生一個隨機數(shù)r，若r

(3) 交叉運算

采用多點交叉的方式來跳出局部解.

1) 根據(jù)選擇出來的父代群體，按順序取出兩個父代進行交叉.

2) 在[0,1]區(qū)間內(nèi)產(chǎn)生一個隨機數(shù)r，若r

(4) 使用TSM算子變異

1) 對于子代種群中的每一個染色體，在[0,1]區(qū)間內(nèi)產(chǎn)生一個隨機數(shù)r，若r

2) 將當前染色體作為禁忌搜索算法的初始解.

3) 由該初始解產(chǎn)生候選解集，根據(jù)解的適配值和禁忌表情況選擇最優(yōu)解，并更新禁忌表.

4) 將最優(yōu)解作為初始解重復步驟(3)，直至完成迭代要求.依次產(chǎn)生新的種群.

(5) 以新的種群返回(1)，繼續(xù)進行遺傳優(yōu)化運算，直至得到該聚類對應的最優(yōu)任務序列.

圖1 遺傳禁忌混合算法框圖Fig.1 Flow chart of genetic-tabu hybrid algorithm

3 仿真與分析

為驗證第2節(jié)算法的效果，對優(yōu)化算法進行仿真.仿真平臺為：Windows10操作系統(tǒng)下的Matlab2018b，計算機配置為Intel(R) Corei7-7700HQ@ CPU 2.8GHz處理器，16G內(nèi)存.

3.1 模型參數(shù)

設計星座有兩個軌道面，每個軌道面有4顆衛(wèi)星，采用太陽同步軌道.降交點地方時分別為10:30和13:30，仿真周期為86 400 s即一天.

種子衛(wèi)星軌道根數(shù)：

半長軸a=(6 371+500)km

偏心率e=0

傾角i=97.4°

近地點幅角ω=0°

升交點赤經(jīng)Ω=160°

為充分利用星座的覆蓋能力，每個軌道內(nèi)相鄰的兩顆衛(wèi)星相位差為90°，相鄰軌道第一顆衛(wèi)星相位差為45°.每個軌道面內(nèi)有一顆衛(wèi)星為紅外相機.星座對于赤道上的點的最大重訪周期約為2.95 h.

共選取目標點50個，隨機分布在78°W～73°W、37°N～42°N之間，設置一個地面站，坐標為95°W，65°N，目標點和地面站分布如圖2所示.

圖2 目標點和地面站分布示意圖Fig.2 Diagram of target points and groundstations distribution

3.2 優(yōu)化算法參數(shù)

對于遺傳算法，理論上種群規(guī)模越大、進化代數(shù)越多，得到的優(yōu)化結果越接近最優(yōu)解，但是隨之帶來的運算復雜度也會大大增加，根據(jù)經(jīng)驗交叉概率應在0.9附近選取，而變異概率不宜大于0.1.

對于禁忌搜索算法，候選集的大小和禁忌長度都會對優(yōu)化結果產(chǎn)生較大影響，理論上候選集越大，在有限的迭代次數(shù)內(nèi)找到最優(yōu)解的機會就越大，但會增加運算時間.禁忌長度的選取同實際問題有緊密的聯(lián)系，同時它決定了計算的復雜性，過短會造成循環(huán)的出現(xiàn)，過長又會導致收斂變慢.對于不同問題需要通過仿真驗證選取合適的參數(shù).

對于遺傳禁忌混合算法，可以充分利用兩種優(yōu)化算法的互補性，在不影響最終優(yōu)化效果的前提下，調(diào)整參數(shù)使得運算時間盡可能地減少.

經(jīng)過多次仿真驗證，對于3.1節(jié)描述的任務規(guī)劃模型，采用以下參數(shù)可以得到相對滿意的結果.令m為聚類中元任務數(shù)量.

遺傳算法：種群大小為10m，交叉概率為0.9，變異概率為0.09.

3.3 仿真結果與分析

為了直觀比較分析三種優(yōu)化算法的優(yōu)化效果，選取一個聚類的優(yōu)化過程作具體展示：

此聚類包含40個元任務，40個目標點，總權值為119，優(yōu)化效果如圖3所示.

圖3 單聚類優(yōu)化仿真示意圖Fig.3 Optimization result for a single cluster

可以看出，遺傳混合算法可以在在很短的代數(shù)內(nèi)達到遺傳算法多代迭代的優(yōu)化結果，禁忌搜索算法雖然收斂迅速，但優(yōu)化效果不如混合算法.

根據(jù)三種算法的具體優(yōu)化效果，在每個聚類的優(yōu)化中設置最少迭代次數(shù)n，迭代次數(shù)大于n后，若連續(xù)5代最優(yōu)解不變，便結束迭代.遺傳算法和禁忌算法至少迭代50次，遺傳禁忌混合算法至少迭代10次.

對于總體優(yōu)化任務，共有309個元任務，包含50個目標點，總權重為154.每種優(yōu)化算法運行30次，仿真結果如表1所示.其中載荷不匹配數(shù)量占比為一次任務規(guī)劃得到的任務序列中，紅外相機在陽照區(qū)觀測次數(shù)占觀測總次數(shù)的比例.

相對于遺傳算法，遺傳禁忌混合算法適配值標準差減少26.56%，優(yōu)化耗時減少37.41%，在不影響優(yōu)化效果的前提下，大大減少了優(yōu)化時間；相對于禁忌算法，遺傳禁忌混合算法適配值平均值提高8.49%，最差適配值提高13.99%，適配值標準差減少51.00%，載荷不匹配占比減少41.14%，混合算法克服了禁忌算法對初值依賴性強，優(yōu)化效果不穩(wěn)定的問題.

綜上，混合算法繼承了遺傳算法廣域搜索能力強和禁忌算法收斂速度快的特點，優(yōu)化時間短，優(yōu)化性能指標高，載荷不匹配數(shù)量占比小，有效解決了多星多載荷任務協(xié)同分配問題.

表1 任務規(guī)劃仿真結果Tab.1 Simulation results of mission scheduling

4 結 論

本文采用了一種遺傳禁忌混合算法解決多星多載荷任務協(xié)同分配問題.針對傳統(tǒng)遺傳算法求解時間代價大、傳統(tǒng)禁忌算法對初始解依賴問題，將禁忌算法嵌入遺傳算法作為禁忌算法變異算子，打破種群個體間的局部相似性.仿真結果表明，該算法充分利用了兩種算法的互補性，優(yōu)化效果和收斂速度俱佳.