基于基因表達(dá)式編程的多星成像任務(wù)規(guī)劃算法*

明衛(wèi)鵬，馬廣彬，章文毅

(1 中國科學(xué)院遙感與數(shù)字地球研究所， 北京 100094； 2 中國科學(xué)院大學(xué)， 北京 100049) (2018年11月30日收稿； 2019年3月4日收修改稿)

對地觀測技術(shù)的優(yōu)勢在于能夠快速準(zhǔn)確地獲取人類地表活動信息[1]，而遙感作為對地觀測技術(shù)的一種，其應(yīng)用范圍越來越廣泛，不僅在環(huán)境災(zāi)害防治、城市建設(shè)規(guī)劃、氣象預(yù)報等領(lǐng)域發(fā)揮重要作用[2]，而且在考古遺址[3]、遙感衛(wèi)星車輛檢測[4]、氣溶膠輻射觀測[5]等方面的應(yīng)用也越加普遍。雖然對地觀測衛(wèi)星的數(shù)量和成像能力已得到巨大提升，但由于各行各業(yè)對遙感影像數(shù)據(jù)的大量需求，使得成像衛(wèi)星的資源仍相對稀缺。因此，研究如何充分利用衛(wèi)星資源，以經(jīng)濟(jì)快捷的方式獲取較高質(zhì)量的遙感數(shù)據(jù)，就成為必要之舉，也是本文要研究的多星成像任務(wù)規(guī)劃問題。它是指考慮星上傳感器成像能力、傳感器的側(cè)擺能力等因素，合理安排衛(wèi)星，對區(qū)域目標(biāo)制定成像方案[6-7]。

多星成像任務(wù)規(guī)劃是一類極其復(fù)雜的組合優(yōu)化問題[8],同時在數(shù)學(xué)上也是一種NP—完全問題[9]。這類問題，國內(nèi)外已有大量研究[10-11]，通常包括模型建立和求解兩部分。如Wolfe和Sorensen[12]將衛(wèi)星成像任務(wù)規(guī)劃問題映射為帶時間窗約束的背包問題，建立整數(shù)規(guī)劃模型；Song等[13]對單星成像規(guī)劃問題建立非線性規(guī)劃模型；賀仁杰等[14]對成像規(guī)劃問題建立約束滿足問題模型。而模型求解的方法多采用啟發(fā)式算法，如模擬退火算法[14]、蟻群算法[15]、遺傳算法[16]等。這些算法大都從解的鄰域搜索最優(yōu)解，容易陷入局部最優(yōu)，得到次優(yōu)解。雖然模擬退火算法對陷入局部最優(yōu)有所改善，但計算效率不高。因此，為增強(qiáng)全局最優(yōu)解的搜索能力，并兼顧計算效率，本文采用基因表達(dá)式編程來求解多星成像規(guī)劃問題。

1 基因表達(dá)式編程算法簡介

基因表達(dá)式編程(gene expression programming,GEP)起源于遺傳算法，但又結(jié)合了遺傳編程的優(yōu)點，是二者融合的產(chǎn)物[17]。它的染色體是由一個或多個基因組成，用固定長度的線性符號串來表示。每個基因也是由固定長度的線性符號串構(gòu)成，包括頭部和尾部兩部分。表1為染色體的構(gòu)成。

表1 染色體的構(gòu)成Table 1 Chromosome composition

基因頭部符號串包含函數(shù)符號和終止符；尾部符號串只包含終止符。長度為t的尾部和長度為h的頭部滿足公式

t=h×(n-1)+1，

(1)

式中：n為函數(shù)符中的最大操作數(shù)目[18]。例如，“+”，“-”，“×”的操作數(shù)目都為2；Q代表平方根，它為一目運算符。對于函數(shù)符號集{+，-， ×，Q}中最大操作數(shù)目為2，則n=2。

此外，基因表達(dá)式編程的多基因家族染色體中可以包含多個基因家族，基因家族之間按某種規(guī)則相互作用，而基因家族又可以包含多個基因。GEP的遺傳算子有變異、逆串、插串、根插串、兩點重組等，豐富的遺傳算子和靈活的染色體結(jié)構(gòu)使得GEP具有強(qiáng)大的應(yīng)用功能。

2 多星成像模型的建立

