基于任務合成機制的多星調度問題

任送蓮, 孫海權, 靳 鵬

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

0 引 言

對地觀測衛星通過星載傳感器,包括可見光、多光譜、高光譜、超光譜、合成孔徑雷達等[1],獲取地面數據信息,因其具有覆蓋面積大、觀測范圍廣、數據生成快、成像效果好等優點,廣泛應用于軍事、農業、工業、氣象等領域。根據地面成像目標能否被衛星條帶一次覆蓋完成,將目標分為點目標和區域目標[2],衛星一次覆蓋條帶即可完成對點目標的觀測,區域目標需要先對其進行區域劃分,衛星多次過境形成多個覆蓋條帶方可完成對它的觀測,為簡化研究,本文主要研究成像衛星對點目標的觀測。

傳統模式下衛星對點目標均采用單任務觀測方式,即衛星傳感器在同一個偏轉角度下僅僅觀測一個元任務,如文獻[3-6]中的處理方式,這種方式能夠對目標以最佳角度成像,成像精度高,用戶滿意度最大。但是由于任務時間窗重疊,姿態轉換時間不夠充足等原因,導致觀測任務數量大大減少且資源使用效率極低。因此,近年來學者逐漸采用對任務合成觀測的方式來提高衛星資源使用率,增大任務觀測收益。如文獻[7]中的處理方式,綜合最小派系劃分思想將任務合成,然后依據特定規則刪除部分合成任務,該方法能夠有效減少衛星搜尋任務時的復雜度,同時存在刪除部分優解的風險。文獻[8-9]在單顆衛星已有的任務序列上采用動態規劃方法對任務合成,這種方式能夠一定程度上求得問題最優解,但是隨著任務規模的增大,計算復雜度會大幅度增加,無法有效求得全局最優解。文獻[10-13]提出了考慮合成的應急任務動態規劃問題,將實時到來的應急任務與已有的常規任務序列動態合成,這種處理方式更加符合實際,但是對原來的任務序列的魯棒性要求極高,否則將會耗費大量時間用于任務序列重新生成。此外,上述文獻[7-13]均采用“均值法”計算合成觀測角度,方式雖簡便易行,但是沒有考慮角度偏轉帶來的圖像過分扭曲造成的影響。

衛星調度問題屬于NP-Hard[14]問題,常見解決算法包括精確算法和近似算法,精確算法通常應用于小規模算例,如列生成和分支定界算法[15]等,大規模算例則常使用近似算法求解,包括模擬退火[16-17]、禁忌搜索[18]以及遺傳算法[19]等。蟻群優化(ant colony optimization,ACO)算法[20]最早由意大利學者Dorigo提出,隨著時間發展后人在其基礎上提出了許多改進機制,包括蟻群系統算法[21]、最大最小蟻群系統算法[22]、變異特征ACO算法[23]、混合二進制人造螞蟻算法[24]等。此外,文獻[25]提出了一種基于分布度均勻的自適應ACO算法,引入“聚度”衡量螞蟻路徑分布均勻情況,動態調整信息量更新策略和選擇路徑的概率,文獻[26]采用一種具有感覺和知覺特征的ACO算法,將絕對感覺閾限原理、差別感覺閾限原理以及韋伯定律依次應用于螞蟻搜索的初始、中間和結束階段,加快收斂速度的同時保證解的多樣性。雖然上述近似算法能在一定程度上獲得較優解,但也伴有陷入局部最優或收斂速度過慢的缺陷。

為有效避免以往研究的不足,本文考慮對任務合成觀測。基于合成任務集,采用基于任務合成的改進蟻群優化(improved ant colony optimization based on task merging, IACO-TM)算法高效生成任務序列,主要工作為以下4點:

(1) 設計一種多任務合成機制(multi-task merging mechanism,MTMM),綜合考慮角度約束、開機約束以及成像分辨率要求,對元任務合成,生成合成任務集。

(2) 提出一種自適應蟻窗策略,螞蟻使用輪盤賭方式選擇任務觀測時,動態調整當前任務的可達任務數量,實現螞蟻搜索空間的有效裁剪,同時兼顧隨機性與目的性,加快搜索速度。

(3) 設計一種強制擾動機制,當算法連續收斂于固定值的次數達到給定上限時,啟動擾動機制,重置對應路徑上的信息素,避免螞蟻在后期重復走該條路徑,算法過早停滯。

(4) 提出一種動態調節算法參數策略,算法前期與后期采用不同的螞蟻數量以及信息素揮發系數。依據算法前期歷次迭代的局部最優解重置信息素矩陣,為算法后期提供較優的初始解方案,實現算法前期加大搜索范圍,后期加快收斂速度的目標。

