面向多星區(qū)域觀測調(diào)度的改進(jìn)型自適應(yīng)遺傳算法

樊育，劉瑩瑩，周軍

西北工業(yè)大學(xué) 航天學(xué)院，西安 710072

地球觀測衛(wèi)星(Earth observation satellite, EOS)可以實(shí)現(xiàn)對指定點(diǎn)目標(biāo)或區(qū)域目標(biāo)的觀測成像。但是，如果衛(wèi)星不具有側(cè)擺能力，那么衛(wèi)星僅能對其星下點(diǎn)軌跡上視場角范圍內(nèi)的目標(biāo)實(shí)現(xiàn)觀測；而實(shí)際任務(wù)目標(biāo)中的大部分區(qū)域都是沒有在指定衛(wèi)星星下點(diǎn)軌跡上及其視場角范圍內(nèi)的。因此在衛(wèi)星不具有側(cè)擺能力的情況下，對指定區(qū)域目標(biāo)的覆蓋效率是很低的。為了解決這個問題，可將星載相機(jī)在垂直于衛(wèi)星星下點(diǎn)軌跡的方向上進(jìn)行擺動，以此實(shí)現(xiàn)對未在星下點(diǎn)軌跡上及其視場角范圍內(nèi)的目標(biāo)進(jìn)行觀測，大大提高衛(wèi)星的對地覆蓋效率。另外，隨著微小衛(wèi)星的發(fā)展，大大降低了衛(wèi)星的制作成本，使得越來越多的衛(wèi)星組成衛(wèi)星星座[1-2]去完成對指定區(qū)域目標(biāo)的觀測成為各個國家和企業(yè)的研究重點(diǎn)。

當(dāng)今資源充分利用的環(huán)境下，如何利用一定的衛(wèi)星資源實(shí)現(xiàn)對目標(biāo)區(qū)域最大程度的覆蓋[3]，已經(jīng)是研究對地觀測衛(wèi)星的熱點(diǎn)問題，引起眾多學(xué)者的關(guān)注。伍國華等[4-5]提出了動態(tài)聚類調(diào)度算法(dynamic clustering scheduling algorithm, DCSA)來解決多星多軌道圈次的觀測調(diào)度問題，并使用模擬退火算法搜索全局最優(yōu)解；李仕學(xué)等[6]面向月表大區(qū)域成像任務(wù)需求，提出了拼接成像側(cè)擺角優(yōu)化方法，并提出基于sigmoid函數(shù)的自適應(yīng)遺傳算法(sigmoid adaptive genetic algorithm, SAGA)對其進(jìn)行求解；Wang等[7]為了提高計算效率，考慮了當(dāng)前任務(wù)與歷史任務(wù)的相似性，提出具有檢索、匹配和修正的相似性學(xué)習(xí)法，并結(jié)合遺傳算法對實(shí)際觀測任務(wù)進(jìn)行求解，大大加快了任務(wù)的求解速度； Fei等[8]考慮衛(wèi)星傳感器的實(shí)際側(cè)擺能力，結(jié)合貪婪算法的思想提出一種動態(tài)劃分目標(biāo)區(qū)域的算法；Xu 等[9]針對多衛(wèi)星區(qū)域調(diào)度問題，提出一種3階段解決框架，即離散、分解和調(diào)度階段，在最后一階段利用遺傳算法進(jìn)行求解；Zhu等[10]綜合考慮地球觀測衛(wèi)星調(diào)度中的成像與數(shù)據(jù)傳輸問題，提出了一種兩階段遺傳模擬退火算法去解決調(diào)度問題；Wu等[11]針對調(diào)度任務(wù)中的重要緊急任務(wù)調(diào)度處理，提出一種結(jié)合局部搜索的混合蟻群算法對調(diào)度問題進(jìn)行優(yōu)化；劉華俊等[12]針對現(xiàn)有覆蓋算法低效耗時的技術(shù)瓶頸，提出了一種針對成像衛(wèi)星區(qū)域覆蓋的自適應(yīng)規(guī)劃方法，包括自適應(yīng)的網(wǎng)格劃分、平衡成像精度和覆蓋效率的最大可視覆蓋計算以及窗口優(yōu)化的衛(wèi)星區(qū)域覆蓋策略。

