劉建銀，王忠偉

（中南林業(yè)科技大學(xué) 物流與交通學(xué)院，湖南 長沙 410004）

森林作為一個(gè)生態(tài)系統(tǒng)，是地球表面生態(tài)系統(tǒng)的主體和生物多樣化的基礎(chǔ)，它不僅能夠?yàn)樯a(chǎn)生活提供寶貴的木材原料，還能夠調(diào)節(jié)氣候、涵養(yǎng)水源、保持水土、改善土壤、凈化空氣、消除噪音，特別是在防止風(fēng)沙、冰雹、旱澇等自然災(zāi)害方面發(fā)揮著重要作用。對(duì)森林資源進(jìn)行科學(xué)管理與合理開發(fā)，可產(chǎn)生巨大的社會(huì)、生態(tài)和經(jīng)濟(jì)效益[1]。

在保護(hù)森林資源的大背景下，如何科學(xué)地對(duì)森林資源進(jìn)行生態(tài)采伐是十分重要的。其中的基礎(chǔ)和核心就是要做好森林資源的觀測與統(tǒng)計(jì)。我國國土遼闊，森林資源豐富，截止2017年，森林總面積已超過2.58億hm2，森林覆蓋率達(dá)21.93%。與此同時(shí)，我國森林資源存在地區(qū)分布不均、南北結(jié)構(gòu)差距大的特點(diǎn)。通過森林調(diào)查及時(shí)掌握資源狀態(tài)，全面獲取林業(yè)的地理、生物、生態(tài)和相關(guān)信息，是進(jìn)行森林開發(fā)和生態(tài)采伐的基本前提。由于森林資源還處于不斷變化之中，優(yōu)選調(diào)查手段，應(yīng)用先進(jìn)的調(diào)查技術(shù)顯得尤為重要。傳統(tǒng)的森林資源調(diào)查方法主要使用地形圖進(jìn)行外業(yè)區(qū)劃、采用羅盤儀和全站儀進(jìn)行測距定位和測定邊界、通過尋找地物繪制手圖等[2-3]。

上述方法往往存在制圖精度低、外業(yè)工作強(qiáng)度大、調(diào)查成本高、耗時(shí)周期長、人為誤差大等不足。從20世紀(jì)80年代起，遙感技術(shù)、大數(shù)據(jù)等各種方法開始在林業(yè)資源調(diào)查上得到廣泛應(yīng)用[4-5]。其中，衛(wèi)星遙感通過天基平臺(tái)有效載荷對(duì)觀測目標(biāo)進(jìn)行非接觸性探測和記錄，具有極大的空間探測能力和高分辨率成像能力，逐漸成為森林資源觀測的高效手段[6-7]，在評(píng)估森林蓄積量、監(jiān)測森林火災(zāi)、識(shí)別林木類型、監(jiān)視森林蟲害、監(jiān)測森林沙化、濕地監(jiān)測等多個(gè)方面發(fā)揮重要作用。

如何高效應(yīng)用有限的衛(wèi)星資源實(shí)現(xiàn)對(duì)森林資源的成像監(jiān)測是一個(gè)急需解決的重要問題。設(shè)計(jì)有效的衛(wèi)星任務(wù)規(guī)劃算法，合理調(diào)度衛(wèi)星資源完成對(duì)森林區(qū)域的觀測覆蓋，是提高衛(wèi)星系統(tǒng)資源在林業(yè)中應(yīng)用效能的關(guān)鍵。由于森林資源所在區(qū)域較大，衛(wèi)星一次過境不能完全覆蓋，因此首先對(duì)衛(wèi)星觀測區(qū)域進(jìn)行點(diǎn)格化分解，評(píng)估點(diǎn)格化效果，構(gòu)建了相應(yīng)的任務(wù)規(guī)劃數(shù)學(xué)規(guī)模，提出一種新型的融合禁忌策略的粒子群算法求解該模型。通過仿真實(shí)驗(yàn)，驗(yàn)證了文章所提方法的有效性。

1 模型與算法

待觀測森林資源的幾何形狀可抽象為一個(gè)由多邊形或封閉曲線包含的區(qū)域，由于面積廣闊，往往不能被星載遙感器的單景視場或一個(gè)掃描條帶覆蓋，需要進(jìn)行區(qū)域分解，逐個(gè)觀測后拼接成像[4]。

