李鵬宇, 崔家山, 孫 然

(1.上海電子信息職業(yè)技術(shù)學(xué)院 中德工程學(xué)院,上海 201411; 2.西安電子科技大學(xué) 空間科學(xué)與技術(shù)學(xué)院,陜西 西安 710126;3.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

干涉合成孔徑雷達(dá)(Interferometric Synthetic Aperture Radar,InSAR)對(duì)地測(cè)繪任務(wù)規(guī)劃[1-3]是結(jié)合衛(wèi)星編隊(duì)和優(yōu)化技術(shù)的一種對(duì)地觀測(cè)任務(wù)應(yīng)用,由于衛(wèi)星編隊(duì)技術(shù)載荷約束的復(fù)雜性,相應(yīng)地對(duì)地觀測(cè)任務(wù)約束也更加復(fù)雜,任務(wù)求解難度更高,因此為了使衛(wèi)星使用效能達(dá)到最優(yōu),有必要研究InSAR編隊(duì)任務(wù)規(guī)劃建模和優(yōu)化方法。評(píng)價(jià)衛(wèi)星任務(wù)規(guī)劃的優(yōu)劣需要考慮目標(biāo)及重要目標(biāo)的覆蓋率、任務(wù)規(guī)劃總時(shí)間[4-6]等。由于編隊(duì)衛(wèi)星獨(dú)特的工作特點(diǎn),存在測(cè)繪基線和開(kāi)關(guān)機(jī)等多種約束條件,衛(wèi)星軌道為雙星繞飛或者跟飛軌道模式,雙星聯(lián)合對(duì)地成像,所以雷達(dá)衛(wèi)星對(duì)地面目標(biāo)的測(cè)繪為一個(gè)個(gè)觀測(cè)條帶,任務(wù)規(guī)劃就是從多種觀測(cè)條帶任務(wù)組合中選優(yōu)的問(wèn)題,即NP-hard問(wèn)題[7-8]。

關(guān)于衛(wèi)星任務(wù)規(guī)劃算法研究方面,主要有整數(shù)規(guī)劃模型、啟發(fā)式算法和遺傳優(yōu)化算法等。國(guó)外的Deb等[9]建立整數(shù)規(guī)劃模型,以最大化任務(wù)收益為優(yōu)化目標(biāo),運(yùn)用優(yōu)先搜索和動(dòng)態(tài)規(guī)劃對(duì)衛(wèi)星成像調(diào)度問(wèn)題求解;Li等[10]研究了衛(wèi)星對(duì)區(qū)域目標(biāo)的測(cè)繪調(diào)度問(wèn)題,建立了約束滿足模型,比較了貪婪、整數(shù)規(guī)劃和遺傳算法,實(shí)驗(yàn)證明,雖然遺傳算法性能較好,但對(duì)于大規(guī)模約束問(wèn)題建模比較困難。Bianchessi等[11]提出了二進(jìn)制整數(shù)模型,采用基于拉格朗日松弛和梯度的啟發(fā)式算法[11]。以上研究是以單顆衛(wèi)星最大化任務(wù)收益為優(yōu)化目標(biāo),在雙星編隊(duì)能源利用平衡方面研究比較少,對(duì)遺傳優(yōu)化算法只是理論上的研究和證明,沒(méi)有建立完備的關(guān)于雙星編隊(duì)任務(wù)的規(guī)劃模型。

針對(duì)雙星編隊(duì)測(cè)繪任務(wù)的多目標(biāo)多約束任務(wù)規(guī)劃需求,提出了一種基于優(yōu)先級(jí)的遺傳優(yōu)化算法,并建立模型仿真求解任務(wù)規(guī)劃的最優(yōu)解集。對(duì)編隊(duì)測(cè)繪任務(wù)進(jìn)行數(shù)據(jù)預(yù)處理,給出問(wèn)題的形式化描述,分析各項(xiàng)約束條件,提出了滿足雙星編隊(duì)任務(wù)規(guī)劃的約束模型;以最小化測(cè)繪任務(wù)總時(shí)間和平衡雙星資源調(diào)度為優(yōu)化目標(biāo),提出了一種基于優(yōu)先級(jí)的遺傳優(yōu)化算法,結(jié)合雙星編隊(duì)載荷特點(diǎn)求解問(wèn)題,通過(guò)實(shí)驗(yàn)仿真驗(yàn)證算法有效性和可行性。

1 雙星編隊(duì)建模

由于衛(wèi)星編隊(duì)在重訪周期軌道的空間運(yùn)行,所有測(cè)繪任務(wù)同一時(shí)刻只能選擇在特定雷達(dá)波位覆蓋范圍內(nèi)進(jìn)行,不可能對(duì)所有雷達(dá)波位范圍的測(cè)繪任務(wù)進(jìn)行成像。為了實(shí)現(xiàn)對(duì)衛(wèi)星資源合理使用,需要對(duì)不同衛(wèi)星、不同時(shí)段和不同波位測(cè)繪任務(wù)實(shí)施優(yōu)化調(diào)度,選擇合適的任務(wù)條帶進(jìn)行成像。圖1為主從星相對(duì)運(yùn)動(dòng)軌跡,假設(shè)編隊(duì)為繞飛構(gòu)型,一個(gè)衛(wèi)星為主星,另一個(gè)星為從星,兩星之間的相對(duì)運(yùn)動(dòng)軌跡為橢圓,投影到XY軸軌跡為圓形。圖2所示的是測(cè)繪模式為雙星交替發(fā)射雷達(dá)波束、兩星同時(shí)接收的工作方式。兩星間距變化為幾公里至十幾公里,其垂直有效基線和沿航跡基線需要滿足測(cè)繪需求[12-14]。

圖1 主從星相對(duì)運(yùn)動(dòng)軌跡

圖2 雙星繞飛編隊(duì)InSAR測(cè)繪

假定設(shè)計(jì)雙星編隊(duì)的雷達(dá)載荷約束描述如表1所示。

表1 衛(wèi)星任務(wù)規(guī)劃約束

規(guī)劃元任務(wù)定義為不可分割的最小衛(wèi)星測(cè)繪條帶,圖3所示的條帶1、條帶2分別可以作為2個(gè)不同的規(guī)劃元任務(wù)。其中越南北部區(qū)域的條帶分割圖,由于衛(wèi)星工作的特點(diǎn),每次衛(wèi)星航過(guò)越南北部區(qū)域的時(shí)候只有一個(gè)條帶可以被選中執(zhí)行,因此如何選取合適的條帶組合,就是一個(gè)典型凸優(yōu)化問(wèn)題[15-17],優(yōu)化目標(biāo)為選取最少的條帶,衛(wèi)星使用的資源最少即用最少衛(wèi)星圈次進(jìn)行測(cè)繪,同時(shí)能夠完成區(qū)域的最大化覆蓋。這個(gè)優(yōu)化問(wèn)題既要考慮單顆衛(wèi)星平臺(tái)的載荷約束條件,還要考慮如何調(diào)配組合雙星開(kāi)關(guān)機(jī)策略,從而達(dá)到衛(wèi)星的資源使用最優(yōu),同時(shí)達(dá)到任務(wù)收益最大化。

圖3 不同的規(guī)劃任務(wù)條帶組成衛(wèi)星任務(wù)最小單元

2 任務(wù)規(guī)劃問(wèn)題建模

在多目標(biāo)多約束優(yōu)化問(wèn)題中,各目標(biāo)通常相互沖突且不可同時(shí)兼顧,對(duì)其中的某一個(gè)目標(biāo)進(jìn)行優(yōu)化就必須以犧牲其他目標(biāo)作為代價(jià),各目標(biāo)約束條件的單位又往往不一致,因此很難客觀地評(píng)價(jià)多目標(biāo)問(wèn)題解的優(yōu)劣性。與單目標(biāo)優(yōu)化問(wèn)題相比,多目標(biāo)優(yōu)化問(wèn)題的解并不是唯一的,而是存在一個(gè)最優(yōu)解集合,集合中元素稱為 Pareto 最優(yōu)或非劣最優(yōu)。其中最優(yōu)解往往有無(wú)窮多個(gè),如何在最優(yōu)解集合中求出一組分布均勻且數(shù)量充足的候選解供給決策者進(jìn)行選擇就顯得十分重要。經(jīng)典的方法很好地解決了部分單目標(biāo)優(yōu)化問(wèn)題,然而現(xiàn)實(shí)世界中的許多優(yōu)化問(wèn)題都涉及多個(gè)目標(biāo)的優(yōu)化,而且這些目標(biāo)并不是獨(dú)立存在的,它們往往是耦合在一起且處于相互競(jìng)爭(zhēng)的狀態(tài),它們的競(jìng)爭(zhēng)和復(fù)雜度使優(yōu)化變得十分困難[18-19]。一般地,多目標(biāo)優(yōu)化問(wèn)題可以用函數(shù)f來(lái)定義,該函數(shù)把決策向量X映射到目標(biāo)向量Y,可得:

(1)

式中:X=(x1,x2,…,xm)由m個(gè)決策變量xi構(gòu)成;Y為n個(gè)須同時(shí)優(yōu)化的目標(biāo)fi(X)構(gòu)成;約束g(X)為r個(gè)等式和不等式構(gòu)成。制定InSAR編隊(duì)衛(wèi)星優(yōu)化目標(biāo)準(zhǔn)則主要包含以下幾個(gè)方面。

① 雙星總計(jì)目標(biāo)元任務(wù)數(shù)量最大。

② 雙星總計(jì)成像重點(diǎn)目標(biāo)元任務(wù)數(shù)量最大。

③ 雙星總計(jì)需要規(guī)劃圈次最小。

④ 單圈總時(shí)長(zhǎng)滿足小于等于TD_SS。

⑤ 單次成像時(shí)長(zhǎng)小于等于MD_SI。

⑥ 雙星開(kāi)關(guān)機(jī)最小間隔大于等于MITI。

⑦ 單軌雙星最大成像次數(shù)小于等于SC_SS。

其中,在互相沖突的情況下第②目標(biāo)要高于第①目標(biāo),雙星編隊(duì)測(cè)繪任務(wù)規(guī)劃設(shè)計(jì)的數(shù)學(xué)模型為

(2)

式中:i為衛(wèi)星工作圈號(hào);j為單圈內(nèi)成像序號(hào);m為圈號(hào)i內(nèi)總計(jì)成像次數(shù);n為指定時(shí)間范圍內(nèi)衛(wèi)星工作的總計(jì)圈次;TN為元任務(wù)時(shí)長(zhǎng);IN為重點(diǎn)區(qū)域元任務(wù)時(shí)長(zhǎng);countof(circle)為本次優(yōu)化衛(wèi)星工作的總?cè)Υ巍?/p>

