應用于衛星自主任務調度的改進遺傳算法

趙萍，陳志明

南京航空航天大學 航天學院, 南京 210016

應用于衛星自主任務調度的改進遺傳算法

趙萍，陳志明﹡

南京航空航天大學 航天學院, 南京 210016

針對具有側擺能力的對地觀測衛星的自主任務調度問題，對衛星自主任務調度問題和約束條件進行了描述，針對衛星自主任務調度NP-hard的特點，構建了基于目標收益及多約束衛星任務調度模型。設計了一種改進的遺傳算法，從遺傳操作的各個部分進行算法優化。首先將小區間法應用于初始種群生成，保證了種群的多樣性，并且交叉和變異算子均引入自適應概率；同時采用兩代競爭技術來避免“早熟”現象，提高算法的效率和魯棒性。算法還采用最優保留策略用來保存進化中的最優解，使得算法收斂于全局最優。對局部多沖突觀測任務應用該改進遺傳算法，并針對區域密集目標的觀測問題設計了仿真試驗，與傳統模擬退火算法及免疫蟻群遺傳混合算法進行了比較，驗證了該算法的有效性和收斂效果。

對地觀測衛星；衛星側擺角；自主任務調度；建模；改進遺傳算法；自適應概率

觀測衛星是利用星載傳感器，根據用戶的需求對地面目標成像，具有觀測效果好、覆蓋區域廣、持續時間長等特點，已經在環境監測，災害預報以及軍事作戰等領域得到了應用[1]。

對地觀測衛星調度問題的輸入是來自用戶的任務要求。每個任務有自己特定的有效時間窗口，在這些時間段以外，命令就沒有意義了。但是由于各種資源、時間等約束，不一定所有的任務都能夠被執行。所以，衛星在滿足各種約束的情況下，應盡可能多完成請求的任務[2]。從衛星接收的所有觀測任務請求中，根據星上資源以及衛星對任務的時間窗口約束，利用算法快速選擇待觀測的任務序列，完成對衛星觀測任務的調度。所以，對地觀測衛星調度的輸出是無沖突待觀測的任務序列。

隨著衛星數量和觀測任務數量的增多以及衛星機動能力的增強，任務調度問題的規模呈指數的增長。觀測衛星的調度問題已經被證明是NP-hard問題，問題的指數爆炸特征明顯，很難求解[3]。觀測衛星的任務調度問題涉及許多非線性約束，求解目標不唯一，所以并不存在適用于所有問題的算法[4]。現有的研究一般將衛星的任務調度問題轉化成組合優化問題進行求解。

文獻[3]針對敏捷衛星提出的約束模型，比較了約束調度、動態調度以及局部搜索等求解算法。文獻[5]構建了敏捷衛星任務調度的數學模型，用模擬退火算法和遺傳算法相結合的混合遺傳算法進行求解。文獻[6]針對多星對區域目標的觀測調度問題設計了貪婪隨機變鄰域搜索算法、禁忌搜索和模擬退火算法，提高了算法的求解效率。文獻[7]設計了一種新的遺傳算法并將該優化算法應用于實際的衛星任務調度問題模擬。偏置隨機密鑰遺傳算法[8](BRKGA)可以有效地解決組合優化問題，文獻[8]提出了一種混合解碼的方法，并對敏捷地球觀測衛星進行了試驗。文獻[9]提出了一種基于指標的多目標局部搜索算法(IBMOLS)解決多目標優化問題，并且將IBMOLS的結果與偏置隨機密鑰遺傳算法的結果進行比較。也有學者對各種算法性能進行了比較分析，文獻[10]在衛星任務調度中比較了模擬退火算法、遺傳算法、爬山算法等性能。

從現有的研究可以看出，智能優化算法在求解衛星任務調度問題上有很大的優勢。同時，現有的研究中，任務的調度模型都較為簡單，沒有考慮或簡化了衛星側擺角、轉換時間等約束；很少有針對密集任務的觀測調度算法[11]。針對這些問題，本文提出了快速計算觀測衛星側擺角的方法，對衛星自主任務調度問題構建了基于目標收益及多約束的任務調度模型，最后設計了一種改進的自適應遺傳算法應用于衛星局部沖突觀測任務的調度。并針對區域密集目標的觀測問題設計了仿真試驗，將試驗結果與傳統模擬退火算法及其他改進遺傳算法進行了比較，驗證了算法的有效性。

