李小牧，田妙苗，馬廣彬，林友明，程博

(1 中國科學院空天信息創(chuàng)新研究院， 北京 100094； 2 中國科學院大學電子電氣與通信工程學院， 北京 100049)

成像衛(wèi)星是遙感系統(tǒng)實現(xiàn)對地觀測的重要手段之一，主要采用星載遙感器從太空對地球、月球等天體實現(xiàn)成像，目前已經(jīng)廣泛應(yīng)用于氣象預(yù)報、環(huán)境監(jiān)測、軍事偵察等不同領(lǐng)域。近年來，用戶對成像衛(wèi)星數(shù)據(jù)的需求量越來越大，所要求的數(shù)據(jù)質(zhì)量也越來越高。考慮到衛(wèi)星的發(fā)射成本和指數(shù)級增長的用戶需求，合理利用衛(wèi)星資源顯得尤為重要。這就要求合理分配衛(wèi)星資源，解決成像衛(wèi)星任務(wù)規(guī)劃問題，以在有限的衛(wèi)星資源下最大限度地滿足用戶對衛(wèi)星數(shù)據(jù)的需求。

國內(nèi)外學者對衛(wèi)星成像規(guī)劃問題已有大量的研究，在模型建立和算法求解兩方面有很多成果。Bensana等[1]研究SPOT5衛(wèi)星常規(guī)任務(wù)的任務(wù)規(guī)劃，認為該問題可以表述為非線性規(guī)劃問題，建立了整數(shù)規(guī)劃模型，但在模型中考慮到的約束條件較少。賀仁杰[2]認為多星聯(lián)合任務(wù)規(guī)劃是一個具有時間窗口約束的并行機器調(diào)度問題，建立了多星任務(wù)規(guī)劃問題的約束滿足模型，但未考慮衛(wèi)星存儲和數(shù)據(jù)下傳及成像時云量大小等約束。學者Vasquez和Hao[3]把偵察衛(wèi)星的任務(wù)方案規(guī)劃和執(zhí)行問題轉(zhuǎn)化為背包問題模型，但主要討論衛(wèi)星任務(wù)規(guī)劃問題和背包問題模型的轉(zhuǎn)化，涉及衛(wèi)星的約束較少。在算法方面，Wolfe和Soersnen[4]通過實驗證明相比于貪婪算法，遺傳算法可以較大幅度地改進調(diào)度結(jié)果，但后續(xù)的研究表明當問題達到一定規(guī)模時，遺傳算法的尋優(yōu)效果降低。白保存[5]針對成像衛(wèi)星的任務(wù)規(guī)劃問題中點目標與區(qū)域目標同時存在的情況，提出動態(tài)合成啟發(fā)式算法與快速模擬退火算法對問題進行整體優(yōu)化求解，但是動態(tài)合成啟發(fā)式算法調(diào)度結(jié)果不理想，快速模擬退火算法對大規(guī)模求解問題存在不足。李志亮等[6]考慮觀測時間因素，將離散差分進化與變鄰域搜索相結(jié)合，使用混合算法求解構(gòu)建的約束滿足模型，但在實驗?zāi)Ｐ椭形纯紤]云量約束。李海玲和黨琦[7]通過分解和分析成像任務(wù)規(guī)劃過程和目標的重要程度和緊急程度，設(shè)計了一種基于目標優(yōu)先級的快速成像任務(wù)規(guī)劃流程，但文中并未涉及實際的應(yīng)用案例。明衛(wèi)鵬等[8]分析衛(wèi)星成像規(guī)劃的約束條件，建立了相應(yīng)的約束滿足模型，使用基因表達式編程求解該問題，但其模型考慮的約束較少，模型的應(yīng)用價值有待提高。申經(jīng)偉[9]改進了布谷鳥搜索算法，利用經(jīng)典函數(shù)對比檢驗，表明改進的布谷鳥搜索算法可以在較少的迭代次數(shù)中搜索到精確度較高的全局最優(yōu)值，最后將其應(yīng)用于集裝箱港口群鐵路班列網(wǎng)絡(luò)運輸模型的求解中，驗證了算法的有效性。徐楊麗和葉春明[10]使用布谷鳥搜索算法解決置換流水車間調(diào)度問題，驗證了在不同參數(shù)的支配下，布谷鳥搜索算法尋優(yōu)效果均強于貓群算法。明波等[11]使用改進的布谷鳥搜索算法求解梯級水庫調(diào)度模型，在實驗中驗證了布谷鳥搜索算法的可行性和有效性。邵萌等[12]將布谷鳥搜索算法引入包含地理信息懲罰因子的變電站選址模型，實驗表明布谷鳥搜索算法可有效克服傳統(tǒng)算法中的“早熟”現(xiàn)象，全局尋優(yōu)能力和搜索率更高。為增強算法的全局搜索能力，改善求解結(jié)果，本文首次提出使用布谷鳥搜索算法解決衛(wèi)星成像規(guī)劃問題。