在研究區(qū)域目標(biāo)多星成像時，需要進(jìn)行衛(wèi)星軌道的預(yù)報計算，本文采用應(yīng)用廣泛的SGP4(simplified general perturbations)模型，即簡化常規(guī)攝動模型[19-20]求解衛(wèi)星的位置和速度。然后再根據(jù)目標(biāo)區(qū)域，結(jié)合過境衛(wèi)星的側(cè)擺能力和過境時間計算成像條帶。在選取條帶組成成像方案時，需要考慮約束性。

2.1 模型的約束條件分析

模型的約束主要考慮衛(wèi)星的成像約束，表2是本文考慮的衛(wèi)星成像的約束規(guī)則。

表2 衛(wèi)星成像的約束規(guī)則Table 2 Constraint rules of satellite imaging

衛(wèi)星過境時，所攜帶的傳感器的不同成像模式都有可能參與成像，本文將傳感器以不同的成像模式過境稱為邏輯軌道。所以邏輯上來講，一顆有多種模式傳感器的衛(wèi)星過境一次就會產(chǎn)生多個邏輯軌道。如果傳感器不同的成像模式不能同時參與成像，就只能選取其中之一的邏輯軌道產(chǎn)生的條帶參與成像，否則，便不滿足表2衛(wèi)星約束中的1)、2)約束條件。同一邏輯軌道產(chǎn)生的多個條帶，只能選擇其中一個參與成像，否則便不滿足表2衛(wèi)星約束中的3)、4)約束條件。如果參與成像的條帶之間重疊范圍過大，會造成極大的資源浪費。所以需要檢查選取的條帶是否滿足成像覆蓋約束。通常設(shè)定一個閾值OverLap為一個常數(shù)，兩個條帶分別為Stripx, Stripy，二者的重疊部分為

Intersection=Stripx∩Stripy.

(2)

設(shè)重疊區(qū)域的面積為Aintersect，條帶Stripx的面積為AStripx，條帶Stripy的面積為AStripy，則應(yīng)滿足約束條件

Aintersect/AStripx

和

Aintersect/AStripy

(3)

2.2 建立約束滿足性模型

為便于模型的建立及求解，本文將一條成像條帶看作是一個元任務(wù)，作為模型的數(shù)據(jù)輸入[14]。它包含衛(wèi)星、傳感器、成像范圍、成像模式、成像時間等重要信息。決定成像任務(wù)規(guī)劃方案優(yōu)劣的因素有多個，主要包括：目標(biāo)區(qū)域的覆蓋率；成像方案的起止時間；參與成像的傳感器個數(shù)；成像過境的軌道數(shù)；成像的條帶數(shù)。其中任意因素皆可作為成像任務(wù)優(yōu)化的目標(biāo)，多星成像任務(wù)規(guī)劃是一個多目標(biāo)優(yōu)化問題。其數(shù)學(xué)模型一般描寫為如下形式：

(4)

(5)

式中：X=[x1,x2,…,xn]T為決策變量的向量,Z=F(X)為目標(biāo)向量，Φ(X)≤G為約束向量。

(6)

(7)

(8)

(9)

2.3 模型的復(fù)雜性分析

假設(shè)有L顆衛(wèi)星,Li(i=1,2,…,L)為第i顆衛(wèi)星過境次數(shù)，si為第i顆衛(wèi)星載有的傳感器數(shù)，Mji為第j個傳感器成像模式數(shù)；設(shè)第i顆衛(wèi)星的第j個傳感器第k個成像模式產(chǎn)生LSMPi,j,k個條帶。則所有衛(wèi)星過境產(chǎn)生的邏輯軌道數(shù)為

(10)

邏輯軌道產(chǎn)生的可能成像的總條帶數(shù)為

(11)

進(jìn)一步簡化分析，將經(jīng)過預(yù)處理后得到的過境邏輯軌道數(shù)設(shè)為n,設(shè)每一過境軌道可能的成像條帶個數(shù)分別為s1,s2,…,sn。設(shè)成像方案數(shù)為F(n,s),一般地可以推斷出[16]

(12)

3 算法求解

3.1 解的編碼設(shè)計

本文設(shè)計了包含兩個基因家族的染色體，每一個基因家族包含多個基因?；虻念^部h=0，由式(1)可得尾部t=1，故基因長度等于1。