1 衛星對地觀測側擺角計算

為了擴大衛星對地觀測的范圍，通常在衛星上采用側擺技術，使得衛星能夠沿著垂直星下點軌跡的方向也進行觀測[1]。衛星的側擺角是指星載遙感器沿著垂直軌道方向轉動與星地連線之間形成的夾角。如圖1所示，假設觀測的目標點在A(λ,φ)處，S是衛星的位置，O為地心，S′(λs,φs)是星地連線與地面的交點，并且AS′垂直于星下點軌跡，H為衛星的高度，Re為地球半徑，FOV視場角，β為側擺角。

圖1 衛星對地覆蓋示意Fig.1 Illustration of ground coverage of satellite

文獻[1]給出了計算衛星側擺角的方法。根據目標點和星下點的經緯度坐標，利用文獻[12]中給出的方法求解側擺角。具體方法如下：

該算法基于以下兩點前提：1)弧度為1′的弧長在地球上對應的距離長度是1海里；2)1海里=1.852 km。首先，計算出AS′：

計算 arccos(·)的時候，如果是弧度要轉換成角度進行計算AS′。

地心覆蓋角∠AOS：

則側擺角β：

2 任務調度問題的描述和模型建立

2.1 任務調度問題的描述

衛星對地觀測的步驟如下：用戶給出成像任務要求，可能包括不同的任務類型，不同的優先級等要求。衛星任務觀測系統根據得到的任務信息，衛星自身位置信息以及星上傳感器和可用能源約束進行相應的任務調度，最大限度地完成用戶提交的任務請求。從上述過程可知，任務調度在整個衛星成像應用過程中起著關鍵作用，主要解決衛星資源的有效分配和調度。

傳統的任務調度大多由地面站直接進行任務調度，然后向衛星傳遞執行指令。相比于傳統的依賴于地面站的任務調度，星上自主任務調度有自己的優勢：1)衛星的效能進一步提高。2)能夠快速響應任務沖突。3)提高緊急任務的應對能力。4)減少對地面測控的依賴，衛星具有較高的自主能力。此外，對軍用衛星來說，自主任務調度能夠減少星地之間通信的概率，提高衛星的生存能力。

為了提高衛星的整體效能，本文采取一種星上自主調度算法，事先對衛星的姿態機動角度和相機成像時刻進行調度。對于敏捷衛星而言，多目標成像的時間和順序都不再唯一。因此，有必要對多個目標的成像時間和順序進行研究。同時對任務的優先級進行甄別，在任務出現沖突時，使高級別任務優先于低級別任務。

觀測范圍以及問題的假設如下:

敏捷衛星具有不止一維的自由度，能夠繞俯仰、滾轉、偏航三個軸變化。敏捷衛星的觀測范圍遠大于普通的衛星，觀測的時間也更為靈活，目標可以位于星下點之前或之后。所以任務成像的時間和順序都不再唯一。

敏捷衛星自主任務調度問題是一個非常復雜的問題，涉及條件約束繁多，在解決問題時不可能考慮所有約束[14]。所以，在建立問題模型之前，做出以下合理假設。

1)假設衛星只攜帶一個星載傳感器，并且任意時刻只能執行一個任務，不考慮中斷去執行其他任務。

2)只考慮衛星的側擺能力。

3)不考慮云層遮擋，天氣變化等對任務調度的影響。

4)不考慮衛星工作時發生故障等問題。

2.2 問題建模

衛星自主任務調度問題建模主要是衛星根據獲取的用戶觀測請求以及星上資源約束進行任務的觀測調度，最大限度地完成觀測任務。下面兩部分主要介紹任務調度的星上約束以及任務調度的目標函數。

(1)約束條件

主要考慮的約束如下：

