王凌峰,陳兆榮,陳 浩,陳宏盛

1(國防科學(xué)技術(shù)大學(xué) 電子科學(xué)與工程學(xué)院 信息工程系,長沙 410073)

2(95874部隊,南京 210022)

1 引 言

隨著航天科技的不斷發(fā)展,對地觀測衛(wèi)星(Earth Observing Satellite,EOS)已成為獲取遙感數(shù)據(jù)的重要航天資源,在農(nóng)業(yè)、氣象、軍事、科學(xué)研究等領(lǐng)域都起到了重要作用[1,2].為了更好地使用對地觀測衛(wèi)星對地面目標(biāo)進行有計劃的觀測,需要根據(jù)衛(wèi)星的能力制定優(yōu)化衛(wèi)星觀測方案,確定衛(wèi)星載荷開關(guān)機時間及載荷工作模式.

對地觀測衛(wèi)星通常運行在預(yù)先設(shè)定的固定軌道上,衛(wèi)星對地觀測過程受到能量、存儲、姿態(tài)調(diào)整等約束限制,難以保證所有觀測任務(wù)都能夠被響應(yīng).各應(yīng)用部門日益增加的遙感數(shù)據(jù)獲取需求與衛(wèi)星有限觀測能力之間的矛盾日益突出.衛(wèi)星任務(wù)規(guī)劃就是要從待觀測任務(wù)集合中挑選一個子集,在滿足衛(wèi)星約束的同時,使得觀測效益最大化.衛(wèi)星觀測任務(wù)規(guī)劃已被證明是一個典型的NP-hard問題[3,4],過載規(guī)劃特性明顯.為了充分利用寶貴的衛(wèi)星資源,衛(wèi)星觀測任務(wù)規(guī)劃問題得到了國內(nèi)外學(xué)者的高度關(guān)注,涌現(xiàn)出了大量研究工作.

Chen Y等[5]提出了一種求解多星任務(wù)規(guī)劃問題的演化學(xué)習(xí)型蟻群算法,在優(yōu)化過程中不斷抽取構(gòu)件知識用來指導(dǎo)后續(xù)優(yōu)化;Wei J等[6]建立了衛(wèi)星任務(wù)協(xié)同規(guī)劃模型,在一種基于遺傳禁忌選擇的求解算法基礎(chǔ)上提出協(xié)同進化模型的求解技術(shù);Wang J等[7]針對任務(wù)動態(tài)提交,任務(wù)數(shù)量和提交時間的不確定性,建立了衛(wèi)星動態(tài)實時規(guī)劃的多目標(biāo)模型;Chen H等[8]綜合考慮衛(wèi)星的觀測任務(wù)和數(shù)據(jù)傳輸任務(wù)規(guī)劃,構(gòu)建了衛(wèi)星觀測任務(wù)和數(shù)據(jù)傳輸任務(wù)聯(lián)合規(guī)劃模型,提出了一種基于遺傳算法的算法求解;Wang C等[9]將基于案例的學(xué)習(xí)方法引入到調(diào)度過程,考慮類似的歷史調(diào)度方案,提出了一種基于案例學(xué)習(xí)和遺傳算法的算法.

上述工作中,均假設(shè)一旦地面目標(biāo)被衛(wèi)星觀測,則該任務(wù)完成.但隨著遙感數(shù)據(jù)應(yīng)用的不斷深入,逐漸出現(xiàn)了帶有時間分辨率要求的對地觀測需求.即要求多顆對地觀測衛(wèi)星組成的星群對同一地面目標(biāo)進行周期性連續(xù)觀測,以便定期刷新地面目標(biāo)態(tài)勢.上述對地觀測需求的出現(xiàn),為衛(wèi)星任務(wù)規(guī)劃帶來了新的挑戰(zhàn),如觀測周期較目標(biāo)要求的觀測時間分辨率過大,會導(dǎo)致目標(biāo)態(tài)勢刷新不及時;而觀測周期太小,又會導(dǎo)致寶貴的衛(wèi)星資源被浪費.所以,衛(wèi)星周期性持續(xù)觀測任務(wù)規(guī)劃問題表現(xiàn)出了明顯的多目標(biāo)優(yōu)化特性.

