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

章 密, 胡笑旋

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

?

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

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

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

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

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

0 引 言

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

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

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

1 問題描述

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

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

1.1 時(shí)間窗

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

1.2 觀測(cè)過渡時(shí)間

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

1.3 能量消耗

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

1.4 任務(wù)時(shí)效性

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

1.5 本文假設(shè)

(1) 衛(wèi)星在觀測(cè)某一個(gè)地面目標(biāo)時(shí),在與該地面目標(biāo)的可見時(shí)間窗開始時(shí)間進(jìn)行觀測(cè)。

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

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

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

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

(1)

(3)

(4)

(5)

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

(6)

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

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

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

3 遺傳算法

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

3.1 編碼

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

圖2 編碼示意圖

3.2 初始化

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

pi=vi/di

(7)

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

算法1 任務(wù)插入算法(以觀測(cè)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í)行的觀測(cè)任務(wù)數(shù)量占所有觀測(cè)任務(wù)數(shù)量的比例,以及已執(zhí)行的觀測(cè)任務(wù)的權(quán)重之和占所有觀測(cè)任務(wù)的權(quán)重之和的比例,表達(dá)式如下:

(8)

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

3.4 交叉

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

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

3.5 變異

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

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

4.3 與蟻群算法的比較

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

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

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

5 結(jié) 論

多星調(diào)度問題是成像任務(wù)規(guī)劃問題中重要的內(nèi)容。本文首先建立了多星調(diào)度整數(shù)規(guī)劃模型,模型中考慮圈次的能量約束;然后闡述引入按圈次進(jìn)行交叉變異的遺傳算法;用STK提供仿真數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析,通過與經(jīng)典蟻群算法進(jìn)行比較,實(shí)驗(yàn)結(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] 朱新新,譚躍進(jìn),鄧宏鐘,等.求解成像衛(wèi)星調(diào)度問題的改進(jìn)蟻群算法[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] 姜維,龐秀麗,郝會(huì)成.成像衛(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] 黃生俊,邢立寧,郭波.基于改進(jìn)模擬退火的多星任務(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)合對(duì)地觀測(cè)調(diào)度[J].計(jì)算機(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] 李泓興,豆亞杰,鄧宏鐘,等.基于改進(jìn)蟻群算法的成像衛(wèi)星調(diào)度方法[J].計(jì)算機(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

國(guó)家自然科學(xué)基金創(chuàng)新研究群體資助項(xiàng)目(71521001);國(guó)家自然科學(xué)基金資助項(xiàng)目(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