在以上研究中還存在以下不足：1)文獻(xiàn)[4-5]只研究了點(diǎn)目標(biāo)任務(wù)的聚類調(diào)度問題，針對區(qū)域目標(biāo)的調(diào)度問題還未研究；2)文獻(xiàn)[6]只研究了單星成像問題，并未對多星成像問題進(jìn)行研究；3)文獻(xiàn)[12]提出的優(yōu)化方法只找到一個局部最優(yōu)解，并不能保證其全局最優(yōu)性；4)都是通過STK(Satellite tool kit)獲得時間窗口，沒有通過軌道六要素自主計算星下點(diǎn)軌跡，從而獲得對目標(biāo)觀測的時間窗口，使得程序算法缺乏靈活性；5)都是僅僅以衛(wèi)星對地觀測的覆蓋率作為唯一的收益指標(biāo)，均未考慮對目標(biāo)區(qū)域總覆蓋時間這一指標(biāo)；而這一指標(biāo)直接反映了衛(wèi)星在規(guī)定時間內(nèi)對指定目標(biāo)的觀測時間長短，是一個重要的覆蓋指標(biāo)。

基于以上情況，本文根據(jù)衛(wèi)星的軌道六要素計算出星下點(diǎn)軌跡，并采用網(wǎng)格點(diǎn)法自主劃分區(qū)域目標(biāo)，在指定的最大側(cè)擺角范圍內(nèi)計算出每顆衛(wèi)星每次過境的時間窗口，得出每顆衛(wèi)星在每次過境時段內(nèi)的側(cè)擺角集合。最后將問題轉(zhuǎn)化為多個時間窗口和多個側(cè)擺角集合的動態(tài)組合調(diào)度優(yōu)化問題，為了更高效地實(shí)現(xiàn)目標(biāo)收益的最大化，提出了結(jié)合平均Hamming距離、神經(jīng)元激活函數(shù)sigmoid和高斯函數(shù)的改進(jìn)型自適應(yīng)遺傳算法(Hamming distance sigmoid Gauss function adaptive genetic algorithm, HSGAGA)對此動態(tài)組合調(diào)度優(yōu)化問題進(jìn)行求解，并通過算例與其他常用的優(yōu)化算法,包括標(biāo)準(zhǔn)遺傳算法(genetic algorithm，GA)、改進(jìn)型遺傳算法(improved genetic algorithm,IGA)、標(biāo)準(zhǔn)模擬退火算法(simulated annealing algorithm,SA)、改進(jìn)型模擬退火算法(improved simulated annealing algorithm，ISA)進(jìn)行對比，驗(yàn)證了本文所提出的HSGAGA算法的優(yōu)良性能。

1 衛(wèi)星對目標(biāo)的側(cè)擺角度計算

1.1 星載遙感器的覆蓋能力

在衛(wèi)星具有側(cè)擺能力的情況下，衛(wèi)星在軌道上對地的觀測角指的是衛(wèi)星在垂直于星下點(diǎn)軌跡的方向上，視場角與側(cè)擺角的結(jié)合。如圖1所示。

圖1 衛(wèi)星對地覆蓋示意Fig.1 Illustration ofsatellite coverage

若衛(wèi)星某時刻t的瞬時軌道高度為h，相應(yīng)星下點(diǎn)為S′，星載遙感器的側(cè)擺角度為β，視場角為FOV(field of view)，則衛(wèi)星對地觀測角為β+FOV/2。假設(shè)地球是一半徑為Re的均勻圓球體，h為衛(wèi)星軌道高度，衛(wèi)星距地心距離SOe=h+Re，由幾何關(guān)系，此時弧段AS′對應(yīng)的地心覆蓋角φ為：

(β+FOV/2)

同時，由地心覆蓋角可得覆蓋幅寬為：

AS′=φ·Re

當(dāng)然，對于不同高度的軌道衛(wèi)星，觀測角β+FOV/2也有其相應(yīng)的約束范圍，如圖2所示。

圖2 衛(wèi)星對地觀測范圍示意Fig.2 Illustration of satellite observation range