論文首先對衛(wèi)星周期性持續(xù)觀測任務(wù)規(guī)劃問題進行了描述與分析,建立了數(shù)學(xué)規(guī)劃模型,提出了基于多目標(biāo)分解進化算法的衛(wèi)星周期性持續(xù)觀測任務(wù)規(guī)劃方法進行求解,最后通過實驗驗證了算法的可行性和有效性.

2 衛(wèi)星周期性持續(xù)觀測任務(wù)規(guī)劃問題

對地觀測衛(wèi)星繞地球飛行,運行在固定軌道上,當(dāng)衛(wèi)星飛行至地面目標(biāo)上空可視范圍內(nèi)(可視時間窗),星載傳感器開機,完成對目標(biāo)一次觀測.衛(wèi)星只能在若干離散的可視時間窗內(nèi)對目標(biāo)進行觀測.

多顆對地觀測衛(wèi)星分布在若干預(yù)先設(shè)定的軌道面上,位于同一軌道面上的多顆衛(wèi)星之間存在固定相位差,從而組網(wǎng)形成對地觀測衛(wèi)星群.于是,星群中成員衛(wèi)星可通過多星接力方式對地面目標(biāo)實施周期性觀測,不斷獲得觀測數(shù)據(jù),從而實現(xiàn)目標(biāo)態(tài)勢定期刷新.目標(biāo)的觀測周期要求稱為觀測時間分辨率.調(diào)度的目的就是針對每一個有觀測時間分辨率的地面觀測任務(wù),合理優(yōu)化地安排一系列衛(wèi)星在適當(dāng)?shù)目梢晻r間窗對其進行觀測,使得觀測時間分辨率滿足程度最大化,且衛(wèi)星能耗盡可能小.

我們擬構(gòu)建約束滿足問題(Constraint Satisfaction Problem,CSP)模型,首先給出相關(guān)形式化描述.

2.1 問題建模

衛(wèi)星周期觀測調(diào)度問題可形式化描述如下:

(a)任務(wù)規(guī)劃時段.規(guī)定規(guī)劃時段T=[TB,TE],TB為規(guī)劃開始時間,TE為規(guī)劃結(jié)束時間.衛(wèi)星所有活動須在此規(guī)劃時段內(nèi)進行.

2.2 約束模型

衛(wèi)星繞地球飛行,執(zhí)行對地觀測任務(wù),由于運行軌道、載荷能力、衛(wèi)星能量等限制,需要考慮的約束較多.本文主要考慮如下約束:

(a)兩次開機時間最短時間間隔約束.星載傳感器關(guān)機之后,必須經(jīng)過一段時間才能再次開機.

?satk∈Sat,?awi∈AW_DO_Satk,

(1)

(b)單次開機時間約束.星載傳感器單次開機時間不能低于單次最短開機時間,且不能長于單次最長開機時間.

?satk∈Sat,?awi∈AW_DO_Satk,

(2)

(c)單圈最長開機時間約束.星載傳感器單圈累積開機時間不能大于單圈最長開機時間.

(3)

(d)單天最大開機次數(shù)約束.傳感器單天累計開機次數(shù)不能大于單天最大開機次數(shù).

(4)

2.3 目標(biāo)函數(shù)

基于衛(wèi)星運行實際業(yè)務(wù)需求,本文主要考慮以下兩個優(yōu)化目標(biāo):

1)方案總超時程度(the Degree of Timeout,DT):對于每個觀測任務(wù),在規(guī)劃時間段內(nèi)的兩次開機間隔均小于任務(wù)時間分辨率,則任務(wù)完成;若兩次開機時間大于時間分辨率,超出時間稱為超時時間.我們定義目標(biāo)在任務(wù)規(guī)劃時間段內(nèi)累計超時時間與規(guī)劃時間長度的比值稱為該任務(wù)的超時程度.方案中每個任務(wù)的超時程度用任務(wù)優(yōu)先級加權(quán)平均得到方案總超時程度.

