基于Transformer層次預(yù)測的多星應(yīng)急觀測任務(wù)規(guī)劃方法

羅棕，杜春，陳浩，彭雙，李軍

國防科技大學(xué) 電子科學(xué)學(xué)院，長沙 410073

隨著衛(wèi)星觀測技術(shù)不斷發(fā)展，對地觀測衛(wèi)星已成為獲取地震、洪澇、海嘯等突發(fā)事件災(zāi)情的重要手段，觀測信息可以幫助地面人員在第一時(shí)間掌握災(zāi)區(qū)受災(zāi)情況。當(dāng)面臨較為密集的觀測請求時(shí)，單顆對地觀測衛(wèi)星往往效能不足，而多星協(xié)同觀測能夠有效響應(yīng)觀測需求。在應(yīng)急條件下，多星任務(wù)規(guī)劃不僅需要考慮復(fù)雜的約束因素(星載存儲(chǔ)空間、星上能源消耗、側(cè)擺角等)，而且還應(yīng)考慮觀測任務(wù)的強(qiáng)時(shí)效性[1]，任務(wù)必須在規(guī)定的時(shí)限內(nèi)完成，否則任務(wù)就會(huì)失效。目前關(guān)于衛(wèi)星應(yīng)急任務(wù)規(guī)劃的研究多是單獨(dú)優(yōu)先規(guī)劃應(yīng)急任務(wù)，雖然保證了應(yīng)急任務(wù)的響應(yīng)時(shí)間但犧牲了常規(guī)任務(wù)的完成度，使整體規(guī)劃收益(簡稱收益)受到較大影響[2]。如何在兼顧收益與效率的前提下，完成多星應(yīng)急觀測任務(wù)規(guī)劃成為當(dāng)前亟需解決的問題。

為了提升多星任務(wù)規(guī)劃的計(jì)算效率，Mirror等[3]提出任務(wù)分解的方法，將多星任務(wù)規(guī)劃問題分解為任務(wù)分配主問題、單星任務(wù)規(guī)劃子問題。但是作者并未對如何分配任務(wù)提出求解策略。對此，Yao等[4]提出采用自適應(yīng)蟻群優(yōu)化算法求解任務(wù)分配問題，選用啟發(fā)式算法(HA)求解單星任務(wù)規(guī)劃問題具有更好的規(guī)劃收益，采用快速模擬退火算法(VFSA)求解單星任務(wù)規(guī)劃問題具有更高的求解效率，實(shí)現(xiàn)了兩種不同效果的求解算法。孫凱等[5]采用學(xué)習(xí)型遺傳算法求解任務(wù)分解問題，在迭代過程中不斷學(xué)習(xí)和提取知識(shí)，反饋并引導(dǎo)分配過程。白保存[6]、朱政霖[7]等將調(diào)度結(jié)果作為反饋信息用于調(diào)整任務(wù)分配過程，有效地提升了模型的求解效率，且取得相對較優(yōu)的規(guī)劃結(jié)果。當(dāng)前基于優(yōu)化分解的多星任務(wù)規(guī)劃方法多采用啟發(fā)式算法進(jìn)行求解，在兼顧收益的同時(shí)，規(guī)劃效率得到了很大地提升，但是啟發(fā)式算法的優(yōu)化方向具有一定程度的隨機(jī)性，且算法的初始解通常采用隨機(jī)方式生成，解的搜索空間較大，影響計(jì)算的效率。

近些年，為了幫助用戶預(yù)測衛(wèi)星觀測任務(wù)是否執(zhí)行，衛(wèi)星規(guī)劃領(lǐng)域提出了任務(wù)可調(diào)度性的概念。Li等[8]利用經(jīng)典機(jī)器學(xué)習(xí)方法決策樹和支持向量機(jī)實(shí)現(xiàn)了任務(wù)可調(diào)度性預(yù)測，證明了方法的有效性。隨著機(jī)器學(xué)習(xí)的興起，白國慶[9]、劉嵩[10]、邢立寧[11]等提出利用BP(Back Propagation)神經(jīng)網(wǎng)絡(luò)對衛(wèi)星任務(wù)可調(diào)度性進(jìn)行預(yù)測，實(shí)現(xiàn)了預(yù)測效果的提升，但是該方法忽略了觀測任務(wù)時(shí)序特征的學(xué)習(xí)。對此，Peng等[12]提出了一種基于LSTM(Long Short-Term Memory)的任務(wù)可調(diào)度性預(yù)測方法，將任務(wù)序列作為輸入，實(shí)現(xiàn)了任務(wù)時(shí)序特征的前后傳遞，預(yù)測準(zhǔn)確率得到進(jìn)一步提升，且計(jì)算過程快捷有效。任務(wù)可調(diào)度性的預(yù)測結(jié)果實(shí)質(zhì)是對衛(wèi)星規(guī)劃結(jié)果的0/1預(yù)測，對初始衛(wèi)星任務(wù)規(guī)劃的快速預(yù)測具有很大的指導(dǎo)意義。