最大觀測角即就是觀測邊界與地球相切，即θ=90°，根據(jù)幾何關(guān)系，軌道高度為h的衛(wèi)星對地最大觀測角為：

即有觀測角約束：

β+FOV/2≤φ

而且，對于不同高度、不同相機(jī)幅寬的軌道衛(wèi)星，對地觀測的視場角FOV也不同，如圖3所示，其中l(wèi)為相機(jī)半幅寬。

根據(jù)幾何關(guān)系，軌道高度為h，相機(jī)幅寬為2l的衛(wèi)星對地觀測的視場角大小為：

圖3 衛(wèi)星相機(jī)半幅寬l與視場角FOVFig.3 Satellite camera width l and field of view FOV

1.2 側(cè)擺角度的計算

對于衛(wèi)星對區(qū)域目標(biāo)的側(cè)擺角度計算，可采用經(jīng)典的網(wǎng)格點(diǎn)法將區(qū)域目標(biāo)轉(zhuǎn)化為點(diǎn)目標(biāo)集合，進(jìn)而將問題轉(zhuǎn)化為衛(wèi)星對區(qū)域點(diǎn)集合中各個點(diǎn)的側(cè)擺角度計算。此時，采用點(diǎn)的包含性檢驗(yàn)來判斷是否可見，同時計算出側(cè)擺角集合。

如圖1所示，若目標(biāo)點(diǎn)位于B(λ,φ)，則過B點(diǎn)作垂直于衛(wèi)星星下點(diǎn)軌跡的垂線，并與其交與S′(λx,φx)。根據(jù)幾何關(guān)系，采用基于球面三角學(xué)的大圓距離求解算法，得目標(biāo)點(diǎn)B與衛(wèi)星星下點(diǎn)S′的弧長BS′為：

BS′=arccos[sinλsinλx+

cosλcosλxcos(φx-φ)]·Re

則地心覆蓋角∠BOeS為：

∠BOeS=BS′/Re

最后，在三角形BOeS中，根據(jù)幾何關(guān)系，求得處于S處的衛(wèi)星對目標(biāo)點(diǎn)B的側(cè)擺角度β為：

2 多星觀測調(diào)度模型

2.1 問題特點(diǎn)及約束分析

對于本文所研究的多星觀測調(diào)度問題，具有如下的特點(diǎn)及約束。

1)衛(wèi)星調(diào)度方式：所有衛(wèi)星僅在垂直于星下點(diǎn)軌跡的方向上具有側(cè)擺能力。

2)衛(wèi)星機(jī)動能力約束：限制衛(wèi)星在同一過境時段內(nèi)，只能以單一的側(cè)擺角進(jìn)行過境，在不同過境時段內(nèi)，可以以不同的側(cè)擺角進(jìn)行過境。

3)光照條件約束：為了獲得衛(wèi)星對指定目標(biāo)更好的的觀測信息，必須要保證衛(wèi)星對指定目標(biāo)觀測時的太陽高度角，即任一顆衛(wèi)星對區(qū)域目標(biāo)內(nèi)的任意一個子目標(biāo)進(jìn)行觀測時，太陽高度角[13]都必須大于所要求的保證良好光照條件的臨界值。

2.2 調(diào)度模型中的參數(shù)含義及表示

1)Sat={S1,S2,…,SNS}表示衛(wèi)星資源集合，即在調(diào)度任務(wù)中共有NS顆對地觀測衛(wèi)星資源可執(zhí)行目標(biāo)區(qū)域的觀測任務(wù)。

2)O={oi|i=1,2,…,Ni}表示衛(wèi)星對目標(biāo)區(qū)域進(jìn)行過境的軌道圈次資源，Ni表示多顆衛(wèi)星的總的過境次數(shù)。

3)T={ti|i=1,2,…,N}是待觀測的目標(biāo)集合，N表示總?cè)蝿?wù)數(shù)量。

4)Twrj={twrj1,twrj2,…,twrjNrj}表示在考慮天氣條件的情況下，衛(wèi)星r對目標(biāo)j的Nrj個可見時間窗口，其可寫為twrjm=[Strjm,Etrjm]。其中Strjm、Etrjm分別表示衛(wèi)星r對候選任務(wù)j的第m個可見時間窗口的開始時間和結(jié)束時間。