?satk∈Sat,?awi∈AW_DO_Taskk,

(5)

(6)

方案總超時程度:

(7)

2)衛(wèi)星資源消耗(Resource Consumption,RC):衛(wèi)星在執(zhí)行觀測任務(wù)時會消耗能源、存儲容量等資源,我們考慮用衛(wèi)星使用時間來衡量衛(wèi)星資源的消耗,使用時間越長資源的消耗越多,并用衛(wèi)星訪問窗口的總時長進行歸一化,表示方案對衛(wèi)星觀測資源的使用程度.

(8)

3 衛(wèi)星周期性持續(xù)觀測任務(wù)規(guī)劃方法

考慮單個優(yōu)化目標(biāo)的衛(wèi)星對地觀測任務(wù)規(guī)劃問題是典型的NP-Hard問題[10].我們考慮了方案總超時程度和資源消耗兩個優(yōu)化目標(biāo),求解難度不會低于單目標(biāo)優(yōu)化問題.如果采用完全搜索算法進行求解,當(dāng)問題規(guī)模較大時,有效時間內(nèi)將很難給出可行解.所以,我們擬選用基于多目標(biāo)分解進化算法的衛(wèi)星周期性持續(xù)觀測任務(wù)規(guī)劃方法進行求解.

基于分解的多目標(biāo)進化算法(MOEA/D)是由Zhang Q等[11]提出的,算法將多目標(biāo)優(yōu)化問題分解轉(zhuǎn)化為多個單目標(biāo)優(yōu)化子問題,并認為每個子問題對相鄰的子問題有指導(dǎo)作用,分別對每一個子問題進行求解,最終得到原優(yōu)化問題的Pareto最優(yōu)解.

由于遺傳算法具有良好的全局搜索能力,具有內(nèi)在并行性,適合求解多目標(biāo)優(yōu)化問題[12].并且MEOA/D算法的進化計算部分能夠直接應(yīng)用單目標(biāo)遺傳算法,理論分析表明其計算復(fù)雜度比NSGA-II算法低[13].該算法已應(yīng)用于近空通信系統(tǒng)部署優(yōu)化[14]、作業(yè)車間調(diào)度問題[15]、天線設(shè)計[16]等領(lǐng)域,取得了較好的計算效果.

我們采用MOEA/D算法框架,提出基于多目標(biāo)分解進化算法的衛(wèi)星周期性持續(xù)觀測任務(wù)規(guī)劃方法(Satellite Periodic Continuous Observing Scheduling Multi-objective Optimization Algorithm Based on Decomposition,SPCOSM).

3.1 算法流程圖

SPCOSM算法的流程圖如圖1所示.

3.2 關(guān)鍵算子設(shè)計

3.2.1 問題編碼

我們采用等長二進制編碼方式來構(gòu)造染色體,決策變量采用觀測窗口的使用標(biāo)志.將參與規(guī)劃的訪問時間窗口按照開始時間先后排序,取出每一個訪問時間窗口的使用標(biāo)志,組合得到一個解:

X=(x1,x2,…,xi,…,xKall).

(9)

3.2.2 種群初始化

算法需要初始化參考點z*=(inf,inf);初始化權(quán)向量,生成N個均勻分布的權(quán)向量λ1,λ2,…,λN,對應(yīng)得到N個子問題;初始化進化種群P,隨機生成規(guī)模為N的進化種群P.

圖1 SPCOSM算法流程圖Fig.1 Flow diagram of SPCOSM

3.2.3 交叉算子

如圖2所示,我們采用單點交叉算子,在種群中依概率選擇兩個父代個體,并隨機確定一個交叉點,互換交叉點后的基因序列,實現(xiàn)交叉過程.

圖2 交叉操作算子示意圖Fig.2 Schematic diagram of crossover operator

3.2.4 變異算子

如圖3所示,在交叉?zhèn)€體中,我們依概率選取個體執(zhí)行變異操作.我們采取單點隨機變異,在交叉?zhèn)€體中依照變異概率選取個體進行變異操作,隨機選取基因位置進行反向變異.