從機(jī)器學(xué)習(xí)角度分析，多星任務(wù)規(guī)劃問題的輸入是由多個(gè)觀測任務(wù)組成的序列，輸出也是由相應(yīng)任務(wù)類別組成的等長序列，輸入與輸出之間存在一一對應(yīng)的映射關(guān)系，因而多星任務(wù)規(guī)劃問題是一個(gè)seq2seq問題[13]。當(dāng)前解決seq2seq問題的主流架構(gòu)有：卷積神經(jīng)網(wǎng)絡(luò)[14]、循環(huán)神經(jīng)網(wǎng)絡(luò)[13]。卷積神經(jīng)網(wǎng)絡(luò)易于并行化，卻不適合捕捉變長序列內(nèi)的依賴關(guān)系，循環(huán)神經(jīng)網(wǎng)絡(luò)適合捕捉長距離變長序列的依賴，但是卻難以實(shí)現(xiàn)并行化處理序列[15]。為此，2017年谷歌提出了一種新的seq2seq模型——Transformer[15]。該模型采用與卷積神經(jīng)網(wǎng)絡(luò)、循環(huán)神經(jīng)網(wǎng)絡(luò)完全不同的結(jié)構(gòu)，并且在機(jī)器翻譯上表現(xiàn)出更優(yōu)越的性能。2018年谷歌又提出用于語義理解的預(yù)訓(xùn)練模型BERT[16]，一種基于Transformer的雙向深層預(yù)訓(xùn)練模型。BERT在由斯坦福大學(xué)發(fā)起的國際權(quán)威機(jī)器閱讀理解評測SQuAD1.1挑戰(zhàn)賽中兩個(gè)衡量指標(biāo)上優(yōu)于人類表現(xiàn)，此外還在11種不同自然語言處理測試中創(chuàng)出最優(yōu)成績。

為此，本文提出一種基于Transformer層次預(yù)測的多星應(yīng)急觀測任務(wù)規(guī)劃方法(簡稱TTH)。TTH將多星觀測任務(wù)規(guī)劃問題的求解過程分解為任務(wù)可調(diào)度性預(yù)測、任務(wù)分配、優(yōu)化調(diào)整。如圖1 所示，首先利用基于Transformer的任務(wù)可調(diào)度性預(yù)測模型對待規(guī)劃的任務(wù)集合進(jìn)行預(yù)測，得到預(yù)執(zhí)行任務(wù)集合與不執(zhí)行任務(wù)集合，縮小任務(wù)分配的范圍，使任務(wù)規(guī)劃的收益接近最佳。然后基于Transformer的任務(wù)分配模型對預(yù)執(zhí)行任務(wù)集合進(jìn)行衛(wèi)星分配，得到與最優(yōu)解較為相似的初始規(guī)劃方案。最后利用基于隨機(jī)爬山的約束修正法消除任務(wù)可調(diào)度性預(yù)測模型和任務(wù)分配模型中因預(yù)測偏差引發(fā)的不合理問題(任務(wù)沖突、任務(wù)過飽和等)，輸出可執(zhí)行的觀測方案。TTH將機(jī)器學(xué)習(xí)方法與啟發(fā)式算法相結(jié)合用于解決衛(wèi)星觀測任務(wù)快速規(guī)劃問題，利用機(jī)器學(xué)習(xí)模型為啟發(fā)式算法預(yù)測高價(jià)值的初始解，該步驟可以有效減少啟發(fā)式算法的搜索計(jì)算量，在較短的時(shí)間內(nèi)獲取收益較高的可行解。相比于單獨(dú)優(yōu)先規(guī)劃應(yīng)急任務(wù)的優(yōu)化算法[2]，TTH可以在短時(shí)間內(nèi)完成任務(wù)的重新規(guī)劃，實(shí)現(xiàn)收益與計(jì)算效率的兼顧。

圖1 所提方法流程圖Fig.1 Flow chart of proposed method

論文組織如下：第1節(jié)構(gòu)建多星觀測任務(wù)規(guī)劃的數(shù)學(xué)模型；第2節(jié)設(shè)計(jì)基于層次預(yù)測的規(guī)劃算法；第3節(jié)是實(shí)驗(yàn)結(jié)果對比與分析；第4節(jié)是總結(jié)，并提出下一步研究方向。

1 多星觀測任務(wù)規(guī)劃問題建模

1.1 基本假設(shè)

本文研究的多星觀測任務(wù)規(guī)劃問題可描述為：在規(guī)定調(diào)度時(shí)間內(nèi)，已知有若干組基于約束條件集合和觀測衛(wèi)星集合的多星對地觀測歷史任務(wù)規(guī)劃數(shù)據(jù)，現(xiàn)對一組待規(guī)劃的觀測任務(wù)進(jìn)行調(diào)度，要求在滿足約束條件的前提下，安排衛(wèi)星收益最大化地執(zhí)行集合中的觀測任務(wù)。為了便于后續(xù)研究，本文對該問題進(jìn)行如下合理假設(shè)：