1 問題描述

本文主要考慮解決基于任務合成機制的多星調度問題。首先按照約束對元任務合成,然后將合成任務作為最小單元為其分配合適的衛星資源及時間窗[27],生成觀測任務序列。具體過程如圖1所示,衛星在運行軌道上選擇由單個元任務或多個元任務組成的合成任務觀測,每次成像獲得的數據暫時存放在衛星存儲器內,直到軌道上任務被遍歷完成。

圖1 衛星觀測過程示意圖

(1) 衛星資源。單顆衛星的多個屬性可用七元組表示,其中ID表示衛星編號,O表示單次最長開機時間,E表示星上能量存儲,C表示星上內存存儲,G表示傳感器角度偏轉范圍,W表示衛星單次覆蓋幅寬,R表示傳感器旋轉速率。衛星過境對地面掃描形成覆蓋條帶,如圖1中灰色區域所示,同時處于覆蓋條帶內的多個任務被一次觀測完成。通過變換傳感器角度,衛星可以連續完成多個滿足姿態轉換時間、開關機時間、存儲以及能量約束的任務。

(2) 元任務。元任務是指不需要對其進行區域劃分,衛星過境時單個覆蓋條帶內即可完成觀測的任務。單個元任務的多個屬性可用四元組表示,MD表示任務編號,TW表示任務觀測時間窗,包括開始觀測時間和結束觀測時間,BG表示最佳觀測角度,P表示觀測收益。衛星對元任務的單個觀測機會,我們稱之為觀測時間窗。為最大化觀測效益,我們必須為任務分配合適的時間窗成像,且不對任務重復觀測,觀測完成后獲得相應的觀測收益。

為便于問題求解,本文對成像衛星任務調度做出以下假設:① 由于傳感器角度偏轉引起的圖像分辨率變化計算度極為復雜,為方便研究,本文假定單個元任務的最低成像分辨率要求所對應的最大最小偏轉角度已知;② 不考慮衛星飛行過程中出現故障、天氣、云層、晝夜等氣象條件對觀測的影響。

2 任務合成

任務合成指的是衛星傳感器在同一個覆蓋條帶內以一個特定的偏轉角度將多個地理位置相近的點目標任務(元任務)按照某種規則組合為一個合成任務,規則包括角度約束和開機約束[28-29]。傳感器采用的特定偏轉角度必須保證單個元任務的成像分辨率均達到其最低要求,角度偏轉帶來的圖像扭曲在用戶接受范圍內。合成任務示意圖如圖2所示。

圖2 合成任務示意圖

2.1 合成優點

與傳統觀測模式相比,對任務合成觀測具有以下優點:

(1) 減少衛星傳感器姿態轉換次數。合成觀測時多個元任務允許傳感器采用同一角度觀測,觀測相同任務數量的情況下姿態轉換次數更少,滿足機動性能較差且單圈次姿態轉換次數有限的衛星需求,如HJ1A衛星。

(2) 增加觀測任務數量。對于具有時間窗重疊、姿態轉換時間不夠充足的任務,傳統觀測模式是從中選擇一個任務進行觀測,放棄其余任務。合成觀測時,衛星傳感器采用居中的觀測角度一次觀測多個地理位置相近的任務,避免因時間窗重疊或姿態轉換時間不夠充足而需要放棄部分任務,增加觀測任務數量。

(3) 減少能量消耗,增強衛星穩定性。傳感器旋轉過程中需要消耗大量能量,姿態轉換完成后,衛星仍需要部分時間穩定,在這個過程中,衛星無法對目標成像,減少姿態轉換次數后,能量消耗也隨之減少,同時增強衛星穩定性。

2.2 合成約束

(1) 角度約束

(2) 開機約束

2.3 合成任務屬性

(1) 合成角度

(2) 合成觀測收益

(3) 有效數據比

其中,分子表示單個元任務的觀測時間之和,分母表示合成任務的總觀測時間,有效數據與冗余數據示意圖如圖2所示。

2.4 合成算法

輸入元任務集合T

輸出合成任務集MT

步驟 3依次將衛星rj上編號為1,2,3,…的元任務作為合成任務的開始任務,將后序任務作為終止任務,對任務按照連續不跳過的原則嘗試合成,假定衛星rj上有3個元任務,對1,2合成,1,2,3合成,2,3合成,但不對1,3合成,檢驗角度約束和開機約束。

3 調度模型及求解算法

3.1 調度模型

(1) 符號設定

