基于遺傳算法的多星調度方法

章 密, 胡笑旋

(1.合肥工業大學 管理學院,安徽 合肥 230009; 2.合肥工業大學 過程優化與智能決策教育部重點實驗室,安徽 合肥 230009)

?

基于遺傳算法的多星調度方法

章 密1,2, 胡笑旋1,2

(1.合肥工業大學 管理學院,安徽 合肥 230009; 2.合肥工業大學 過程優化與智能決策教育部重點實驗室,安徽 合肥 230009)

多星調度是一類約束條件眾多且復雜的調度問題,除了要考慮時間窗、過渡時間等約束外,還需要考慮任務的時效性約束和能量消耗約束。為此,文章建立了相應的數學模型,并設計了基于圈次進行交叉、變異的遺傳算法;通過STK生成測試數據,并與蟻群算法結果對比,說明該方法能有效解決多星調度問題。

衛星;多星調度;遺傳算法;衛星圈次

0 引 言

地球觀測衛星是一種重要的目標圖像獲取平臺,它們在運行軌道上,依據用戶提出的觀測需求,通過遙感器對地面目標進行成像。地球觀測衛星的任務調度是指根據一定優化目標,對多個對地觀測任務(簡稱觀測任務)進行排程,以確定執行任務的具體衛星和具體時間。在任務調度過程中,計劃觀測的時間應該在目標對衛星的可見時間窗之內,且要在任務要求的截止時間之前;衛星在觀測時會消耗一定能量,而衛星繞地球一圈能接收到太陽光照的時間是一定的,即衛星在每一圈次內最大可消耗能量是一定的。能量消耗需要考慮衛星的軌道圈次,但如果以圈次為周期安排調度,那么每一圈次最優化并不代表整個周期最優化,因此需要從整個規劃周期來安排任務,這就需要考慮時間約束和能量約束問題。

多星調度問題一直是學術界關注的焦點。文獻[1] 將多星調度問題建立為背包模型,并提出禁忌搜索算法解決該模型；文獻[2]提出一種基于分區的方法求解調度問題的上限；文獻[3]對spot5衛星的日調度問題進行了研究,文中并未對該問題建立數學模型,而是直接對benchmark問題采用遺傳算法求解；文獻[4]針對蟻群算法求解多星調度問題時容易陷入局部最優解的問題,提出一種改進的蟻群算法,實驗證明該方法的可行性和相對優越性；文獻[5]應用新的遺傳算法模擬實際衛星任務調度問題；文獻[6]建立協同規劃模型，并將能量約束簡化為時間和開關機約束，進而提出算法協同進化模型求解技術,最后通過評價幾種典型的求解算法,驗證了提出算法的有效性；文獻[7]考慮了多星調度問題,文中假設能量與存儲都足夠使用,并使用混合遺傳粒子群算法進行求解；文獻[8]對多星任務規劃問題進行建模,模型將能量約束直接轉化為時長約束;文獻[9]對衛星對地觀測構建了非循環有向圖模型,并將求解過程劃分為任務聚類、安排調度2個階段；文獻[10]針對多星、多軌道、多用戶環境,建立了衛星調度模型;文獻[11]將多星聯合調度問題分解為任務資源匹配以及單星任務處理2個子問題,并設計了學習型遺傳算法解決該問題。多星調度問題的典型解決算法包括遺傳算法[3,5,12]、蟻群算法[4,13-14]和禁忌搜索算法[1,15]等。

在上述文獻中,針對多星對地觀測調度問題,大部分學者都是考慮了時間窗約束、任務間過渡約束等,并未考慮任務的時效性約束以及能量約束。本文針對以上情況，建立多星調度規劃模型,考慮任務時效性以及能量等約束;設計了基于圈次進行交叉、變異的遺傳算法;對本文提出的遺傳算法進行穩定性測試,并與蟻群算法進行對比實驗。

1 問題描述

衛星觀測示意圖如圖1所示。衛星在運行軌道上通過遙感器對地面目標成像,每次成像動作會在地面上形成一個具有一定幅寬的成像條帶(具體如圖1中的灰色區域),且一個地面目標只需被成像一次即可完成觀測。

圖1 衛星觀測示意圖

