張秀秀， 王俊峰， 楊 春

(1.四川大學(xué)計(jì)算機(jī)學(xué)院, 成都 610065； 2. 四川大學(xué)空天科學(xué)與工程學(xué)院， 成都 610065； 3.四川師范大學(xué)可視化計(jì)算與虛擬現(xiàn)實(shí)四川省重點(diǎn)實(shí)驗(yàn)室， 成都 610068)

1 引 言

近年來(lái)小衛(wèi)星發(fā)射數(shù)量愈來(lái)愈多，占據(jù)了航天活動(dòng)的主要領(lǐng)域[1]，對(duì)地觀測(cè)作為衛(wèi)星技術(shù)主要應(yīng)用方向之一，備受人們的重視.根據(jù)美國(guó)衛(wèi)星工業(yè)協(xié)會(huì)(SIA)發(fā)布的數(shù)據(jù)顯示，2017年全球發(fā)射的小衛(wèi)星中將近一半用于地面觀測(cè)服務(wù)[2].傳統(tǒng)的對(duì)地觀測(cè)任務(wù)規(guī)劃模式為：地面控制中心就用戶所提交的任務(wù)集合，根據(jù)所掌握的各種衛(wèi)星參數(shù)信息，通過(guò)計(jì)算生成特定的觀測(cè)計(jì)劃表，上注給對(duì)應(yīng)的衛(wèi)星，使衛(wèi)星按照計(jì)劃完成觀測(cè)任務(wù).該模式往往采用離線規(guī)劃的方式，計(jì)劃一旦生成則不可改變，不利于對(duì)觀測(cè)需求動(dòng)態(tài)變化的任務(wù)的調(diào)度.且該模式計(jì)算部分嚴(yán)重依賴地面控制中心，容易出現(xiàn)因任務(wù)數(shù)量多導(dǎo)致規(guī)劃效率低下的問(wèn)題，因此衛(wèi)星擁有任務(wù)自主調(diào)度能力尤為重要.

自主調(diào)度將規(guī)劃?rùn)?quán)從控制中心剝離，轉(zhuǎn)移到衛(wèi)星的計(jì)算單元上，每顆衛(wèi)星可結(jié)合自身資源約束以及任務(wù)要求來(lái)決定需要觀測(cè)的任務(wù)序列，該方式已引起許多學(xué)者的重視[3-4]，國(guó)內(nèi)外已有不少研究成果和應(yīng)用.文獻(xiàn)[5-6]針對(duì)敏捷對(duì)地觀測(cè)衛(wèi)星LemaTre建立了觀測(cè)問(wèn)題的簡(jiǎn)化模型，提出了快速貪婪、動(dòng)態(tài)規(guī)劃、約束規(guī)劃、局部搜索四種算法，通過(guò)實(shí)驗(yàn)對(duì)比，局部搜索算法表現(xiàn)出了較好的性能；而Habet提出了一種禁忌搜索算法來(lái)進(jìn)行求解，多數(shù)實(shí)例運(yùn)行結(jié)果達(dá)到了最優(yōu)，但研究對(duì)于約束的精確性還需進(jìn)一步考慮.文獻(xiàn)[7-8]分別介紹了Casper和ASPEN衛(wèi)星任務(wù)規(guī)劃系統(tǒng).Casper采用星上自主監(jiān)視，地面重新規(guī)劃任務(wù)并重傳機(jī)制，而ASPEN作為一個(gè)面向?qū)ο蟮南到y(tǒng)，主要實(shí)現(xiàn)以日為周期來(lái)對(duì)衛(wèi)星的活動(dòng)進(jìn)行規(guī)劃.文獻(xiàn)[9]針對(duì)多衛(wèi)星提出了星上自主任務(wù)重新規(guī)劃系統(tǒng)，算法核心由多目標(biāo)混合動(dòng)態(tài)變異遺傳算法和重新規(guī)劃技術(shù)組成，仿真結(jié)果表明,系統(tǒng)可在緊急的情況下對(duì)任務(wù)作出有效的重規(guī)劃.伍保峰等人[10]提出了小衛(wèi)星面向任務(wù)自主指令設(shè)計(jì)的辦法，令衛(wèi)星具有自行判斷執(zhí)行指令的能力.劉嵩等[11]針對(duì)敏捷成像衛(wèi)星自主任務(wù)規(guī)劃，提出了一種結(jié)合了隨機(jī)機(jī)制和輪盤(pán)賭思想的迭代貪婪算法，但易陷入局部最優(yōu)的困境.文獻(xiàn)[12]針對(duì)突發(fā)性事件提出了一種雙階段規(guī)劃算法，以仿真案例證明了動(dòng)作并行執(zhí)行可行性，但未考慮事件優(yōu)先級(jí)對(duì)事件執(zhí)行順序的影響.趙萍等[13]采用了精英保存策略對(duì)遺傳算法進(jìn)行了改進(jìn)，但對(duì)于成像操作之間有交疊的任務(wù)沒(méi)有進(jìn)行考慮.張弛等人[14]基于高分三號(hào)衛(wèi)星的任務(wù)特點(diǎn)，提出了九種編排指令模版用于任務(wù)的自主規(guī)劃，測(cè)試證明了設(shè)計(jì)的實(shí)用性.