1)時間窗約束：

2)任意兩次成像操作之間不能有交疊，任意兩次拍攝之間必須有任務的準備時間，包括開機準備時間和衛星角度變換需要的時間等。

式中：ski為從任務k結束到任務i開始的準備時間。

3)側擺角約束:

式中：endi為任務i的結束時間；Anglei為觀測任務i時的側擺角；v為衛星側擺時的角速度。式(6)表示當前任務到下一次任務的時間要足夠多來完成側擺角轉換。

4)太陽高度角約束:

式中：ASun,min為完成任務的最小太陽高度角；ai(t)為t時刻衛星執行任務i的太陽高度角。

5)能量約束：

式中：ei為完成任務i消耗的能量；εki為從任務k結束到任務i開始的準備操作消耗能量；E為可用的星上總能量；xi表示任務i是否被完成，1表示被完成，否則為0；xki表示從任務k到任務i的轉換，存在轉換則為1，否則為0。

6)星上存儲容量約束：

式中：M為星上總存儲容量；mi為完成任務i需要占用的容量。

(2)目標函數

衛星任務調度的目標是在給定的時間范圍中，在滿足衛星各類約束條件的情況下，盡可能獲得更多的衛星任務完成收益。這里只考慮單一目標函數。任務調度的目標函數如下：

式中：Bi為完成任務i的收益，Bi≥0；αi是表示任務i的是否完成的二元變量，完成為1，否則為0。

最大化任務完成收益，這里面任務的收益Bi與觀測任務的優先級成正比，優先級大的任務收益相對應較高。

(3)適應度函數

遺傳算法中使用適應度來評價個體的性能用以指導搜索。適應度高的個體遺傳到下一代的概率大一些。本文的目標函數是最大值函數，所以定義一個與目標函數相近的適應度函數來評價個體的性能。適應度函數定義如下：

式中：Bi表示完成任務i的收益，Bi≥0；Ci表示任務i是否被選中，1表示被選中完成，0則表示沒有。

3 改進的遺傳算法

衛星的任務調度問題已經被證明是一種NP-hard問題，很難通過解析或計算求解最優解。許多研究已經成功將各種改進過的遺傳算法應用于解決衛星的任務調度問題[14-15]。遺傳算法的主要步驟是將問題的解空間進行編碼，構成染色體，再生成一個由染色體產生的初始種群，根據需要優化問題的目標函數來構造適應度函數，對種群對環境的適應度進行評估。適應度高的個體被保留下來，經過交叉、變異等遺傳算子產生新的更加優異的種群，不斷進行迭代，最終收斂到一個比較好的解，這個解接近問題的最優解。遺傳算法作為一種優化方法，也存在自身的局限性：1)遺傳算法容易出現過早收斂現象(早熟)；2)在快要接近最優解時在最優解附近收斂較慢等。本文在遺傳算法的基礎上進行一定的改進，提高算法的收斂性能。將該算法應用到衛星任務調度模型的求解。

3.1 編碼和初始種群生成

i∈1,2,…，N

染色體編碼結構的一個簡單示例如下所示：

本文采用的產生初始群體的方法叫小區間生成法[17]。具體的步驟是：把優化區間分成若干個小區間，在各個小區間內隨機產生一個初始個體。這樣生成的初始群體會均勻分布在整個空間，保證了初始群體的豐富性，增強了搜索收斂于全局最優的可能性。同時初始種群中保留全1個體，這是無約束下最優解。

3.2 遺傳算子

(1)復制操作

為了保證較好的個體不會因為遺傳操作被破壞，采取兩代競爭遺傳算法[18]的操作。將父代的個體全部復制保留與子代一起進行選擇操作。

(2)交叉算子

本文中采用的是優選的交叉操作，在父代中隨機產生兩個個體，保留適應度較大的個體，將上面的操作進行兩次，得到兩個保留下來的個體。將得到的兩個體格進行自適應單點交叉。交叉概率表示如下:

(12)

式中：fc為兩個交叉個體中的適應度較大的值；fmax,favg分別是群體中的個體適應度最大值和平均值。