本文首先將產(chǎn)生的所有邏輯軌道劃分為不同的集合，邏輯軌道集合的數(shù)量即是基因家族包含的單基因的數(shù)量，每個邏輯軌道集合包含的多個邏輯軌道相互沖突，不能同時參與成像。第一個基因家族中單個基因代表從邏輯軌道集合里被選中的邏輯軌道，另一個基因家族中的單個基因代表由上一個基因家族中相對應(yīng)的邏輯軌道產(chǎn)生的條帶集中被選中的參與成像的條帶。這樣的設(shè)計就可以滿足表2中衛(wèi)星約束的相關(guān)條件。圖1 為染色體的結(jié)構(gòu)。

圖1 染色體結(jié)構(gòu)Fig.1 Chromosome structure

3.2 引入知識庫

倒置這一遺傳算子能夠增強(qiáng)算法對于解空間的搜索能力，同時對于染色體結(jié)構(gòu)的破壞性也較大，不利于保留優(yōu)良基因。為此本文引入知識庫，該知識庫包含了種群在進(jìn)行迭代操作前的較優(yōu)的小部分個體。設(shè)每次迭代產(chǎn)生的種群中最優(yōu)個體為X，知識庫中最優(yōu)個體為Y，若X的適應(yīng)度函數(shù)值(自適應(yīng)值)大于Y，則將種群中比Y優(yōu)的個體加入到知識庫，替換掉知識庫中次于Y的個體；若X的適應(yīng)度函數(shù)值小于Y，則用知識庫中所有優(yōu)于X的個體置換掉種群里最差的一部分個體。此操作保證了參與迭代計算的種群個體始終是較優(yōu)的，也有利于保留每次迭代產(chǎn)生的最優(yōu)個體，避免最優(yōu)解丟失。

3.3 算法求解過程

在算法流程中染色體的自適應(yīng)值也就是優(yōu)化目標(biāo)的收益函數(shù)值，收益函數(shù)可見式(6)～式(9)。具體遺傳算子如下：

1)交叉：先用輪盤賭注的方法選擇個體，然后采取兩點重組的方式進(jìn)行交叉。當(dāng)?shù)?條染色體的邏輯軌道和第2條染色體的邏輯軌道進(jìn)行交換時(交換的邏輯軌道必須屬于同一邏輯軌道集，如邏輯軌道集B中的B1、B2), 相應(yīng)的條帶也得進(jìn)行交換，這樣保證了染色體始終滿足表2中衛(wèi)星約束的相關(guān)條件。

2)變異：當(dāng)執(zhí)行變異操作時，先進(jìn)行邏輯軌道的變異，再從變異的邏輯軌道產(chǎn)生的條帶中選取新的條帶。

3)倒置：在第1個基因家族中隨機(jī)選取2個基因，將二者內(nèi)的基因片段倒置，相對應(yīng)的第1個基因家族中的基因片段也進(jìn)行倒置。這一操作可能使基因非法，所以需要對倒置的基因片段進(jìn)行檢驗，如果條帶號超出對應(yīng)的邏輯軌道產(chǎn)生的條帶范圍，則基因非法，重新選取條帶，使基因合法。

此外，為了防止條帶之間的重疊率過大而造成重復(fù)拍攝，還應(yīng)做重疊率約束性檢驗。本文的做法是：

1)在染色體所包含的所有條帶集{S1,S2,…，Sn}中，按順序遍歷條帶Si(i=1, 2，…，n)，若遍歷完所有條帶，遍歷結(jié)束，轉(zhuǎn)4)；否則轉(zhuǎn)2)。

2)依次查驗條帶Si與第i個之前的所有條帶Sj(j=1,2，…，i-1)是否滿足重疊率約束條件，滿足轉(zhuǎn)1)；不滿足，在Si對應(yīng)的邏輯軌道里產(chǎn)生的條帶集里重新選取條帶，若選取的條帶Si與Sj(j=1,2，…，i-1)滿足重疊率約束條件，轉(zhuǎn)1)；否則，轉(zhuǎn)3)。

3)比較條帶Si，與Sj(j=1,2，…，i-1)對目標(biāo)區(qū)域覆蓋率的大小，若Si的較小，將Si設(shè)置為空，轉(zhuǎn)1)；若Sj的較小，將Sj設(shè)置為空,繼續(xù)比較剩余的條帶Sj，直至j=i-1時，比較結(jié)束，轉(zhuǎn)1)。

4)檢驗結(jié)束，輸出結(jié)果。

