基于改進(jìn)布谷鳥搜索的衛(wèi)星成像規(guī)劃方法*

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

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

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

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

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

1 布谷鳥搜索算法簡(jiǎn)介

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

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

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

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

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

(1)

(2)

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

(3)

其中

(4)

2 成像規(guī)劃模型

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

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

2.1 預(yù)處理

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

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

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

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

2.2 約束條件分析

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

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

2.3 約束滿足模型的建立

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

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

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

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

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

stripNumber≤k.

(5)

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

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

endTimei-startTimei≥minSatpictime.

(6)

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

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

startTimei≥startTime,endTimei≤endTime.

(7)

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

④單次最長(zhǎng)開機(jī)時(shí)間約束。衛(wèi)星對(duì)區(qū)域目標(biāo)進(jìn)行觀測(cè)時(shí)，時(shí)間窗應(yīng)在單次最長(zhǎng)開機(jī)時(shí)間范圍內(nèi)。

maxSatontime.

(8)

其中：maxSatontime為衛(wèi)星單次最長(zhǎng)開機(jī)時(shí)間。

⑤載荷每軌、每天工作合計(jì)時(shí)長(zhǎng)約束。

當(dāng)satNamei=satNamej，senNamei=senNamej時(shí)，

endTimei-startTimei≤maxSenontperpas.

(9.a)

(endTimei-startTimei)+…+

(endTimej-startTimej)≤maxSenontperday.

(9.b)

其中：maxSenontperpas、maxSenontperday為載荷每軌、每天工作最長(zhǎng)時(shí)間。

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

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

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

(10)

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

3 改進(jìn)算法求解

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

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

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

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

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

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

3.3 布谷鳥搜索算法的改進(jìn)

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

i=1,2,…,N.

(11)

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

(12)

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

通過(guò)引入非線性慣性權(quán)重，對(duì)標(biāo)準(zhǔn)的布谷鳥搜索算法進(jìn)行改進(jìn)，從而建立改進(jìn)的布谷鳥搜索算法(improved cuckoo search，ICS)。

3.4 求解過(guò)程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表4 不同區(qū)域目標(biāo)實(shí)驗(yàn)結(jié)果對(duì)比Table 4 Comparison of experimental results of different regional targets

為更直觀地將3種算法做對(duì)比，將實(shí)驗(yàn)的覆蓋率變化圖記錄在圖5。

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

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

從結(jié)果穩(wěn)定性來(lái)看，在進(jìn)行的3組實(shí)驗(yàn)中，ICS優(yōu)化結(jié)果的標(biāo)準(zhǔn)差分別為GA的0%、28.57%、14.29%，CS優(yōu)化結(jié)果的標(biāo)準(zhǔn)差分別為GA的0%、42.85%、14.29%?？梢?jiàn)無(wú)論是ICS還是CS，其魯棒性均強(qiáng)于GA，優(yōu)化結(jié)果相對(duì)更穩(wěn)定。

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

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

5 結(jié)語(yǔ)

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