(5)βr,i={βr,i,1,βr,i,2,…,βr,i,Ng}表示衛(wèi)星r在第i次過境下可供選擇的Ng個側(cè)擺角集合。

(6)v={v1,v2,…,vi,…,vr}表示衛(wèi)星r上的傳感器要對準(zhǔn)待觀測目標(biāo)時的側(cè)擺速率。

(7)a={a1,a2,…,ai,…,ar}表示衛(wèi)星r在對某個目標(biāo)觀測之前的傳感器開機(jī)時間。

(8)wr={wr,1,wr,2,…,wr,oi,…,wr,N}表示衛(wèi)星r在過境圈次oi上對地觀測活動消耗星上存儲資源的速率。

(9)Wr={Wr,1,Wr,2,…,Wr,oi,…,Wr,N}表示衛(wèi)星r在過境圈次oi上允許消耗的最大存儲資源。

(10)Xr,i,j={Xr,i,j,1,Xr,i,j,2,…,Xr,i,j,N}表示衛(wèi)星r在第i次過境第j次側(cè)擺情況下對各個目標(biāo)點(diǎn)的可見性集合。若Xr,i,j,k=1，則表示衛(wèi)星r在第i次過境第j次側(cè)擺情況下對目標(biāo)點(diǎn)k可見；反之，若Xr,i,j,k=0，則表示對目標(biāo)點(diǎn)k不可見。

(11)tmr,i,j={tmr,i,j,1,tmr,i,j,2,…,tmr,i,j,N}表示衛(wèi)星r在第i次過境第j次側(cè)擺情況下對各個目標(biāo)點(diǎn)的觀測時刻集合。若tmr,i,j,k=t(t≠0)，則表示衛(wèi)星r在第i次過境第j次側(cè)擺情況下對目標(biāo)點(diǎn)k的觀測時刻為t；反之，若tmr,i,j,k=0則表示對目標(biāo)點(diǎn)k不可見。

(12)tcr,i={tcr,i,1,tcr,i,2,…,tcr,i,Ng}表示衛(wèi)星r在第i次過境且采用各個側(cè)擺角的情況下對目標(biāo)區(qū)域的覆蓋持續(xù)時間。若tcr,i,j=t(t≠0)，則表示衛(wèi)星r在第i次過境第j次側(cè)擺情況下對目標(biāo)區(qū)域的持續(xù)覆蓋時間為t；反之，若tcr,i,j=0則表示對目標(biāo)區(qū)域不可觀測。

2.3 調(diào)度模型的建立

在指定時間段內(nèi)，衛(wèi)星對地觀測的覆蓋指標(biāo)主要有兩個：一是對目標(biāo)區(qū)域的覆蓋率；二是對目標(biāo)區(qū)域總的覆蓋時間。為了綜合考慮這兩種覆蓋指標(biāo)，此多星觀測調(diào)度問題的目標(biāo)收益取為：

式中：{x1,x2,…,xN}為決策向量集，xi表示多顆衛(wèi)星第i次過境時選擇第xi個側(cè)擺角；wk為各覆蓋指標(biāo)的權(quán)值；fk{x1,x2,…,xN}為在決策向量集{x1,x2,…,xN}下的第k個覆蓋指標(biāo)的值，f1、f2分別表示覆蓋率和總的覆蓋時間。

調(diào)度過程中需要滿足復(fù)雜的約束條件，如下所示。

1)側(cè)擺角約束：考慮機(jī)動能力，任意側(cè)擺角都必須不大于最大側(cè)擺角，否則將不能側(cè)擺成功。

2)側(cè)擺時間約束：任意一顆衛(wèi)星在對指定目標(biāo)相鄰兩次過境觀測過程中，所間隔的時間必須不小于衛(wèi)星星載設(shè)備所需機(jī)動調(diào)整的時間，即：

3)存儲容量約束：在第oi次過境觀測中，衛(wèi)星所獲得的觀測信息容量必須不大于衛(wèi)星單軌運(yùn)行所允許的最大存儲容量，即：

3 改進(jìn)型自適應(yīng)遺傳算法

3.1 算法實(shí)現(xiàn)流程