1.1 時間窗

衛星是在軌道上不斷運動的,在給定的調度周期內,衛星有不同的軌道圈次。衛星在某一軌道圈次內,運動至目標的上空時,才可以對地面目標進行成像。此時,衛星的遙感器在一個時間段之內能夠看見目標,這個時間段稱為可見時間窗。在給定的規劃周期內,衛星與目標之間一般不止1個時間窗,衛星對目標的觀測需在其中某一個時間窗之內完成,且目標觀測時間窗一般會小于可見的時間窗。

1.2 觀測過渡時間

一顆衛星在先后執行2個觀測任務之間,需要有一定的過渡時間,在這段時間內,衛星需要對遙感器進行調整。后一個觀測任務的開始時間減去前一個觀測任務的結束時間要大于任務執行過渡時間。

1.3 能量消耗

衛星在觀測目標時會消耗能量,而衛星在每一個軌道圈次內可使用的能量是有限的,因此在調度過程中,衛星在每一圈次內的能量消耗不能超過該衛星的能量限制。

1.4 任務時效性

用戶提出的任務都有一個截止時間,超過這個時間再執行這個任務將沒有任何意義,因此調度任務時,需要將任務能在該時間限制前完成的時間窗內執行。

1.5 本文假設

(1) 衛星在觀測某一個地面目標時,在與該地面目標的可見時間窗開始時間進行觀測。

(2) 一個觀測任務只在一個軌道圈次內完成。

(3) 執行觀測任務的能量消耗與任務執行時間成正比。

2 數學模型

多星觀測任務調度問題的數學模型如下:

(1)

(3)

(4)

(5)

?j∈{1,2,…,NS}

(6)

(1)式為目標函數,由如下2個部分組成：一是已執行的觀測任務數量總和；二是已執行的觀測任務權重總和。調度目標是使它們的加權和最大化,其中,Rmm、Rwgt為比例系數。

2018年上半年，中國國內生產總值(GDP)實際同比增長6.8%，延續了穩定增長的態勢。在出口較快增長的帶動下，制造業投資和民間投資保持著良好的發展勢頭，消費則繼續成為支撐經濟增長的主要動力。而在供給一側，工業增加值同比增速也穩定在6.6%—6.9%之間，與實際GDP增速的走勢基本一致。中國經濟表現出相當的韌性。

約束(2)表示每個觀測任務最多只能被執行1次;約束(3)表示執行觀測必須在可見時間窗之內進行;約束(4)表示如果有2個觀測任務被同一顆衛星先后執行,則2個任務之間需要有足夠的過渡時間;約束(5)表示任務必須在最晚完成時間之前完成觀測;約束(6)表示衛星在每一個軌道圈次內消耗的能量不能超過最大能量限制。

3 遺傳算法

遺傳算法是模仿自然界生物進化機制的一種演化算法,因其具有良好的全局搜索能力而被廣泛應用于解決各種組合優化問題。本文采用遺傳算法求解上文所述模型。

3.1 編碼

本文采用十進制的編碼方式,每條染色體代表一個調度方案,即表示哪一個目標在哪一顆衛星的哪一個軌道圈次內被觀測,在染色體中加入虛擬衛星,用于存放暫時不能被觀測的任務,以保證染色體的長度一致。每一條染色體上的任務是按照衛星觀測時間順序排列的。由于衛星往返周期不同,出現每顆衛星在給定的規劃周期內有不同數量的圈次。編碼示意圖如圖2所示,染色體中包含2顆衛星(Sat1,Sat2),一顆虛擬衛星,共有觀測任務15個,其中虛擬衛星放置不能被觀測的任務9、10。Sat1在給定的規劃周期內有2個圈次,其中圈次1中Sat1觀測了任務1、2、11;圈次2中Sat1觀測了任務3、12、4。Sat2在給定的規劃周期內有3個圈次,其中圈次1中Sat2觀測了任務5;圈次2中Sat2觀測了任務14、6、13、7;圈次3中Sat2觀測了任務8、15。

圖2 編碼示意圖

3.2 初始化