1) 每個(gè)觀測任務(wù)只能執(zhí)行一次，不允許重復(fù)執(zhí)行。

2) 每個(gè)衛(wèi)星同一時(shí)間只能執(zhí)行一個(gè)觀測任務(wù)。

3) 衛(wèi)星執(zhí)行的觀測任務(wù)不允許拆分。

4) 假設(shè)調(diào)度時(shí)間的跨度較長，觀測任務(wù)呈均勻分布，單顆衛(wèi)星實(shí)際執(zhí)行的任務(wù)數(shù)量較少，任務(wù)間的平均間隔時(shí)間遠(yuǎn)遠(yuǎn)大于任務(wù)轉(zhuǎn)換所需時(shí)間，可忽略衛(wèi)星觀測任務(wù)間轉(zhuǎn)換時(shí)間。

1.2 參數(shù)及決策變量定義

1) 觀測任務(wù)集合X={x1，x2,…,xn}，n為觀測任務(wù)總數(shù)。

2) 成像衛(wèi)星集合S={s1,s2,…,sm}，m為成像衛(wèi)星總數(shù)。

3) 觀測任務(wù)收益pi，觀測任務(wù)xi的收益越高，被執(zhí)行的概率越高。此處定義觀測任務(wù)xi的收益pi∈[1,10]，最高收益為10。

4) 觀測時(shí)長需求ti，用戶對觀測任務(wù)提出的觀測時(shí)長要求。此處定義觀測時(shí)長需求ti∈[10,59]。

8) 最長工作時(shí)間Tj，表示衛(wèi)星sj在調(diào)度時(shí)間內(nèi)觀測總時(shí)長的最大值。

9) 最大存儲(chǔ)消耗Bj，表示衛(wèi)星sj在調(diào)度時(shí)間E內(nèi)存儲(chǔ)總消耗的最大值。

10) 觀測任務(wù)可調(diào)度性決策變量yi，yi=0表示觀測任務(wù)xi預(yù)測為不執(zhí)行，yi=1表示觀測任務(wù)xi預(yù)測為執(zhí)行。

1.3 約束條件定義

基于上述假設(shè)和參數(shù)定義，參考文獻(xiàn)[17-19]中關(guān)于多星任務(wù)規(guī)劃建模約束條件，本文主要考慮以下約束條件：

1) 優(yōu)化目標(biāo)：本文定義多星任務(wù)規(guī)劃的優(yōu)化目標(biāo)是在滿足所有約束條件的情況下，衛(wèi)星集合S收益最大化地執(zhí)行待觀測任務(wù)集合X。計(jì)算公式為

(1)

2) 觀測時(shí)長需求：衛(wèi)星執(zhí)行觀測任務(wù)的觀測時(shí)長要與用戶的觀測時(shí)長需求一致，不允許任務(wù)拆分，表達(dá)式為

(2)

式中：i∈[1,n],j∈[1,m]。

3) 最長工作時(shí)間：衛(wèi)星的觀測活動(dòng)存在間歇性，總的觀測時(shí)間越長，星上的能耗越多，可用于能量補(bǔ)充、數(shù)據(jù)傳輸?shù)臅r(shí)間越少。此外，衛(wèi)星對地面目標(biāo)進(jìn)行觀測時(shí)，星上能量的補(bǔ)充非常少，通常忽略不計(jì)。衛(wèi)星sj在調(diào)度時(shí)間E內(nèi)觀測總時(shí)長不大于最長工作時(shí)間Tj，即

(3)

式中：j∈[1,m]。

4) 最大存儲(chǔ)消耗：衛(wèi)星對地面目標(biāo)進(jìn)行觀測時(shí)會(huì)產(chǎn)生大量的觀測數(shù)據(jù)，而星載存儲(chǔ)空間是有限的，數(shù)據(jù)傳輸只能在有限窗口進(jìn)行。為了簡化問題，本文定義衛(wèi)星sj在調(diào)度時(shí)間E內(nèi)存儲(chǔ)總消耗不大于最大存儲(chǔ)消耗Bj：

(4)

式中：j∈[1,m]。

5) 觀測時(shí)間窗：每顆衛(wèi)星同一時(shí)間只能執(zhí)行一個(gè)任務(wù)，相同衛(wèi)星的觀測時(shí)間窗不能重疊。表達(dá)式為

(5)

式中：i∈[1,n],j∈[1,n],k∈[1,m]。

考慮上述約束條件，本文選用觀測任務(wù)的收益，觀測時(shí)長需求，各星對應(yīng)的觀測時(shí)間窗起始、結(jié)束時(shí)間，各星對應(yīng)的存儲(chǔ)消耗，各星實(shí)際對應(yīng)的觀測時(shí)長，相同衛(wèi)星中相鄰任務(wù)時(shí)間窗的時(shí)間間隔作為觀測任務(wù)集合X的特征屬性。

2 基于層次預(yù)測的規(guī)劃算法