本文介紹布谷鳥搜索算法的基本原理，構(gòu)建衛(wèi)星成像規(guī)劃模型，設(shè)計改進布谷鳥搜索算法求解該問題的具體步驟，最后在實驗中將之與布谷鳥搜索算法和遺傳算法對比，并對實驗結(jié)果進行分析，證明了本文方法的可行性和優(yōu)越性。

1 布谷鳥搜索算法簡介

布谷鳥搜索算法(cuckoo search, CS)是2009年英國學者Yang和Deb在群體智能技術(shù)的基礎(chǔ)上提出的一種新型群智能優(yōu)化算法[13]。該算法模擬某些布谷鳥寄生育雛(brood parasitism) 時巢寄生的繁殖習性，利用萊維飛行(Levy fights)和偏好隨機游走進行種群更新，有效求解最優(yōu)化問題，具有全局搜索能力強、所需參數(shù)較少易于進行調(diào)節(jié)等特點。算法的流程圖如圖1所示。

圖1 布谷鳥搜索算法流程圖Fig.1 Flow chart of cuckoo search algorithm

在CS算法模型中，一個宿主巢的原有蛋表示一個候選解，一個布谷鳥新產(chǎn)的蛋表示一個新解，該算法的目標是利用新解或者可能產(chǎn)生的優(yōu)解替代巢中原有的劣解。為了簡單描述布谷鳥搜索算法并將其應(yīng)用到實際的優(yōu)化問題中，Yang和Deb在提出布谷鳥搜索算法時引入了以下3條理想化規(guī)則：1)布谷鳥一次只產(chǎn)一個蛋，并隨機選擇宿主鳥巢存放；2)目前具有優(yōu)質(zhì)蛋的巢穴會被保留到下一代；3)布谷鳥可以選擇的巢穴數(shù)量是固定的，且宿主鳥發(fā)現(xiàn)外來蛋的概率也是固定的[13]。一旦布谷鳥蛋被發(fā)現(xiàn)，宿主鳥將拋棄布谷鳥蛋或舊巢。

另外，在自然界中，許多動物的飛行都具有冪律規(guī)律，這是萊維飛行的典型特征。萊維分布是由數(shù)學家Levy提出的一種概率分布，萊維飛行是一種服從萊維分布的隨機搜索方法，主要靠短間距的搜索與偶爾較長間距的行走相間的方式，在搜索過程中產(chǎn)生較大的躍動和較劇烈的運動方向的變化，使得算法跳出局部最優(yōu)。Yang將其應(yīng)用在鳥窩位置的更新上，從而布谷鳥搜索算法也具有良好的全局搜索能力。

在以上3條理想化規(guī)則下，布谷鳥尋窩的路徑和位置更新公式[14]如下

(1)

(2)

其中：β是一個[1,2]之間的數(shù)，u和v服從正態(tài)分布

(3)

其中

(4)

2 成像規(guī)劃模型

建立衛(wèi)星成像規(guī)劃模型，就是將實際的成像規(guī)劃問題簡化為數(shù)學模型，把問題的需求、條件、結(jié)果轉(zhuǎn)化為模型輸入輸出、約束條件等，主要包含預(yù)處理、約束條件的分析、約束滿足模型的建立3個步驟[16]。

在建立約束滿足模型前，用戶首先提出包含目標區(qū)域、圖像類型、圖像約束、觀測有效時間等內(nèi)容的觀測需求集合。通常來說，相對于用戶需求，衛(wèi)星資源是非常稀缺的。衛(wèi)星成像規(guī)劃的目標就是生成一個滿意的調(diào)度方案，以合理分配衛(wèi)星資源。