本文設計了插入即檢查初始解生成策略,在對每一個觀測任務進行插入時即檢查對約束條件的滿足情況,不滿足約束的放入到虛擬衛星中。為了綜合考慮權重和能量這2個指標,定義觀測任務的權重密度pi如下:

pi=vi/di

(7)

將觀測任務按權重密度的大小進行排序,權重密度大的優先安排。在固定周期內,觀測任務所有時間窗是固定的,因此可以在該觀測任務的時間窗集合中隨機挑選一個,插入到相應的衛星任務序列當中,見算法1。同時檢查是否滿足約束,如果不滿足,則轉向下一個時間窗。

算法1 任務插入算法(以觀測i為例)

Set flag=false

end if

end if

Set flag=true

q=q+1

end for

if flag==false then

將任務插入虛擬衛星。

end if

3.3 選擇

適應度函數考慮了已執行的觀測任務數量占所有觀測任務數量的比例,以及已執行的觀測任務的權重之和占所有觀測任務的權重之和的比例,表達式如下:

(8)

采用輪盤賭選擇機制。按照適應度函數計算每個解的適應度值,再按輪盤賭選擇留下來的解。輪盤賭選擇使得比較優秀的解保留下來的概率比較大,加速了種群的收斂性,從而提高了算法運行效率。

3.4 交叉

本文采用基于圈次的交叉方式,在每一顆衛星中隨機選擇一個圈次,將染色體中每一個衛星在該圈次的任務進行交叉。原染色體中任務與交叉過來的任務重復地放入到虛擬衛星中,與虛擬衛星中的任務一起重新插入,具體如圖3所示。

圖3 染色體交叉前后示意圖

3.5 變異

變異采用基于圈次的變異方式,在每一顆衛星中隨機選擇一個圈次,將每顆衛星上該圈次的任務進行變異。變異策略是將需要變異的任務放入到虛擬衛星中,與虛擬衛星中的任務一起重新插入。

4 仿真實驗

4.1 實驗設置

本文通過仿真實驗來分析算法求解性能。實驗中設置了2顆衛星,并分別設置了大、中、小3個不同規模的觀測任務數量。其中小規模數據含有50個觀測任務,調度周期為24 h；中等規模數據含有100個觀測任務,調度周期為48 h；大規模數據含有200個觀測任務,調度周期為72 h。令觀測任務的權重都在[0,1]之間,Rnum=0.3,Rwgt=0.7。

實驗所用計算的配置為:CPU酷睿E7500 2.93 GHz,RAM 2 GB,操作系統Windows7。所有算法都在Microsoft Visual Studio2008開發環境下使用C#語言編寫。

4.2 遺傳算法穩定性測試

本文通過測試3個規模的數據200次(10組實驗,每組實驗跑20次)對遺傳算法的穩定性進行測試,記錄最大值、最小值、平均值、方差以及平均時間(ms)。試驗中GA的種群規模分別為50、100、200,交叉概率為0.9,變異概率為0.1，實驗結果如圖4所示。

圖4 遺傳算法穩定性測試統計數據

從圖4可以看出,遺傳算法在求解該問題時的解相對穩定。求解小規模數據時方差約為0.01左右,求解中等規模時方差約為0.07左右,求解大規模數據時方差約為0.04左右。即求解數據規模越大時,算法越穩定。

4.3 與蟻群算法的比較

蟻群算法[4,13-14]是解決多星調度問題的常用算法。針對上述3個規模的數據,將本文算法(GA)與蟻群算法(ACO)進行比較,驗證本文算法的有效性。試驗中GA的種群規模分別為50、100、200,交叉概率為0.9,變異概率為0.1。ACO的螞蟻數量分別為5、10、20，記錄目標函數的最大值、最小值、平均值以及平均時間(ms)。以上實驗中,所有的結果數據都是運行20次的平均值。遺傳算法與蚊群算法的質量比較見表1所列。

表1 遺傳算法與蟻群算法比較結果

從表1可以看出,GA在實驗的幾個例子中,都取得比ACO更為優化的結果;特別是觀測任務數目較多時,GA比ACO在時間上的效率越發優化。

5 結 論

