基于超啟發(fā)式的多星協(xié)同任務(wù)規(guī)劃算法研究

陳金勇，張 超，李艷斌

(1. 中國電子科技集團(tuán)公司航天信息應(yīng)用技術(shù)重點實驗室，石家莊 050081； 2. 中國電子科技集團(tuán)公司第五十四研究所，石家莊 050081)

0 引 言

衛(wèi)星對地觀測任務(wù)是利用其攜帶的光電遙感器或無線設(shè)備等有效載荷，從太空軌道上捕獲地面、海面和低空的重要目標(biāo)信息并將信息傳回地面接收站，如圖1所示。衛(wèi)星具有軌道高、探測范圍大、周期性強(qiáng)等特點，是執(zhí)行各類對地觀測任務(wù)的主要平臺。但衛(wèi)星在執(zhí)行任務(wù)的過程中，受到機(jī)動能力受限、時間窗口固定等約束，如何給衛(wèi)星分配合理的任務(wù)列表，以充分利用星上載荷執(zhí)行各類任務(wù)，是衛(wèi)星任務(wù)規(guī)劃研究中的主要問題之一。目前針對衛(wèi)星任務(wù)規(guī)劃問題的研究在系統(tǒng)建模技術(shù)和求解算法上取得了一定的成果。其中系統(tǒng)建模技術(shù)以混合整數(shù)規(guī)劃[1]、約束滿足模型[2]、多Agent技術(shù)[3-4]最為常見，前者主要運用數(shù)學(xué)規(guī)劃方法對確定性、靜態(tài)環(huán)境下的多任務(wù)規(guī)劃問題進(jìn)行建模，后者將多個衛(wèi)星或衛(wèi)星群刻畫成多Agent系統(tǒng)，從而利用多Agent技術(shù)實現(xiàn)多星、動態(tài)環(huán)境下的任務(wù)規(guī)劃系統(tǒng)建模；求解算法以遺傳算法[5-6]、蟻群算法[7-8]、粒子群算法[9]等并行程度較高的亞啟發(fā)式算法最為常見。

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

經(jīng)典優(yōu)化算法和智能算法的搜索空間是問題解空間，而超啟發(fā)式算法的搜索空間對象是各種經(jīng)典的優(yōu)化算法、啟發(fā)式算法和智能算法。文獻(xiàn)[10]指出超啟發(fā)式算法是一種高層次啟發(fā)式方法，能夠?qū)Φ讓右幌盗兴惴ㄟM(jìn)行管理和調(diào)度，并從中選擇合適的算法求解問題，而且還可以生成新的啟發(fā)式算法求解問題。經(jīng)典優(yōu)化算法和智能算法無法根據(jù)問題的規(guī)模確定算法的參數(shù)范圍，以及選擇其它算法協(xié)調(diào)求解優(yōu)化問題。文獻(xiàn)[11]認(rèn)為超啟發(fā)式算法的框架由兩層組成，底層是求解實際優(yōu)化問題的啟發(fā)規(guī)則、各種經(jīng)典算法以及智能算法；高層負(fù)責(zé)底層算法的管理與調(diào)度。根據(jù)計算結(jié)果反饋機(jī)制，高層算法管理與調(diào)度機(jī)制又可劃分為在線學(xué)習(xí)、離線學(xué)習(xí)以及無監(jiān)督學(xué)習(xí)[12]。文獻(xiàn)[13]運用蒙特卡洛超啟發(fā)式算法就考試日程安排問題進(jìn)行了求解，通過線性和指數(shù)概率函數(shù)選擇底層算法。實驗結(jié)果表明，蒙特卡洛超啟發(fā)式問題求解效果比現(xiàn)有的智能算法更好。

因此本文針對常規(guī)多星對地觀測任務(wù)規(guī)劃算法適應(yīng)性弱、魯棒性差,難以適應(yīng)實際工程需要的問題，采用超啟發(fā)式算法(Hyper-Heuristic Algorithm)的思路，研究一種新的算法應(yīng)用框架對多種算法的管理和調(diào)度，研究超啟發(fā)式多星對地觀測任務(wù)規(guī)劃模型和求解方法。