2.1 預(yù)處理

預(yù)處理根據(jù)觀測需求集合，分析用戶需求及所能夠調(diào)度的衛(wèi)星資源的屬性，獲取目標區(qū)域的地理位置和衛(wèi)星的軌道信息，對任務(wù)進行分解及規(guī)范化處理，為后期問題建模提供數(shù)據(jù)基礎(chǔ)。成像規(guī)劃問題的預(yù)處理過程主要包括以下幾個方面：軌道計算、對目標區(qū)域的訪問時間計算、基于條帶的區(qū)域分解計算和成像條帶的篩選。按照側(cè)擺角大小、圖像分辨率高低等條件對計算出的條帶進行篩選。

成像衛(wèi)星在單次過境時，根據(jù)側(cè)擺角的不同，能夠產(chǎn)生多個可選的觀測活動，即產(chǎn)生多個條帶，但每次過境只能選擇其中的一個條帶或不選擇條帶參與最終的成像。此時，衛(wèi)星成像規(guī)劃的調(diào)度方案便轉(zhuǎn)化為條帶的組合方案。

根據(jù)以上所述，預(yù)處理的流程圖如圖2所示。

圖2 預(yù)處理基本步驟Fig.2 Basic steps of preprocessing

2.2 約束條件分析

預(yù)處理時已根據(jù)一些條件篩選出較高質(zhì)量的成像條帶，但成像方案是不同的條帶組合，組合過程中也需要根據(jù)實際情況考慮多方面約束條件，現(xiàn)將考慮的約束整理在表1中[8,17-18]。

表1 約束規(guī)則Table 1 Constraint rules

2.3 約束滿足模型的建立

在分析了衛(wèi)星成像時需要考慮的主要約束后，便可建立約束滿足模型，將問題中涉及到的模型輸入、模型輸出、約束條件、目標函數(shù)等用數(shù)學符號表示出來。

1)模型輸入：所有可能的成像條帶集。包含衛(wèi)星標識、傳感器型號、傳感器成像模式、側(cè)擺角、成像開始與結(jié)束時間、成像區(qū)域范圍等重要信息。

2)模型輸出：需安排的條帶集合。該集合包含衛(wèi)星在每個軌道圈次是否成像，成像時選擇的傳感器、傳感器模式、傳感器側(cè)擺角、成像開始時間、成像結(jié)束時間等信息。

3)約束條件：首先對約束滿足模型中用到的符號進行定義。設(shè)兩個成像條帶sidi、sidj相對應(yīng)的衛(wèi)星標識分別為satNamei、satNamej，對應(yīng)的傳感器型號分別為senNamei、senNamej，傳感器成像模式分別為modei、modej，成像開始與結(jié)束時間分別為startTimei、startTimej、endTimei、endTimej，側(cè)擺角sideRighti、sideRightj。

①成像條帶總和小于等于可成像條帶總數(shù)。

stripNumber≤k.

(5)

其中：stripNumber為每次參與成像條帶總數(shù)，k為可成像條帶總數(shù)。

②任意衛(wèi)星的成像條帶時間長度大于該衛(wèi)星要求的最小拍攝時間。

endTimei-startTimei≥minSatpictime.

(6)

其中：minSatpictime為衛(wèi)星的單次最小拍攝時間。

③成像條帶的最早開始時間晚于指定開始時間，最晚結(jié)束時間早于指定的結(jié)束時間。

startTimei≥startTime,endTimei≤endTime.

(7)

其中：startTime、endTime為成像規(guī)劃的指定開始、結(jié)束時間。

④單次最長開機時間約束。衛(wèi)星對區(qū)域目標進行觀測時，時間窗應(yīng)在單次最長開機時間范圍內(nèi)。

maxSatontime.

(8)

其中：maxSatontime為衛(wèi)星單次最長開機時間。

⑤載荷每軌、每天工作合計時長約束。

當satNamei=satNamej，senNamei=senNamej時，

endTimei-startTimei≤maxSenontperpas.

(9.a)

(endTimei-startTimei)+…+

(endTimej-startTimej)≤maxSenontperday.

(9.b)

其中：maxSenontperpas、maxSenontperday為載荷每軌、每天工作最長時間。