基因表達(dá)式編程與遺傳算法的流程[22]類似，綜合上文可得圖2為本文的算法流程圖。

圖2 算法流程圖Fig.2 Flow chart of the algorithm

4 仿真實驗

本文的仿真實驗，采用NetBeans軟件以及java語言編程，在World Wind Java基礎(chǔ)上實現(xiàn)了多星成像任務(wù)規(guī)劃算法，規(guī)劃方案顯示等功能。為驗證本文算法的性能并與文獻(xiàn)[16]中的遺傳算法作對比，首先選取多個行政區(qū)，作為目標(biāo)觀測區(qū)域。同一目標(biāo)觀測區(qū)域調(diào)用兩種算法時，輸入?yún)?shù)相同，即選取的衛(wèi)星、規(guī)劃起止時間，收斂條件均相同，以成像方案的條帶數(shù)最少作為優(yōu)化目標(biāo)。為了更直觀地對比調(diào)用兩種算法得出的成像方案的覆蓋率、條帶數(shù)，分別將結(jié)果整理為圖3、圖4。

圖3 觀測次數(shù)對比Fig.3 Comparison of the observation times

圖4 成像覆蓋率對比Fig.4 Comparison of the imaging coverage

由圖3、圖4可知，基因表達(dá)式編程GEP相對于遺傳算法GA所得的觀測方案，不僅條帶數(shù)均少于后者，而且覆蓋率大于后者。從觀測次數(shù)(條帶數(shù))以及目標(biāo)區(qū)域覆蓋率兩項指標(biāo)而言，基因表達(dá)式算法得出的成像方案是較優(yōu)的。在計算耗時上，對于大多數(shù)目標(biāo)區(qū)域GEP計算用時均比GA要長，這是因為遺傳算法在迭代過程中出現(xiàn)種群退化或停滯，然后過早地結(jié)束迭代計算；再者，在GEP的迭代計算過程中，本文引入倒置這一遺傳算子，增加了計算量。但總體而言，GEP對大多數(shù)目標(biāo)區(qū)域的計算用時在90 s內(nèi)，是一種較為理想的結(jié)果。

圖5 覆蓋率變化趨勢Fig.5 The coverage changes

繼續(xù)選取內(nèi)蒙古作為觀測區(qū)域，每兩天作為時間間隔，逐漸增加觀測天數(shù)，并追蹤目標(biāo)區(qū)域觀測情況。將結(jié)果整理成圖5，可知GEP算法對觀測區(qū)域隨觀測天數(shù)的增加，其覆蓋率增加得較快，且約兩周后達(dá)到頂峰，即覆蓋率為99.782%，并處于穩(wěn)定狀態(tài)。而GA算法對觀測區(qū)域的覆蓋率雖然也在隨觀測天數(shù)的增加而增加，但起伏較大，達(dá)到最優(yōu)解的周期較長，而且不穩(wěn)定。另外，GA算法求得最優(yōu)解的覆蓋率為96.442%，低于GEP的最優(yōu)解。以上說明，GEP應(yīng)用于多星成像任務(wù)規(guī)劃問題，具有全局搜索能力強(qiáng)、魯棒性較佳等優(yōu)點,并極大提高了解的精度。

對廣東、云南、四川等區(qū)域進(jìn)行成像規(guī)劃仿真顯示。圖6直觀顯示了基因表達(dá)式編程所得的成像任務(wù)規(guī)劃方案較佳。

圖6 觀測方案的仿真顯示Fig.6 Simulating display of the observation schemes

5 結(jié)語

多星成像規(guī)劃問題的研究對于衛(wèi)星資源的充分利用及快速獲取區(qū)域數(shù)據(jù)具有重要意義。本文結(jié)合實際應(yīng)用，對面向區(qū)域目標(biāo)的多星成像規(guī)劃進(jìn)行研究，首次用基因表達(dá)式編程GEP進(jìn)行求解，并在算法過程中引入知識庫保證參與迭代計算的種群是較優(yōu)的。結(jié)果表明，本文算法求解精度高，魯棒性較佳，相比遺傳算法性能顯著。但是，理論上講，GEP計算效率是較高的，本文用于求解多星成像規(guī)劃問題時，計算效率并未完全挖掘出來；此外，對于衛(wèi)星的側(cè)擺，只考慮了左右側(cè)擺，未考慮衛(wèi)星的前后側(cè)擺，這些有待于進(jìn)一步研究和探索。