圖3 變異操作算子示意圖Fig.3 Schematic diagram of mutation operator

3.2.5 約束檢測及修正算子

值得注意的是,在進化計算過程中,種群經(jīng)過交叉和變異操作后會產(chǎn)生不滿足衛(wèi)星約束條件的個體,稱為不可行解.我們提出約束檢查及修正(Constraint Checking and Correction,CCC)算法,遍歷種群中所有個體,進行約束檢查,對不可行解進行約束修正,直至種群中所有個體均滿足約束為止.算法主要步驟如圖4所示.

圖4 CCC算法主要步驟Fig.4 Main steps of the CCC

在算法CCC中,randomDelete函數(shù)執(zhí)行隨機刪除輸入集合中一個元素的操作;step 1-step 2從衛(wèi)星觀測任務(wù)集合中將需要執(zhí)行的衛(wèi)星觀測任務(wù)選取出來;step 3-step 7檢測單次開機時間約束,并將不滿足約束的時間窗刪除;step 8-step 15中,temp是不滿足兩次開機時間約束的連續(xù)窗口集合,所有不滿足兩次開機時間約束的窗口集合組成集合A;step 16- step 19對集合A中每一個集合調(diào)用randomDelete 函數(shù),直到該集合滿足兩次開機時間約束為止,checkInterval函數(shù)只要輸入集合中存在不滿足兩次開機約束的窗口,就返回ture;step 20將每一圈的時間窗選取出來分別組成集合;step 21-step 24對每一個集合調(diào)用randomDelete 函數(shù),直到該集合滿足單圈最長開機時間約束為止;step 25將每一天的時間窗選取出來分別組成集合;step 26-step 29對每一個集合調(diào)用randomDelete 函數(shù),直到該集合滿足單天最大開機次數(shù)約束為止.

3.2.6 更新算子

更新參考點z*,z*=(min(fDT(X)),min(fRC(X)));更新子問題的最優(yōu)解xi,若f(xi)>f(yi),xi=yi;更新外部種群(EP).

4 實驗及分析

目前衛(wèi)星規(guī)劃調(diào)度領(lǐng)域尚沒有公認的Benchmark 測試問題集,為了驗證我們提出算法的適用性和可行性,在AGI公司發(fā)布的星歷數(shù)據(jù)庫中選擇了12顆衛(wèi)星,在地圖上選擇16個點目標(biāo),模擬真實的多星任務(wù)規(guī)劃過程,選擇不同數(shù)量的點目標(biāo)生成了不同規(guī)模、不同目標(biāo)時間分辨率的測試數(shù)據(jù)集.我們選擇了3種目標(biāo)分辨率,分別為1小時(1h)、2小時(2h)、4小時(4h),具體測試數(shù)據(jù)集見表1.經(jīng)過試驗,得到了每個實驗用例的進化情況和Pareto前沿.

設(shè)置衛(wèi)星任務(wù)規(guī)劃時段為24小時,計算平臺為Core-i5 2.70 GHz,8G RAM,采用MATLAB編碼.在算法中,我們?nèi)∽訂栴}規(guī)模和種群規(guī)模N=101,交叉概率為0.8,變異概率為0.15,進化代數(shù)為1000代.

表1 測試數(shù)據(jù)集Table 1 Testing dataset

每個用例得到的Pareto前沿如圖5所示.

如圖5可知,在SPCOSM計算過程中,種群的非支配前沿隨著進化過程的推進逐漸散開,向Pareto最優(yōu)解集逼近.SPCOSM算法的計算結(jié)果能夠為操作員提供多目標(biāo)決策數(shù)據(jù)支持,而不僅僅找到一個優(yōu)化解.

為了驗證我們提出算法的有效性,我們引入了求解該問題的一種基于啟發(fā)式規(guī)則的搜索算法(Search Algorithm Based on Heuristic Rules for Satellite Periodic Continuous Observing Scheduling Problem,SABHR).