關(guān)于成像時衛(wèi)星的傳感器和傳感器模式、光照條件、云量等其他約束，可以設(shè)計將其融入到解的編碼方式和目標函數(shù)中，這樣不僅可以降低模型的復雜度，也可以提高模型的可移植性，利于后期使用不同算法解決此模型并進行比較。

上述約束條件都是建立在成像條帶基礎(chǔ)上的。計算過程中所需要的信息都已包含在成像條帶中，這也是以成像條帶為基礎(chǔ)建立約束條件的前提。

4)目標函數(shù)：通常情況下，根據(jù)用戶的不同需求，評價一個成像方案優(yōu)劣的指標有很多，但最基礎(chǔ)的是成像方案對目標區(qū)域的覆蓋率，本文的側(cè)重點在于驗證本文方法對于成像規(guī)劃問題的適用性和優(yōu)越性，因此設(shè)置基礎(chǔ)的目標函數(shù)，把成像方案對區(qū)域目標的覆蓋率作為評價其優(yōu)劣的指標，同時，考慮云量因素和光照因素，以懲罰因子的形式加入到目標函數(shù)中，即

(10)

所建的約束滿足模型為maxP，s.t.(5)、(6)、(7)、(8)、(9)。

3 改進算法求解

3.1 算法的編碼設(shè)計

求解所建模型時，編碼方式對算法的尋優(yōu)性能具有一定的影響。衛(wèi)星成像規(guī)劃的結(jié)果是一組條帶的組合，解的編碼應(yīng)根據(jù)條帶信息所包含的內(nèi)容進行設(shè)計。成像方案的所有信息都由最終組成解的成像條帶確定，本文以衛(wèi)星的過境次數(shù)作為編碼的基礎(chǔ)，以該軌道下可以產(chǎn)生的成像條帶個數(shù)為編碼內(nèi)容設(shè)計解的基本編碼[16]。

按照衛(wèi)星的軌道，將所有條帶進行分組，衛(wèi)星每次過境都可以產(chǎn)生若干個可用的成像條帶，從其中選擇出1個或0個條帶作為解編碼中的一個碼，選擇0個則相應(yīng)的編碼為-1，表示該次過境軌道不成像。這樣所有的過境軌道選擇完畢后，就形成了一個碼序列。這樣的一個碼序列是解的基本編碼序列，也代表針對目標區(qū)域的一個可行的成像方案。

3.2 更新操作的設(shè)計

在以上編碼方式中，解的編碼序列由一組整數(shù)對組合而成，每個整數(shù)對代表一個條帶，其中第1個整數(shù)代表該條帶所屬的衛(wèi)星軌道序號，第2個整數(shù)代表該軌道產(chǎn)生的若干條帶中參與規(guī)劃的特定條帶序號。對所有整數(shù)對的第2個整數(shù)進行萊維飛行操作，其鄰域范圍為該整數(shù)對第1個整數(shù)對應(yīng)的軌道圈次可以產(chǎn)生的條帶個數(shù)總數(shù)加1，這樣就保證經(jīng)過萊維飛行更新，產(chǎn)生的新條帶仍然在約束范圍內(nèi)。為保證經(jīng)過萊維飛行后的數(shù)值仍為整數(shù)，對更新后的數(shù)值進行取整操作，通過這樣的改變，萊維飛行的鄰域轉(zhuǎn)化為離散空間，且可以直接通過布谷鳥搜索算法的位置更新公式獲得新解。假設(shè)某一條帶的編碼為(3,p)，更新后的編碼為(3,q)，p、q均屬于該軌道圈次可產(chǎn)生的條帶個數(shù)，若q=-1，則表示更新后該軌道圈次不參與成像，若q=p，則表示經(jīng)過該次更新，所選條帶不變。若q≠-1且q≠p，則表示選擇新的條帶參與成像。對解的編碼序列中每一個整數(shù)對都進行萊維飛行更新，可產(chǎn)生一個新的編碼序列，即產(chǎn)生一個新的解。具體的編碼和更新方式如圖3所示。

圖3 解的基本編碼及更新圖Fig.3 Schematic diagram of the basic coding and updating strategies

3.3 布谷鳥搜索算法的改進