衛(wèi)星任務(wù)規(guī)劃歸根結(jié)底是一種基于組合優(yōu)化理論生成可行方案的問(wèn)題.已有的算法研究多數(shù)為啟發(fā)式算法，該類型算法研究取得了一定的成果，但也存在著幾個(gè)問(wèn)題.(1) 對(duì)于觀測(cè)任務(wù)就資源消耗問(wèn)題都做了粗略的處理，計(jì)算結(jié)果與實(shí)際應(yīng)用相差較大;(2) 對(duì)于沖突關(guān)系的處理，是基于收益最大原則在任務(wù)中做出選擇觀測(cè)，這樣使得整體規(guī)劃率不高;(3) 由于啟發(fā)式算法是在解空間中進(jìn)行解的搜索，因此時(shí)間耗費(fèi)較長(zhǎng).

針對(duì)以上缺陷，本文設(shè)計(jì)并實(shí)現(xiàn)了一種新的用于小衛(wèi)星自主調(diào)度觀測(cè)任務(wù)的啟發(fā)式自主規(guī)劃算法.與已有的啟發(fā)式算法不同的是本算法采用分而治之的思路，即將問(wèn)題分為兩個(gè)子問(wèn)題進(jìn)行求解:(1) 在對(duì)任務(wù)進(jìn)行資源消耗的精確計(jì)算下，對(duì)任務(wù)間存在的沖突關(guān)系基于最小冗余原則進(jìn)行消解；(2) 采用優(yōu)化的蛙跳算法進(jìn)行解的搜索.在沖突消解的基礎(chǔ)上進(jìn)行搜索，保證了更多任務(wù)有觀測(cè)可能的同時(shí)縮小了第二模塊的解空間，可在較短時(shí)間內(nèi)計(jì)算得到收益最大的觀測(cè)隊(duì)列.

2 問(wèn)題分析與建模

2.1 觀測(cè)動(dòng)作與問(wèn)題描述

衛(wèi)星在沿特定的軌道運(yùn)行時(shí)，遙感成像設(shè)備[15]會(huì)在地球上形成一圈投影，這圈投影稱為星下點(diǎn)軌跡.由于傳感器具有側(cè)擺功能，衛(wèi)星在運(yùn)行過(guò)程中會(huì)形成以星下點(diǎn)軌跡為中心的條帶狀區(qū)域[16]，即衛(wèi)星對(duì)地球的可視范圍.處于可視范圍內(nèi)的目標(biāo)均有機(jī)會(huì)被衛(wèi)星所觀測(cè)，受遙感器視場(chǎng)限制的影響，衛(wèi)星的一次成像僅能覆蓋比可視范圍小的區(qū)域，如圖1中藍(lán)色長(zhǎng)方形所示.

圖1 衛(wèi)星對(duì)地觀測(cè)示意Fig.1 Schematic diagram of satellite observation

觀測(cè)目標(biāo)通常分為點(diǎn)目標(biāo)和區(qū)域目標(biāo)兩種，如圖1中圓形形狀為點(diǎn)目標(biāo)，紫色不規(guī)則形狀為區(qū)域目標(biāo).對(duì)目標(biāo)進(jìn)行觀測(cè)時(shí)，點(diǎn)目標(biāo)對(duì)地覆蓋區(qū)域小，一般只需遙感傳感器側(cè)擺一次，而區(qū)域目標(biāo)往往需要角度轉(zhuǎn)換兩次及以上，在實(shí)際活動(dòng)中，區(qū)域目標(biāo)往往被劃分為幾個(gè)點(diǎn)目標(biāo)來(lái)完成觀測(cè).因此為使研究方法具有通用性，本文的研究對(duì)象選取以點(diǎn)目標(biāo)為代表的觀測(cè)需求.

