考慮閑時(shí)對(duì)地遙感衛(wèi)星的天基觀測(cè)補(bǔ)網(wǎng)規(guī)劃*

楊元, 祝開(kāi)建, 侯重遠(yuǎn), 郭偉娜, 常羽彤, 王志亮, 胡思才, 王蔚東

(1. 中國(guó)西安衛(wèi)星測(cè)控中心, 西安 710043; 2. 中國(guó)人民解放軍63768 部隊(duì), 西安 710600)

1 引言

天基觀測(cè)是空間目標(biāo)探測(cè)實(shí)現(xiàn)的重要途徑。相比地基觀測(cè), 天基觀測(cè)位置與空間目標(biāo)的距離更近, 加之沒(méi)有大氣對(duì)信號(hào)的干擾, 其觀測(cè)方法的分辨率更高[1]。 美國(guó)和俄羅斯已經(jīng)發(fā)射數(shù)顆專用空間目標(biāo)探測(cè)衛(wèi)星用于以空間目標(biāo)監(jiān)視為核心任務(wù)的系統(tǒng)[2], 如美國(guó)的天基監(jiān)視系統(tǒng)(Space Based Surveillance System, SBSS)、 軌道深空成像系統(tǒng)(Orbit Deep Space Imager, ODSI)、 空間跟蹤與監(jiān)視系統(tǒng) (Space Tracking and Surveillance System, STSS)、 星歷表精調(diào)天基望遠(yuǎn)鏡(Spacebased Telescopes for Actionable Refinement of Ephemeris, STARE) 等。 這些天基監(jiān)測(cè)系統(tǒng)都大大地拓展了空間目標(biāo)的監(jiān)視范圍, 提高了空間目標(biāo)的觀測(cè)精度。

我國(guó)目前的空間目標(biāo)監(jiān)視設(shè)備大多為非專用設(shè)備, 多采用兼用的微小型空間目標(biāo)監(jiān)視平臺(tái)[3]。 一類對(duì)地遙感衛(wèi)星日常工作雖未安排天基監(jiān)測(cè)任務(wù), 但它們具有高分辨率、 高機(jī)動(dòng)能力、多任務(wù)模式, 除滿足對(duì)地成像需求外, 其軟硬件性能同樣具備空間目標(biāo)監(jiān)視能力。 以“吉林” 一號(hào)對(duì)地遙感星座為例, 近年來(lái)它們已完成了多次對(duì)慣性空間目標(biāo)成像, 實(shí)現(xiàn)了對(duì)空間目標(biāo)交匯成像定姿定軌的需求, 并驗(yàn)證了對(duì)地遙感衛(wèi)星用于天基觀測(cè)的可行性[4]。 可以說(shuō), 利用好這些對(duì)地遙感衛(wèi)星不僅可以增加我國(guó)空間目標(biāo)識(shí)別范圍和空間監(jiān)視網(wǎng)絡(luò)的性能, 而且還可以進(jìn)一步支持衛(wèi)星編目和空間態(tài)勢(shì)感知能力。

隨著空間目標(biāo)數(shù)量的不斷增加, 現(xiàn)有觀測(cè)資源明顯不足, 勢(shì)必需要優(yōu)化空間目標(biāo)監(jiān)測(cè)計(jì)劃,盡可能實(shí)現(xiàn)觀測(cè)設(shè)備的充分利用, 這是當(dāng)前空間目標(biāo)監(jiān)測(cè)系統(tǒng)中必須考慮的問(wèn)題。 文獻(xiàn)[5]針對(duì)多成像衛(wèi)星聯(lián)合調(diào)度規(guī)劃問(wèn)題, 建立了多星聯(lián)合調(diào)度約束滿足最優(yōu)化模型, 提出了一種改進(jìn)的差分進(jìn)化算法有效地分配衛(wèi)星資源。 文獻(xiàn)[6]針對(duì)應(yīng)急條件下成像衛(wèi)星任務(wù)規(guī)劃問(wèn)題, 建立了面向任務(wù)需求的應(yīng)急條件下單任務(wù)綜合規(guī)劃模型, 采用深度優(yōu)先搜索算法分析了衛(wèi)星、 測(cè)控及數(shù)傳資源的分配問(wèn)題。 文獻(xiàn)[7]針對(duì)多個(gè)成像任務(wù)同時(shí)監(jiān)視問(wèn)題, 采用禁忌搜索算法與知識(shí)型蟻群算法相結(jié)合的策略則可實(shí)現(xiàn)以較快的速度獲得較優(yōu)的解。 文獻(xiàn)[8]針對(duì)密集觀測(cè)場(chǎng)景下敏捷成像衛(wèi)星任務(wù)規(guī)劃問(wèn)題, 提出融合IndRNN 和Pointer Networks 的算法模型對(duì)敏捷成像衛(wèi)星任務(wù)規(guī)劃問(wèn)題進(jìn)行求解, 從而獲得更高的觀測(cè)收益率。 這些工作都在設(shè)備衛(wèi)星資源不變的情況下, 針對(duì)不同規(guī)劃需求實(shí)現(xiàn)了觀測(cè)能力的較大提升。