本文選用基于注意力機(jī)制的Transformer來構(gòu)建任務(wù)可調(diào)度性預(yù)測模型和任務(wù)分配模型，通過注意力機(jī)制去捕獲觀測任務(wù)與其他任務(wù)之間的依賴關(guān)系來實(shí)現(xiàn)對每個(gè)任務(wù)分類的預(yù)測，并且模型訓(xùn)練時(shí)可以進(jìn)行并行化計(jì)算。

2.1 放縮點(diǎn)積注意力

點(diǎn)積的幾何含義是計(jì)算兩個(gè)向量之間的相似度，點(diǎn)積越大，相似度越高。Transformer采用放縮點(diǎn)積注意力[20](Scaled Dot-Product Attention)來計(jì)算注意力數(shù)值，有關(guān)公式為

(6)

式中：Q表示查詢；K表示鍵；V表示值。當(dāng)放縮點(diǎn)積注意力中Q=K=V時(shí)，放縮點(diǎn)積注意力機(jī)制也稱為自注意力機(jī)制。式(6)中:dk表示Q與K矩陣的列數(shù)，作用是防止內(nèi)積過大。

在多星任務(wù)規(guī)劃問題中，Q、K、V由輸入觀測任務(wù)的特征矩陣線性變化所得，且存在Q=K=V的關(guān)系，矩陣中的每一行都代表著一個(gè)觀測任務(wù)的特征向量。Q與K的點(diǎn)積運(yùn)算實(shí)現(xiàn)了每一個(gè)觀測任務(wù)與所有觀測任務(wù)的相似度計(jì)算，經(jīng)Softmax歸一化之后即可獲得單個(gè)觀測任務(wù)與全部觀測任務(wù)之間的關(guān)聯(lián)性。最后將歸一化后的注意力權(quán)重與V進(jìn)行加權(quán)求和，實(shí)現(xiàn)了每一個(gè)觀測任務(wù)的規(guī)劃特征提取。

2.2 多頭注意力機(jī)制

如圖2所示，多頭注意力機(jī)制[21](Multi-head Attention)首先由輸入X經(jīng)過線性變化得到h組不同的Qi、Ki、Vi，然后每組Qi、Ki、Vi均進(jìn)行放縮點(diǎn)積注意力計(jì)算輸出headi，最后headi將進(jìn)行拼接，經(jīng)過線性變化之后得到輸出矩陣。

圖2 多頭注意力機(jī)制的結(jié)構(gòu)模型Fig.2 Multi-head attention architecture

輸入觀測任務(wù)特征矩陣的不同的線性變化可得到不同的[Qi,Ki,Vi]，每組[Qi,Ki,Vi]所關(guān)注的細(xì)節(jié)不同，通過多次放縮點(diǎn)積注意力計(jì)算可實(shí)現(xiàn)不同子空間的規(guī)劃特征提取，實(shí)現(xiàn)對不同約束條件的建模表達(dá)。有關(guān)公式為

[V1,V2,…,Vh]=XWV

(7)

[K1,K2,…,Kh]=XWK

(8)

[Q1,Q2,…,Qh]=XWQ

(9)

headi=Attention(Qi,Ki,Vi)

(10)

MultiHead(Q,K,V)=

Concat(head1,head2,…,headh)WO

(11)

式中:X∈Rn×d；WQ∈Rd×d；WK∈Rd×d；WV∈Rd×d,WO∈Rd×d；n表示觀測任務(wù)數(shù)量；d表示觀測任務(wù)的特征數(shù)量，d能被h整除。

2.3 預(yù)測模型

如圖3 預(yù)測模型結(jié)構(gòu)框圖所示，預(yù)測模型由多層Transformer Layer和全連接層組成。Transformer Layer由多頭注意力機(jī)制、求和與歸一化、前饋神經(jīng)網(wǎng)絡(luò)3種結(jié)構(gòu)組成，上一層的輸出傳遞到下一層，總共疊加了M次。

圖3 預(yù)測模型結(jié)構(gòu)框圖Fig.3 Block diagram of prediction model

1) 求和與歸一化

求和與歸一化(Add & Norm)由兩部分組成：求和、歸一化，有關(guān)計(jì)算公式為

Z=Norm(X+MultiHead(X))

(12)

Y=Norm(Z+FeedForward(Z))

(13)

式中：X表示模型輸入；Z表示第1次求和與歸一化輸出，同理Y表示第2次求和與歸一化輸出。求和可以幫助網(wǎng)絡(luò)提升訓(xùn)練效果，關(guān)注訓(xùn)練前后差異部分變化。對求和結(jié)果標(biāo)準(zhǔn)化的目的是對神經(jīng)元輸入進(jìn)行標(biāo)準(zhǔn)化，使得均值方差一致，加快網(wǎng)絡(luò)收斂。

2) 前饋神經(jīng)網(wǎng)絡(luò)

前饋(Feed Forward)神經(jīng)網(wǎng)絡(luò)由2個(gè)全連接層組成，有關(guān)公式為