衛(wèi)星完成一次觀測(cè)的完整步驟為：開(kāi)機(jī)、側(cè)擺、穩(wěn)定、觀測(cè)、關(guān)機(jī)，如圖2所示.具體描述為：遙感傳感器在指定時(shí)間開(kāi)機(jī)，隨后側(cè)擺到規(guī)定的角度使目標(biāo)為其可見(jiàn)，待傳感器穩(wěn)定后執(zhí)行觀測(cè)，觀測(cè)達(dá)到時(shí)間要求后關(guān)機(jī).并非每個(gè)任務(wù)都必須執(zhí)行這5個(gè)步驟，在滿足衛(wèi)星最長(zhǎng)開(kāi)機(jī)時(shí)間條件限制下，可省略開(kāi)關(guān)機(jī)操作.每個(gè)任務(wù)擁有特定的可見(jiàn)窗口，觀測(cè)動(dòng)作需在可見(jiàn)時(shí)間窗口內(nèi)完成.以任務(wù)間可見(jiàn)窗口是否交叉為依據(jù)，任務(wù)間的關(guān)系可被劃分為沖突或不沖突兩種.如圖2中共列出了三個(gè)任務(wù)，任務(wù)1與任務(wù)2的成像間隔時(shí)間足夠讓設(shè)備進(jìn)行姿態(tài)轉(zhuǎn)換，這樣的兩個(gè)任務(wù)互相獨(dú)立，反之則互相沖突，如任務(wù)2和任務(wù)3.為了對(duì)目標(biāo)點(diǎn)達(dá)到最佳觀測(cè)，傳感設(shè)備對(duì)每個(gè)目標(biāo)點(diǎn)都有一個(gè)最佳側(cè)擺角，若對(duì)目標(biāo)都使用最佳側(cè)擺角進(jìn)行觀測(cè)，那么對(duì)于形如任務(wù)2和任務(wù)3成像間隔時(shí)間小于姿態(tài)轉(zhuǎn)換所需時(shí)間的任務(wù)來(lái)說(shuō)，不一定能被設(shè)備同時(shí)觀測(cè)到.

圖2 觀測(cè)任務(wù)示意Fig.2 Observation task

沖突關(guān)系的存在是造成任務(wù)規(guī)劃效率較低的一個(gè)重要因素，在考慮衛(wèi)星的能量、存儲(chǔ)以及轉(zhuǎn)換時(shí)間等各種約束條件下如何對(duì)任務(wù)做出選擇，充分利用匱乏的資源使最終形成的觀測(cè)隊(duì)列收益之和最大化，是本文要解決的問(wèn)題.

2.2 系統(tǒng)模型

2.2.1 基本假設(shè) 衛(wèi)星資源約束較多，為了便于研究有必要對(duì)問(wèn)題進(jìn)行簡(jiǎn)化，本研究作出如下的合理假設(shè)：(1) 每顆衛(wèi)星上只攜帶有一個(gè)遙感傳感器；(2) 衛(wèi)星的開(kāi)機(jī)和關(guān)機(jī)均需要一定時(shí)間，且會(huì)消耗一定電量；(3) 大氣、光照等自然條件以及衛(wèi)星的側(cè)擺對(duì)觀測(cè)質(zhì)量沒(méi)有影響；(4) 在一個(gè)調(diào)度周期內(nèi)，衛(wèi)星所擁有的能量是一定的； (5) 在完成一個(gè)周期的調(diào)度后，衛(wèi)星才進(jìn)行數(shù)據(jù)的下傳.

2.2.2 模型與約束 根據(jù)任務(wù)可見(jiàn)窗口以及衛(wèi)星的唯一性，結(jié)合星載資源限制，我們采用0-1整數(shù)規(guī)劃對(duì)衛(wèi)星自主調(diào)度觀測(cè)任務(wù)問(wèn)題進(jìn)行建模，便于之后使用所提出的啟發(fā)式自主規(guī)劃算法對(duì)任務(wù)進(jìn)行調(diào)度和優(yōu)化.

