任送蓮, 孫海權(quán), 靳 鵬

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

0 引 言

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

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

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

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

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

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

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

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

1 問題描述

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

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

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

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

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

2 任務(wù)合成

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

圖2 合成任務(wù)示意圖

2.1 合成優(yōu)點

與傳統(tǒng)觀測模式相比,對任務(wù)合成觀測具有以下優(yōu)點:

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

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

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

2.2 合成約束

(1) 角度約束

(2) 開機約束

2.3 合成任務(wù)屬性

(1) 合成角度

(2) 合成觀測收益

(3) 有效數(shù)據(jù)比

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

2.4 合成算法

輸入元任務(wù)集合T

輸出合成任務(wù)集MT

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

3 調(diào)度模型及求解算法

3.1 調(diào)度模型

(1) 符號設(shè)定

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

Δgj為衛(wèi)星rj的覆蓋幅寬;

ΔOj為衛(wèi)星rj的單次最長開機時間;

Cj為衛(wèi)星rj的最大存儲容量;

c為單位時間衛(wèi)星成像需要的存儲容量;

Ej為衛(wèi)星rj單圈次可消耗的最大能量;

rate為衛(wèi)星傳感器旋轉(zhuǎn)速率;

a為單位時間衛(wèi)星成像所需的能量;

b為單位角度衛(wèi)星姿態(tài)轉(zhuǎn)換所需的能量。

(2) 線性模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

3.2 改進ACO算法

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

3.2.1 狀態(tài)轉(zhuǎn)移規(guī)則

3.2.2 信息素更新

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

3.2.3 改進機制

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

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

圖3 自適應(yīng)蟻窗策略應(yīng)用前后對比

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

圖4 擾動前后路徑對比圖

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

圖5 參數(shù)動態(tài)調(diào)節(jié)示意圖

3.2.4 算法主要流程

輸入合成任務(wù)MT,IACO-TM相關(guān)參數(shù)

輸出最優(yōu)任務(wù)序列Sbest

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

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

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

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

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

步驟 7更新信息素矩陣g_trial和歷史最優(yōu)解Sbest。

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

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

4 仿真算例

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

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

表1 部分任務(wù)數(shù)據(jù)信息

(1) 參數(shù)敏感性測試

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

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

β=1.6。

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

圖6 參數(shù)敏感性測試

(2) 算法性能對比

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

實驗結(jié)果分析:

(1) MTMM對ICAO的影響

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

表2 3種算法實驗結(jié)果對比

運行時間上,在小規(guī)模算例下,本文所提的3種算法均能在幾秒內(nèi)生成任務(wù)序列,隨著任務(wù)規(guī)模的增大,算法也能在幾十秒內(nèi)完成?？傮w而言,IACO在求解時間上優(yōu)勢更為明顯,算法收斂的速度更快,這是因為對任務(wù)合成觀測時需要先對任務(wù)進行合成預(yù)處理,占用了部分時間,并且對任務(wù)合成后,任務(wù)間的組合使得任務(wù)規(guī)模急劇增加,使得搜索時間相應(yīng)延長,但二者時間差距不大,這是因為合成觀測時衛(wèi)星也相應(yīng)減少了姿態(tài)轉(zhuǎn)換次數(shù),從而導致了IACO-TM運行時間略長的情況?？梢酝茢嚯S著任務(wù)規(guī)模的增大,且滿足合成約束的任務(wù)數(shù)量更多時,合成觀測在時間上也能獲得令我們更為滿意的結(jié)果。

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

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

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

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

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

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

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

5 結(jié)束語

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

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