3 規(guī)劃算法設(shè)計(jì)

3.1 算法設(shè)計(jì)流程

多目標(biāo)遺傳算法主要步驟包括參數(shù)編碼、設(shè)定初始種群、設(shè)置適應(yīng)值函數(shù)、復(fù)制、選擇、交叉、變異操作以及問(wèn)題解碼,具有全局優(yōu)化、魯棒性好、搜索效率高和本質(zhì)并行性等特點(diǎn)。本研究運(yùn)用基于優(yōu)先級(jí)的遺傳算法解決多目標(biāo)優(yōu)化問(wèn)題,首先,根據(jù)軌道動(dòng)力學(xué)理論計(jì)算衛(wèi)星雷達(dá)載荷對(duì)地覆蓋的條帶區(qū)域;然后,對(duì)不同重點(diǎn)區(qū)域設(shè)置不同優(yōu)先級(jí)別,通過(guò)多目標(biāo)遺傳算法生成基因和染色體,并根據(jù)條帶優(yōu)先級(jí)進(jìn)行變異優(yōu)化以求取最優(yōu)解;最后,根據(jù)其他約束生成衛(wèi)星成像任務(wù)調(diào)度計(jì)劃。任務(wù)規(guī)劃基于優(yōu)先級(jí)的遺傳算法如圖4所示。