(1) 參數(shù)設(shè)置模型中涉及到的參數(shù)如表1所示.

表1 模型參數(shù)

其中,資源參數(shù)由衛(wèi)星自身決定，任務(wù)的權(quán)重、持續(xù)觀測(cè)時(shí)間以及觀測(cè)角度等由需求決定，每個(gè)任務(wù)的可用窗口通過(guò)衛(wèi)星計(jì)算單元利用自己的六軌道根數(shù)以及目標(biāo)點(diǎn)的位置計(jì)算得到.軌道根數(shù)是描述衛(wèi)星沿軌道運(yùn)行狀態(tài)的一組參數(shù)[17]，通常是指包括軌道半長(zhǎng)軸a、軌道偏心率e、軌道傾角i、升交點(diǎn)赤經(jīng)Ω、近地點(diǎn)幅角ω、指定歷元的平近點(diǎn)角M0在內(nèi)的六個(gè)參數(shù)；目標(biāo)點(diǎn)的位置一般用經(jīng)緯度坐標(biāo)來(lái)確定，如Targeti=(Li,Bi)，其中Li為經(jīng)度，Bi為緯度.

(2) 目標(biāo)函數(shù)及約束.

subject to

C1:CNCNi=i?CNi≠0，?i∈[1,N]

C2:CNi≠CNj?CNi,CNj≠0，?i,j∈[1,N],i≠j

C3:Xi=XCNi?CNi≠0，?i∈[1,N]

C6:|Ai|≤Max_A?i∈[1,N]

模型的目標(biāo)函數(shù)是使被安排觀測(cè)任務(wù)的總權(quán)重最大化.約束C1～C2保證了兩個(gè)任務(wù)在合成時(shí)的關(guān)聯(lián)性；約束C3表示進(jìn)行合成觀測(cè)的兩個(gè)任務(wù)具有規(guī)劃一致性；約束C4～C5為任務(wù)規(guī)劃時(shí)的資源限制，C4為任務(wù)數(shù)據(jù)存儲(chǔ)約束，C5為能量約束，包括傳感器開(kāi)機(jī)、側(cè)擺及穩(wěn)定、觀測(cè)和關(guān)機(jī)所消耗的能量，其中,f(CNi)保證因任務(wù)合成所產(chǎn)生的冗余數(shù)據(jù)或能量消耗不被重復(fù)計(jì)算；約束C6為側(cè)擺角限制，任務(wù)觀測(cè)所需的側(cè)擺角度不能超過(guò)星載遙感器的最大側(cè)擺角.

3 啟發(fā)式自主規(guī)劃算法

星上計(jì)算資源有限，為了快速且有效地對(duì)任務(wù)進(jìn)行規(guī)劃，我們基于問(wèn)題模型提出了一種啟發(fā)式自主規(guī)劃算法(Heuristic Independent Programming Algorithm,HIPA).HIPA采用分而治之的思路，即將問(wèn)題分解為任務(wù)合成與序列規(guī)劃兩個(gè)子模塊進(jìn)行求解.這兩個(gè)子模塊看似獨(dú)立但又聯(lián)系緊密，其邏輯關(guān)系如圖3所示.

流程中任務(wù)資源消耗預(yù)處理部分主要完成的工作是針對(duì)每一個(gè)任務(wù)，按觀測(cè)的完整過(guò)程計(jì)算可能的電量和數(shù)據(jù)存儲(chǔ)空間耗費(fèi).

Di=TCi*DUT

(1)

式(1)中,DUT為單位時(shí)間觀測(cè)數(shù)據(jù)上行傳輸率.

(2)

式(2)中,Tof為一次開(kāi)關(guān)機(jī)所需的時(shí)間;w為傳感設(shè)備的擺動(dòng)角速度;Tsta指?jìng)?cè)擺后到穩(wěn)定所需的時(shí)間;EUT為開(kāi)機(jī)狀態(tài)時(shí)單位時(shí)間設(shè)備的耗電量.

圖3 HIPA整體流程Fig.3 HIPA overall process

3.1 基于啟發(fā)式規(guī)則的任務(wù)合成