遺傳算法(GA)是由Holland[14]于20世紀(jì)70年代提出的一種基于自然選擇法則的搜索尋優(yōu)算法。但標(biāo)準(zhǔn)遺傳算法在交叉操作和變異操作中的交叉率和變異率為固定值，對于耦合性較高的復(fù)雜優(yōu)化問題，不利于種群的進(jìn)化而易于陷入局部最優(yōu)。

為了改進(jìn)這一缺陷，Srinivas、任子武等[15-16]提出了自適應(yīng)遺傳算法，但在進(jìn)化初期或后期，都存在易陷入局部最優(yōu)的問題。

為了更快更高效地搜索到全局最優(yōu)解，實(shí)現(xiàn)目標(biāo)收益的最大化，本文提出了結(jié)合平均Hamming距離、神經(jīng)元激活函數(shù)sigmoid和高斯函數(shù)的改進(jìn)型自適應(yīng)遺傳算HSGAGA對動態(tài)組合調(diào)度優(yōu)化問題進(jìn)行求解，其算法流程如圖4所示，其中R表示染色體長度。

圖4 改進(jìn)型自適應(yīng)遺傳算法HSGAGA的流程Fig.4 Flowchart of improved adaptive genetic algorithm HSGAGA

3.2 算法典型步驟

(1)編碼

采用k進(jìn)制編碼，直接將決策向量集x={x1,x2,…,xN}作為染色體，x中的元素xi作為基因。k編碼類似于十進(jìn)制編碼，唯一不同的是十進(jìn)制編碼中基因的取值為0～9之間的整數(shù)，而k編碼中基因的取值為1～k之間的整數(shù)。

(2)種群初始化

使用蒙特卡洛方法逐步生成初始種群中的個體，并且通過比較兩個k進(jìn)制編碼的染色體對應(yīng)基因不同的個數(shù)作為Hamming距離，以此來控制初始種群的個體差異，改善初始種群的活力，以擴(kuò)大種群的多樣性。具體方法如下：若新產(chǎn)生的個體與前面已產(chǎn)生的某一個體的Hamming距離小于染色體長度的三分之一，則摒棄此新個體，重新產(chǎn)生新的個體，直到種群初始化結(jié)束。

(3)交叉、變異操作的順序確定

基本的遺傳算法不論種群適應(yīng)度如何變化，都是先進(jìn)行交叉操作，后進(jìn)行變異操作。這在種群的進(jìn)化中，易于導(dǎo)致種群早熟而陷入局部最優(yōu)解。如在種群進(jìn)化后期，種群個體差異很小，此時倘若先進(jìn)行交叉操作，則對優(yōu)良個體的產(chǎn)生基本沒有作用，縮小了搜索空間，使得種群陷入局部最優(yōu)。

因此提出一種根據(jù)當(dāng)代種群平均Hamming距離對交叉與變異操作的順序進(jìn)行確定的方法：

(1)

式中：Ha為當(dāng)代種群的平均Hamming距離。若式(1)成立，說明此時種群多樣性較小，應(yīng)先進(jìn)行變異操作，后進(jìn)行交叉操作；反之，應(yīng)先進(jìn)行交叉操作，后進(jìn)行變異操作。

(4)改進(jìn)型的交叉操作、變異操作

本文中的交叉操作選擇以“門當(dāng)戶對”原則且結(jié)合混沌序列[17]的多點(diǎn)交叉，利用混沌序列產(chǎn)生待交換位置串，進(jìn)而實(shí)行多點(diǎn)交叉。變異操作選擇結(jié)合混沌序列的多點(diǎn)變異。

交叉操作和變異操作中的交叉率和變異率是決定算法收斂速度、穩(wěn)定程度的關(guān)鍵參數(shù)。交叉率是種群進(jìn)化的基礎(chǔ)，交叉率越大，種群越豐富，算法搜索空間越大，但優(yōu)良個體被破壞的可能性也越大；交叉率過小，不易產(chǎn)生新個體，而最后陷于早熟現(xiàn)象。變異率則是產(chǎn)生全局最優(yōu)解的關(guān)鍵一步，變異率過小，不易產(chǎn)生新個體，而最后陷于局部最優(yōu)；變異率過大，又會使遺傳算法趨近于隨機(jī)搜索算法，大大增加了運(yùn)算開銷。