不同于上述研究, 本文針對(duì)資源不足的條件下, 結(jié)合我國(guó)空間目標(biāo)天基監(jiān)測(cè)網(wǎng)的實(shí)際, 利用處于空閑時(shí)間的對(duì)地遙感衛(wèi)星, 增加可監(jiān)測(cè)資源數(shù)量, 建立一種考慮閑時(shí)對(duì)地遙感衛(wèi)星的天基觀測(cè)補(bǔ)網(wǎng)規(guī)劃模型, 解決天基觀測(cè)動(dòng)態(tài)調(diào)度的可用性和穩(wěn)定性。

2 天基觀測(cè)補(bǔ)網(wǎng)的特點(diǎn)

目前對(duì)于天基觀測(cè)規(guī)劃的研究, 多是基于靜態(tài)條件, 即假設(shè)觀測(cè)調(diào)度一旦開(kāi)始, 參與調(diào)度的任務(wù)和資源不再變化。 而事實(shí)上, 天基觀測(cè)在一個(gè)十分復(fù)雜的環(huán)境中, 觀測(cè)規(guī)劃在執(zhí)行過(guò)程中往往會(huì)出現(xiàn)各種擾動(dòng)因素, 如衛(wèi)星資源狀態(tài)的變化、 新任務(wù)到達(dá)、 空間預(yù)警影響等, 這就使得天基觀測(cè)網(wǎng)覆蓋不全。 如果不顧任務(wù)動(dòng)態(tài)變化, 仍用舊的調(diào)度方案將導(dǎo)致存在監(jiān)測(cè)盲區(qū); 如果拋棄初始調(diào)度方案, 在資源不增的條件下重新進(jìn)行規(guī)劃, 則變動(dòng)規(guī)模較大時(shí), 實(shí)時(shí)性要求很難滿足,且容易打亂衛(wèi)星后續(xù)任務(wù)安排。 因此, 相比于天基觀測(cè)的日常規(guī)劃, 補(bǔ)網(wǎng)規(guī)劃特點(diǎn)有: (1) 補(bǔ)充原有觀測(cè)資源的空缺, 盡能力完成全部任務(wù), 提高任務(wù)的完成率; (2) 對(duì)原有調(diào)度方案的調(diào)整盡可能少, 保持規(guī)劃的穩(wěn)定性和重用性, 便于后續(xù)工作開(kāi)展; (3) 主要針對(duì)動(dòng)態(tài)應(yīng)急任務(wù), 在滿足前兩個(gè)特點(diǎn)的基礎(chǔ)上, 以任務(wù)結(jié)束時(shí)間最早作為優(yōu)化的第三層目標(biāo)。

3 衛(wèi)星資源空閑窗口與天基觀測(cè)時(shí)間約束

3.1 衛(wèi)星資源空閑窗口

對(duì)地遙感衛(wèi)星是探測(cè)地球資源和環(huán)境的衛(wèi)星, 當(dāng)陸地資源衛(wèi)星運(yùn)行至海洋上空與海洋資源衛(wèi)星運(yùn)行至陸地和河流上空時(shí)就屬于任務(wù)空閑期。 根據(jù)衛(wèi)星最新的精軌根數(shù)在STK 軟件和MTALAB 軟件配合下可以求解未來(lái)一段時(shí)間衛(wèi)星資源空閑窗口。 以某陸地資源衛(wèi)星為例, 計(jì)算流程如下:

Step1: 利用MTALAB 中Mapping Toolbox 工具箱, 導(dǎo)入海岸線數(shù)據(jù)(load coastlines), 計(jì)算海洋與非海洋區(qū)域, 并繪制海岸線地圖。 問(wèn)題初始化, 在STK 中導(dǎo)入衛(wèi)星最新精軌瞬根和載荷幅寬, 設(shè)置初值: 記錄變量i =0, 衛(wèi)星資源空閑窗口TL =0, 需要考慮時(shí)間段T0=(ta,tb) 。

Step2: 根據(jù)衛(wèi)星的軌道根數(shù), 利用STK 中HPOP 模型進(jìn)行時(shí)間段為Ti軌道外推, 求星下點(diǎn)軌跡, 獲得衛(wèi)星時(shí)間與星下點(diǎn)經(jīng)緯度的對(duì)應(yīng)表A, 迭代i = i +1。

Step3: 采用微分法, 求解衛(wèi)星星下點(diǎn)與海岸線相交點(diǎn), 得衛(wèi)星星下點(diǎn)臨界經(jīng)緯度, 查表A獲得衛(wèi)星處于海洋上空的時(shí)間窗口Ti o ={(t1a,t1b), …(tka,tkb), …(tna,tnb)} 。

Step4: 如果衛(wèi)星在Ti時(shí)段內(nèi)有機(jī)動(dòng)計(jì)劃, 變軌時(shí)段為Ci =(tca,tcb) , 本輪衛(wèi)星處于資源空閑窗口Til:

滿足(1)、 (2)、 (3) 三種情況之一衛(wèi)星資源空閑窗口TL =TL +Til, 修改Ti =(tca,tb) , 獲取機(jī)動(dòng)策略中的控后軌道根數(shù), 并轉(zhuǎn)Step2; 否則轉(zhuǎn)Step5。

Step5: 計(jì)算確定時(shí)間段T0=(ta,tb) 內(nèi)衛(wèi)星資源空閑窗口為TL = TL + Tio, 求解結(jié)束。

3.2 成像活動(dòng)的時(shí)間約束

為了滿足觀測(cè)目標(biāo)的可見(jiàn)和成像質(zhì)量高, 成像活動(dòng)需要考慮太陽(yáng)、 地球、 空間目標(biāo)和監(jiān)測(cè)衛(wèi)星空間幾何關(guān)系和載荷性能要求兩大類約束。 這些約束具有很強(qiáng)的時(shí)間依賴性, 可以轉(zhuǎn)換為相應(yīng)的時(shí)間約束。

①考慮地球遮擋的時(shí)間約束

當(dāng)?shù)厍蛱幵谟^測(cè)衛(wèi)星與空間目標(biāo)之間且位于二者連線上時(shí), 空間目標(biāo)不可見(jiàn)。 當(dāng)滿足公式(1) 時(shí), 衛(wèi)星可規(guī)避地球遮擋約束。

式中:rT(t) 為t時(shí)刻空間目標(biāo)在J2000 慣性坐標(biāo)系下的位置矢量,rO(t) 為t時(shí)刻觀測(cè)衛(wèi)星在J2000 慣性坐標(biāo)系下的位置矢量,RE為平均地球半徑。

②考慮地影的時(shí)間約束

空間目標(biāo)必須在太陽(yáng)光照射下才能清晰可見(jiàn), 若目標(biāo)進(jìn)入地影區(qū)將導(dǎo)致成像質(zhì)量灰暗, 難以辨別, 因此考慮地影的可見(jiàn)條件需滿足公式(2) 或(3)。

式中:rS(t) 為t時(shí)刻太陽(yáng)在J2000 慣性坐標(biāo)系下的位置矢量。

③考慮太陽(yáng)光干擾的時(shí)間約束

當(dāng)逆向太陽(yáng)光觀測(cè)空間目標(biāo)時(shí), 由于背景光強(qiáng)烈, 導(dǎo)致成像質(zhì)量模糊不清, 無(wú)法使用。 如公式(4) 所示, 當(dāng)實(shí)際太陽(yáng)光約束角大于觀測(cè)設(shè)備的臨界太陽(yáng)約束角時(shí), 拍照不會(huì)造成成像效果曝光過(guò)度。

式中:θsum,min∈(0, π/2) 為觀測(cè)設(shè)備的臨界太陽(yáng)約束角。

④考慮視場(chǎng)角的時(shí)間約束