任務(wù)間沖突關(guān)系以不同形式呈現(xiàn)，通常有兩種情況.一種為任務(wù)間可見(jiàn)窗口交叉且觀測(cè)角度不同，另一種為窗口不交叉但任務(wù)間觀測(cè)間隔時(shí)間不能滿足設(shè)備進(jìn)行姿態(tài)轉(zhuǎn)換.這兩種情況均需進(jìn)行沖突消解，為使存在沖突關(guān)系的任務(wù)都具有被觀測(cè)的可能，本文采用合成的辦法進(jìn)行處理.

(1) 合成條件.合成需要滿足兩個(gè)條件，角度約束和時(shí)間限制.角度約束是為了保證待合成的目標(biāo)均處于傳感器的視野范圍內(nèi)，要求進(jìn)行合成的兩對(duì)象側(cè)擺角之差不超過(guò)觀測(cè)設(shè)備的視場(chǎng)角；時(shí)間限制是由傳感設(shè)備自身決定的，是制造廠商為了保障設(shè)備的使用壽命而設(shè)定的最長(zhǎng)開(kāi)機(jī)時(shí)間，合成所得任務(wù)的總觀測(cè)時(shí)間不能超過(guò)這個(gè)設(shè)定值.將合成條件用表達(dá)式(3)進(jìn)行描述如下.

?i,j∈[1,N],i≠j

(3)

其中,ΔFOV為衛(wèi)星遙感傳感器的視場(chǎng)角;ΔTon為傳感器的最長(zhǎng)開(kāi)機(jī)時(shí)間.

任務(wù)合成后的側(cè)擺角度以及可見(jiàn)窗口的起始和結(jié)束時(shí)間的計(jì)算分別如式(4)和式(5)所示.

(4)

(5)

(2) 合成任務(wù)選擇.任務(wù)合成，一方面可以進(jìn)行沖突關(guān)系的化解，但另一方面也可能會(huì)給觀測(cè)增加一些不必要的區(qū)域，這主要針對(duì)于沖突的第二種情況而言，即可見(jiàn)窗口不交叉.對(duì)這種情況因合成產(chǎn)生的數(shù)據(jù)量化如圖4所示，灰色框表示觀測(cè)任務(wù)所產(chǎn)生的圖像，即有效數(shù)據(jù)，白色框表示因觀測(cè)不必要的區(qū)域所產(chǎn)生的冗余數(shù)據(jù),因觀測(cè)該區(qū)域所造成的能量損耗稱為冗余消耗.

圖4 冗余數(shù)據(jù)示意Fig.4 Redundant data

將任務(wù)m、n因合成產(chǎn)生的冗余存儲(chǔ)RedDmn及冗余能量RedEmn用式(6)進(jìn)行計(jì)算.

RedDmn=

RedEmn=

(6)

我們提出了基于最小耗費(fèi)的啟發(fā)式規(guī)則來(lái)進(jìn)行最優(yōu)合成對(duì)象的選擇，引入評(píng)價(jià)指標(biāo)EI，計(jì)算公式如式(7)所示.

?m,n∈[1,N]

(7)

其中,α為評(píng)價(jià)參數(shù)，這里設(shè)定數(shù)據(jù)存儲(chǔ)和能量具有相同的重要性，取α值為0.5，EI越小，代表合成造成的損耗越少，基于該值對(duì)合成對(duì)象做出選擇.該規(guī)則的目的是減少對(duì)星載資源的浪費(fèi)，給其它任務(wù)提供所需資源可被滿足的機(jī)會(huì)，可提高任務(wù)的規(guī)劃率.

3.2 基于蛙跳優(yōu)化的序列規(guī)劃

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)作為一種啟發(fā)式群體進(jìn)化算法，具有參數(shù)少、易實(shí)現(xiàn)的優(yōu)點(diǎn)，其求解原理為：一群數(shù)量確定的青蛙通過(guò)在放置有不同數(shù)量食物的石頭之間跳躍以找到食物最多的石頭.青蛙在尋找食物過(guò)程會(huì)形成不同的族群，族群中的個(gè)體互相交流以更新自己的信息，交流完成后所有個(gè)體進(jìn)行全局匯合，隨后進(jìn)行重新分組，直到尋找結(jié)束.

(8)

(9)