SABHR采用貪婪思想,其核心思路是:按照任務(wù)按照優(yōu)先級從高到低的順序依次處理,均以目標(biāo)要求的時間分辨率截止點為起點,先按照時間順序反向向前搜索,使用搜索到的第一個可用的訪問時間窗口,若反向搜索沒有找到可用訪問時間窗口,再按照時間順序正向向后搜索,安排搜索到的第一個可用的訪問時間窗口,直到找到可用的訪問時間窗口或遍歷完所有時間窗口為止,從而得到一個可行的衛(wèi)星觀測方案.采用這樣的策略,能夠保證在盡量滿足目標(biāo)時間分辨率的前提下,降低衛(wèi)星資源消耗.算法主要步驟如圖6所示.

step1將任務(wù)按照優(yōu)先級由高到低的順序排序,step 2-step 8選出屬于當(dāng)前任務(wù)的訪問時間窗,step 9將篩選的時間窗按照開始時間排序,step 10定義一個時間標(biāo)簽變量,記錄使用窗口的結(jié)束時間,step 11-step 19將當(dāng)前安排時間窗之后的時間窗分為兩個集合,集合A表示未超過時間分辨率的時間窗,集合B表示超過的時間窗,step 20定義一個標(biāo)簽變量,表示是否找到一個未超出時間分辨率的時間窗,step 21-step 27選擇集合A中按照時間順序最后一個可用的時間窗,如果沒有,則step 28-step 36選擇集合B中按照時間順序第一個可用的時間窗.安排時間窗時,均調(diào)用SetConflictFlag函數(shù)將與當(dāng)前安排時間窗不滿足公式(1)-公式(4)約束的時間窗沖突標(biāo)志置為yi=1,如step 24和step 32.

圖5 目標(biāo)空間和Pareto前沿Fig.5 Objective space and Pareto front

表2 SABHR算法的結(jié)果Table 2 Results of SABHR algorithm

在測試數(shù)據(jù)集上,使用SABHR算法,得到了衛(wèi)星可用的觀測方案,通過(7)式和(8)式計算出方案總超時程度和資源消耗,如表2所示.

將SABHR算法的解和SPCOSM算法的Pareto解集分別在方案總超時程度、資源消耗和綜合兩個優(yōu)化目標(biāo)三個方面做了比較比較,將SPCOSM的Pareto解集中支配SABHR的解的個數(shù)分別做了統(tǒng)計,如圖7-圖9所示.

圖6 SABHR的主要步驟Fig.6 Main steps of the SABHR

圖7 在DT上SPCOSM支配SABHR解的數(shù)量Fig.7 Number of solutions that SPCOSM dominates ABHR on DT

從圖7、圖8和圖9中,可以看出SPCOSM算法能夠得到比SABHR算法質(zhì)量更好的解,且能夠提供大量的方案供操作員選擇,這表明SPCOSM算法具有有效性和實用性.

5 結(jié)論及下一步工作

本文針對衛(wèi)星周期性持續(xù)觀測任務(wù)規(guī)劃問題,建立了約束滿足問題模型,采用基于分解的多目標(biāo)優(yōu)化框架,提出了基于分解的衛(wèi)星觀測調(diào)度多目標(biāo)算法(SPCOSM),并設(shè)計了仿真實驗.結(jié)果表明,算法能夠求得較好質(zhì)量的Pareto前沿.能夠有效求解組網(wǎng)衛(wèi)星周期性持續(xù)觀測任務(wù)規(guī)劃問題.

圖8 在RC上SPCOSM支配SABHR解的數(shù)量Fig.8 Number of solutions that SPCOSM dominates SABHR on RC

圖9 SPCOSM支配SABHR解的數(shù)量Fig.9 Number of solutions that SPCOSM dominates SABHR

SPCOSM算法會計算整個Pareto前沿,但操作員通常只關(guān)注某一特定解空間內(nèi)的Pareto優(yōu)化解集,而非整個Pareto前沿.這就是用戶的偏好信息.所以,我們下一步的工作在于將研究基于偏好的多目標(biāo)優(yōu)化方法在衛(wèi)星任務(wù)規(guī)劃中的應(yīng)用.