FeedForward(Z)=ReLu(ZW1+b1)W2+b2

(14)

式中：Z表示輸入，第1層全連接輸出經(jīng)過激活函數(shù)Relu的處理，第2層全連接輸出未經(jīng)非線性函數(shù)處理。

3) 全連接層及損失函數(shù)

輸入數(shù)據(jù)經(jīng)過多層Transformer Layer特征提取之后，輸出被傳輸?shù)饺B接層，經(jīng)過非線性處理之后，由Softmax函數(shù)輸出相應(yīng)類別的概率。

為了訓(xùn)練網(wǎng)絡(luò)，本文選用交叉熵計(jì)算損失，在任務(wù)可調(diào)度性預(yù)測模型中，損失函數(shù)為

(15)

式中：c表示預(yù)測結(jié)果的種類，取值上限在任務(wù)可調(diào)度性預(yù)測模型中為1，在任務(wù)分配預(yù)測模型中為m；i為觀測任務(wù)；yic表示模型預(yù)測結(jié)果；pic為Softmax的輸出，表示觀測任務(wù)xi在預(yù)測結(jié)果為c時(shí)的預(yù)測概率。

上述內(nèi)容即為TTH中機(jī)器學(xué)習(xí)模型結(jié)構(gòu)介紹。任務(wù)可調(diào)度性預(yù)測模型與任務(wù)分配模型運(yùn)用了相同的網(wǎng)絡(luò)結(jié)構(gòu)，但是模型輸入、輸出不同。任務(wù)可調(diào)度性預(yù)測模型與任務(wù)分配模型均使用同一套訓(xùn)練數(shù)據(jù)集，但是數(shù)據(jù)集的標(biāo)簽不同，任務(wù)可調(diào)度性預(yù)測模型的標(biāo)簽屬于[0,1]，任務(wù)分配模型的標(biāo)簽屬于[0,1,…，m]，后者比前者更加精細(xì)。在輸入特征方面，可調(diào)度預(yù)測模型輸入為任務(wù)的特征(見1.3節(jié))；而任務(wù)分配模型輸入同時(shí)包含任務(wù)可調(diào)度性預(yù)測模型的輸入數(shù)據(jù)和標(biāo)簽數(shù)據(jù)。

在訓(xùn)練過程中，任務(wù)可調(diào)度性預(yù)測模型與任務(wù)分配模型均獨(dú)立進(jìn)行訓(xùn)練，使用同一套數(shù)據(jù)集，不存在相互影響。測試時(shí)，將兩個(gè)網(wǎng)絡(luò)串聯(lián)在一起，任務(wù)分配模型輸入數(shù)據(jù)中所需的任務(wù)可調(diào)度性特征由任務(wù)可調(diào)度性預(yù)測模型預(yù)測所得。

2.4 基于隨機(jī)爬山的約束修正算法

TTH優(yōu)化調(diào)整的思想是在初始解的鄰域范圍內(nèi)搜索最優(yōu)解，在兼顧收益與計(jì)算耗時(shí)的同時(shí)，輸出可行規(guī)劃方案。相應(yīng)的方法功能為任務(wù)沖突消除、任務(wù)分配優(yōu)化、超限任務(wù)剔除、空缺任務(wù)補(bǔ)充。為此，本文選用基于隨機(jī)爬山的約束修正算法作為優(yōu)化算法。

隨機(jī)爬山算法[22]是一種啟發(fā)式算法，通過與周圍相鄰節(jié)點(diǎn)進(jìn)行值的比對，如果優(yōu)于當(dāng)前節(jié)點(diǎn)取值，則替換當(dāng)前節(jié)點(diǎn)，循環(huán)反復(fù)直至搜索到鄰域最優(yōu)節(jié)點(diǎn)，否則跳出搜索。由于完全循環(huán)的搜索優(yōu)化會(huì)極大的消耗時(shí)間，所以TTH對隨機(jī)爬山算法的終止條件進(jìn)行了改進(jìn),通過不斷的修正循環(huán)條件來獲取最終的規(guī)劃結(jié)果。優(yōu)化調(diào)整過程中為衡量節(jié)點(diǎn)的狀態(tài)，引導(dǎo)任務(wù)分配調(diào)整，本文定義節(jié)點(diǎn)的狀態(tài)函數(shù)為各個(gè)衛(wèi)星資源空余部分的乘積的總和，有關(guān)公式為

Jlack=

(16)

式(16)可以使得隨機(jī)爬山算法在搜索過程中通過調(diào)整任務(wù)的分配使得資源的消耗更低，實(shí)現(xiàn)相同的觀測任務(wù)占用更少的觀測資源消耗，目的是為下一步觀測任務(wù)補(bǔ)充騰出“空間”。基于隨機(jī)爬山的約束修正算法具體計(jì)算步驟如圖4所示。

圖4 基于隨機(jī)爬山的約束修正算法流程圖Fig.4 Flow chart of constraint correction algorithm based on random hill climbing