構(gòu)建森林區(qū)域觀測任務(wù)的形式化描述模型，如下所示[9-11]:

式中，Idi為任務(wù)編號(hào)；Useri為提交任務(wù)的用戶中心；TSeni為所需的成像類型；STi為提交時(shí)刻；RTWi=[RETi,RDTi]為任務(wù)執(zhí)行的期望時(shí)段,RETi為最早允許執(zhí)行時(shí)刻，RDTi為執(zhí)行截止期；PVi為任務(wù)優(yōu)先級(jí)；RBi={Pi1，Pi2，…，Pik}為觀測區(qū)域的順序邊界點(diǎn)坐標(biāo)序列，Pik=(pxik，pyik)為邊界點(diǎn)Pi的地面坐標(biāo)。

觀測任務(wù)由不同用戶提交至衛(wèi)星管理中心，為便于統(tǒng)一規(guī)劃，應(yīng)根據(jù)任務(wù)描述進(jìn)行預(yù)處理（點(diǎn)格化），主要步驟如下:

（1）計(jì)算衛(wèi)星成像載荷的單景視場范圍，作為點(diǎn)格化區(qū)域的大??；

（2）將任務(wù)區(qū)域與單景視場范圍大小進(jìn)行比較，作為挑選待分解對(duì)象的依據(jù)；

（3）針對(duì)待分解對(duì)象，通過點(diǎn)格分解算法構(gòu)建點(diǎn)格化區(qū)域；

（4）判斷任務(wù)區(qū)域的點(diǎn)格化覆蓋情況，并生成任務(wù)對(duì)象的子任務(wù)集。

1.1 單景視場計(jì)算

森林資源觀測衛(wèi)星通常在近地軌道上穩(wěn)定運(yùn)行，衛(wèi)星位置隨著時(shí)間的變化發(fā)生移動(dòng)。在任意時(shí)刻衛(wèi)星位置與地球質(zhì)心連線與地球表面的相交點(diǎn)稱為星下點(diǎn)[12-14]。由連續(xù)星下點(diǎn)構(gòu)成的弧線稱之為星下點(diǎn)軌跡，如圖1所示。

圖1 成像衛(wèi)星的星下點(diǎn)軌跡Fig. 1 Ground track of imaging satellite

成像衛(wèi)星通過有效載荷對(duì)森林資源進(jìn)行觀測，其觀測區(qū)域由星下點(diǎn)位置和成像載荷的視場范圍確定[15-16]。成像載荷的單景視場范圍可根據(jù)視場角計(jì)算，如圖2所示。計(jì)算單景視場范圍的方法如下:

圖2 成像衛(wèi)星的單景視場范圍Fig. 2 Single view field range of imaging satellite

式中，d1，d2是單景視場區(qū)域的長和寬；r為地球半徑；h為成像衛(wèi)星的軌道高度。

1.2 任務(wù)區(qū)域計(jì)算

設(shè)taski為待觀測森林區(qū)域任務(wù)，由其任意邊界點(diǎn)Pim，Pin，Pip∈RBi構(gòu)成的覆蓋區(qū)域面積為:

由式（3），taski的覆蓋區(qū)域面積可表示為:

式中，Ni為taski邊界點(diǎn)數(shù)量。

1.3 區(qū)域點(diǎn)格化分解

將觀測范圍大于單景視場范圍的任務(wù)區(qū)域，按照成像衛(wèi)星載荷的單景視場尺寸切割為多個(gè)互不相交的點(diǎn)格，如圖3所示。

圖3 任務(wù)區(qū)域的點(diǎn)格化效果Fig. 3 Grid partition effect of task area

在圖3中，以點(diǎn)格單元的中心點(diǎn)代表點(diǎn)格所在區(qū)域。若某個(gè)點(diǎn)格的中心點(diǎn)可被成像衛(wèi)星觀測到，則認(rèn)為其代表的整個(gè)點(diǎn)格區(qū)域都被觀測到。通過點(diǎn)格化處理，可將區(qū)域目標(biāo)觀測問題轉(zhuǎn)換為點(diǎn)目標(biāo)集合觀測問題。