R={r1,r2,…,rj,…,rh}為衛星集合,rj表示第j顆衛星,共h顆衛星;

Δgj為衛星rj的覆蓋幅寬;

ΔOj為衛星rj的單次最長開機時間;

Cj為衛星rj的最大存儲容量;

c為單位時間衛星成像需要的存儲容量;

Ej為衛星rj單圈次可消耗的最大能量;

rate為衛星傳感器旋轉速率;

a為單位時間衛星成像所需的能量;

b為單位角度衛星姿態轉換所需的能量。

(2) 線性模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

3.2 改進ACO算法

ACO最初于1991年由意大利學者Dorigo等人提出[20],其靈感來源于自然界中真實蟻群覓食行為。研究表明,螞蟻在覓食過程中會釋放“信息素”標記行走路徑,信息素隨著時間推移部分揮發,部分留存下來用于引導螞蟻下一次尋找路徑。距離短的路徑上的信息素累積量大且累積速度快,而距離長的路徑上的信息素由于累積量少且不斷揮發,導致其濃度越來越低,最終使得所有螞蟻都聚集到距離最短的路徑上。然而,正是由于這種正反饋機理的作用,ACO同時伴隨著容易陷入局部最優的困境。因此,本文通過在螞蟻尋優過程中添加自適應蟻窗策略、強制擾動機制以及算法參數動態調節策略,有效提高了算法的全部尋優能力和收斂速度。

3.2.1 狀態轉移規則

3.2.2 信息素更新

每經過一次迭代信息素都將被更新,路徑上的信息素隨著迭代次數的增加動態調整,較優路徑上信息素累積量不斷增大,而較差路徑上的信息素不斷揮發,隨著時間的推移其正反饋機制作用越來越明顯,指導螞蟻聚集到最優路徑上。信息素更新方式為

3.2.3 改進機制

為在搜索全局最優與加快收斂速度之間尋求均衡,對基于任務合成的傳統ACO(traditional ACO based on task merging, TACO-TM)做出了部分改進,在算法中設計了自適應蟻窗策略、強制擾動機制以及算法參數動態調節策略,提出了IACO-TM高效生成任務序列。

(1) 自適應蟻窗策略。螞蟻采用輪盤賭方式[32]選擇觀測任務的同時動態調整當前任務的可達任務集,當可達任務數量較多時,隨機刪除部分任務不進入候選任務集,保留隨機性的同時有效裁剪螞蟻搜索范圍。如圖3(a)所示,假定當前任務的可達任務為1～8,圖中的扇面面積分別表示每個任務的候選概率。常規情況下會從可達任務1～8之間選擇下一個觀測任務。自適應蟻窗策略應用后,如圖3(b)所示,我們隨機刪除了幾個任務,將可達任務由1～8縮減至任務1、4、5、6、7,該種方式直接減少了螞蟻搜索時的候選任務數量，隨機刪減的做法實現了螞蟻搜索范圍的有效裁剪,分散信息素的累加,避免螞蟻陷入局部最優的同時大大提高了螞蟻尋優過程的效率。

圖3 自適應蟻窗策略應用前后對比

(2) 強制擾動機制。當算法連續收斂的次數到達一定上限時,將該收斂值對應路徑上的信息素重置為一個常量。測試不同常量取值下的最佳觀測收益和算法運行時間,綜合考慮兩個因素確定常量取值,確保算法跳出局部最優且較優任務在后續迭代中仍以較大概率被選中。如圖4所示,未進行擾動前,路徑1上的信息素累積量最高,路徑2次之,路徑3最少。依據當前信息素分布情況會使得螞蟻在后續迭代中以很大的概率走路徑1,路徑1上的信息素不斷累加,最終引導所有螞蟻都走路徑1,算法停滯。假定已知一條路徑4比路徑1的收益更大,在當前信息素的作用下螞蟻卻無法搜尋到該條路徑。因此,添加擾動機制后,路徑1上的信息素濃度迅速下降到一個較低的值,此時,原來走路徑1的螞蟻3選擇了路徑4,螞蟻2選擇了路徑2,有效避免了算法陷入局部最優。

圖4 擾動前后路徑對比圖

(3) 算法迭代過程中動態調整參數,如圖5所示,迭代次數i之前屬于算法前期階段,螞蟻數量取m1,信息素揮發系數取ρ1;i之后屬于算法后期階段,螞蟻數量取m2,信息素揮發系數取ρ2。i的界定方式為:當歷史最優解連續不變的次數到達給定上限時,進入算法后期。為了提高較優解的歷史作用,在算法前期結束時重置信息素矩陣,保留前期歷次迭代的局部最優解對應路徑上的信息素,將其余路徑信息素歸零,給予算法后期較好的初始解方案,加速算法收斂速度。