在標準布谷鳥搜索算法中，萊維飛行的方向和步長是隨機的，這可能導致算法后期收斂速度較慢，影響其尋優(yōu)效果。據(jù)此，考慮在算法迭代的不同階段，引入非線性慣性權(quán)重，采用非線性的步長更新方法，使得算法在前期能夠快速尋優(yōu)，而后期可以跳出局部最優(yōu)[19]。具體的步長更新公式如下

i=1,2,…,N.

(11)

其中:φ為非線性權(quán)重系數(shù)，取值如下

(12)

其中:φ0為充分大的正實數(shù)，h為當前迭代次數(shù)，h0為指定迭代次數(shù)。

通過引入非線性慣性權(quán)重，對標準的布谷鳥搜索算法進行改進，從而建立改進的布谷鳥搜索算法(improved cuckoo search，ICS)。

3.4 求解過程

衛(wèi)星成像規(guī)劃問題模型的求解步驟如下：

1)讀取條帶信息，確定解的基本編碼和更新方式。通過編碼將實際問題轉(zhuǎn)換為可使用改進布谷鳥搜索算法求解的數(shù)學問題，并根據(jù)布谷鳥搜索的特點，確定解的更新方式。

2)初始化各參數(shù)，設(shè)定初始種群規(guī)模N，循環(huán)次數(shù)T，發(fā)現(xiàn)概率Pa。

3)初始化種群，隨機生成N個初始解，得到一組規(guī)劃方案，并計算這N個解的適應(yīng)度。這里的適應(yīng)度取規(guī)劃方案對目標區(qū)域的覆蓋率。

4)第一次迭代開始，設(shè)h=0，當h

6)比較x和y的覆蓋率，保留兩個方案中覆蓋率較大的一個，以此更新目前最優(yōu)方案x。

7)產(chǎn)生一個服從均勻分布的隨機數(shù)R作為宿主鳥發(fā)現(xiàn)外來鳥蛋的可能性，也即新解保留下來的可能性，將其與拋棄概率pa進行比較。若R>pa，則使用隨機游走方法改變鳥窩位置產(chǎn)生新規(guī)劃方案z，反之不變。最后保留最好的規(guī)劃方案，即再次更新最優(yōu)解x。h=h+1。

8)判斷算法是否滿足設(shè)置的最大迭代次數(shù)：若不滿足，重復進行迭代尋優(yōu);若滿足，結(jié)束搜索過程，輸出最優(yōu)解，得到最優(yōu)成像方案。

基于改進布谷鳥搜索算法的衛(wèi)星成像規(guī)劃流程如圖4所示。

圖4 基于改進布谷鳥搜索算法的衛(wèi)星成像規(guī)劃流程圖Fig.4 Flow chart of satellite imaging planning based on improved cuckoo search algorithm

4 仿真實驗

本文仿真實驗在Windows10操作系統(tǒng)下完成，設(shè)備處理器為Inter(R)Core(TM)i5，設(shè)備內(nèi)存為8 G，運行環(huán)境為PyCharm Community Edition 2 020.2 x64，使用的編程語言為Python。

分別選取面積較小的北京市、面積居中的河南省和面積較大的青海省作為目標區(qū)域，進行3組實驗，具體任務(wù)信息如表2所示。

表2 任務(wù)信息表Table 2 Table of task information

為了驗證本文算法的性能，將之與標準的CS和遺傳算法(genetic algorithm，GA)做對比，在調(diào)用3種算法時，保證模型輸入相同，即目標區(qū)域、選用衛(wèi)星、成像規(guī)劃時間、收斂條件相同，同時把對目標區(qū)域的覆蓋率作為優(yōu)化目標。

CS的主要參數(shù)為拋棄概率和種群規(guī)模，算法的發(fā)明者經(jīng)過多組參數(shù)實驗驗證拋棄概率為0.25，種群規(guī)模在15～40之間時，收斂速度對參數(shù)選擇并不敏感。因此，設(shè)置拋棄概率為0.25，種群規(guī)模為26。ICS中，取φ0為4，h0為200，此取值為多次實驗得到的經(jīng)驗取值。作為對比算法，GA的種群規(guī)模與布谷鳥搜索算法保持一致，交叉概率、變異概率的取值是經(jīng)過多次實驗調(diào)參后的優(yōu)選取值組合。算法中參數(shù)的取值如表3所示。