圖4 任務(wù)規(guī)劃基于優(yōu)先級(jí)的遺傳算法

3.2 規(guī)劃算法詳細(xì)設(shè)計(jì)

3.2.1 編碼

衛(wèi)星元任務(wù)定義為相同雷達(dá)波位覆蓋的一段衛(wèi)星測(cè)繪條帶,圖3中越南部分區(qū)域是被衛(wèi)星測(cè)繪條帶覆蓋的。如圖5所示,可以把每個(gè)元任務(wù)作為一個(gè)基礎(chǔ)的規(guī)劃單元,也即一個(gè)基因,多個(gè)基因組合為一個(gè)單圈次規(guī)劃的染色體,其中,黃色基因?yàn)橹攸c(diǎn)測(cè)繪區(qū)域的元任務(wù),每個(gè)染色體包含重點(diǎn)區(qū)域元任務(wù)的數(shù)量決定當(dāng)前染色體的優(yōu)先級(jí),優(yōu)先級(jí)越高的染色體被選擇的概率越高。

圖5 染色體編碼設(shè)計(jì)

圖6 交叉優(yōu)先級(jí)流程

染色體定義為具有相同軌道圈次編號(hào)的衛(wèi)星任務(wù)基因的組合,也即一個(gè)軌道圈次內(nèi)滿足載荷約束要求的衛(wèi)星任務(wù)基因組合。衛(wèi)星任務(wù)規(guī)劃時(shí)間與任務(wù)基因數(shù)量、染色體數(shù)量成正比,因此,合理規(guī)劃衛(wèi)星任務(wù)基因數(shù)量以及合理規(guī)劃各個(gè)染色體執(zhí)行順序可以提高衛(wèi)星任務(wù)執(zhí)行效能。