圖5 參數動態調節示意圖

3.2.4 算法主要流程

輸入合成任務MT,IACO-TM相關參數

輸出最優任務序列Sbest

步驟 1將單顆衛星上的任務隨機排列,選擇開始觀測時間最早的合成任務作為螞蟻k的任務序列Sk上的第一個任務。

步驟 2檢驗姿態轉換、開機時間、傳感器角度偏轉范圍以及重復點任務約束,得到當前任務的可達任務集Taskallowed。

步驟 4綜合輪盤賭機制和自適應蟻窗策略,從Taskallowed中挑選下一個觀測任務。

步驟 5重復步驟2～步驟4,直到衛星上所有任務遍歷完成,生成完整任務序列Sk。

步驟 6重復步驟1～步驟5,得到一次迭代中所有任務序列S1,S2,…,Sk,…,Sm,記錄本次迭代最優解Slocal。

步驟 7更新信息素矩陣g_trial和歷史最優解Sbest。

步驟 8檢驗Slocal持續不變的次數是否達到給定上限count1,如果是,啟動擾動機制。

步驟 9檢驗Sbest持續不變的次數是否到達給定上限count2或迭代次數到達算法最大迭代次數iteration,如果是,則將Sbest作為全局最優解,算法結束,否則返回步驟6。

4 仿真算例

本節通過實驗對模型和算法進行了仿真測試,該實驗基于Intel(R) Core(TM) i5-4210U處理器、4G內存、64位Windows10環境運行,在myeclipse2017環境下采用java語言編程,實現IACO-TM、ICAO和TACO-TM的對比,驗證本文所提出的MTMM以及ICAO-TM的有效性。

目前在成像衛星調度領域沒有公認的測試集,因此我們利用仿真軟件衛星工具箱(satellite tool kit, STK)生成3顆衛星,隨機生成100個任務、200個任務、400個任務作為測試算例,任務規劃時域為24 July 2019 00:00:00.000 UTCG—25 July 2019 00:00:00.000 UTCG。每種任務規模下生成3組數據,共生成9組算例(C1,C2,C3,C4,C5,C6,C7,C8,C9),每種算例運行30次,取平均值作為最終實驗結果,分別比較不同算例的最佳觀測收益,任務完成數量以及算法運行時間,并對實驗結果分析總結。表1列舉了任務部分數據信息。

表1 部分任務數據信息

(1) 參數敏感性測試

在每種算例規模下隨機選取一個算例,采用定義取值區間以及固定步長的方式對IACO-TM進行參數敏感性調試。其中,設置信息素權重參數α范圍為[1.0,2.5],步長為0.1;啟發式信息權重參數β范圍為[1.0,2.5],步長為0.1;信息素揮發系數ρ范圍為[0.2,0.6],步長為0.1;螞蟻數量m范圍為[10,40],步長為5。為省略篇幅,僅展示C9算例下α和β的測試結果,如圖6所示。

如圖6(a)所示,隨著α的增加,觀測收益總體呈現下降趨勢且運行時間波動很大,為最大化觀測收益,選定α=1.0。在既定的α取值下,如圖6(b)所示,當β≥1.7時,隨著β的增加,運行時間與觀測收益總體呈現下降趨勢;當β<1.7時,除β=1.2外,觀測收益與運行時間總體呈正相關走向,綜合觀測收益與運行時間兩項指標,選定α=1.0,

β=1.6。

IACO -TM其他參數設置為:算法前期ρ=0.3,m=30,算法后期ρ=0.2,m=15。TACO-TM參數設置為:α=1.0,β=1.6,ρ=0.2,m=30,最大迭代次數均設置為iteration=200。

圖6 參數敏感性測試

(2) 算法性能對比

對9組算例(C1,C2,C3,C4,C5,C6,C7,C8,C9)分別進行IACO-TM、IACO以及TACO-TM這3種算法的對比實驗。此外,將IACO-TM的3種策略分開實驗,通過最佳觀測收益、完成觀測任務數量和運行時間3個指標綜合評價,驗證MTMM及IACO-TM的有效性。部分實驗結果及算法性能對比如表2及圖7～圖9所示。

實驗結果分析:

(1) MTMM對ICAO的影響