表3 算法參數(shù)表Table 3 Algorithm parameters

用3種算法分別對本文所建模型進行求解，設(shè)定迭代次數(shù)上限為400次，將各組實驗分別獨立進行10次，記錄實驗結(jié)果表4所示。

表4 不同區(qū)域目標實驗結(jié)果對比Table 4 Comparison of experimental results of different regional targets

為更直觀地將3種算法做對比，將實驗的覆蓋率變化圖記錄在圖5。

圖5 不同區(qū)域目標覆蓋率變化圖Fig.5 Changes in coverage rate of different regional targets

從目標函數(shù)值來看，當目標區(qū)域為北京市時，GA的平均覆蓋率為97.11%，ICS和CS均可達到97.80%的覆蓋率；以河南省為目標區(qū)域時，GA的平均覆蓋率為99.10%，ICS和CS平均可達到99.60%及以上的覆蓋率；以青海省為目標區(qū)域時，ICS的覆蓋率為99.76%，相比于CS的99.69%和GA的98.78%，尋優(yōu)效果也有提升。由此可見，對于不同規(guī)模的衛(wèi)星成像規(guī)劃問題，ICS的求解精度高于CS和GA。

從結(jié)果穩(wěn)定性來看，在進行的3組實驗中，ICS優(yōu)化結(jié)果的標準差分別為GA的0%、28.57%、14.29%，CS優(yōu)化結(jié)果的標準差分別為GA的0%、42.85%、14.29%?？梢姛o論是ICS還是CS，其魯棒性均強于GA，優(yōu)化結(jié)果相對更穩(wěn)定。

從收斂次數(shù)來看，在以北京市作為目標區(qū)域時，ICS的平均收斂次數(shù)是14次，少于CS和GA的平均收斂次數(shù)；目標區(qū)域為河南省時，問題規(guī)模、解空間增大，ICS的平均收斂次數(shù)仍小于CS和CA，且從覆蓋率大小看，GA易陷入局部最優(yōu)；當目標區(qū)域變?yōu)榍嗪Ｊr，ICS的平均收斂次數(shù)為156次，少于CS的平均收斂次數(shù)，而GA迭代400次未收斂。從收斂時間來看，當問題規(guī)模較小時，3種算法均可以在較短時間內(nèi)達到收斂，ICS及CS的收斂時間比GA略長；隨著問題規(guī)模的增大，3種算法的收斂時間都有所增加；而當問題規(guī)模進一步增大時，ICS和CS可以在一定時間內(nèi)達到收斂，而GA未收斂。這是由于ICS和CS通過短距離的搜索與偶爾較長距離的行走相間的萊維飛行，使得算法的尋優(yōu)性能更好。可見隨著問題規(guī)模的增大，ICS和CS的尋優(yōu)性能保持穩(wěn)定，而GA易陷入局部最優(yōu)，收斂性變差。對于大規(guī)模問題，IGA和GA的收斂性要優(yōu)于CS。此外，在3組實驗中，ICS的收斂時間均小于CS，這是由于引入的非線性慣性權(quán)重使得算法的尋優(yōu)性能進一步增強，說明改進策略是有效的。

相比于GA，ICS和CS既提高了覆蓋率，又提高了結(jié)果的穩(wěn)定性，而且收斂性較好；相比于CS，在保證算法求解精度和穩(wěn)定性的前提下，ICS縮短了收斂時間，考慮到研究問題的規(guī)劃周期較長，本文采用算法的運行時間是可以接受的。總體而言，針對成像規(guī)劃問題，采用ICS求解要優(yōu)于CS和GA。

5 結(jié)語

本文針對多衛(wèi)星區(qū)域目標的成像規(guī)劃問題，考慮衛(wèi)星姿態(tài)、傳感器使用和過境時間、成像時云量及光照等約束條件，建立約束滿足模型，設(shè)計了布谷鳥搜索算法求解。為進一步提高求解效率，在算法搜索過程中引入非線性慣性權(quán)重，提出一種改進的布谷鳥搜索算法，加快了收斂速度。結(jié)果表明，與遺傳算法和標準布谷鳥算法相比，改進布谷鳥搜索算法的目標完成率和穩(wěn)定性有明顯提高，衛(wèi)星資源利用率得到了提高，驗證了本文方法的有效性。