基因?qū)傩悦枋鋈绫?所示。

表2 基因?qū)傩悦枋?/p>

染色體屬性描述如表3所示。

表3 染色體屬性描述

3.2.2 初始染色體生成

對(duì)步驟1產(chǎn)生的基因數(shù)組按照優(yōu)先級(jí)由高到低排序,生成第1個(gè)優(yōu)先級(jí)數(shù)組level_list?；騼?yōu)先級(jí)計(jì)算式為

GeneLevel=import_weight×ITN+time_weight×TTN+base_weight×BASE_N

(3)

式中:import_weight為重點(diǎn)區(qū)域任務(wù)時(shí)長(zhǎng)權(quán)值;ITN為重點(diǎn)區(qū)域任務(wù)總時(shí)長(zhǎng);time_weight為基因內(nèi)任務(wù)總時(shí)長(zhǎng)權(quán)值;TTN為基因任務(wù)總時(shí)長(zhǎng);base_weight為基因內(nèi)基線的權(quán)值;BASE_N為基因的基線的滿足度。基于level_list優(yōu)先級(jí)數(shù)組,生成其他9個(gè)newlevel_list,共計(jì)10個(gè)優(yōu)先級(jí)數(shù)據(jù),詳細(xì)算法如下。

Input:level_list //初始基因優(yōu)先級(jí)數(shù)組N//優(yōu)先級(jí)個(gè)數(shù)output: newlevel_list //基因優(yōu)先級(jí)數(shù)組1.for i=1 to 10 do2.for j=1 to 5 do3.k=random(ticks)//生成隨機(jī)數(shù)k4.m=random(ticks)//生成隨機(jī)數(shù)m5.newlevel=swap(level_listk,level_listm)//交換序號(hào)為k,m基因的優(yōu)先級(jí)6.end for7.newlevel_listi=newlevel//生成一個(gè)新的優(yōu)先級(jí)數(shù)組8.end for9.return newlevel_list//返回基因優(yōu)先級(jí)數(shù)組

在生成newlevel_list優(yōu)先級(jí)數(shù)組后,按照每組優(yōu)先級(jí)排列生成對(duì)應(yīng)初始染色體。詳細(xì)算法如下。