步驟1在對鄰域搜索之前，將相同衛(wèi)星分組的任務(wù)進(jìn)行統(tǒng)一編碼，預(yù)測不執(zhí)行的任務(wù)均編碼為0，各個(gè)衛(wèi)星所屬任務(wù)按照衛(wèi)星不同依次編碼為1，2,…,m。

步驟2計(jì)算各個(gè)衛(wèi)星所屬任務(wù)與相鄰任務(wù)的時(shí)間間隔、觀測任務(wù)的實(shí)際觀測時(shí)長。

步驟3判斷觀測任務(wù)時(shí)間窗是否滿足約束條件。若否，則選擇收益損失最小的優(yōu)化方案，將不合理的觀測任務(wù)移出至不執(zhí)行觀測任務(wù)集合；若是，則進(jìn)入步驟4。

步驟4計(jì)算當(dāng)前節(jié)點(diǎn)中各個(gè)衛(wèi)星的觀測總時(shí)長、存儲(chǔ)總消耗，判斷是否超出衛(wèi)星最大負(fù)載。若是，則選擇收益損失最小的優(yōu)化方案，將部分觀測任務(wù)移出至不執(zhí)行觀測任務(wù)集合，使得規(guī)劃方案滿足資源消耗的限制；若否，則進(jìn)入步驟5。

步驟5計(jì)算當(dāng)前各個(gè)衛(wèi)星的觀測總時(shí)長、存儲(chǔ)總消耗，判斷是否能夠進(jìn)行任務(wù)補(bǔ)充。若是，則在滿足約束的前提條件下從不執(zhí)行的任務(wù)集合中選取收益最大的補(bǔ)充方案；若否，則進(jìn)入步驟6。

步驟6對當(dāng)前節(jié)點(diǎn)的觀測任務(wù)分配狀況進(jìn)行隨機(jī)爬山算法優(yōu)化。首先設(shè)定隨機(jī)爬山算法的搜索次數(shù)，然后根據(jù)當(dāng)前各個(gè)衛(wèi)星的觀測總時(shí)長、存儲(chǔ)總消耗確定優(yōu)化的目標(biāo)衛(wèi)星，對該衛(wèi)星內(nèi)觀測任務(wù)進(jìn)行鄰域搜索，搜索范圍為其他衛(wèi)星內(nèi)觀測任務(wù)。重復(fù)隨機(jī)爬山搜索優(yōu)化直至滿足搜索截至條件。任務(wù)分配調(diào)整之后從不執(zhí)行觀測任務(wù)中進(jìn)行收益最大化補(bǔ)充。

步驟7輸出當(dāng)前節(jié)點(diǎn)的任務(wù)規(guī)劃方案。

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)平臺(tái)：實(shí)驗(yàn)計(jì)算機(jī)配置為Inter(R) Core(TM) i7-9750H CPU @2.60 GHz，運(yùn)行內(nèi)存8.0 GHz，操作系統(tǒng)為Windows10。

1) 數(shù)據(jù)準(zhǔn)備：目前多星觀測任務(wù)規(guī)劃暫無公開的標(biāo)準(zhǔn)數(shù)據(jù)集。本次實(shí)驗(yàn)使用第1節(jié)描述的多星觀測任務(wù)規(guī)劃模型構(gòu)建約束集合，設(shè)定2018年8月18日00:00:00—2018年8月18日23:59:59為調(diào)度時(shí)間，選用成像衛(wèi)星SPOT-5、SPOT-6、SPOT-7、WORLDVIEW-1、WORLDVIEW-2、WORLDVIEW-3、WORLDVIEW-4組成衛(wèi)星集合，并采用真實(shí)衛(wèi)星軌道數(shù)據(jù)進(jìn)行仿真。參照文獻(xiàn)[23]中采用的觀測目標(biāo)構(gòu)造方法，在緯度-70°～70°、 經(jīng)度-180°～180°的范圍內(nèi)隨機(jī)生成1 000個(gè)點(diǎn)目標(biāo)組成觀測目標(biāo)集合，觀測目標(biāo)集合分布狀態(tài)如圖5所示。

圖5 點(diǎn)目標(biāo)分布圖Fig.5 Point target distribution map