3.2.1 蛙跳優(yōu)化算法 SFLA局部更新策略可通過(guò)數(shù)列極限[18]被證明為是收斂的，但更新僅針對(duì)于最差個(gè)體，忽略了其他個(gè)體的有用信息，導(dǎo)致解的收斂速度較慢，易出現(xiàn)局部早熟.本模塊在SFLA的基礎(chǔ)上進(jìn)行改進(jìn)，使優(yōu)化后的算法以較短的時(shí)間求得最優(yōu)的規(guī)劃序列.

算法1 局部更新策略

mark global best frog forPgb

fori←0 tom-1 do

mark thei-thsubmemeplex as memplexi

iter←0

本文研究的社區(qū)養(yǎng)老設(shè)施體系構(gòu)建是基于規(guī)劃層面的,因此應(yīng)參照《城市居住區(qū)規(guī)劃設(shè)計(jì)規(guī)范》《城鎮(zhèn)養(yǎng)老設(shè)施規(guī)劃規(guī)范》及《養(yǎng)老設(shè)施建筑設(shè)計(jì)規(guī)范》的相關(guān)標(biāo)準(zhǔn)．綜合3部規(guī)范對(duì)養(yǎng)老設(shè)施類型與項(xiàng)目的劃分及前文對(duì)3種醫(yī)養(yǎng)結(jié)合實(shí)現(xiàn)方式依托的設(shè)施類型研究,構(gòu)建出醫(yī)養(yǎng)結(jié)合模式下的社區(qū)養(yǎng)老設(shè)施類型體系(表2)．

while iter

iter←iter+1

start←rand() % (n-1)

end←rand() % (n-1-b) +b+ 1

forj←start to end do

mark the local best frog inmemplexiasPlb

mark thej-th frog in memplexiasPij

Ptemp← updatePijwithPlb

Pij←Ptemp

else

Ptemp← updatePijwithPgb

if(fitness(Ptemp)>fitness(Pij))thenPij←Ptemp

else

Pij←randomInit( )

endif

endif

endfor

endwhile

endfor

unitvalue=Weighti/TSi

(10)

圖5 全局更新策略Fig.5 Global update strategy

3.2.2 序列規(guī)劃算法流程 該模塊基于蛙跳優(yōu)化算法實(shí)現(xiàn)，流程如圖6所示，對(duì)于圖中的主要步驟說(shuō)明如下.

(1) 適應(yīng)度值計(jì)算.適應(yīng)度是評(píng)價(jià)青蛙個(gè)體好壞的指標(biāo)，其值為模型中目標(biāo)函數(shù)的計(jì)算結(jié)果.

(2) 模因分組.模因組由青蛙個(gè)體按適應(yīng)度值大小排序后進(jìn)行種群分組得到.種群分組采用循環(huán)依次進(jìn)組原則，循環(huán)的周期為模因組數(shù)量，每次循環(huán)每組只放入一個(gè)個(gè)體.

(3) 模因演化，即青蛙按改進(jìn)后的局部更新策略進(jìn)行跳躍.

(4) 全局交叉變異，即全局搜索.目的是進(jìn)行精英個(gè)體篩選和保留.

HIPA核心由兩個(gè)具有先后邏輯關(guān)系的模塊構(gòu)成，對(duì)于任務(wù)集T={t1,t2,…,tn},如果存在可合成情況下，首先，基于資源浪費(fèi)最少的啟發(fā)式規(guī)則進(jìn)行合成對(duì)象的選擇，待規(guī)劃任務(wù)數(shù)量將變?yōu)閙，m≤n.當(dāng)ti,tj|i,j∈[1,n]有沖突時(shí)，按照單獨(dú)規(guī)劃的原則，則必有一個(gè)不能被執(zhí)行，若可對(duì)其進(jìn)行合成，則兩個(gè)任務(wù)具有捆綁規(guī)劃的性質(zhì)，由此可提高任務(wù)的規(guī)劃率.在序列規(guī)劃過(guò)程中每一只青蛙都是一個(gè)長(zhǎng)度為l的二進(jìn)制位串，一個(gè)種群可看作是一個(gè)狀態(tài).當(dāng)種群規(guī)模為N時(shí),算法的狀態(tài)空間為Ω={0,1}l·N.由于前一模塊的合成，減少了任務(wù)數(shù)量，即l的取值從n變化成了m，有效地縮小了算法的狀態(tài)空間.改進(jìn)后的局部更新和全局更新策略使得第k+1輪算法開(kāi)始時(shí)已擁有的解的上界不小于第k輪解的上界，保證精英個(gè)體不會(huì)向下逃逸，驅(qū)使最優(yōu)青蛙不斷向食物最多的石頭跳躍，不斷逼近解空間的最優(yōu)解，從而HIPA向上收斂，算法向上快速收斂的性能將在實(shí)驗(yàn)部分得到驗(yàn)證.