本文基于sigmoid函數(shù)[18]和高斯基函數(shù)[19]對交叉率和變異率進(jìn)行改進(jìn)，設(shè)計出一種自適應(yīng)非線性調(diào)整交叉率和變異率的調(diào)節(jié)公式，如下所示：

(2)

(3)

根據(jù)式(2)和式(3)繪制本文HSGAGA算法中自適應(yīng)交叉率和變異率的調(diào)整曲線，如圖5和圖6所示。

圖5 自適應(yīng)交叉率調(diào)整曲線Fig.5 Curve of adaptive crossover rate

圖6 自適應(yīng)變異率調(diào)整曲線Fig.6 Curve of adaptive mutation rate

由圖5和圖6可以看出：首先，在種群進(jìn)化初期，由蒙特卡洛方法和Hamming距離生成的種群多樣性可以在較大的交叉率下充分發(fā)揮作用，產(chǎn)生初始的優(yōu)良個體；并且，較小的變異率可以阻止對初始優(yōu)良個體的破壞，增加了算法的收斂速度。其次，在種群個體適應(yīng)度與種群平均適應(yīng)度favg相近時，為了防止種群產(chǎn)生“早熟”現(xiàn)象而陷入局部最優(yōu)，給予了較大的交叉率Pc和變異率Pm，增加種群的多樣性，避免了算法停滯不前。最后，當(dāng)種群個體適應(yīng)度接近種群最大適應(yīng)度fmax時，說明種群的多樣性很低，此時通過交叉操作已經(jīng)不能產(chǎn)生更優(yōu)的個體，應(yīng)給予較小的交叉率Pc，而為了增加種群的多樣性，防止種群“早熟”而陷入局部最優(yōu)解，應(yīng)適當(dāng)?shù)卦黾幼儺惵蔖m。

(5)選擇操作

結(jié)合雙精英保留策略和錦標(biāo)賽選擇策略[20]對經(jīng)過交叉和變異之后的種群進(jìn)行選擇操作，構(gòu)成新的種群。

雙精英保留策略：為了防止遺傳算法在運(yùn)行過程中，由于交叉和變異等遺傳操作破壞了當(dāng)前種群中的最優(yōu)個體，大大影響遺傳算法的收斂速度，這里提出一種雙精英保留策略，主要思想是，若下一代種群中的最優(yōu)個體適應(yīng)度小于當(dāng)代種群中的最優(yōu)個體適應(yīng)度，則用當(dāng)代種群中最優(yōu)的兩個個體替換掉下一代種群中最差的兩個個體，以保證種群的收斂能力，增大種群的收斂速度。

錦標(biāo)賽選擇策略：模擬錦標(biāo)賽競爭的方式，通過隨機(jī)選擇多個個體，并在多個個體中通過擇優(yōu)錄取的方式實(shí)現(xiàn)選擇操作。

(6)停機(jī)條件

采用雙重停機(jī)條件。傳統(tǒng)的遺傳算法通常采用單一的g停機(jī)條件，即若進(jìn)化代數(shù)達(dá)到預(yù)先給定的總的進(jìn)化代數(shù)g，則結(jié)束算法運(yùn)行。但若初始種群較優(yōu)且參數(shù)選取非常理想，使得遺傳算法很快能夠搜索到最優(yōu)解，倘若此時仍采取單一的g停機(jī)條件，便會額外增加算法的運(yùn)行時間。

因此，本文算法在執(zhí)行過程中，采用雙重停機(jī)條件：進(jìn)化代數(shù)達(dá)到總的進(jìn)化代數(shù)g；連續(xù)N次進(jìn)化的最優(yōu)結(jié)果不變。在遺傳進(jìn)化過程中，滿足上述兩個條件中的任何一個，都結(jié)束算法的運(yùn)行，大大提高了算法的收斂速度，減少了額外的計算時間。

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

4.1 衛(wèi)星及目標(biāo)區(qū)域參數(shù)設(shè)置