由于觀測(cè)設(shè)備有視場(chǎng)限制, 空間目標(biāo)的可見(jiàn)條件是觀測(cè)角小于觀測(cè)設(shè)備的最大視場(chǎng)角。 設(shè)因此滿足公式(5) 時(shí), 空間目標(biāo)才在衛(wèi)星視場(chǎng)角范圍內(nèi)。

式中:rL(t) 為t時(shí)刻觀測(cè)設(shè)備光軸在J2000 慣性坐標(biāo)系下的位置矢量,θsight,max∈(0, π/2) 為觀測(cè)設(shè)備的最大視場(chǎng)角。

⑤考慮觀測(cè)距離的時(shí)間約束

由于觀測(cè)星等有限, 因此對(duì)給定尺寸的空間目標(biāo)的探測(cè)距離有限。 觀測(cè)衛(wèi)星的最大探測(cè)距離如公式(6) 所示, 可以由給定觀測(cè)星等與空間目標(biāo)等效橫截面積確定。 監(jiān)視衛(wèi)星與目標(biāo)相對(duì)距離必須小于觀測(cè)衛(wèi)星對(duì)給定目標(biāo)的最大探測(cè)距離, 即滿足公式(7)。

式中:D為衛(wèi)星最大成像距離,L為觀測(cè)星等,S為觀測(cè)對(duì)象等效橫截面積, ΔR(t) 為監(jiān)視衛(wèi)星到目標(biāo)相對(duì)距離。

⑥考慮相對(duì)角速度的時(shí)間約束

由于觀測(cè)星與空間目標(biāo)在慣性空間都非靜止不動(dòng), 兩者相對(duì)運(yùn)動(dòng)過(guò)大將會(huì)導(dǎo)致成像任務(wù)失敗[9]。 如公式(8) 所示t時(shí)刻目標(biāo)與監(jiān)視衛(wèi)星的相對(duì)角速度大小Δω(t) 不能超過(guò)觀測(cè)設(shè)備能識(shí)別的最大相對(duì)角速度Δωmax, Δω(t) 的計(jì)算方法如式(9) 所示。

式中:Δv(t) 為目標(biāo)與監(jiān)視衛(wèi)星的相對(duì)速度矢量,ΔvT(t) 為Δv(t) 切向分量。

綜上所述, 在衛(wèi)星成像活動(dòng)時(shí)間窗口TP內(nèi),有?t∈TP, 使得公式(1)—(10) 成立, 則觀測(cè)衛(wèi)星可獲得可見(jiàn)的高質(zhì)量目標(biāo)圖像。

3.3 衛(wèi)星工況引起的時(shí)間約束

①姿態(tài)轉(zhuǎn)換時(shí)間

在衛(wèi)星機(jī)動(dòng)方面, 為了盡可能使空間目標(biāo)在觀測(cè)設(shè)備的視場(chǎng)角內(nèi), 衛(wèi)星平臺(tái)或星上載荷可以通過(guò)側(cè)擺、 俯仰和偏航三個(gè)自由度方向的軌道姿態(tài)機(jī)動(dòng)開(kāi)展成像活動(dòng)[10]。 姿態(tài)機(jī)動(dòng)最大需求時(shí)間可用公式(11) 表示。

式中:Tg,max(t) 表示t時(shí)刻衛(wèi)星姿態(tài)機(jī)動(dòng)最大需求時(shí)間,ag,max(t) 為衛(wèi)星任務(wù)需要的最大姿態(tài)轉(zhuǎn)角,vg為姿態(tài)機(jī)動(dòng)轉(zhuǎn)速,c為衛(wèi)星姿態(tài)穩(wěn)定時(shí)間。

②固存接受的最大拍攝時(shí)間

在固存容量方面, 觀測(cè)衛(wèi)星的存儲(chǔ)上限不僅受限于衛(wèi)星單次服務(wù)時(shí)間, 同時(shí)依賴于衛(wèi)星何時(shí)對(duì)固存進(jìn)行格式化擦除。 如公式(12) 所示, 固存接受的最大拍攝時(shí)間:

式中:Tf_s,max(t) 表示t時(shí)刻固存所能接受的最大拍攝時(shí)長(zhǎng),Δs(t) 為t時(shí)刻觀測(cè)衛(wèi)星剩下的存儲(chǔ)容量,vw,min為星上固存允許的最小寫入速度。