：

[1] Lin Zhen-hai.Mission planning for electromagnetic environment monitors satellite based on simulated annealing algorithm[C].Proceeding of IEEE Canadian Conference on Electrical and Computer Engineering (CCECE),2015:530-535.

[2] Steve Chien,Joshua Doubleday,David Mclaren,et al.Monitoring flooding in thailand using earth observing one in a sensorweb[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing,2013,6(2):291-297.

[3] Lin Wei-cheng,Liao Da-yin,Liu Chung-yang,et al.Daily imaging scheduling of an earth observation satellite[J].IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans,2005,35(2):213-223.

[4] Li Yu-qing,Wang Ri-xin,Liu Yu,et al.Satellite range scheduling with the priority constraint:an improved genetic algorithm using a station ID encoding method[J].Chinese Journal of Aeronautics,2015,28(3):789-803.

[5] Chen Ying-wu,Yao Feng,Li Ju-fang,et al.A learnable ant colony optimization to the mission planning of multiple satellites[J].Systems Engineering-Theory & Practice,2013,33(3):791-801.

[6] Jiang Wei,Pang Xiu-li,Hao Hui-cheng.Collaborative scheduling model and algorithm for imaging satellite network[J].System Engineering and Electronics,2013,35(10):2093-2101.

[7] Wang Jian-jiang,Zhu Xiao-min,Yang Laurence T,et al.Towards dynamic real-time scheduling for multiple earth observation satellites[J].Journal of Computer and System Sciences,2015,81(1):110-124.

[8] Chen Hao,Wu Jiang-jiang,Shi Wen-yuan,et al.Coordinate scheduling approach for EDS observation tasks and data transmission jobs[J].Journal of Systems Engineering and Electronics,2016,27(4):822-835.

[9] Wang Chen,Chen Hao,Zhai Bao-rong,et al.Satellite observing mission scheduling method based on case-based learning and a genetic algorithm[C].Proceedings of IEEE International Conference on Tools with Artificial Intelligence (ICTAI),2016:627-634.

[10] Chen Yu,Zhang Deng-yi,Zhou Meng-qiang,et al.Multi-satellite observation scheduling algorithm based on hybrid genetic particle swarm optimization[M].Advances in Information Technology and Industry Applications,Springer Berlin Heidelberg,2012:441-448.

[11] Zhang Qing-fu,Li Hui.MOEA/D:a multi-objective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.

[12] Yu Wei,Li Bai-zhan,Jia Hong-yuan,et al.Application of multi-objective genetic algorithm to optimize energy efficiency and thermal comfort in building design[J].Energy and Buildings,2015,88:135-143.

[13] Li Hui,Zhang Qing-fu.Multi-objective optimization problems with complicated Pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.

[14] Wang Zhao,Gong Mao-guo,Lei Yu,et al.A memetic algorithm based on MOEA/D for near space communication system deployment optimization on tide user model[C].Proceeding of IEEE Congress on Evolutionary Computation (CEC),2016:3614-3621.

[15] Zhao Fu-qing,Chen Zhen,Wang Jun-biao,et al.An improved MOEA/D for multi-objective job shop scheduling problem[J].International Journal of Computer Integrated Manufacturing,2016,30(6):616-640.

[16] Ding Da-wei,Wang Gang.Modified multi-objective evolutionary algorithm based on decomposition for antenna design[J].IEEE Transactions on Antennas and Propagation,2013,61(10):5301-5307.

附中文參考文獻：

[5] 陳英武,姚 鋒,李菊芳,等.求解多星任務(wù)規(guī)劃問題的演化學(xué)習(xí)型蟻群算法[J].系統(tǒng)工程理論與實踐,2013,33(3):791-801.

[6] 姜 維,龐秀麗,郝會成.成像衛(wèi)星協(xié)同任務(wù)規(guī)劃模型與算法[J].系統(tǒng)工程與電子技術(shù),2013,35(10):2093-2101.