對(duì)于待分解任務(wù)taski，為其構(gòu)建點(diǎn)格化區(qū)域，不妨令:

估算點(diǎn)格數(shù)量:

點(diǎn)格化區(qū)域的初始點(diǎn)坐標(biāo)為:構(gòu)建點(diǎn)格單元的中心點(diǎn)集合:其中:

1.4 點(diǎn)格覆蓋效果評(píng)估

從點(diǎn)格化區(qū)域中挑選出覆蓋任務(wù)區(qū)域的點(diǎn)格單元，作為任務(wù)分解后的子任務(wù)。對(duì)于任務(wù)點(diǎn)格單元的中心點(diǎn)判斷其是否覆蓋于任務(wù)區(qū)域內(nèi)的主要步驟如下:

Step 2:設(shè)Pi1和Pi2的中點(diǎn)為Oi12，作至Oi12方向的射線

式中，Ei越大說明點(diǎn)格化區(qū)域設(shè)置與任務(wù)區(qū)域越匹配；Ei，2越小說明點(diǎn)格單元分布對(duì)任務(wù)區(qū)域的覆蓋效果越好。

1.5 任務(wù)規(guī)劃模型構(gòu)建

經(jīng)過分割處理后的任務(wù)均為可一次性觀測的獨(dú)立子任務(wù)，對(duì)于當(dāng)前調(diào)度事件為slnow，不妨將生成的所有子任務(wù)和無需分割的原任務(wù)重新標(biāo)記為:式中，TN為任務(wù)集合中的元素?cái)?shù)量。

任務(wù)集合通過集中規(guī)劃生成資源分配結(jié)果，而整個(gè)調(diào)度過程可分解為由若干調(diào)度事件構(gòu)成的調(diào) 度 序 列表示第i次調(diào)度事件占用的時(shí)段。

設(shè)成像衛(wèi)星資源集合為:

式中，SN為衛(wèi)星集合中的元素?cái)?shù)量。

將Satk攜帶的載荷類型標(biāo)記為SSenk，Satk對(duì)taski的可視窗口集合記為VTWSi,k。表示在sli中向用戶追加釋放Satk的可用時(shí)段，其中FTBegini,k, FTEndi,k分別為FTWi,k的開始時(shí)刻和結(jié)束時(shí)刻。

對(duì)于當(dāng)前調(diào)度事件為slnow，向用戶累計(jì)釋放的Satk可用時(shí)段為:

i,j=0。若taski可執(zhí)行，設(shè)其為分配的執(zhí)行時(shí)段為執(zhí)行資源為ESati。

構(gòu)建成像衛(wèi)星任務(wù)規(guī)劃問題的優(yōu)化目標(biāo)函數(shù)，如下所示:

其中，Q為決策變量X的可行域。

對(duì)于Tasknow中的任務(wù)，在調(diào)度過程中應(yīng)滿足以下約束[17-18]:

1.6 任務(wù)規(guī)劃算法設(shè)計(jì)

在現(xiàn)有研究成果中，群智能算法被廣泛應(yīng)用于成像衛(wèi)星任務(wù)規(guī)劃問題的求解。其中，粒子群算法（Particle swarm optimization，PSO）以實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)在解決實(shí)際問題中展示出其優(yōu)越性。PSO算法的基本步驟如下:

Step 1:初始化種群，設(shè)定種群規(guī)模和個(gè)體進(jìn)化規(guī)則；

Step 2:對(duì)初始化種群中的每個(gè)粒子進(jìn)行適應(yīng)度評(píng)估；

Step 3:更新種群信息

Step 3.1:對(duì)于每個(gè)粒子，將其當(dāng)前搜索位置的適應(yīng)度與個(gè)體最優(yōu)位置的適應(yīng)度比較，若更好，則將當(dāng)前搜索位置作為個(gè)體最優(yōu)位置；

Step 3.2:檢查所有粒子的搜索位置，若存在優(yōu)于種群歷史最優(yōu)位置的情況，將出現(xiàn)的更優(yōu)搜索位置作為種群歷史最優(yōu)位置；