如表2所示,除C1算例外,對任務進行合成觀測獲得的最佳觀測收益均大于未進行合成觀測時的收益,且觀測任務數量更多。這一點很容易解釋,由于任務之間的時間窗存在重疊,姿態轉換時間不夠充足等情況,當不對任務進行合成時,衛星只能選擇部分任務觀測,從而導致了大量任務被舍棄的情況。然而,合成觀測同時存在觀測冗余數據的風險,當個別合成任務產生的冗余數據占據了較多存儲空間時,后續衛星則沒有足夠空間存儲其他任務,導致觀測收益降低,如C1結果,但二者差別很小,且其余算例均未出現該種情況,說明這種風險很低,對任務合成觀測的方式依舊是可取的。

表2 3種算法實驗結果對比

運行時間上,在小規模算例下,本文所提的3種算法均能在幾秒內生成任務序列,隨著任務規模的增大,算法也能在幾十秒內完成。總體而言,IACO在求解時間上優勢更為明顯,算法收斂的速度更快,這是因為對任務合成觀測時需要先對任務進行合成預處理,占用了部分時間,并且對任務合成后,任務間的組合使得任務規模急劇增加,使得搜索時間相應延長,但二者時間差距不大,這是因為合成觀測時衛星也相應減少了姿態轉換次數,從而導致了IACO-TM運行時間略長的情況。可以推斷隨著任務規模的增大,且滿足合成約束的任務數量更多時,合成觀測在時間上也能獲得令我們更為滿意的結果。

(2) 改進機制對TACO -TM的影響

由表2可得,除C1算例外,IACO -TM獲得的觀測收益均大于TACO -TM。C1算例下TACO -TM獲得的最佳收益雖多于IACO -TM,但差別極小,且時間更長。200規模與400規模下IACO -TM的最佳收益顯然大于TACO -TM,C9算例下前者的最佳觀測收益甚至遠高于后者,達到了166.8。就運行時間而言,TACO -TM較IACO -TM優勢更為明顯,但綜合情況下時間相差仍在我們可接受范圍內,如C8算例下二者的時間相差多至6 s,但IACO -TM獲得的收益明顯大于TACO -TM,這是由于算法跳出局部最優導致收斂速度下降的結果。下面我們對改進機制給算法性能帶來的影響一一分析。

圖7 合成對算法性能的影響

圖8 改進機制對算法性能的影響

如圖9(a)所示,自適應蟻窗策略的應用增大了TACO-TM獲得的最佳觀測收益,說明對螞蟻選擇窗口的限制并沒有將對最終目標函數貢獻大的任務篩選掉,而是實現了搜索空間的有效裁剪,簡化了螞蟻的搜索過程。如圖9(b)所示,擾動機制的添加大大提高了TACO -TM的觀測收益,說明擾動機制的加入更容易使算法跳出局部最優,指導了螞蟻的尋優方向,避免了算法過早停滯。如圖9(c)所示,由于TACO -TM陷入了局部最優,導致其快速收斂,在運行時間上優勢更為明顯。添加了擾動機制的TACO -TM雖然觀測收益明顯提高,但運行時間大幅度增加。算法參數動態調節策略的加入起到了折中作用,使得算法收斂速度快速上升。可以得出結論,擾動機制與參數動態調節策略的組合使用,算法的綜合性能將更為明顯。

圖9 3種改進策略對算法性能的影響

根據上述實驗結果分析可知,隨著任務規模的增大,觀測收益會逐漸增加,算法的求解時間也會相應變長。當任務間存在大量的時間窗重疊、姿態轉換時間不夠充足的情況時,對任務進行合成觀測能夠有效提高觀測收益。此外,算法中設計的自適應蟻窗策略實現了螞蟻搜索范圍的有效裁剪,提高了搜索速度;設計的擾動機制雖然在一定程度上耗費了部分運行時間,卻有效避免了算法陷入局部最優,通過結合算法參數動態調節策略,顯著提高了算法的收斂速度和綜合性能。

5 結束語

本文主要研究了考慮任務合成機制的多星調度問題,設計了一種多任務合成機制,基于合成任務集,建立了數學規劃模型,提出了一種基于任務合成的改進ACO,在算法中設計了自適應蟻窗策略,強制擾動機制以及算法參數動態調節策略。通過對比實驗,證明了當任務間存在大量時間窗重疊、姿態轉換時間不夠充足的情況下,本文提出的多任務合成機制和求解算法能夠有效提高算法的全局搜索能力且加快收斂速度。

本文所研究的內容依舊有許多亟待解決的問題,下一步的主要工作包括:① 將點目標與區域目標綜合考慮任務合成,擴大研究目標范圍;② 考慮任務可見時間窗提前或延遲策略,增強任務序列魯棒性,增加觀測收益。