圖6 蛙跳優(yōu)化算法流程示意

4 仿真實(shí)驗(yàn)

4.1 仿真實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)測(cè)試集借助Satellite Tool Kit軟件[19]生成.利用該軟件建立場(chǎng)景，設(shè)置一顆星載傳感器視場(chǎng)角FOV為10°，觀測(cè)側(cè)擺范圍為±30°的衛(wèi)星.地面站目標(biāo)隨機(jī)分布在星下點(diǎn)周?chē)?，保證對(duì)衛(wèi)星可見(jiàn)，衛(wèi)星沿軌道運(yùn)行生成目標(biāo)點(diǎn)的可見(jiàn)窗口，每個(gè)目標(biāo)點(diǎn)的優(yōu)先級(jí)為區(qū)間[1,10]上的隨機(jī)整數(shù)，觀測(cè)需要的側(cè)擺角取值范圍為區(qū)間[-30°,+30°]上的隨機(jī)數(shù).

為驗(yàn)證本文所提出的啟發(fā)式自主規(guī)劃算法HIPA的有效性，實(shí)驗(yàn)設(shè)置了遺傳算法(Genetic Algorithm,GA)、變鄰域搜索算法(Variable Neighborhood Search,VNS)、人工蜂群算法(Artificial Bee Colnony,ABC)、貪婪蛙跳算法(Greedy Frog Leaping Algorithm,GFLA)等4組算法作為對(duì)照實(shí)驗(yàn)，各算法的參數(shù)設(shè)置具體如表2所示.

表2 不同算法參數(shù)設(shè)置

本文實(shí)驗(yàn)在操作系統(tǒng)為macOS High Sierra (10.13)，處理器為2.3 GHz Intel Core i5，內(nèi)存為8 GB的筆記本上進(jìn)行，實(shí)驗(yàn)開(kāi)發(fā)平臺(tái)為CLion 2018.3.1，開(kāi)發(fā)語(yǔ)言為C++.

4.2 實(shí)驗(yàn)結(jié)果

本文對(duì)于任務(wù)數(shù)量分別為100、200、300的樣本在星載資源條件不同的情況下分別用每種算法進(jìn)行仿真驗(yàn)證，實(shí)驗(yàn)結(jié)果如表3和表4所示.

從表3和表4中可知，對(duì)于3種數(shù)量不同的任務(wù)集，本文提出的啟發(fā)式自主規(guī)劃算法在每種情況下均取得了收益最大值.通過(guò)對(duì)相同任務(wù)數(shù)量、不同資源限制的實(shí)驗(yàn)結(jié)果比較，發(fā)現(xiàn)資源因素對(duì)規(guī)劃結(jié)果有著舉足輕重的影響.在兩種不同的星載資源限制條件下，隨著樣本數(shù)量的增加，5種算法取得的收益最優(yōu)及平均都在逐漸增加，但遺傳算法、人工蜂群算法的增長(zhǎng)幅度略小于其他3種算法.本文提出的算法在對(duì)計(jì)算資源的消耗上達(dá)到了最小，盡管貪婪蛙跳算法和鄰域搜索算法在收益上比遺傳算法和人工蜂群算法得到了較優(yōu)的回報(bào)，但時(shí)間耗費(fèi)比人工蜂群算法多，且大于本文算法運(yùn)行時(shí)長(zhǎng).

表3 算法在資源不充足時(shí)的實(shí)驗(yàn)結(jié)果

表4 算法在資源充足時(shí)的實(shí)驗(yàn)結(jié)果

星載資源有限且寶貴，充分利用有限的資源進(jìn)行規(guī)劃是需要不斷追求的目標(biāo).為了直觀地反映每種算法對(duì)于資源的利用率，我們就電量和存儲(chǔ)兩種資源做了統(tǒng)計(jì)和分析，如圖7所示.