Step 4:計(jì)算各粒子的移動(dòng)速度和方向，從而更新粒子的搜索位置；

Step 5:如果搜索過程達(dá)到預(yù)先設(shè)定的終止條件，算法結(jié)束；否則，返回Step 2繼續(xù)迭代。

為克服基本PSO算法存在的搜索精度不高、易陷入早熟等不足，本文將具有全局搜索能力的禁忌搜索策略和遺傳算法中的交叉進(jìn)化策略嵌入至基本PSO算法中，作為面向森林區(qū)域覆蓋觀測的成像衛(wèi)星規(guī)劃算法。

（1）禁忌搜索策略

為避免迭代過程中出現(xiàn)迂回搜索，防止過早陷入局部最優(yōu)，在每次迭代時(shí)記錄最近接受的歷史最優(yōu)解信息，在一定次數(shù)內(nèi)禁止粒子再次訪問該搜索位置；超過一定次數(shù)后，禁忌對(duì)象被解除，可重新訪問。禁忌表的設(shè)計(jì)包括三個(gè)要素，即禁忌長度、禁忌對(duì)象和特赦規(guī)則。

所謂禁忌對(duì)象就是禁忌表中的元素，而禁忌目的是為避免搜索循環(huán)。本文將各子群每次進(jìn)化時(shí)的精英粒子位置作為禁忌對(duì)象，搜索粒子應(yīng)避免朝著禁忌對(duì)象相同的位置移動(dòng)。

禁忌長度通常指禁忌表的規(guī)模，即表中可存儲(chǔ)元素?cái)?shù)量。為不影響搜索速度，節(jié)省存儲(chǔ)空間，禁忌表中僅保存單個(gè)元素。

將禁忌對(duì)象從禁忌表中移出稱之為特赦，本文考慮兩種特赦情況:一是當(dāng)禁忌對(duì)象經(jīng)歷的迭代次數(shù)到達(dá)預(yù)定閥值；二是有其它滿足禁忌特征的粒子替換當(dāng)前禁忌對(duì)象。

（2）交叉進(jìn)化策略

對(duì)于弱勢子群的度量，可在每次迭代后，將各子群按其最歷史優(yōu)解的適應(yīng)度排序，然后以適應(yīng)度處于后半部分的子群作為弱勢子群，與處于前半部分的強(qiáng)勢子群交叉基因，改善種群質(zhì)量。

算法采用雙點(diǎn)逆轉(zhuǎn)方式實(shí)現(xiàn)交叉操作，首先隨機(jī)選擇斷點(diǎn)，將粒子信息劃分為前、中、后三部分。在交叉時(shí)，僅保留父代1（Parent 1）的前部分，而將中間部分逆轉(zhuǎn)，再結(jié)合父代2（Parent 2）的后部分，形成子代1（Child 1）；同理，保留父代2（Parent 2）前部分，將其中間部分逆轉(zhuǎn)，并結(jié)合父代1（Parent 1）后部分，形成子代2（Child 2）。

（3）粒子搜索方式

第r個(gè)粒子在第t次迭代時(shí)的移動(dòng)速度為:

第r個(gè)粒子在第t次迭代時(shí)的最優(yōu)位置為:

此外，描述種群在第t次迭代時(shí)具有的種群歷史最優(yōu)位置為:

粒子的搜索位置和移動(dòng)速度采用以下方式進(jìn)行迭代:

式中，F(xiàn)為種群規(guī)模；r1，r2∈[0，1]為均勻分布隨機(jī)數(shù)；為移動(dòng)速度；c1，c2為學(xué)習(xí)因子；w為慣性系數(shù)。

2 仿真實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文所提算法的可行性，我們利用衛(wèi)星工具箱（Satellite tool kit，STK）搭建仿真場景，并基于MATLAB R2012b進(jìn)行仿真驅(qū)動(dòng)。

首先在STK場景中隨機(jī)產(chǎn)生若干個(gè)待觀測區(qū)域，并生成相應(yīng)的任務(wù)參數(shù)，然后采用文中的點(diǎn)格化方法進(jìn)行預(yù)處理，效果如圖4所示。

圖4 待觀測區(qū)域點(diǎn)格化效果Fig. 4 The point grid partition effect of observation area

