章 密, 胡笑旋

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

?

基于遺傳算法的多星調(diào)度方法

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

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

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

衛(wèi)星;多星調(diào)度;遺傳算法;衛(wèi)星圈次

0 引 言

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

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

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

1 問題描述

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

圖1 衛(wèi)星觀測示意圖

1.1 時間窗

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

1.2 觀測過渡時間

一顆衛(wèi)星在先后執(zhí)行2個觀測任務(wù)之間,需要有一定的過渡時間,在這段時間內(nèi),衛(wèi)星需要對遙感器進行調(diào)整。后一個觀測任務(wù)的開始時間減去前一個觀測任務(wù)的結(jié)束時間要大于任務(wù)執(zhí)行過渡時間。

1.3 能量消耗

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

1.4 任務(wù)時效性

用戶提出的任務(wù)都有一個截止時間,超過這個時間再執(zhí)行這個任務(wù)將沒有任何意義,因此調(diào)度任務(wù)時,需要將任務(wù)能在該時間限制前完成的時間窗內(nèi)執(zhí)行。

1.5 本文假設(shè)

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

(2) 一個觀測任務(wù)只在一個軌道圈次內(nèi)完成。

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

2 數(shù)學(xué)模型

多星觀測任務(wù)調(diào)度問題的數(shù)學(xué)模型如下:

(1)

(3)

(4)

(5)

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

(6)

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

2018年上半年，中國國內(nèi)生產(chǎn)總值(GDP)實際同比增長6.8%，延續(xù)了穩(wěn)定增長的態(tài)勢。在出口較快增長的帶動下，制造業(yè)投資和民間投資保持著良好的發(fā)展勢頭，消費則繼續(xù)成為支撐經(jīng)濟增長的主要動力。而在供給一側(cè)，工業(yè)增加值同比增速也穩(wěn)定在6.6%—6.9%之間，與實際GDP增速的走勢基本一致。中國經(jīng)濟表現(xiàn)出相當?shù)捻g性。

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

3 遺傳算法

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

3.1 編碼

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

圖2 編碼示意圖

3.2 初始化

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

pi=vi/di

(7)

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

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

Set flag=false

end if

end if

Set flag=true

q=q+1

end for

if flag==false then

將任務(wù)插入虛擬衛(wèi)星。

end if

3.3 選擇

適應(yīng)度函數(shù)考慮了已執(zhí)行的觀測任務(wù)數(shù)量占所有觀測任務(wù)數(shù)量的比例,以及已執(zhí)行的觀測任務(wù)的權(quán)重之和占所有觀測任務(wù)的權(quán)重之和的比例,表達式如下:

(8)

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

3.4 交叉

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

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

3.5 變異

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

4 仿真實驗

4.1 實驗設(shè)置

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

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

4.2 遺傳算法穩(wěn)定性測試

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

圖4 遺傳算法穩(wěn)定性測試統(tǒng)計數(shù)據(jù)

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

4.3 與蟻群算法的比較

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

表1 遺傳算法與蟻群算法比較結(jié)果

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

5 結(jié) 論

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

[1] VASQUEZ M,HAO J K.A “l(fā)ogic-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] 朱新新,譚躍進,鄧宏鐘,等.求解成像衛(wèi)星調(diào)度問題的改進蟻群算法[J].科學(xué)技術(shù)與工程,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] 姜維,龐秀麗,郝會成.成像衛(wèi)星協(xié)同任務(wù)規(guī)劃模型與算法[J].系統(tǒng)工程與電子技術(shù),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] 黃生俊,邢立寧,郭波.基于改進模擬退火的多星任務(wù)規(guī)劃方法[J].科學(xué)技術(shù)與工程,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] 孫凱,邢立寧,陳英武.基于分解優(yōu)化策略的多敏捷衛(wèi)星聯(lián)合對地觀測調(diào)度[J].計算機集成制造系統(tǒng),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] 李泓興,豆亞杰,鄧宏鐘,等.基于改進蟻群算法的成像衛(wèi)星調(diào)度方法[J].計算機應(yīng)用,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.

(責(zé)任編輯 萬倫來)

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

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

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

10.3969/j.issn.1003-5060.2017.07.025

TP391.9

A

1003-5060(2017)07-0995-04