③能量允許的最大拍攝時(shí)長(zhǎng)

在電量方面, 觀測(cè)衛(wèi)星對(duì)日充能的時(shí)刻與時(shí)間也制約著衛(wèi)星的拍攝時(shí)長(zhǎng),t時(shí)刻能量允許的最大拍攝時(shí)長(zhǎng)表示為Te_s,max(t) 。

4 基于時(shí)間約束的天基觀測(cè)補(bǔ)網(wǎng)規(guī)劃建模與求解

4.1 多時(shí)間約束的補(bǔ)網(wǎng)規(guī)劃模型

結(jié)合第二節(jié)中衛(wèi)星觀測(cè)時(shí)間分析, 本文以如下符號(hào)描述天基觀測(cè)補(bǔ)網(wǎng)規(guī)劃問(wèn)題中的參數(shù):①TiL: 衛(wèi)星si空閑時(shí)間窗口集合; ②TijP: 衛(wèi)星si對(duì)目標(biāo)aj的可見(jiàn)時(shí)間窗口集合; ③Tk ijExe: 衛(wèi)星si對(duì)目標(biāo)aj的第k個(gè)可執(zhí)行時(shí)間窗口; ④Tig,max:衛(wèi)星si姿態(tài)機(jī)動(dòng)最大時(shí)長(zhǎng); ⑤Tif_s,max: 衛(wèi)星si固存接受的最大拍攝時(shí)長(zhǎng); ⑥Tie_s,max: 衛(wèi)星si儲(chǔ)能允許的最大拍攝時(shí)長(zhǎng); ⑦TjDeadline: 目標(biāo)aj的任務(wù)截止時(shí)間; ⑧TjObs目標(biāo)aj任務(wù)要求觀測(cè)時(shí)長(zhǎng)。一個(gè)多時(shí)間約束的天基觀測(cè)補(bǔ)網(wǎng)規(guī)劃問(wèn)題可以用5 元組表示, 其中:

A: 觀測(cè)任務(wù)集合,A={a1,a2…,an} ,n表示需要規(guī)劃的元任務(wù)數(shù)量。

S: 衛(wèi)星資源集合,S ={s1,s2…,sm} ,m表示參與補(bǔ)網(wǎng)的衛(wèi)星資源數(shù)量。

TE: 可執(zhí)行時(shí)間窗口集合, 即為的集合,i≤m,j≤n,k取值范圍由實(shí)際計(jì)算得到,為可執(zhí)行開(kāi)始時(shí)間,為可執(zhí)行結(jié)束時(shí)間, 這里的時(shí)間窗口與任務(wù)目標(biāo)和衛(wèi)星資源有對(duì)應(yīng)關(guān)系。

: 原任務(wù)規(guī)劃變量集,表示原方案中事件“目標(biāo)aj由衛(wèi)星si在范圍進(jìn)行觀測(cè)” 被規(guī)劃,表示未被規(guī)劃。

Z: 新任務(wù)規(guī)劃變量集,表示新方案中事件“目標(biāo)aj由衛(wèi)星si在范圍進(jìn)行觀測(cè)” 被規(guī)劃,表示未被規(guī)劃。

根據(jù)以上約定, 我們建立補(bǔ)網(wǎng)規(guī)劃問(wèn)題的約束條件:

條件(1) 表示衛(wèi)星觀測(cè)時(shí)間滿足可用且可見(jiàn); 條件(2) 表示觀測(cè)時(shí)間滿足衛(wèi)星工況約束;條件(3) 表示觀測(cè)時(shí)間滿足任務(wù)時(shí)間要求; 條件(4) 防止資源沖突, 即同一衛(wèi)星資源時(shí)間窗口, 不能同時(shí)分配給兩個(gè)及兩個(gè)以上的任務(wù), 且同一衛(wèi)星的兩任務(wù)執(zhí)行上至少需要保留姿態(tài)轉(zhuǎn)換的時(shí)間間隔; 條件(5) 防止資源冗余, 即某一任務(wù)一旦已經(jīng)執(zhí)行, 原則上不再安排其他時(shí)間或其他衛(wèi)星資源再執(zhí)行。

在此基礎(chǔ)上, 目標(biāo)函數(shù)構(gòu)造如下:

(3 ) 最小化任務(wù)結(jié)束時(shí)間:

利用信息熵加權(quán)法合成三個(gè)子目標(biāo), 設(shè)置α,β,γ為影響因子。 根據(jù)天基觀測(cè)補(bǔ)網(wǎng)的特點(diǎn),約定α≥β≥γ。 最終優(yōu)化目標(biāo):

當(dāng)優(yōu)化結(jié)果F ＜α?xí)r, 判斷觀測(cè)補(bǔ)網(wǎng)規(guī)劃失敗,決策者需要精簡(jiǎn)任務(wù)或增加資源; 當(dāng)α≤F≤α +β時(shí), 判斷補(bǔ)網(wǎng)規(guī)劃成功, 但原規(guī)劃方案有調(diào)整;當(dāng)F ＞α+β時(shí), 判斷補(bǔ)網(wǎng)規(guī)劃成功, 原規(guī)劃方案無(wú)需調(diào)整, 新任務(wù)和資源直接插入原規(guī)劃方案即可。

4.2 算法設(shè)計(jì)與求解實(shí)現(xiàn)

相關(guān)研究表明, 衛(wèi)星觀測(cè)任務(wù)規(guī)劃問(wèn)題是一類典型的NP-hard 問(wèn)題, 難以求解, 且問(wèn)題的組合爆炸特征十分明顯。 現(xiàn)代智能優(yōu)化算法在求解組合優(yōu)化問(wèn)題方面顯示了較強(qiáng)的能力, 但由于本文模型時(shí)間約束條件較多, 勢(shì)必導(dǎo)致計(jì)算速度緩慢, 影響下一步的規(guī)劃部署, 不適合動(dòng)態(tài)應(yīng)急補(bǔ)網(wǎng)。 基于規(guī)則的啟發(fā)式算法可以綜合考慮優(yōu)先規(guī)則, 并加入一定的隨機(jī)因素, 從而獲得滿意的結(jié)果, 其優(yōu)勢(shì)在于運(yùn)行速度較快, 但難以從全局優(yōu)化的角度搜索問(wèn)題解。 筆者通過(guò)選擇吱呀輪算法(Squesky-Wheel Optimization, SWO) 作為導(dǎo)向式搜索, 快速獲取可行解, 再利用遺傳算法(Genetic algorithm, GA) 充分?jǐn)U展可行解的搜索空間, 通過(guò)這兩種算法整合預(yù)提高模型求解效率和求解質(zhì)量。 算法具體步驟如下。

(1) 編碼方法

借用文獻(xiàn)[11] 中編碼思想。 將天基觀測(cè)規(guī)劃問(wèn)題每個(gè)解劃分兩個(gè)部分: 一是對(duì)衛(wèi)星資源分配序列(Satellites Assignment, SA), 將每個(gè)元任務(wù)分配給一顆觀測(cè)衛(wèi)星; 二是針對(duì)元任務(wù)每衛(wèi)星資源可執(zhí)行時(shí)間分配序列 (Time Assignment,TA), 即為每個(gè)元任務(wù)和對(duì)應(yīng)的衛(wèi)星資源分配執(zhí)行開(kāi)始時(shí)間和結(jié)束時(shí)間。 基因的編碼采用自然數(shù)編碼, 每個(gè)基因的序號(hào)對(duì)應(yīng)元任務(wù)按截止時(shí)間由小到大排序的序號(hào), 基因座上的基因值標(biāo)識(shí)是衛(wèi)星與執(zhí)行時(shí)間的編號(hào), 參見(jiàn)圖1。

圖1 算法編碼Fig.1 Algorithmic coding

(2) 初始化種群

初始種群的產(chǎn)生速度和質(zhì)量影響算法的運(yùn)行效率, 快速生成高質(zhì)量初始種群是我們算法的關(guān)鍵步驟。 我們引入SWO 算法快速獲取多樣性的初始解。 SWO 算子由構(gòu)造器、 分析器和排序器組成, 如圖2 所示。

圖2 SWO 算子迭代過(guò)程示意圖Fig.2 SWO operator iteration process diagram

①構(gòu)造器設(shè)計(jì)