圖7反映了不同算法在不同情況下對(duì)于不同資源的利用率不同.在資源不充足情況下，對(duì)于任務(wù)數(shù)為100的樣本，本文所提出的算法對(duì)于兩種資源的利用率皆達(dá)到了最高，但在任務(wù)數(shù)分別為200和300的樣本集上，鄰域搜索和本文算法相差無(wú)幾. 值得注意的是在資源充足情況下，鄰域搜索算法對(duì)于資源的利用率低于本文算法，略次于貪婪蛙跳算法.

(a) 存儲(chǔ)利用率(資源不充足)

(b) 能量利用率(資源不充足)

(c) 存儲(chǔ)利用率(資源充足)

(d) 能量利用率(資源充足)

為表明算法的收斂性，實(shí)驗(yàn)選取了GFLA作為對(duì)照試驗(yàn)組，將迭代終止條件手動(dòng)設(shè)置為1 200，分別統(tǒng)計(jì)了不同迭代次數(shù)下的結(jié)果，如圖8所示，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為任務(wù)規(guī)劃收益.

從圖8可知，無(wú)論是資源充足或者資源不充足，HIPA都較快地收斂到了最優(yōu)值，表現(xiàn)出了較好的收斂性能.

為清楚地反應(yīng)不同算法運(yùn)行不同次數(shù)所得規(guī)劃方案結(jié)果的差異性，我們以序列總收益為指標(biāo)，計(jì)算了資源限制不同、樣本不同情況下各算法運(yùn)行10次所得值的標(biāo)準(zhǔn)差，結(jié)果如圖9所示.

從圖9可以看出，啟發(fā)式自主規(guī)劃算法在相同樣本相同資源條件下不同次數(shù)的運(yùn)行所得收益的離散程度總體較小.盡管在樣本任務(wù)數(shù)為300，資源不充足情況下，本文所提出的算法運(yùn)行所得結(jié)果數(shù)值分布不如遺傳算法集中，但遺傳算法在其他情況下均表現(xiàn)出較大的離散性，因此我們可以認(rèn)為啟發(fā)式自主規(guī)劃算法在任務(wù)規(guī)劃結(jié)果上具有一定的穩(wěn)定性.

(a) 算法在任務(wù)數(shù)為200，資源不充足情況下的收斂情況 (b) 算法在任務(wù)數(shù)為100，資源充足情況下的收斂情況

圖8 算法收斂性能比較

Fig.8 Algorithm convergence performance comparison

(a) 資源不充足

(b) 資源充足

綜合以上實(shí)驗(yàn)結(jié)果分析可得，本文所提出的面向小衛(wèi)星的啟發(fā)式自主規(guī)劃算法能夠在最短的時(shí)間內(nèi)，使衛(wèi)星利用自身有限的資源，以任務(wù)總收益最大化為目標(biāo)進(jìn)行觀測(cè)序列的自主規(guī)劃.

5 結(jié) 論

衛(wèi)星自主規(guī)劃任務(wù)作為提高衛(wèi)星運(yùn)行效率的手段之一，其重要性日漸增大[22-23].針對(duì)星上計(jì)算單元與星載資源有限的現(xiàn)狀，本文提出了一種面向小衛(wèi)星觀測(cè)任務(wù)的啟發(fā)式自主規(guī)劃算法，算法采用分塊思想將問(wèn)題分為兩個(gè)子模塊求解，即基于啟發(fā)式規(guī)則的任務(wù)合成與蛙跳優(yōu)化序列規(guī)劃，通過(guò)仿真實(shí)驗(yàn)表明所提出的啟發(fā)式規(guī)劃算法性能優(yōu)于貪婪蛙跳算法、鄰域搜索算法、遺傳算法、人工蜂群算法等幾種算法，能夠有效利用計(jì)算資源生成任務(wù)序列，可為諸如工業(yè)生產(chǎn)、無(wú)人機(jī)任務(wù)規(guī)劃、車(chē)輛路徑規(guī)劃等組合優(yōu)化問(wèn)題提供求解思路.下一步研究將在此基礎(chǔ)上展開(kāi)在動(dòng)態(tài)資源下的大規(guī)模多窗口衛(wèi)星任務(wù)自主規(guī)劃；數(shù)傳任務(wù)的自主規(guī)劃體系以及規(guī)劃算法的研究.