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

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

0 引 言

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

傳統(tǒng)模式下衛(wèi)星對(duì)點(diǎn)目標(biāo)均采用單任務(wù)觀測(cè)方式,即衛(wèi)星傳感器在同一個(gè)偏轉(zhuǎn)角度下僅僅觀測(cè)一個(gè)元任務(wù),如文獻(xiàn)[3-6]中的處理方式,這種方式能夠?qū)δ繕?biāo)以最佳角度成像,成像精度高,用戶滿意度最大。但是由于任務(wù)時(shí)間窗重疊,姿態(tài)轉(zhuǎn)換時(shí)間不夠充足等原因,導(dǎo)致觀測(cè)任務(wù)數(shù)量大大減少且資源使用效率極低。因此,近年來學(xué)者逐漸采用對(duì)任務(wù)合成觀測(cè)的方式來提高衛(wèi)星資源使用率,增大任務(wù)觀測(cè)收益。如文獻(xiàn)[7]中的處理方式,綜合最小派系劃分思想將任務(wù)合成,然后依據(jù)特定規(guī)則刪除部分合成任務(wù),該方法能夠有效減少衛(wèi)星搜尋任務(wù)時(shí)的復(fù)雜度,同時(shí)存在刪除部分優(yōu)解的風(fēng)險(xiǎn)。文獻(xiàn)[8-9]在單顆衛(wèi)星已有的任務(wù)序列上采用動(dòng)態(tài)規(guī)劃方法對(duì)任務(wù)合成,這種方式能夠一定程度上求得問題最優(yōu)解,但是隨著任務(wù)規(guī)模的增大,計(jì)算復(fù)雜度會(huì)大幅度增加,無法有效求得全局最優(yōu)解。文獻(xiàn)[10-13]提出了考慮合成的應(yīng)急任務(wù)動(dòng)態(tài)規(guī)劃問題,將實(shí)時(shí)到來的應(yīng)急任務(wù)與已有的常規(guī)任務(wù)序列動(dòng)態(tài)合成,這種處理方式更加符合實(shí)際,但是對(duì)原來的任務(wù)序列的魯棒性要求極高,否則將會(huì)耗費(fèi)大量時(shí)間用于任務(wù)序列重新生成。此外,上述文獻(xiàn)[7-13]均采用“均值法”計(jì)算合成觀測(cè)角度,方式雖簡(jiǎn)便易行,但是沒有考慮角度偏轉(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]最早由意大利學(xué)者Dorigo提出,隨著時(shí)間發(fā)展后人在其基礎(chǔ)上提出了許多改進(jìn)機(jī)制,包括蟻群系統(tǒng)算法[21]、最大最小蟻群系統(tǒng)算法[22]、變異特征ACO算法[23]、混合二進(jìn)制人造螞蟻算法[24]等。此外,文獻(xiàn)[25]提出了一種基于分布度均勻的自適應(yīng)ACO算法,引入“聚度”衡量螞蟻路徑分布均勻情況,動(dòng)態(tài)調(diào)整信息量更新策略和選擇路徑的概率,文獻(xiàn)[26]采用一種具有感覺和知覺特征的ACO算法,將絕對(duì)感覺閾限原理、差別感覺閾限原理以及韋伯定律依次應(yīng)用于螞蟻搜索的初始、中間和結(jié)束階段,加快收斂速度的同時(shí)保證解的多樣性。雖然上述近似算法能在一定程度上獲得較優(yōu)解,但也伴有陷入局部最優(yōu)或收斂速度過慢的缺陷。

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

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

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

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

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

1 問題描述

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

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

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

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

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

2 任務(wù)合成

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

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

2.1 合成優(yōu)點(diǎn)

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

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

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

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

2.2 合成約束

(1) 角度約束

(2) 開機(jī)約束

2.3 合成任務(wù)屬性

(1) 合成角度

(2) 合成觀測(cè)收益

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

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

2.4 合成算法

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

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

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

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

3.1 調(diào)度模型

(1) 符號(hào)設(shè)定

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

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

ΔOj為衛(wèi)星rj的單次最長(zhǎng)開機(jī)時(shí)間;

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

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

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

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

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

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

(2) 線性模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

3.2 改進(jìn)ACO算法

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

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

3.2.2 信息素更新

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

3.2.3 改進(jìn)機(jī)制

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

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

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

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

圖4 擾動(dòng)前后路徑對(duì)比圖

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

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

3.2.4 算法主要流程

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

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

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

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

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

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

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

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

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

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

4 仿真算例

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

目前在成像衛(wèi)星調(diào)度領(lǐng)域沒有公認(rèn)的測(cè)試集,因此我們利用仿真軟件衛(wèi)星工具箱(satellite tool kit, STK)生成3顆衛(wèi)星,隨機(jī)生成100個(gè)任務(wù)、200個(gè)任務(wù)、400個(gè)任務(wù)作為測(cè)試算例,任務(wù)規(guī)劃時(shí)域?yàn)?4 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),每種算例運(yùn)行30次,取平均值作為最終實(shí)驗(yàn)結(jié)果,分別比較不同算例的最佳觀測(cè)收益,任務(wù)完成數(shù)量以及算法運(yùn)行時(shí)間,并對(duì)實(shí)驗(yàn)結(jié)果分析總結(jié)。表1列舉了任務(wù)部分?jǐn)?shù)據(jù)信息。

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

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

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

如圖6(a)所示,隨著α的增加,觀測(cè)收益總體呈現(xiàn)下降趨勢(shì)且運(yùn)行時(shí)間波動(dòng)很大,為最大化觀測(cè)收益,選定α=1.0。在既定的α取值下,如圖6(b)所示,當(dāng)β≥1.7時(shí),隨著β的增加,運(yùn)行時(shí)間與觀測(cè)收益總體呈現(xiàn)下降趨勢(shì);當(dāng)β<1.7時(shí),除β=1.2外,觀測(cè)收益與運(yùn)行時(shí)間總體呈正相關(guān)走向,綜合觀測(cè)收益與運(yùn)行時(shí)間兩項(xiàng)指標(biāo),選定α=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ù)敏感性測(cè)試

(2) 算法性能對(duì)比

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

實(shí)驗(yàn)結(jié)果分析:

(1) MTMM對(duì)ICAO的影響

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

表2 3種算法實(shí)驗(yàn)結(jié)果對(duì)比

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

(2) 改進(jìn)機(jī)制對(duì)TACO -TM的影響

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

圖7 合成對(duì)算法性能的影響

圖8 改進(jìn)機(jī)制對(duì)算法性能的影響

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

圖9 3種改進(jìn)策略對(duì)算法性能的影響

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

5 結(jié)束語

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

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