對(duì)照原規(guī)劃方案從已排序的任務(wù)但未安排資源的序列中依次選出可供使用的各個(gè)執(zhí)行衛(wèi)星和對(duì)應(yīng)時(shí)間, 將其插入到已安排任務(wù)序列中, 如果沒(méi)有已安排任務(wù)與當(dāng)前任務(wù)沖突, 則插入成功,跳過(guò)分析器和排序器, 生成一基因串。 否則將計(jì)算當(dāng)前任務(wù)和與之沖突的已安排資源任務(wù)一起轉(zhuǎn)入未安排任務(wù)重新規(guī)劃, 進(jìn)入分析器和排序器進(jìn)行局部?jī)?yōu)化搜索排序, 再回到構(gòu)造器重新生成規(guī)劃結(jié)果。

②分析器設(shè)計(jì)

分析器主要是對(duì)個(gè)體內(nèi)部進(jìn)行編排梳理。 為了加快搜索速度, 防止一個(gè)資源在迭代過(guò)程中被反復(fù)地安排、 取消、 再安排, 分析器采用最小沖突原則進(jìn)行責(zé)罰值Penalty 分析。

式中:fi為迭代過(guò)程中資源i在被安排及取消的次數(shù),l為迭代次數(shù),δ∈(0.5, 1) 為機(jī)會(huì)因子。

③排序器設(shè)計(jì)

排序器按資源的責(zé)罰值由大到小順序?qū)ξ窗才湃蝿?wù)序列排序。

(3) 個(gè)體適應(yīng)度值

將規(guī)劃模型的目標(biāo)函數(shù)作為該算法的適應(yīng)度函數(shù)。 但是由于本文采用的天基補(bǔ)網(wǎng)任務(wù)規(guī)劃模型是多目標(biāo)的約束滿足模型, 最終的適應(yīng)度值采取熵權(quán)法為各目標(biāo)函數(shù)賦權(quán)計(jì)算所得, 即根據(jù)種群內(nèi)部個(gè)體的三個(gè)目標(biāo)函數(shù)值, 進(jìn)行計(jì)算信息熵, 并根據(jù)信息熵的數(shù)值明確各目標(biāo)的權(quán)重, 最后使用該權(quán)重計(jì)算目標(biāo)函數(shù)值的和作為該個(gè)體的適應(yīng)度。

(4) 選擇操作

以個(gè)體適應(yīng)度占種群適應(yīng)度的比例為選擇概率, 對(duì)群內(nèi)部每個(gè)個(gè)體選擇操作。 對(duì)種群內(nèi)部所有個(gè)體按其概率選取兩個(gè)個(gè)體。

(5) 交叉操作

對(duì)于選擇出的父代按照交叉概率p并隨機(jī)選擇基因執(zhí)行交叉操作, 生成兩個(gè)子代個(gè)體。

(6) 變異操作

對(duì)種群中所有個(gè)體運(yùn)用變異算子之前采取精英保留策略, 即種群內(nèi)部表現(xiàn)優(yōu)秀的個(gè)體不會(huì)觸發(fā)變異, 精英保留比例為10%～25%之間。 針對(duì)其他個(gè)體中每個(gè)SA 編碼以變異概率q進(jìn)行變異操作。

(7) 新第一代種群

對(duì)交叉后的新個(gè)體進(jìn)行可行解獲取, 如圖2所示, 處理過(guò)程同獲得初始種群方式保持一致。利用信息熵加權(quán)法更新新種群內(nèi)所有個(gè)體的適用度值。

(8) 終止條件判斷

若達(dá)到最大迭代次數(shù)或種群中最大適應(yīng)度值滿足要求, 則終止運(yùn)算, 否則轉(zhuǎn)入步驟4 選擇操作進(jìn)行新一輪迭代。

5 仿真實(shí)驗(yàn)與分析

仿真場(chǎng)景設(shè)定原規(guī)劃中15 顆低軌衛(wèi)星選自STK 軟件中的衛(wèi)星數(shù)據(jù)庫(kù), 200 個(gè)空間目標(biāo)選自Spare-Track 網(wǎng)站下載的TLE 數(shù)據(jù), 并借助STK 軟件與Matlab 軟件計(jì)算可執(zhí)行時(shí)間窗口。 任務(wù)觀測(cè)截止時(shí)間按24h 至48h 隨機(jī)生成, 任務(wù)未全部完成, 需啟用補(bǔ)網(wǎng)規(guī)劃。