(3)變異算子

遺傳算法使用交叉算子從全局的角度出發找到了一些較好的個體編碼結構，它們已經接近最優解了。但使用交叉算子無法對局部細節進行搜索。使用變異算子能夠改善遺傳算法的局部搜索能力。本文采用基本位變異，以變異概率指定變異點做變異操作，在該算法中就是進行取反操作，0變成1或者1變成0。在該算法中采用的是自適應變異概率，即：

式中：Pm1=0.1；Pm2=0.001； fmax為群體的最大適應度；favg為群體的平均適應度值；fc為要變異的個體的適應值。

(4)選擇算子

上文提到采用兩代競爭遺傳，將父代與產生的子代一起進行選擇操作。具體的步驟如下：1)將最優個體保存下來，將兩代個體中適應度最大的個體直接保存下來。這種方法稱為精英保存策略[19]，研究表明，保留最優個體的遺傳算法以概率1收斂到全局最優解。該步驟保證了全局收斂性。2)兩兩競爭選擇，將除了最優個體以外的全部個體進行兩兩競爭選擇，隨機選出兩個個體，保留適應度較大的。重復該操作，一直到產生完整的下一代。

(5)終止條件

該算法的終止條件為種群穩定，規定最大迭代次數，若群體中最大適應度與平均適應度差值小于10-6或者達到最大迭代次數則終止。

4 算法仿真

在STK中設置仿真場景，總共設置了500個觀測目標，500個待觀測目標主要是針對單圈次觀測，某塊區域的密集觀測，示意如圖2所示。算法用Matlab 2013a在1.8 GHz CPU,4G內存的計算機上實現。設定衛星的高度為500 km，衛星的視場角為8°，側擺能力為40°，衛星機動角速度為2(°)/s。衛星模型是J4擾動模型，考慮可見光對觀測影響。將STK與Matlab互聯，在Matlab中獲取衛星和目標點的參數，用上面提出的算法進行仿真。同時將改進的遺傳算法的仿真結果與傳統的模擬退火算法以及文獻[13]中提出的免疫遺傳蟻群混合算法仿真結果進行比較。

圖2 500個觀測目標與星下點軌跡示意Fig.2 Illustration of 500 targets and ground track

500個目標點中單圈次只有96個目標點在給定的時間內可以觀測到。對于可觀測96個目標，按照可見時間窗口的開始時間進行排序得到任務序列。對應于每個觀測目標，給定對應的任務收益進行仿真。

圖3是該算法一次仿真迭代的過程，是種群平均適應度和最大適應度隨著迭代次數的變化。從圖3可以看出初始種群因為保留了所有任務均選中的全1個體，所以最大適應度值最大。因不滿足條件很快被放棄，種群迭代初始的適應度比較低，但是經過上述改進的遺傳算法，一段時間內上升幅度較大，但到迭代最后則趨于平穩。

表1是為了比較該算法與模擬退火算法(SA)與免疫遺傳蟻群混合算法(IACOGA)的仿真結果，采用同樣的數據源進行模擬退火算法和免疫遺傳蟻群混合算法進行仿真。從表1可以看出，改進遺傳算法的收益百分比>免疫遺傳蟻群混合算法收益百分比>模擬退火算法收益百分比。而達到全局收斂的時間關系則是，改進遺傳算法收斂時間<模擬退火算法收斂時間<免疫遺傳蟻群混合算法收斂時間。由表1可以看出，模擬退火算法的收益百分比最差，而免疫遺傳蟻群混合算法的收益百分比與本文提出的改進遺傳算法相近，但是，IACOGA算法的運行時間較長，使用蟻群算法改進遺傳算法，雖然可以得到較好的初始解，但是時間代價很大。而本文的算法在達到較好的收益率的同時，運行時間很少，收斂速度很快。

圖3 種群最大適應度和平均適應度的變化值Fig.3 Maximum fitness and average fitness of every population