Input:level_list //基因優(yōu)先級(jí)數(shù)組N//優(yōu)先級(jí)個(gè)數(shù)output: chrom_list//返回染色體數(shù)組1.for i=1 to N do2.Sort(level_listi)//所有基因優(yōu)先級(jí)排序3.gene1=level_listi0//選取最高優(yōu)先級(jí)的基因?yàn)榈?個(gè)選擇的元任務(wù)4.chrom_listi.Add(gene1)//第1個(gè)基因加入到染色體i中5.While(TT_N

3.2.3 交叉

交叉是把初始優(yōu)先級(jí)染色體數(shù)組chrom_list中隨機(jī)選擇2個(gè)染色體的優(yōu)先級(jí)數(shù)組,采用部分一致交叉算法(PMX),交換2個(gè)優(yōu)先級(jí)數(shù)組中的部分片段,生成2個(gè)新的優(yōu)先級(jí)數(shù)組,然后根據(jù)新生成的優(yōu)先級(jí)數(shù)據(jù)采用類(lèi)似于第3.2.2節(jié)的方法生成新的染色體數(shù)組chromlist_intersect。具體步驟如下。

① 隨機(jī)選擇優(yōu)先級(jí)片段;

② 交換優(yōu)先級(jí)片段;

③ 子代優(yōu)先級(jí)合法化;

④ 子代染色體生成。

交叉優(yōu)先級(jí)流程如圖5所示。

3.2.4 變異

變異步驟首先在優(yōu)先級(jí)數(shù)組矩陣level_list中隨機(jī)選擇1個(gè)染色體的優(yōu)先級(jí)數(shù)組,隨機(jī)生成2個(gè)位置v1和v2,并交換優(yōu)先級(jí)數(shù)組的位置v1和v2的優(yōu)先級(jí)數(shù)值,如此重復(fù)2次,獲得2個(gè)子代染色體的優(yōu)先級(jí)數(shù)組,并采用類(lèi)似于第3.2.2節(jié)的方法生成染色體數(shù)組。

3.2.5 適值計(jì)算

合并第3.2.2節(jié)～第3.2.4節(jié)中生成的染色體數(shù)組,并計(jì)算各自的適值。計(jì)算方法為

evaluate=timval×timweight+importval×importweight

(4)

式中:evaluate為對(duì)應(yīng)染色體數(shù)組的適應(yīng)值;timval為染色體任務(wù)總計(jì)規(guī)劃時(shí)長(zhǎng);timweight為總計(jì)規(guī)劃時(shí)長(zhǎng)的權(quán)值;importval為重點(diǎn)區(qū)域染色體任務(wù)的時(shí)長(zhǎng);importweight為重點(diǎn)區(qū)域染色體任務(wù)時(shí)長(zhǎng)權(quán)值。經(jīng)過(guò)仿真實(shí)驗(yàn)m_timweight為0.7,m_importweight為0.3效果最好。

3.2.6 選擇(輪盤(pán)賭算法)

從父代染色體和子代染色體中根據(jù)適應(yīng)值大小排序,最多可以取得8個(gè)新一代染色體。新一代染色體數(shù)目和波位數(shù)量一致,這樣優(yōu)化更合理。具體方法如下:首先,計(jì)算各染色體的選擇概率pk和累計(jì)概率qk為

(5)

式中:evaluatek為第k個(gè)染色體的適應(yīng)值;第k個(gè)染色體的累計(jì)概率為第1個(gè)染色體的選擇概率到第k個(gè)染色體的選擇概率之和。這樣就得到k個(gè)染色體的累計(jì)概率數(shù)組,然后隨機(jī)生成[0,1]之間的隨機(jī)數(shù)rk,選擇符合條件qi-1

3.2.7 優(yōu)化結(jié)果輸出

重復(fù)第3.2.3節(jié)～第3.2.6節(jié)的步驟各100次,選擇適應(yīng)值最高的染色體為結(jié)果輸出,即為單圈次衛(wèi)星任務(wù)的規(guī)劃輸出結(jié)果。

4 仿真分析