對(duì)點(diǎn)格化效果進(jìn)行評(píng)估，挑選出品質(zhì)較好的觀測區(qū)域作為測試對(duì)象，其中部分?jǐn)?shù)據(jù)如表1所示。

表1 測試對(duì)象的點(diǎn)格化效果Table 1 The point grid partition effect of the test tasks

將經(jīng)過預(yù)處理后生成的子任務(wù)作為待規(guī)劃任務(wù)集，模擬3顆對(duì)地成像衛(wèi)星，設(shè)置軌道根數(shù)如表2所示。

表2 成像衛(wèi)星的部分軌道根數(shù)Table 2 The orbit parameters of imaging satellites

采用IPSO算法進(jìn)行優(yōu)化求解，設(shè)置初始種群規(guī)模為35，初始移動(dòng)速度為[0.1，0.7]間的隨機(jī)數(shù)，學(xué)習(xí)因子取2，慣性系數(shù)取0.8，構(gòu)造適應(yīng)度函數(shù)為:

設(shè)置進(jìn)化代數(shù)為30，將IPSO算法的計(jì)算結(jié)果與PSO算法進(jìn)行對(duì)比，如下所示:

由圖5可知，在本文構(gòu)建的測試場景中，IPSO算法獲取的優(yōu)化解好于PSO算法。雖然在初始種群構(gòu)造中，兩種算法獲取的解質(zhì)量相當(dāng)，但在后續(xù)迭代中，IPSO算法快速向高質(zhì)量優(yōu)化解方向搜索，并在迭代周期的1/3～2/3區(qū)間內(nèi)獲取種群的近似最優(yōu)解。上述結(jié)果說明，加入忌搜索策略和交叉進(jìn)化策略的IPSO算法能夠兼顧搜索質(zhì)量和搜索速度，具備較高的優(yōu)化效率。

圖5 不同優(yōu)化算法迭代過程對(duì)比Fig. 5 The comparison between the iteration processes of different algorithms

3 結(jié)論與討論

以森林區(qū)域覆蓋觀測為需求，研究了成像衛(wèi)星任務(wù)規(guī)劃方法?？紤]到森林區(qū)域面積廣闊，通常需要多次成像才能完成觀測，提出森林區(qū)域觀測目標(biāo)的預(yù)處理方法，采用點(diǎn)格化方式實(shí)現(xiàn)區(qū)域狀目標(biāo)向點(diǎn)狀目標(biāo)的轉(zhuǎn)換，詳細(xì)介紹了點(diǎn)格化的步驟和依據(jù)。在此基礎(chǔ)上，分析了成像衛(wèi)星對(duì)地觀測約束條件，構(gòu)建出任務(wù)規(guī)劃數(shù)學(xué)模型。針對(duì)模型求解的復(fù)雜性，設(shè)計(jì)了粒子群算法對(duì)模型進(jìn)行求解。為了進(jìn)一步提高粒子群算法的性能，在其中創(chuàng)造性融入了禁忌策略和交叉策略。通過仿真實(shí)驗(yàn)和對(duì)比分析，驗(yàn)證了文中所提算法的有效性。相比于傳統(tǒng)粒子群算法，融合禁忌與交叉策略的粒子群算法可以在更短的時(shí)間內(nèi)收斂到質(zhì)量更高的解。本文所提方法對(duì)高效應(yīng)用稀缺衛(wèi)星資源實(shí)現(xiàn)對(duì)森林區(qū)域的成像偵察具有重要意義，可為評(píng)估森林儲(chǔ)量、監(jiān)測森林災(zāi)害、判別林木類型、監(jiān)測林地沙化等多個(gè)方面提供支持。

在后續(xù)的工作中還需進(jìn)一步研究動(dòng)態(tài)環(huán)境下的云層遮擋、資源失效等，面向森林資源觀測的成像衛(wèi)星任務(wù)規(guī)劃方法，提高觀測過程的魯棒性與適應(yīng)性。另外，如何協(xié)同無人機(jī)、飛艇、地面?zhèn)鞲衅鞯犬悩?gòu)平臺(tái)實(shí)現(xiàn)對(duì)森林資源的高效觀測覆蓋是一個(gè)值得研究的前沿課題。