多星調度問題是成像任務規劃問題中重要的內容。本文首先建立了多星調度整數規劃模型,模型中考慮圈次的能量約束;然后闡述引入按圈次進行交叉變異的遺傳算法;用STK提供仿真數據進行實驗分析,通過與經典蟻群算法進行比較,實驗結果表明本文提出的遺傳算法能有效解決多星調度問題。

[1] VASQUEZ M,HAO J K.A “logic-constrained” knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[J].Computational Optimization and Applications,2001,20(2): 137-157.

[2] VASQUEZ M,HAO J K.Upper bounds for the SPOT 5 daily photograph scheduling problem[J].Journal of Combinatorial Optimization,2003,7(1):87-103.

[3] MANSOUR M A A,DESSOUKY M M,A genetic algorithm approach for solving the daily photograph selection problem of the SPOT5 satellite[J].Computer & Industrial Engineering,2010,58(3):509-520.

[4] 朱新新,譚躍進,鄧宏鐘,等.求解成像衛星調度問題的改進蟻群算法[J].科學技術與工程,2012,20(31): 8322-8326.

[5] 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.

[6] 姜維,龐秀麗,郝會成.成像衛星協同任務規劃模型與算法[J].系統工程與電子技術,2013,35(10):2093-2101.

[7] CHEN Y,ZHANG D Y,ZHOU M Q,et al.Multi-satellite observation scheduling algorithm based on hybrid genetic particle swarm optimization[J].Advances in Information Technology and Industry Applications,2012,136(7):441-448.

[8] 黃生俊,邢立寧,郭波.基于改進模擬退火的多星任務規劃方法[J].科學技術與工程,2012,20(31):8293-8298.

[9] WU G,LIU J,MA M,et al.A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J].Computers & Operations Research,2013,40(7):1884-1894.

[10] BIANCHESSI N,CORDEAU J F,DESROSIERS J,et al.A heuristic for the multi-satellite,multi-orbit and multi-user management of earth observation satellites[J].European Journal of Operational Research,2007,177(2):750-762.[11] 孫凱,邢立寧,陳英武.基于分解優化策略的多敏捷衛星聯合對地觀測調度[J].計算機集成制造系統,2013,19(1):127-136.

[12] MAO T,XU Z,HOU R,et al.Efficient satellite scheduling based on improved vector evaluated genetic algorithm[J].Journal of Networks,2012,7(3):517-523.

[13] LI Y,WANG R,XU M.Rescheduling of observing spacecraft using fuzzy neural network and ant colony algorithm[J].Chinese Journal of Aeronautics,2014,27(3):678-687.

[14] 李泓興,豆亞杰,鄧宏鐘,等.基于改進蟻群算法的成像衛星調度方法[J].計算機應用,2011,31(6):1656-1659.

[15] HABET D,VASQUEZ M,VIMONT Y.Bounding the optimum for the problem of scheduling the photographs of an Agile Earth Observing Satellite[J].Computational Optimization and Applications,2010,47(2):307-333.

(責任編輯 萬倫來)

Scheduling of multi-satellite based on genetic algorithm

ZHANG Mi1,2, HU Xiaoxuan1,2

(1.School of Management, Hefei University of Technology, Hefei 230009, China; 2.Key Laboratory of Process Optimization and Intelligent Decision Making of Ministry of Education, Hefei University of Technology, Hefei 230009, China)

Multi-satellite scheduling is a complex problem with many constraints. In addition to consider the constraints like time window and transition time, it need consider timelines and energy consumption constraints. In view of this problem, a mathematical model was established. And a genetic algorithm with crossover and mutation based on circles of satellites was proposed. The proposed algorithm and the ant colony algorithm were compared through the same input test data generated by STK tools, which validated the proposed algorithm can effectively solve the multi-satellite scheduling problem.

satellite; multi-satellite scheduling; genetic algorithm; satellite circles

2016-04-18；

2016-11-01

國家自然科學基金創新研究群體資助項目(71521001);國家自然科學基金資助項目(71401048;71131002)

章 密(1992-),女,安徽池州人,合肥工業大學碩士生； 胡笑旋(1978-),男,安徽桐城人,博士,合肥工業大學教授,博士生導師.

10.3969/j.issn.1003-5060.2017.07.025

TP391.9

A

1003-5060(2017)07-0995-04