對(duì)中國(guó)陸地區(qū)域內(nèi)范圍包括大陸、臺(tái)灣和海南島等相關(guān)島嶼進(jìn)行無(wú)差別的InSAR衛(wèi)星任務(wù)規(guī)劃,通過(guò)對(duì)比貪婪式優(yōu)化算法和基于優(yōu)先級(jí)的遺傳優(yōu)化算法的規(guī)劃效率來(lái)驗(yàn)證不同優(yōu)化算法之間的差異。設(shè)計(jì)任務(wù)規(guī)劃約束條件,如表4所示。設(shè)置單軌最大成像時(shí)長(zhǎng)為240 s,單軌雙星最大成像4次,垂直有效基線范圍200～800 m,沿航跡基線最大值600 m,單次最大成像時(shí)間為200 s。

表4 仿真約束條件

如果對(duì)中國(guó)陸地區(qū)域包括周邊島嶼的范圍內(nèi)進(jìn)行無(wú)縫隙的條帶覆蓋,采用基于優(yōu)先級(jí)的遺傳優(yōu)化算法,設(shè)置AB星的各自波位數(shù)量為12個(gè),總計(jì)條帶24個(gè),經(jīng)過(guò)規(guī)劃計(jì)算,相鄰開(kāi)機(jī)時(shí)間、單軌開(kāi)機(jī)總時(shí)長(zhǎng)、開(kāi)機(jī)次數(shù)都在約束范圍內(nèi),滿足仿真預(yù)設(shè)條件,如圖7所示。

圖7 約束情況檢查

本研究對(duì)比了2種優(yōu)化算法的覆蓋效能。采用基于優(yōu)先級(jí)的遺傳優(yōu)化算法的面積覆蓋率,如圖8所示。從圖8可以看出,總計(jì)規(guī)劃時(shí)間為266 d,面積覆蓋率為99.013%。采用基于貪婪優(yōu)化算法的面積覆蓋率,如圖9所示。從圖9可以看出,總計(jì)規(guī)劃時(shí)間為399 d,面積覆蓋率為99.013%。采用貪婪優(yōu)化算法比采用基于優(yōu)先級(jí)的遺傳優(yōu)化多花費(fèi)133 d,從曲線圖分析可知,在覆蓋率不足80%時(shí)兩種算法的效率差別不大,而剩下20%面積覆蓋的時(shí)間中兩種算法相差很大,這是因?yàn)樵谛l(wèi)星任務(wù)充足情況下對(duì)任務(wù)選取的效能是沒(méi)有大的差別的,而在任務(wù)不充足的情況下,遺傳優(yōu)化算法優(yōu)先選取高優(yōu)先級(jí)別侯選解的優(yōu)勢(shì)就體現(xiàn)出來(lái)了,通過(guò)遺傳優(yōu)化算法可以對(duì)單圈次內(nèi)的任務(wù)的篩選更合理,相比貪婪算法對(duì)任務(wù)調(diào)度重訪周期更短。

圖8 基于優(yōu)先級(jí)遺傳優(yōu)化算法規(guī)劃效能分析

圖9 貪婪優(yōu)化算法規(guī)劃效能分析

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

詳細(xì)介紹了InSAR雙星編隊(duì)任務(wù)規(guī)劃方法,充分分析了雙星編隊(duì)規(guī)劃、衛(wèi)星工作方式和負(fù)載約束的特點(diǎn),設(shè)計(jì)了一種基于優(yōu)先級(jí)的衛(wèi)星任務(wù)遺傳優(yōu)化算法,給出了基因和染色體在衛(wèi)星任務(wù)規(guī)劃中的具體實(shí)現(xiàn)方法,并對(duì)優(yōu)化算法進(jìn)行了仿真。與貪婪算法仿真結(jié)果對(duì)比表明,基于優(yōu)先級(jí)的遺傳算法適用于InSAR雙星編隊(duì)任務(wù)規(guī)劃優(yōu)化,本研究采用的算法模型為雙星編隊(duì)和多星星座等衛(wèi)星資源調(diào)度決策支持系統(tǒng)的設(shè)計(jì)提供了有效的參考。