1 多星協(xié)同任務(wù)規(guī)劃調(diào)度模型

采用多個不同類型的遙感衛(wèi)星，實施分布式觀測，能夠以多尺度的時間、空間、譜段分辨率獲得多時段、多重空間覆蓋、多譜段、多極化的目標(biāo)電磁特征信息。這些信息能夠相互驗證和互補(bǔ)，減少目標(biāo)特征理解的不確定性，增加特征提取的全面性和精確性。通過適用的多源信息融合理論和技術(shù)，可達(dá)到對目標(biāo)的綜合感知，大幅度提高識別能力、定位精度能力。

1.1 參數(shù)定義及變量說明

1.2 多星協(xié)同任務(wù)規(guī)劃組合優(yōu)化模型

max:∑(TkPk+Tk)

s.t.

(1)

?Sj∈S,v∈Ij

(2)

?sj∈S,iu∈Ij,iv∈Ij

(3)

?sj∈S,ik∈Ij,r=1…nkj

(4)

?sj∈S,ik∈Ij,r=1…nkj

(5)

?sj∈S,ik∈Ij,r=1…nkj

(6)

?sj∈S,ik∈Ij,r=1…nkj

(7)

?sj∈S,ik∈Ij,gl∈G

(8)

?sj∈S,ik∈Ij,gl∈G

(9)

(10)

(11)

其中：目標(biāo)函數(shù)表示問題求解應(yīng)使得調(diào)度方案的收益最優(yōu)，即安排觀測的成像任務(wù)優(yōu)先級和成像任務(wù)安排數(shù)量最大。式(1)說明成像任務(wù)如果被執(zhí)行，只能在與某顆衛(wèi)星的某個可行時間窗口內(nèi)完成。式(2)說明為所有成像任務(wù)如果被執(zhí)行必定有唯一的前驅(qū)任務(wù)和后繼任務(wù)。式(3)說明了任一衛(wèi)星執(zhí)行的相鄰成像任務(wù)之間的時間推進(jìn)關(guān)系。式(4)和式(5)說明成像任務(wù)如果在與某顆衛(wèi)星的某個可行時間窗口內(nèi)執(zhí)行，任務(wù)的起止時間不能超出時間窗口范圍。式(6)和式(7)說明成像任務(wù)如果被執(zhí)行，那么其起止時間必須在用戶指定的有效期之內(nèi)。式(8)說明任意任務(wù)的觀測時間早于其數(shù)據(jù)傳輸時間；式(9)：說明衛(wèi)星觀測動作與數(shù)據(jù)傳輸動作之間不能在時間上沖突；式(10)說明了在指定時長時間段內(nèi)，衛(wèi)星累計開機(jī)時間不超過給定的最大值。式(11)說明了任意時刻星載存儲器占用不能超過衛(wèi)星的存儲容量上限限制。

2 超啟發(fā)式算法的實現(xiàn)

2.1 算法框架

超啟發(fā)式算法底層包括求解問題描述和用于求解問題的各種算法集合H={H1,H2,…,Hn}兩部分；高層由算法調(diào)度、算法選擇以及可接受解等三個功能組件構(gòu)成。超啟發(fā)式算法框架如圖2所示。

圖2 超啟發(fā)式算法的實現(xiàn)

算法調(diào)度組件，包括：(1)爬山算法，可以看作為局部鄰域搜索算法，用于評價候選解的質(zhì)量，目標(biāo)是產(chǎn)生較好的候選解；(2)變異算法，用于產(chǎn)生新的解空間；(3)用于評價算法的執(zhí)行效率的CPU運行時間；(4)算法選擇與算法學(xué)習(xí)機(jī)制等。

2.2 算法調(diào)度流程