仿真次數AGA仿真時間/sAGA收益百分比/%SA仿真時間/sSA收益百分比/%IACOGA仿真時間/sIACOGA收益百分比/%10 9993 81 6787 9347 6293 621 0194 41 7688 5316 6491 131 1195 21 7589 9333 6793 441 0393 31 6886 2336 0093 351 0195 41 7186 4319 0591 861 0395 81 7086 8334 0192 271 0695 41 7487 8339 7091 681 1292 11 6888 0335 6192 690 9693 51 6985 2314 4291 8101 2092 91 6485 9316 7291 9

5 結束語

觀測衛星的自主任務調度涉及到多種組合約束問題，同時要求衛星能夠快速對得到的任務請求進行調度，所以對任務調度算法的要求較高。對于任務可見窗口有重疊，任務比較密集的衛星觀測調度問題，應該要考慮衛星側擺能力與到達指定側擺角度需要的機動時間等約束。本文給出了快速計算側擺角的方法，并且對衛星對地觀測問題進行基于各類約束以及任務完成收益的建模，設計了改進遺傳算法來求解，使用小區間法保留初始種群的多樣性，并且對于遺傳算子均引入自適應概率，同時采用兩代競爭算法保證優的個體被保存，實施最優保存策略。試驗驗證，該算法相較于傳統的模擬退火算法以及免疫遺傳蟻群混合算法，具有更好的收斂速度和全局收斂性。

References)

[1] 賈志軍,楊敏,孫洋,等. 衛星對地觀測中的側擺策略[J]. 四川兵工學報,2014(7):128- 130.

JIA Z J, YANG M, SUN Y, et al.Swinging strategy on Earth observing satellites[J]. Journal of Sichuan Ordnance, 2014(7):128-130(in Chinese).

[4] 賀仁杰, 高鵬,白保存,等. 成像衛星任務規劃模型、算法及其應用[J]. 系統工程理論與實踐,2011(3):411-422.

HE R J, GAO P, BAI B C, et al. Models,algorithms and applications to the mission planning system of imaging satellites[J]. Systems Engineering-Theory & Practice,2011(3):411-422(in Chinese).

[5] 李玉慶,徐敏強,王日新.三軸穩定衛星點目標觀測任務優化調度技術[J].吉林大學學報(工學版),2008,38(6):1447-1451.

LI Y Q, XU M Q,WANG R X, et al. Scheduling observations of spot object of three-axis stabilized satellites[J]. Journal of Jilin University (Engineering and Technology Edition), 2008, 38(6):1447-1451(in Chinese).

[6] 阮啟明. 面向區域目標的成像偵察衛星調度問題研究[D].長沙:國防科技大學,2005.

[7] BAEK S, HAN S, CHO K, et al. Development of a scheduling algorithm and GUI for autonomous satellite missions[J]. Acta Astronautica, 2011, 68(7): 1396-1402.

[8] TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P. Multi-objective optimization for selecting and scheduling observations by agile Earth observing satellites[M]∥Parallel Problem Solving from Nature-PPSN XII. Berlin: Springer, 2012: 112-121.

[9] TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P. A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite[J]. European Journal of Operational Research, 2015, 245(2): 542-554.

[10] GLOBUS A, CRAWFORD J, LOHN J, et al. Scheduling Earth observing fleets using evolutionary algorithms: problem description and approach[C]∥Proceedings of the 3rd International NASA Workshop on Planning and Scheduling for Space, 2002:27-29.

[11] 郭浩,邱滌珊,伍國華,等. 基于改進蟻群算法的敏捷成像衛星任務調度方法[J]. 系統工程理論與實踐,2012(11):2533-2539.

GUO H, XIU D S,WU G H, et al. Tasks scheduling method for an agile imaging satellite based on improved ant colony algorithm[J]. Systems Engineering-Theory & Practice, 2012(11): 2533-2539(in Chinese).

[12] Geoscience Australia. Distance calculation algorithms[EB/OL].(2013-05)[2016-01-08].http:∥www.ga.gov.au/sc-entific-topics/positioning-navigation/geodesy/geodetic-techniques/distance-calculation-algorithms.