為了驗(yàn)證本文多星調(diào)度模型以及改進(jìn)型自適應(yīng)遺傳算法HSGAGA的性能，進(jìn)行仿真實(shí)驗(yàn)的衛(wèi)星及目標(biāo)區(qū)域參數(shù)設(shè)置如下。

(1)衛(wèi)星軌道參數(shù)

由于對地觀測衛(wèi)星要求較好的光照條件以及一定的回歸特性和穩(wěn)定性[13]，因此本文使用的3顆衛(wèi)星軌道均是作者設(shè)計的太陽同步回歸凍結(jié)軌道，降交點(diǎn)地方時均為早上10:30:00，具體軌道參數(shù)如表1所示。

a,e,i,Ω,ω,f指軌道六要素，分別為軌道半長軸、偏心率、傾角、升交點(diǎn)赤經(jīng)、近地點(diǎn)幅角、真近點(diǎn)角。衛(wèi)星上傳感器的相機(jī)幅寬均為2l=20 km；各衛(wèi)星機(jī)動能力所限制的最大側(cè)擺角為βmax=±30°；各衛(wèi)星上傳感器的側(cè)擺速率為v=1(°)/min ；各衛(wèi)星對地觀測消耗星上存儲資源的速率為w=1.5 Mbyte/s；各衛(wèi)星單軌運(yùn)行所允許的最大存儲容量為W=90 Mbyte；能夠清晰地觀測到目標(biāo)所要求的太陽高度角不小于10°；調(diào)度模型中目標(biāo)收益的權(quán)值分別取為ω1=0.9，ω2=0.1。

表1 衛(wèi)星參數(shù)

(2)目標(biāo)區(qū)域參數(shù)

目標(biāo)區(qū)域選擇包括西安市在內(nèi)的一個矩形區(qū)域，其4個頂點(diǎn)的經(jīng)緯度坐標(biāo)分別為(100°,30°)(110°,30°)(110°,40°)(100°,40°)。通過網(wǎng)格化方法，對此區(qū)域進(jìn)行網(wǎng)格化，一共劃分為13×13=169個網(wǎng)格點(diǎn)；且觀測開始時間為2018-05-01 12:00:00，結(jié)束時間為2018-05-06 12:00:00。

4.2 算法參數(shù)設(shè)置及計算結(jié)果

為了驗(yàn)證本文改進(jìn)型自適應(yīng)遺傳算法HSGAGA的性能，將其與標(biāo)準(zhǔn)遺傳算法(GA)、結(jié)合改良圈、混沌序列的改進(jìn)型遺傳算法(IGA)、文獻(xiàn)[6]中所提出的基于sigmoid激活函數(shù)的自適應(yīng)遺傳算法(SAGA)、模擬退火算法(SA)、結(jié)合蒙特卡洛方法的改進(jìn)型模擬退火算法(ISA)進(jìn)行對比，分別對此次調(diào)度問題進(jìn)行求解。

算法采用Matlab r2012a實(shí)現(xiàn)，計算機(jī)的CPU為Pentium E5800，內(nèi)存為3.00 Gbyte。其中各算法的參數(shù)設(shè)置如下：

SA算法：初始溫度為T0=1，降溫系數(shù)為α=0.999，終止溫度為e=0.130，退火最大次數(shù)為T=40000。

ISA算法：初始溫度為T0=1，降溫系數(shù)為α=0.999，終止溫度為e=0.130，退火最大次數(shù)為T=40 000。

GA算法：種群大小為w=30，最大進(jìn)化代數(shù)為g=1 000，交叉率為Pc=0.7，變異率為Pm=0.1。

IGA算法：種群大小為w=30，最大進(jìn)化代數(shù)為g=1 000，交叉率為Pc=0.7，變異率為Pm=0.1。

SAGA算法：種群大小為w=30，最大進(jìn)化代數(shù)為g=1000，最大交叉率為Pcmax=0.8，最小交叉率為Pcmin=0.5，最大變異率為Pcmin=0.2，最小變異率為Pcmin=0.05。

HSGAGA算法：種群大小為w=30，最大進(jìn)化代數(shù)為g=1 000，最大交叉率為Pcmax=0.8，最小交叉率為Pcmin=0.5，最大變異率為Pcmin=0.2，最小變異率為Pcmin=0.05，停機(jī)代數(shù)為150。