算法調(diào)度流程說明如下：

步驟1：進(jìn)行初始化設(shè)置，設(shè)置超啟發(fā)式算法運行時間T、精英算法best_heuristic、算法運行效力評價因子α=0.5、算法選擇評價因子γ=0.5、當(dāng)前解current_solution、優(yōu)化目標(biāo)適應(yīng)度值fitness_change等；

步驟2：生成問題的初始解，并作為當(dāng)前解current_solution；

步驟3：計算底層算法集中各個算法的評價值E(hi)，i=1,2,…,m，有m個底層算法；

該步驟主要從算法的求解效果和算法的運行效率兩方面對算法進(jìn)行評價，算法評價函數(shù)為：

E(hi)=e1(hi)+e2(hk,hi)+e3(hi)

(12)

(13)

(14)

(15)

步驟4：選擇底層算法集中評價值最大的算法作為精英算法；

步驟5：運用精英算法對多星對地觀測任務(wù)規(guī)劃問題當(dāng)前解進(jìn)行優(yōu)化，得到新解new_solution以及精英算法的運行時間t(hi)；

步驟6：用新解減去當(dāng)前解得到優(yōu)化目標(biāo)適應(yīng)度值fitness_change，并將新解作為當(dāng)前解current_solution=new_solution；

步驟7：修改e1(hi)、e2(hk,hi)、e3(hi)函數(shù)；

步驟8：修改算法運行效力評價因子α和算法選擇評價因子γ；

(16)

γ=1-α

(17)

步驟9：判斷超啟發(fā)式算法運行時間是否達(dá)到設(shè)置的最大運行時間，若沒有達(dá)到，則跳到步驟3；否則，計算將當(dāng)前解作為多星對地觀測任務(wù)規(guī)劃最優(yōu)解。

上述步驟的基本流程如圖3所示。

圖3 算法調(diào)度流程

3 仿真實驗結(jié)果及分析

考慮到目前底層算法有兩類四種即雙染色體遺傳算法、雙蟻群算法、模擬退火算法以及禁忌搜索算法。從算法的種群規(guī)模分類，雙染色體遺傳算法、雙蟻群算法屬于群類算法，而模擬退火算法以及禁忌搜索算法屬于單解算法。因此，超啟發(fā)式算法對底層算法的調(diào)度規(guī)則是寬度搜索算法優(yōu)先，然后是運行深度搜索算法。針對本次仿真實驗，首先是運行雙染色體遺傳算法或雙蟻群算法，對問題解空間進(jìn)行規(guī)模搜索，獲得較好的解。然后運行模擬退火算法或禁忌搜索算法對當(dāng)前解進(jìn)行深度搜索，最終求出問題滿意解。

(1)雙染色體遺傳算法與模擬退火算法

對遺傳算法的參數(shù)設(shè)置如下：種群規(guī)模200、交叉概率0.9、變異概率0.1、迭代次數(shù)1000。模擬退火算法參數(shù)設(shè)置如下：初始溫度200、內(nèi)循環(huán)1000、外循環(huán)200、溫度衰減率0.95。當(dāng)雙染色體遺傳算法求解問題的迭代數(shù)到達(dá)設(shè)定的閾值或解的改善程度低于設(shè)定的閾值時，啟用模擬退火算法對雙染色體遺傳算法當(dāng)前解進(jìn)行深度搜索。

通過對觀測任務(wù)數(shù)分別為50、100、150以及200等4個不同規(guī)模算例，分別用超啟發(fā)式算法和模擬退火算法各自運行10次。兩種算法的而平均運行時間和目標(biāo)函數(shù)平均值如表1所示。

表1 超啟發(fā)式算法與模擬退火算法運行時間和目標(biāo)函數(shù)值比較

表7顯示超啟發(fā)式算法和模擬退火算法對4種不同規(guī)模算例進(jìn)行計算,比較兩個算法的平均運行時間和目標(biāo)函數(shù)平均值。超啟發(fā)式算法運行時間較長，但是超啟發(fā)式算法中的禁忌搜索算法平均運行時間低于單獨運行禁忌搜索算法平均運行時間。