本實(shí)驗(yàn)中設(shè)置補(bǔ)網(wǎng)中增加10 顆對(duì)地遙感衛(wèi)星,遺傳算法中交叉概率p= 0.7, 變異概率q= 0.05。將天基觀測(cè)補(bǔ)網(wǎng)最終優(yōu)化目標(biāo)進(jìn)行歸一化處理,令Vd= F/(α + β + γ) , 并取多目標(biāo)加權(quán)因子α= 100,β=10,γ=1。 圖3、 圖4 和圖5 分別展示了不同觀測(cè)目標(biāo)數(shù)量變化情況下算法運(yùn)行1000次的平均尋優(yōu)結(jié)果、 平均計(jì)算時(shí)間和方差穩(wěn)定性的比較。

圖3 不同觀測(cè)目標(biāo)數(shù)量變化情況下三種算法的平均尋優(yōu)目標(biāo)比較Fig.3 Comparison of the average optimization target of three algorithms under the condition of different number of observation targets

圖4 不同觀測(cè)目標(biāo)數(shù)量變化情況下三種算法的平均尋優(yōu)時(shí)間比較Fig.4 Comparison of the average optimization time of three algorithms under the condition of different number of observation targets

圖5 不同觀測(cè)目標(biāo)數(shù)量變化情況下三種算法的尋優(yōu)穩(wěn)定性比較Fig.5 Comparison of the average optimization stability of three algorithms under the condition of different number of observation targets

在增加衛(wèi)星資源的情況下, 如圖3 所示, 三種算法的尋優(yōu)目標(biāo)值都大于0.9, 即任務(wù)完成率達(dá)到100%。 圖3 表明隨著觀測(cè)目標(biāo)增加三種算法的尋優(yōu)目標(biāo)值雖大于0.9 但都有所下降。 這說(shuō)明在增加一定補(bǔ)網(wǎng)資源數(shù)量的情況下, 隨著任務(wù)數(shù)量遞增, 即使任務(wù)成功率能達(dá)到, 但原方案變動(dòng)率和任務(wù)最早結(jié)束時(shí)間卻隨之變差。

圖3 中GA 算法曲線明顯高于SWO 算法曲線, 表明針對(duì)本文規(guī)劃問(wèn)題GA 算法在尋優(yōu)目標(biāo)性能上優(yōu)于SWO 算法, 改進(jìn)后GA 算法與GA 算法曲線接近。 圖4 表明針對(duì)本文規(guī)劃問(wèn)題SWO 算法具有最佳的尋優(yōu)時(shí)間性能, GA 和SWO 組合算法在尋優(yōu)時(shí)間性能上勝過(guò)GA 算法。 圖5 由各算法運(yùn)行1000 次實(shí)驗(yàn)統(tǒng)計(jì)獲得方差分析三種算法穩(wěn)定性差異, 表明GA 和SWO 組合算法求得的最佳解相比其他兩種方法較為穩(wěn)定。 綜上所述, GA和SWO 組合算法與GA 算法在尋優(yōu)目標(biāo)值上無(wú)顯著差異, 但在尋優(yōu)時(shí)間和尋優(yōu)穩(wěn)定性上有較大提升。

6 結(jié)論

針對(duì)在資源不足情況下天基觀測(cè)規(guī)劃問(wèn)題,本文主要完成三項(xiàng)工作: (1) 分析天基觀測(cè)補(bǔ)網(wǎng)規(guī)劃的需求和特點(diǎn), 確定補(bǔ)網(wǎng)規(guī)劃的任務(wù)目標(biāo);(2) 考慮對(duì)地遙感衛(wèi)星的空閑窗口, 明確衛(wèi)星資源可執(zhí)行觀測(cè)任務(wù)的時(shí)間約束; (3) 鑒于多條件約束需要滿足, 建立基于時(shí)間約束的補(bǔ)網(wǎng)規(guī)劃模型, 并進(jìn)一步采用遺傳算法和吱呀輪的組合算法進(jìn)行求解。 利用STK 提供仿真數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析, 驗(yàn)證了模型的有效性, 實(shí)驗(yàn)表明遺傳與吱呀輪的組合算法在求解方案的評(píng)價(jià)、 算法收斂速度和穩(wěn)定性方面都表現(xiàn)出較高的性能。 該研究不僅可以為今后空閑衛(wèi)星加入天基觀測(cè)補(bǔ)網(wǎng)提供參考, 更可以為實(shí)現(xiàn)天基觀測(cè)動(dòng)態(tài)調(diào)度的重用性和穩(wěn)定性提供有力支持。