分別使用以上6種算法對本文的多星觀測調(diào)度問題進(jìn)行求解。其中，SA算法、ISA算法獲得退火次數(shù)與每次退火后個體適應(yīng)度值的關(guān)系如圖7所示；HSGAGA算法、GA算法、IGA算法、SAGA算法獲得進(jìn)化代數(shù)與每代種群最大適應(yīng)度值的關(guān)系如圖8所示。

圖7 SA、ISA算法的性能比較Fig.7 Performance of SA and ISA

圖8 GA、IGA、HSGAGA算法的性能比較Fig.8 Performance of GA, IGA and HSGAGA

在HSGAGA算法下，這3顆衛(wèi)星開始觀測到區(qū)域目標(biāo)的時間、側(cè)擺角和覆蓋持續(xù)時間如表2所示。

表2 HSGAGA算法下各衛(wèi)星的觀測結(jié)果

使用這6種方法對問題進(jìn)行50次求解，所得到的對地觀測衛(wèi)星對目標(biāo)區(qū)域進(jìn)行觀測的兩個覆蓋指標(biāo)(覆蓋率、總的覆蓋時間)以及各個算法求解的執(zhí)行時間，分別求其平均值，如表3所示。

表3 各算法求解所得覆蓋性能及執(zhí)行時間

由圖7、圖8和表3可以看出：

1)本文提出的HSGAGA算法執(zhí)行了37.39 s，在287代時即達(dá)到全局最優(yōu)解，而GA、IGA、SAGA算法分別執(zhí)行了93.82 s、91.25 s、81.36 s，依然在1 000代仍進(jìn)入了局部最優(yōu)解，SA、ISA算法分別執(zhí)行了121.97 s、123.11 s，依然在40 000次退火之后也仍進(jìn)入了局部最優(yōu)解。

2)應(yīng)用HSGAGA算法對問題進(jìn)行50次求解中，總共觸發(fā)了39次雙重停機(jī)條件，說明了在對問題進(jìn)行優(yōu)化求解中，使用雙重停機(jī)條件的必要性；并且，其所求得的全局最優(yōu)解使得衛(wèi)星對地覆蓋率達(dá)到了36.09%，比次好的SAGA算法高了2.95%；并且總的覆蓋時間1 653 s也是最高的，比次好的SAGA算法高了18 s；而且算法的執(zhí)行時間也最短，為37.39 s，僅是次好的SAGA算法執(zhí)行時間的45.96%。

結(jié)合圖8也可以看出，本文所設(shè)計的改進(jìn)型自適應(yīng)遺傳算法HSGAGA可以在種群初期充分利用種群的多樣性，通過交叉得到較好的個體，并且在種群中期，同時通過交叉和變異操作增加種群的多樣性，避免種群“早熟”而陷入局部最優(yōu)，最后在種群末期，能夠以一定的變異率繼續(xù)進(jìn)行全局尋優(yōu)，避免了種群停滯不前。這也充分說明了本文所提出的HSGAGA算法對于解決復(fù)雜動態(tài)組合優(yōu)化問題的快速性與有效性。

5 結(jié)束語

本文提出了一種改進(jìn)型自適應(yīng)遺傳算法(HSGAGA)，高效地解決了面向多星區(qū)域觀測調(diào)度問題。具體的實(shí)驗(yàn)用例表明，相較于其他現(xiàn)代優(yōu)化算法，HSGAGA算法所求得的側(cè)擺調(diào)度方案不但大大提高了衛(wèi)星對目標(biāo)區(qū)域進(jìn)行觀測的覆蓋率和總的覆蓋持續(xù)時間，而且算法本身的執(zhí)行時間很短，說明該算法既有效也高效。此外，該算法具有通用性，適用于其他動態(tài)組合調(diào)度優(yōu)化問題的求解。

本文研究了只在垂直于星下點(diǎn)軌跡方向上側(cè)擺的衛(wèi)星調(diào)度問題，后續(xù)的工作是進(jìn)一步研究敏捷衛(wèi)星(agile earth observation satellite, AEOS)對地觀測調(diào)度問題。