圖4和圖5表明超啟發(fā)式算法求解問題效果優(yōu)于模擬退火算法，但是超啟發(fā)式算法運行時間較長。超啟發(fā)式算法中的模擬退火算法求解問題目標(biāo)函數(shù)平均值優(yōu)于單獨運行模擬退火算法求解問題目標(biāo)函數(shù)平均值。這是因為獨自運行模擬退火算法，初始解較差算法必須花費較長的時間對問題解空間進(jìn)行搜索，而且容易陷入局部最優(yōu)解。而超啟發(fā)式算法先運行遺傳算法，對問題解空間首先進(jìn)行寬度搜索，獲得較好的解作為下一個優(yōu)化算法的初始解，而后繼的模擬退火算法在當(dāng)前解的基礎(chǔ)上，對問題解空間進(jìn)行深度搜索，容易獲得問題滿意結(jié)。

圖4 超啟發(fā)式算法與模擬退火算法目標(biāo)函數(shù)平均值比較

圖5 超啟發(fā)式算法與模擬退火算法運行時間比較

(2)雙蟻群算法與禁忌搜索算法

雙蟻群算法和禁忌搜索算法的相關(guān)參數(shù)設(shè)置同第六章。當(dāng)雙蟻群算法求解問題的迭代數(shù)到達(dá)設(shè)定的閾值或解的改善程度低于設(shè)定的閾值時，啟用禁忌搜索算法對雙蟻群算法當(dāng)前解進(jìn)行深度搜索。兩種算法的而平均運行時間和目標(biāo)函數(shù)平均值如表2所示。

表2表明超啟發(fā)式算法對4種不同規(guī)模算例進(jìn)行計算,平均運行時間較長。但是超啟發(fā)式算法中的禁忌搜索算法平均運行時間低于單獨運行禁忌搜索算法平均運行時間。

表2 超啟發(fā)式算法與禁忌搜索算法運行時間和目標(biāo)函數(shù)值比較

圖6和圖7表明超啟發(fā)式算法求解問題效果優(yōu)于禁忌搜索算法，但是超啟發(fā)式算法運行時間較長。超啟發(fā)式算法中的禁忌搜索算法求解問題目標(biāo)函數(shù)平均值優(yōu)于單獨運行禁忌搜索算法求解問題目標(biāo)函數(shù)平均值。當(dāng)初始解較差時，禁忌搜索算法對問題解空間搜索時間較長，且容易陷入局部最優(yōu)解。而超啟發(fā)式算法先運行雙蟻群算法，對問題解空間首先進(jìn)行寬度搜索，獲得較好的解作為下一個優(yōu)化算法的初始解，而后繼的禁忌搜索算法在當(dāng)前解的基礎(chǔ)上，對問題解空間進(jìn)行深度搜索，容易獲得問題滿意結(jié)，算法的運行時間較短。

圖6 超啟發(fā)式算法與禁忌搜索算法目標(biāo)函數(shù)平均值比較

圖7 超啟發(fā)式算法與禁忌搜索算法運行時間比較

4 結(jié) 語

通過分析了成像衛(wèi)星對地觀測行為特征，給出了任務(wù)、衛(wèi)星、地面站等元素的形式化表達(dá)，建立了多星協(xié)同任務(wù)規(guī)劃組合優(yōu)化模型。并且建立超啟發(fā)式算法求解問題框架，在典型的智能算法(雙染色體遺傳算法、雙蟻群算法、模擬退火算法以及禁忌搜索算法)的基礎(chǔ)上，利用寬度搜索算法優(yōu)先，然后是運行深度搜索算法的啟發(fā)式規(guī)則，給出多星協(xié)同任務(wù)規(guī)劃超啟發(fā)式算法解的仿真結(jié)果和評價分析。