樊育，劉瑩瑩，周軍

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

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

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

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

基于以上情況，本文根據(jù)衛(wèi)星的軌道六要素計(jì)算出星下點(diǎn)軌跡，并采用網(wǎng)格點(diǎn)法自主劃分區(qū)域目標(biāo)，在指定的最大側(cè)擺角范圍內(nèi)計(jì)算出每顆衛(wèi)星每次過(guò)境的時(shí)間窗口，得出每顆衛(wèi)星在每次過(guò)境時(shí)段內(nèi)的側(cè)擺角集合。最后將問(wèn)題轉(zhuǎn)化為多個(gè)時(shí)間窗口和多個(gè)側(cè)擺角集合的動(dòng)態(tài)組合調(diào)度優(yōu)化問(wèn)題，為了更高效地實(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)對(duì)此動(dòng)態(tài)組合調(diào)度優(yōu)化問(wèn)題進(jìn)行求解，并通過(guò)算例與其他常用的優(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)行對(duì)比，驗(yàn)證了本文所提出的HSGAGA算法的優(yōu)良性能。

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

1.1 星載遙感器的覆蓋能力

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

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

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

(β+FOV/2)

同時(shí)，由地心覆蓋角可得覆蓋幅寬為：

AS′=φ·Re

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

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

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

即有觀測(cè)角約束：

β+FOV/2≤φ

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

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

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

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

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

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

BS′=arccos[sinλsinλx+

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

則地心覆蓋角∠BOeS為：

∠BOeS=BS′/Re

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖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編碼類(lèi)似于十進(jìn)制編碼，唯一不同的是十進(jìn)制編碼中基因的取值為0～9之間的整數(shù)，而k編碼中基因的取值為1～k之間的整數(shù)。

(2)種群初始化

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

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

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

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

(1)

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

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

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

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

本文基于sigmoid函數(shù)[18]和高斯基函數(shù)[19]對(duì)交叉率和變異率進(jìn)行改進(jìn)，設(shè)計(jì)出一種自適應(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)良個(gè)體；并且，較小的變異率可以阻止對(duì)初始優(yōu)良個(gè)體的破壞，增加了算法的收斂速度。其次，在種群個(gè)體適應(yīng)度與種群平均適應(yīng)度f(wàn)avg相近時(shí)，為了防止種群產(chǎn)生“早熟”現(xiàn)象而陷入局部最優(yōu)，給予了較大的交叉率Pc和變異率Pm，增加種群的多樣性，避免了算法停滯不前。最后，當(dāng)種群個(gè)體適應(yīng)度接近種群最大適應(yīng)度f(wàn)max時(shí)，說(shuō)明種群的多樣性很低，此時(shí)通過(guò)交叉操作已經(jīng)不能產(chǎn)生更優(yōu)的個(gè)體，應(yīng)給予較小的交叉率Pc，而為了增加種群的多樣性，防止種群“早熟”而陷入局部最優(yōu)解，應(yīng)適當(dāng)?shù)卦黾幼儺惵蔖m。

(5)選擇操作

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

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

錦標(biāo)賽選擇策略：模擬錦標(biāo)賽競(jìng)爭(zhēng)的方式，通過(guò)隨機(jī)選擇多個(gè)個(gè)體，并在多個(gè)個(gè)體中通過(guò)擇優(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)解，倘若此時(shí)仍采取單一的g停機(jī)條件，便會(huì)額外增加算法的運(yùn)行時(shí)間。

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

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ù)

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

a,e,i,Ω,ω,f指軌道六要素，分別為軌道半長(zhǎng)軸、偏心率、傾角、升交點(diǎn)赤經(jīng)、近地點(diǎn)幅角、真近點(diǎn)角。衛(wèi)星上傳感器的相機(jī)幅寬均為2l=20 km；各衛(wèi)星機(jī)動(dòng)能力所限制的最大側(cè)擺角為βmax=±30°；各衛(wèi)星上傳感器的側(cè)擺速率為v=1(°)/min ；各衛(wèi)星對(duì)地觀測(cè)消耗星上存儲(chǔ)資源的速率為w=1.5 Mbyte/s；各衛(wèi)星單軌運(yùn)行所允許的最大存儲(chǔ)容量為W=90 Mbyte；能夠清晰地觀測(cè)到目標(biāo)所要求的太陽(yáng)高度角不小于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)的一個(gè)矩形區(qū)域，其4個(gè)頂點(diǎn)的經(jīng)緯度坐標(biāo)分別為(100°,30°)(110°,30°)(110°,40°)(100°,40°)。通過(guò)網(wǎng)格化方法，對(duì)此區(qū)域進(jìn)行網(wǎng)格化，一共劃分為13×13=169個(gè)網(wǎng)格點(diǎn)；且觀測(cè)開(kāi)始時(shí)間為2018-05-01 12:00:00，結(jié)束時(shí)間為2018-05-06 12:00:00。

4.2 算法參數(shù)設(shè)置及計(jì)算結(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)行對(duì)比，分別對(duì)此次調(diào)度問(wèn)題進(jìn)行求解。

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

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

ISA算法：初始溫度為T(mén)0=1，降溫系數(shù)為α=0.999，終止溫度為e=0.130，退火最大次數(shù)為T(mén)=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種算法對(duì)本文的多星觀測(cè)調(diào)度問(wèn)題進(jìn)行求解。其中，SA算法、ISA算法獲得退火次數(shù)與每次退火后個(gè)體適應(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)星開(kāi)始觀測(cè)到區(qū)域目標(biāo)的時(shí)間、側(cè)擺角和覆蓋持續(xù)時(shí)間如表2所示。

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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