[13] 郝會成,姜維,李一軍. 基于混合遺傳算法的敏捷衛星任務規劃求解[J]. 科學技術與工程,2013(17):4972-4978.

HAO H C, LI W, LI Y J. Mission planning for agile Earth observation satellites based on hybrid genetic algorithm[J]. Science Technology and Engineering, 2013,17: 4972-4978(in Chinese).

[14] 向仍湘. 敏捷衛星任務調度技術研究[D].長沙：國防科學技術大學,2010.

[15] DJAMAL H, MICHEL V. Saturated and consistent neighborhood for selecting and scheduling photographs of agile Earth observing satellite[C]. MIC2003: The Fifth Metaheuristics International Conference.

[16] VERFAILLIE G, LEMATRE M. Selecting and scheduling observations for agile satellites: some lessons from the constraint reasoning community point of view[C]. The Seventh International Conference on Practical and Principles of Constraint Programming. France, 2001.

[17] 高瑋,尹志喜. 現代智能仿生算法及其應用[M].北京:科學出版社,2011: 58-61.

[18] 于海斌,王浩波,徐心和.兩代競爭遺傳算法及其應用研究[J].信息與控制,2000,29(4): 309-314.

YU H B, WANG H B, XU X H. A genetic algorithm with competitive selection between adjacent two generations and its applications to tsp[J]. Information and Control, 2000,29(4): 309-314 (in Chinese).

[19] 李小平, 王風儒. 優解保留遺傳算法收斂性研究[J].電機與控制學報,2000,4(1): 52- 54.

LI X P, WANG F R. Research on convergence of elitist genetic algorithm[J]. Electric Machines And Control, 2000, 4(1): 52-54 (in Chinese).

(編輯：高珍)

An adapted genetic algorithm applied to satellite autonomous task scheduling

ZHAO Ping，CHEN Zhiming*

College of Astronautics, Nanjing University of Aeronautics & Astronautics, Nanjing 210016, China

Aiming at solving the problem of autonomous task scheduling of earth observing satellites with the ability of swinging,satellite autonomous task scheduling problem and constraints were described.A single-objective multi-constraints model was built according to the NP-hard character of satellite autonomous task scheduling problem.An adapted genetic algorithm was designed.All of the genetic operations of genetic algorithms were optimized. Firstly, mini-region method was applied to generate of the original population to ensure the diversity of population. Adaptive probabilities were used for crossover and mutation operation. Two generations competitive technology was used to avoid the premature and improve the efficiency and the robustness of the algorithm. The algorithm also uses the optimization reserved strategy to preserve the optimal solution, which makes the algorithm converge to the global.The adapted genetic algorithm was applied to the local multi-conflict tasks observation and designed simulation experiments of the observation of regional dense targets. The results are compared with results of simulated annealing algorithm and immune ant colony genetic algorithm,and it shows that the proposed algorithm is more effective and it has a better convergence.

Earth observation satellite；satellite swinging angle；autonomous task scheduling；modeling；adapted genetic algorithm;adaptive probability

10.16708/j.cnki.1000-758X.2016.0064

2016-05-04；

2016-07-13；錄用日期：2016-08-22；

時間：2016-12-16 11:29:09

http:∥www.cnki.net/kcms/detail/11.1859.V.20161216.1129.006.html

國家自然科學基金(61403197)；江蘇省自然科學基金(BK20130816/BK20140830)

趙萍(1991-)，女，碩士研究生，zhaoping_nuaa@163.com,研究方向為編隊衛星在軌自主任務規劃

*通訊作者：陳志明(1984-)，男，講師，lchenzhiming@nuaa.edu.cnl，研究方向為分布式衛星測控技術、星載計算機設計管理

趙萍,陳志明.應用于衛星自主任務調度的改進遺傳算法[J].中國空間科學技術,2016,36(6)：47-54.

ZHAOP,CHENZM.Anadaptedgeneticalgorithmappliedtosatelliteautonomoustaskscheduling[J].ChineseSpaceScienceandTechnology, 2016,36(6)：47-54(inChinese).

TP301.6

A

http:∥zgkj.cast.cn