2) 實(shí)驗(yàn)數(shù)據(jù)：本文實(shí)驗(yàn)所用數(shù)據(jù)均為仿真數(shù)據(jù)，共收集了3種應(yīng)用場景的非應(yīng)急觀測任務(wù)數(shù)據(jù)集：第1種場景下對地觀測衛(wèi)星數(shù)量為3，每組數(shù)據(jù)包含100個(gè)觀測目標(biāo)，共有5 350組多星觀測任務(wù)規(guī)劃數(shù)據(jù)；第2種場景下對地觀測衛(wèi)星數(shù)量為5，每組數(shù)據(jù)包含200個(gè)觀測目標(biāo)，共有5 350組多星觀測任務(wù)規(guī)劃數(shù)據(jù)；第3種場景下對地觀測衛(wèi)星數(shù)量為7，每組數(shù)據(jù)包含300個(gè)觀測目標(biāo)，共有5 350組多星觀測任務(wù)規(guī)劃數(shù)據(jù)。觀測目標(biāo)的觀測時(shí)間窗由STK 11軟件計(jì)算所得，標(biāo)簽由IBM公司的數(shù)學(xué)規(guī)劃軟件ILOG CPLEX Optimizer 12.6.3計(jì)算所得。由于觀測任務(wù)具有多個(gè)時(shí)間窗，為此本文數(shù)據(jù)按照觀測任務(wù)中SPOT-5觀測時(shí)間窗的開始時(shí)間進(jìn)行排序。每個(gè)觀測任務(wù)數(shù)據(jù)由對應(yīng)的特征數(shù)據(jù)組成，實(shí)驗(yàn)中用于機(jī)器學(xué)習(xí)的訓(xùn)練數(shù)據(jù)占比60%，驗(yàn)證數(shù)據(jù)占比20%，測試數(shù)據(jù)占比20%。

3.1 規(guī)劃算法性能測試

為測試TTH的性能，此處選用CPLEX中的求解引擎CPLEX優(yōu)化器和標(biāo)準(zhǔn)遺傳算法(Genetic Algorithm，GA)作為比較對象，分別對不同場景下的100組觀測任務(wù)序列進(jìn)行計(jì)算，結(jié)果如表1所示。表中收益指算法最終規(guī)劃方案的平均收益；耗時(shí)指算法最終規(guī)劃方案的平均計(jì)算耗時(shí)；收益比值為算法平均收益與表1中最大收益的比值；耗時(shí)比值定義為算法平均耗時(shí)與表1中最小耗時(shí)的比值。耗時(shí)增幅為上一規(guī)模耗時(shí)與當(dāng)前規(guī)模耗時(shí)的比值。對表1作如下分析：

表1 規(guī)劃算法性能比較Table 1 Performance comparison planning algorithms

1) 從表1中收益數(shù)據(jù)可以得出，與CPLEX相比，隨著任務(wù)規(guī)劃場景的變化，TTH收益比值與CPLEX收益比值相差均不超過1%。與GA相比，隨著任務(wù)規(guī)劃場景的復(fù)雜化，GA收益比值均低于TTH收益比值。這說明TTH的觀測收益性能與CPLEX相當(dāng)，優(yōu)于GA。

2) 從表1耗時(shí)數(shù)據(jù)可以得出，隨著任務(wù)規(guī)劃規(guī)模的復(fù)雜化，TTH、CPLEX、GA耗時(shí)均在增加，TTH、CPLEX的增幅較小，GA的增幅最大，但是TTH的耗時(shí)遠(yuǎn)低于其他方法。所以，與CPLEX、GA相比，在不同的任務(wù)規(guī)劃場景下，TTH的計(jì)算效率相對更優(yōu)。

3) 綜合算法的收益、耗時(shí)及相應(yīng)的比值可得，TTH的任務(wù)規(guī)劃性能優(yōu)于CPLEX、GA。

3.2 模型有效性測試

為證明TTH子模型的有效性，此處在不同的場景下選取100組觀測任務(wù)序列作為測試數(shù)據(jù)，采用不同的隨機(jī)方式生成兩種初始規(guī)劃方案：

1) 1#隨機(jī)算法(簡稱1#)，對每組觀測序列中觀測任務(wù)進(jìn)行隨機(jī)任務(wù)可調(diào)度性預(yù)測，而后對預(yù)執(zhí)行任務(wù)進(jìn)行隨機(jī)衛(wèi)星分配。

2) 2#隨機(jī)算法(簡稱2#)，經(jīng)TTH任務(wù)可調(diào)度性預(yù)測之后，采用隨機(jī)分配的方式，對預(yù)執(zhí)行任務(wù)進(jìn)行隨機(jī)衛(wèi)星分配。

采用TTH的基于隨機(jī)爬山的約束修正算法分別對1#、2#隨機(jī)算法初始規(guī)劃方案以及TTH的初始規(guī)劃方案(簡稱TTH)進(jìn)行優(yōu)化，得到3種不同的最終規(guī)劃方案，實(shí)驗(yàn)結(jié)果如表2所示。表中任務(wù)沖突度指在初始規(guī)劃方案中各衛(wèi)星觀測時(shí)間窗口出現(xiàn)重疊的平均任務(wù)數(shù)。任務(wù)沖突比值指初始規(guī)劃方案中任務(wù)沖突與表中任務(wù)最小沖突的比值。表中其他指標(biāo)定義與3.1節(jié)相同。通過數(shù)據(jù)的分析，可以得出如下結(jié)論：

表2 模型有效性測試Table 2 Testing of validity of models

1) 通過對相同規(guī)劃場景下不同規(guī)劃方法的分析可得，TTH的規(guī)劃收益最高，其次為2#規(guī)劃收益，1#規(guī)劃收益最低。在不同規(guī)劃場景下，1#收益始終低于TTH和2#收益，分析主要原因是任務(wù)規(guī)劃可調(diào)度性預(yù)測較好地將預(yù)執(zhí)行任務(wù)篩選出來，可以較好地保證后續(xù)規(guī)劃計(jì)算的收益，任務(wù)可調(diào)度性預(yù)測準(zhǔn)確率影響最終任務(wù)規(guī)劃方案的收益。

2) 比較表2中任務(wù)沖突指標(biāo)可以得出，1#、2#的任務(wù)沖突度隨著任務(wù)規(guī)劃規(guī)模的擴(kuò)大而增加。從不同場景下任務(wù)沖突比值可以看出，TTH任務(wù)規(guī)劃方案均能保持較低的任務(wù)沖突度，這表明對于不同規(guī)模的任務(wù)規(guī)劃場景，TTH的分配預(yù)測模型均能較好地避免任務(wù)沖突。

3) 通過對相同場景下不同規(guī)劃算法的耗時(shí)可以看出，1#、2#以及TTH均能夠保持相近的計(jì)算耗時(shí)，耗時(shí)比值較為接近。這說明基于隨機(jī)爬山的約束修正算法能夠快速地對初始規(guī)劃方案進(jìn)行優(yōu)化，搜索到可行解。

4) 上述結(jié)論驗(yàn)證了TTH中任務(wù)可調(diào)度性預(yù)測模型、任務(wù)分配模型和優(yōu)化算法的有效性。

3.3 Transformer與LSTM的性能對比

為測試TTH預(yù)測模型的性能，本文選用長短期記憶網(wǎng)絡(luò)(Long Short-Term Memory，LSTM)作為比較對象，采用控制變量的比較方式，構(gòu)建對比模型LTH、TLH、LLH，比較模型的任務(wù)收益、收益比值、耗時(shí)、耗時(shí)比值。實(shí)驗(yàn)結(jié)果如表3所示，通過分析得出以下結(jié)論：

1) 從表3中的收益和收益比值可以看出，在相同的規(guī)劃場景中，TTH的規(guī)劃收益要高于LTH的規(guī)劃收益，TLH的規(guī)劃收益要高于LLH的規(guī)劃收益，隨著規(guī)劃規(guī)模的復(fù)雜化，規(guī)劃收益的差距變大。由此可以看出Transformer的任務(wù)可調(diào)度性預(yù)測性能優(yōu)于LSTM。

2) 從表3中耗時(shí)可以得出，隨著場景規(guī)模的增大，TTH模型優(yōu)于TLH模型，LTH模型優(yōu)于LLH模型。由此可見，隨著任務(wù)規(guī)劃規(guī)模的增加，Transformer模型在任務(wù)分配效果上優(yōu)于LSTM模型。

3) 從表3任務(wù)沖突度可以看出，隨著場景的增加，初始規(guī)劃結(jié)果的任務(wù)沖突度增加，但是任務(wù)沖突度占任務(wù)規(guī)劃總數(shù)的比例在1%左右，相對較低。但是整體上TTH模型優(yōu)于TLH模型，LTH模型優(yōu)于LLH模型。

表3 Transformer與LSTM性能比較Table 3 Performance comparison between Transformer and LSTM

4) 綜合收益、耗時(shí)、任務(wù)沖突度的比較結(jié)果，Transformer在初始規(guī)劃方案預(yù)測上效果優(yōu)于LSTM。Transformer在注意力權(quán)重時(shí)不需要進(jìn)行時(shí)序信息的前后傳遞，而LSTM需要受序列長度的制約，隨著序列變長，時(shí)序信息的傳遞受到一定程度的影響。

注：表中TRAN表示Transformer。

4 結(jié) 論

本文提出了基于Transformer層次預(yù)測的多星應(yīng)急觀測任務(wù)規(guī)劃方法，采用任務(wù)分解的方式將多星任務(wù)規(guī)劃問題的求解過程分為：任務(wù)可調(diào)度性預(yù)測、任務(wù)分配和優(yōu)化調(diào)整3個(gè)部分。在文中設(shè)定的任務(wù)規(guī)劃條件下，與CPLEX優(yōu)化器、標(biāo)準(zhǔn)遺傳算法相比，TTH表現(xiàn)出耗時(shí)短，收益高的優(yōu)點(diǎn)。通過與隨機(jī)初始規(guī)劃方案對比，證明了TTH中任務(wù)可調(diào)度性預(yù)測模型、任務(wù)分配模型和優(yōu)化算法的有效性；與LSTM模型相比，Transformer任務(wù)可調(diào)度性預(yù)測和任務(wù)分配的性能相對更優(yōu)。

隨著衛(wèi)星數(shù)量的增多和觀測任務(wù)的增加，將對現(xiàn)有模型的學(xué)習(xí)能力帶來更大的挑戰(zhàn)，在下一步的研究工作中，需要構(gòu)建更加適應(yīng)問題的決策網(wǎng)絡(luò)，或是結(jié)合深度強(qiáng)化學(xué)習(xí)等技術(shù)進(jìn)行研究。