基于并行架構(gòu)的敏捷衛(wèi)星任務調(diào)度優(yōu)化算法

張 超,李艷斌,陳金勇

(1. 中國電子科技集團公司航天信息應用技術重點實驗室,石家莊 050081;2. 中國電子科技集團公司第五十四研究所,石家莊 050081)

0 引 言

在衛(wèi)星遙感任務調(diào)度技術中,實際上要解決的是約束優(yōu)化和多目標優(yōu)化問題[1]?，F(xiàn)有研究大多采用最優(yōu)化算法、基于規(guī)則的啟發(fā)式算法和智能優(yōu)化算法求解。許多研究表明，最優(yōu)化算法只能解決小規(guī)模的單星成像任務規(guī)劃問題?；谝?guī)則的啟發(fā)式算法具有簡單、直觀、便于實現(xiàn)、運算效率高等優(yōu)點，但解的質(zhì)量難以保證。禁忌搜索、模擬退火、粒子群算法、差分演化算法等智能優(yōu)化算法在求解組合優(yōu)化問題和多目標優(yōu)化問題方面顯示了較強的能力，近年來在成像衛(wèi)星任務規(guī)劃領域得到了廣泛的應用。Bonissone將領域知識引入進化算法，通過顯性知識和隱性知識，處理衛(wèi)星成像過程中的靜態(tài)和動態(tài)約束，解決了一個包含25個衛(wèi)星的星座的任務規(guī)劃問題[2]。韓偉設計了離散粒子群的位置變化公式利用粒子群算法求解向多對地觀測衛(wèi)星任務規(guī)劃問題[3]。

敏捷衛(wèi)星的發(fā)展使衛(wèi)星對地面目標的觀測時間范圍更大，觀測角度更加靈活多變。敏捷衛(wèi)星在分散目標快速響應、地面目標三維信息獲取、兼顧高分辨率成像與大范圍覆蓋等需求中應用廣泛。敏捷衛(wèi)星的任務規(guī)劃調(diào)度問題國外研究主要集中在法國歐空局的Lematre 和 Panwadee、美國 NASA 噴氣推進實驗室(JPL)等。Lematre[4]針對法國Pleiades敏捷衛(wèi)星的日常任務調(diào)度問題，比較了貪婪、動態(tài)規(guī)劃、約束規(guī)劃以及局部搜索等四種算法，其研究結(jié)果顯示，局部搜索算法在考慮所有約束的情況下性能最好。Mancel[5]在 Lematre的基礎上針對法國的 Pleiades 衛(wèi)星建立了整數(shù)規(guī)劃模型，并采用列生成算法進行求解。在國內(nèi)，李玉慶[6]針對三軸穩(wěn)定衛(wèi)星點目標任務規(guī)劃調(diào)度問題提出了一種基于模擬退火與遺傳算法相結(jié)合的混合遺傳算法。余婧采用序列二次規(guī)劃方法求解敏捷衛(wèi)星同軌多條帶拼幅成像問題[7]。

1 敏捷衛(wèi)星任務規(guī)劃調(diào)度問題分析

敏捷衛(wèi)星能夠以俯仰、滾動以及偏航靈活的姿態(tài)機動調(diào)整能力獲得更大范圍、更加高效的對地觀測能力，典型的工作模式有：多條帶拼接模式，立體成像模式和多點目標快速成像工作模式。其中：

多條帶拼接模式是指敏捷衛(wèi)星將區(qū)域目標分解為多個可觀測的條帶，利用敏捷衛(wèi)星在俯仰、側(cè)擺的二維姿態(tài)快速機動實現(xiàn)推掃成像。敏捷衛(wèi)星繼續(xù)飛行立即進行俯仰方向的反向機動，同時通過側(cè)擺將衛(wèi)星指向平移約一個幅寬的距離，使得后一次推掃的起始條帶與前一次推掃的起始條帶相鄰[8]。在任務調(diào)度時需要通過合理確定它們的拍攝順序，不同的拍攝順序?qū)笮l(wèi)星進行不同的姿態(tài)調(diào)整和變換過程。立體成像模式是指對同一地區(qū)實現(xiàn)不同角度的觀測以形成立體像對，從而得出該地區(qū)的三維成像信息。此種工作模式主要是利用衛(wèi)星俯仰軸的姿態(tài)機動來實現(xiàn)同軌2次或3次對同一地物不同角度觀測。根據(jù)攝影測量原理[9]，當基高比接近1時，對于圖像處理立體效果來說較好，因此可以選取在±25°時進行立體成像，以便得到較好的立體成像效果。在任務調(diào)度時需要通過合理確定衛(wèi)星對目標2次或3次觀測時的姿態(tài)角度，以及后續(xù)目標的沖突關系。多點目標快速成像模式是利用敏捷衛(wèi)星的快速姿態(tài)指向能力，實現(xiàn)對分散的目標快速成像。這種成像模式主要利用衛(wèi)星側(cè)擺加俯仰的快速姿態(tài)機動能力實現(xiàn)同軌內(nèi)距離沿軌跡方向較近的多個點目標成像。在任務調(diào)度時需要通過合理確定每個的目標成像開始時間、姿態(tài)角度實現(xiàn)近距離多個目標的成像沖突消解。

敏捷衛(wèi)星特有的姿態(tài)靈活機動能力使得衛(wèi)星對點目標可視時間窗口的變?yōu)榱艘粋€長時間窗口。點目標觀測需要持續(xù)一段很短的時間，實際觀測片段可以在觀測可見時間窗口內(nèi)自由滑動。因此在一個長時間窗口內(nèi)，對點目標成像的開始時間決定了成像時采用的俯仰角度，也就決定了衛(wèi)星成像質(zhì)量，如圖1所示。同時，敏捷衛(wèi)星的任務調(diào)度過程是一個調(diào)度-選擇相結(jié)合過程，如圖2所示。首先需要調(diào)度衛(wèi)星-目標任務匹配關系；然后備選目標任務還需要在可訪問時間窗口中選擇成像的時刻。

圖1 敏捷衛(wèi)星成像時間影響成像質(zhì)量示意圖

圖2 選擇點目標實際的成像片段示意圖

敏捷衛(wèi)星任務規(guī)劃問題求解面臨著很多的難點，復雜多樣的觀測任務模式、更加靈活的姿態(tài)機動能力、更長的可觀測時間窗口導致了解空間增大，多個臨近目標觀測窗口重疊，且臨近目標耦合度高，觀測順序不再固定。同時不同觀測開始時間對應不同觀測姿態(tài)角度，進而影響成像質(zhì)量和任務間衛(wèi)星姿態(tài)轉(zhuǎn)換時間，這些都給敏捷衛(wèi)星成像任務的調(diào)度及觀測時間的確定帶來了困難。

2 敏捷衛(wèi)星任務規(guī)劃調(diào)度模型

敏捷衛(wèi)星任務規(guī)劃調(diào)度建模十分復雜，文獻[10-11]只考慮任務安排數(shù)量和優(yōu)先級最大化作為規(guī)劃目標建立約束滿足模型，文獻[12]將云層遮擋最小作為規(guī)劃目標建立了敏捷衛(wèi)星任務規(guī)劃數(shù)學模型，上述文獻都沒有將任務安排數(shù)、任務優(yōu)先級和任務質(zhì)量統(tǒng)一考慮。在成像時衛(wèi)星離地面目標越近、采用的觀測角度越小則成像的地面分辨率越高。敏捷衛(wèi)星對目標的成像時間決定了成像姿態(tài)角度，進而決定了成像質(zhì)量，這是一種具有時間依賴性的成像質(zhì)量。這與并行機加工調(diào)度問題“提早-延期”懲罰相似[13]，衛(wèi)星在最佳觀測角度成像獲得的圖像質(zhì)量最高，而提早或延期成像獲得的圖像質(zhì)量則會降低。因此，敏捷衛(wèi)星任務規(guī)劃調(diào)度模型中將成像質(zhì)量最好轉(zhuǎn)化為成像觀測角度最小，并將其引入規(guī)劃目標中，建立了多目標組合優(yōu)化模型。本文只考慮與所研究問題直接相關的約束條件，主要包括數(shù)傳固存約束、數(shù)傳模式、指令模板、工作時間(分為觀測、接收兩個部分)、能源約束和姿態(tài)轉(zhuǎn)換，對相關約束與沖突定義如表1所示。

表1 約束表

① 模型假設及約束變量定義

建立任務調(diào)度模型的假設及約束變量的定義：

1)調(diào)度開始時間為TS，調(diào)度截至時間為TE；

2)假設有n個要完成的任務，記為A={a1,a2,…,an}，每個任務的優(yōu)先級為P={p1,p2,…,pn}，成像角度為IA={ia1,ia2,…,ian}；

3)定義觀測元任務決策變量xj，如果元任務能夠完成，則xj=1，反之，xj=0；

4)第j個觀測元任務的開始時間變量記為sj，結(jié)束時間變量為ej，第j個元任務的實際開始時間為saj，實際結(jié)束時間為eaj；

7)定義一個任務數(shù)傳模式變量Pj，如果任務做記錄模式，則Pj=1，如果任務做實傳模式，則Pj=0；

8)定義接收任務決策變量ki，如果接收元任務能夠執(zhí)行接收，則ki=1，反之，ki=0；

9)第i個接收任務的開始時間變量記為swi，結(jié)束時間變量為ewi；

10)單圈次最大觀測時長為To，單圈次最大接收時長為Tr；

11)衛(wèi)星最大固存為M，單位時間的觀測數(shù)據(jù)占用固存為mj，假設在第j個記錄文件放入固存之前固存占用量為Mj；

12)假設衛(wèi)星電池初始電量為Eg。

② 模型表示

規(guī)劃目標：

(1)

(2)

(3)

考慮約束：

Ts≤sj≤TEandTs≤ej≤TE, 1≤j≤n

(4)

對于?j，滿足saj≥sj且eaj≤ej

(5)

對于?j，如果Pj=0，則?i，使得

saj≥Si，1≤j≤n，1≤i≤m

(6)

對于?j，如果Pj=0，則?i，使得

eaj≤Ei，1≤j≤n，1≤i≤m

(7)

(8)

其中：jh、jb分別表示觀測元任務序列中前后兩個相鄰的任務序號。

Mj+xj(ej-sj)mj≤M

(9)

(10)

(11)

模型說明：

式(1)表示完成任務的優(yōu)先級之和最大；式(2)表示完成元任務數(shù)最多，即完成目標數(shù)量最多；式(3)表示完成任務的成像角度之和最小，即成像質(zhì)量懲罰函數(shù)；式(4)表示所有任務的開始和結(jié)束時間必須在規(guī)定的時間段[Ts,TE]之內(nèi)；式(5)表示所有的觀測元任務的實際觀測片段必須在觀測可見時間窗口內(nèi)； 式(6)表示當aj做實傳模式時如果任務在時間窗口Wi內(nèi)執(zhí)行，那么任務的開始時間必須在相應的時間窗口的開始時間之后；式(7)表示當aj做實傳模式時任務的結(jié)束時間必須在相應的時間窗口的結(jié)束時間之前。式(4)、(5)限定做實傳的任務必須在對應的時間窗口之內(nèi)完成；式(8)表示后一個任務的開始時刻和前一個任務的結(jié)束時刻之間的間隔時間必須不小于它們之間角度姿態(tài)調(diào)整需要的時間；式(9)表示固存占用量加上當前記錄文件固存占用量必須不超過最大固存；式(10)表示單圈次中觀測元任務總的時長必須不超過單圈次最大觀測時長，其中s、e表示單圈次中第一個和最后一個任務的序號；式(11)表示單圈次中接收任務總的時長必須不超過單圈次最大接收時長。

3 敏捷衛(wèi)星任務調(diào)度優(yōu)化算法

① 敏捷衛(wèi)星任務編碼設計

染色體結(jié)構(gòu)由觀測目標的編碼和接收元任務的編碼拼接得到，根據(jù)任務規(guī)劃需求采用整數(shù)編碼的方式。傳統(tǒng)衛(wèi)星一個觀測目標的基因位取值只能是0到1兩種，0代表對應的該點目標沒有被選中，1代表該點目標會被安排進行觀測成像，所有觀測目標和接收元任務的數(shù)量之和即為染色體的長度。然而，敏捷衛(wèi)星根據(jù)不同任務觀測模式基因位取值范圍不同，對于觀測元任務數(shù)量不同。對于多點目標連續(xù)成像模式，每個點目標可以被觀測N次；對于立體成像模式，每個目標至少被觀測2次；對于寬幅目標，根據(jù)區(qū)域條帶分解得到多個觀測條帶，即一個觀測目標對應多個觀測元任務，相關元任務必須一起安排；因此，敏捷衛(wèi)星觀測元任務對應的基因位取值范圍為0到N；敏捷衛(wèi)星接收元任務基因位的取值范圍為0、1或2，0代表對應的接收元任務沒有被選中，1代表對應的接收元任務被選中并且做回放模式，2代表對應的接收元任務被選中且做實傳模式。

② 基于排序變異的差分演化算法

DE算法的核心算子是差分變異算子。一般情況下，變異算子是從當前種群中隨機選擇。在自然界中，優(yōu)良物種總是包含好的基因信息，因此，它們有更多的機會被用來指導其他物種進化。受這種現(xiàn)象啟發(fā)，雙親個體被選中為變異算子的概率是根據(jù)它們在當前種群中的評價值排名來決定的，評價值較高的個體將獲得更大的差分變異概率，其中個體權(quán)重的設置使用二次方模型(quadratic model)。采用這種基于排序的變異方式，將種群個體進行適應度排序后，進行迭代更新，能夠維持局部搜索和全局搜索的平衡。

weights[i]=pow((double)(i+0)/S_size,2.0)

(12)

③ 遺傳模擬退火混合算法

本文針對模擬退火算法解的質(zhì)量與求解時間長之間的矛盾，將遺傳算法與模擬退火算法結(jié)合起來，提出了一種改進的遺傳模擬退火算法。改進遺傳模擬退火算法的基本思想是：與傳統(tǒng)的模擬退火算法總體運行過程相類似，從一組隨機產(chǎn)生的初始解(初始種群)開始全局最優(yōu)解的搜索過程，通過選擇、交叉、變異等遺傳操作來產(chǎn)生候選解，然后對候選解采用Metropolis準則判斷是否接受其作為下一代種群中的個體，執(zhí)行退溫操作。這個運行過程反復迭代進行，直到滿足終止條件。

④ 基于相似度和聚集度的粒子群算法

根據(jù)標準PSO算法的性能分析，隨著算法迭代運行，粒子變得越來越相似，算法缺少多樣性，從而影響算法的全局搜索能力。改進的粒子群算法的基本思想是：根據(jù)每條染色體的基因位與最優(yōu)染色體進行比較，計算出每條染色體與最優(yōu)染色體的相似度，然后根據(jù)相似度計算出每一代種群的聚集度。隨著迭代運行，標準PSO算法會越來越聚集在一起，因為粒子最終都向最優(yōu)點粒子靠近。改進的粒子群通過相似度和聚集度，在染色體變異過程中，當種群聚集度大的時候，增加染色體的變異概率，從而使種群的多樣性增加，有利于尋找到更優(yōu)的結(jié)果。

圖3 約束處理流程

⑤ 約束處理

敏捷衛(wèi)星任務調(diào)度優(yōu)化是一個帶約束的優(yōu)化問題，需要考慮諸多約束。算法運行過程中產(chǎn)生的邏輯規(guī)劃對象很有可能是不合法的，必須要對這樣的邏輯規(guī)劃對象進行處理。算法在產(chǎn)生邏輯規(guī)劃對象經(jīng)約束處理模塊，對組合元任務集進行處理，得到新的滿足約束的組合元任務集。然后通過編碼，生成對應的修正的邏輯規(guī)劃對象，即規(guī)劃結(jié)果。約束處理模塊依次按照以下順序進行約束處理：觀測時間沖突約束、數(shù)傳模式約束、指令模板約束、工作時間約束、文件下傳約束、能源約束。

⑥ 仿真測試結(jié)果

針對差分演化算法、模擬退火算法以及粒子群算法三種算法分別提出了改進算法。為了測試改進算法的效果，選取了5批工程數(shù)據(jù)，每批數(shù)據(jù)包含300個觀測元任務，分別從綜合評價值(完成任務數(shù)、優(yōu)先級之和、俯仰角之和)以及耗時比較改進前后的算法效果。改進后的差分演化算法是使用了rankDE策略的算法，改進后的模擬退火算法是遺傳模擬退火算法，改進后的粒子群算法是通過引入相似度和聚集度的概念來增大變異概率的算法。

圖4 改進前后算法的綜合評價值

圖5 改進前后算法的耗時

通過以上圖表數(shù)據(jù)的展示，可以看出：使用rankDE策略的差分演化算法，其規(guī)劃結(jié)果及耗時與改進前的算法規(guī)劃結(jié)果及耗時比較接近，改進效果并不明顯；遺傳模擬退火算法的改進效果比較明顯，改進后的規(guī)劃結(jié)果明顯較優(yōu)，雖然耗時相對較多，但算法改進后的耗時與差分演化算法接近，屬于可接受范圍；引入相似度和聚集度使變異概率增大之后的粒子群算法，其規(guī)劃結(jié)果比未改進的粒子群算法的規(guī)劃結(jié)果較優(yōu)，雖然其耗時也相應的增加了，但綜合其他算法來看，其耗時仍少于差分演化算法和模擬退火算法，說明粒子群算法的改進效果較明顯。

4 并行算法研究

① 并行算法模型

由于智能優(yōu)化算法的內(nèi)在并行性，其并行處理方式是很自然的解決途徑。本文中，衛(wèi)星任務規(guī)劃算法在并行模式上采用全局型和獨立型。為了應用并行計算，必須把算法分解成相互獨立的若干問題[14]。

全局型—主從式模型(mast-slave model)首先統(tǒng)一三種智能優(yōu)化算法的編碼格式，然后在主線程中進行搜索，然后將算法的每一次迭代中得到的解分配到對應的處理器獨立進行的編碼解析、約束檢查、評價和計算解的適應值等操作，然后將其返回給調(diào)用線程。主從式模型示意圖如圖6。

圖6 主從式模型的并行演化計算架構(gòu)圖

獨立型—孤島模型(island model)進行并行處理，多個解用“種群”表示，將“種群”分為若干個“子種群”分配給對應的處理器，每個處理器不僅獨立計算適應度，而且獨立進行選擇、重組交叉和變異操作。每次迭代完成以后，選擇“種群”中所有解的評價值中最高的解作為當前最優(yōu)解。判斷這個解是否滿足終止條件的要求，滿足則退出，不滿足則繼續(xù)迭代，如圖7所示。

圖7 孤島模型的并行演化計算架構(gòu)圖

② 并行算法測試

并行測試結(jié)果很大程度取決于并行環(huán)境，三種運行模式硬件采用四核Core(TM) i3-4150 3.5 Ghz、內(nèi)存4 G。針對同一批測試數(shù)據(jù)，對主從式并行和孤島式并行進行測試，分別采用三種算法運行10次求平均值，利用平均耗時與未加速的算法耗時進行對比，具體的算法耗時見表3，成像任務規(guī)劃性能加速比如圖8。

在沒有并行運算的情況下，三種算法運行耗時均較多；在采用并行框架后，三種算法運行時間均有明顯下降；在主從式并行模型下，加速比分別為模擬退火算法1.614、差分演化算法1.911、粒子群算法1.990；在孤島式并行模型下加速比分別為差分演化算法1.960、模擬退火算法2.254、粒子群算法2.478。綜合比較兩種模型，加速效果都很明顯，但就兩種模型來看，孤島式并行模型加速效果更明顯，三種算法的加速效果都高于主從式并行模型的加速比。

表2 三種算法并行模型運行時間表

圖8 智能優(yōu)化算法并行加速比圖

5 結(jié) 語

本文針對敏捷衛(wèi)星任務規(guī)劃調(diào)度問題的特點，構(gòu)建了基于成像質(zhì)量懲罰系數(shù)的敏捷衛(wèi)星任務規(guī)劃組合優(yōu)化模型；并對常見智能優(yōu)化算法(差分演化、粒子群和模擬退火三種算法)進行改進實現(xiàn)和測試評價；在此基礎上采用全局-主從式模型和獨立-孤島模型分別實現(xiàn)了三種算法單機多核并行計算技術。實驗結(jié)果驗證了提出的算法是可行的和有效的。

[1] 徐雪仁, 宮鵬, 黃學智,等. 資源衛(wèi)星(可見光)遙感數(shù)據(jù)獲取任務調(diào)度優(yōu)化算法研究[J]. 遙感學報, 2007, 11(1):109-114.

[2] Bonissone P P, Subbu R, Eklund N, et al. Evolutionary algorithms+domain knowledge=real-world evolutionary computation[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3):256-280.

[3] 韓 偉,張學慶. 一種基于離散粒子群的多星任務規(guī)劃算法[J].無線電工程,2015,45(1):1-4.

[5] Mancel C, Lopez P. Complex optimization problems in space systems[C].13Th International Conference on Automated Planning & Scheduling (ICAPS’03). 2003.

[6] 李玉慶, 徐敏強, 王日新. 三軸穩(wěn)定衛(wèi)星點目標觀測任務優(yōu)化調(diào)度技術[J].吉林大學學報:工學版, 2008, 38(6):1447-1451.

[7] 余婧, 喜進軍, 于龍江,等. 敏捷衛(wèi)星同軌多條帶拼幅成像模式研究[J]. 航天器工程, 2015, 24(2):27-34.

[8] 張新偉, 戴君, 劉付強. 敏捷遙感衛(wèi)星工作模式研究[J]. 航天器工程, 2011, 20(4):32-38.

[9] 王任享．三線陣CCD影像衛(wèi)星攝影測量原理[M].北京：測繪出版社，2006:1-23.

[10] 孫凱，邢立寧，陳英武等.基于分解優(yōu)化策略的多敏捷衛(wèi)星聯(lián)合對地觀測調(diào)度[J].計算機集成制造系統(tǒng), 2013, 19(1):127-136.

[11] 郝會成，姜維，李一軍.基于混合遺傳算法的敏捷衛(wèi)星任務規(guī)劃求解 [J].科學技術與工程. 2013, 13(17):4972-4978.

[12] 何磊, 劉曉路, 陳英武, 邢立寧. 面向敏捷衛(wèi)星任務規(guī)劃的云層建模及處理方法[J]. 系統(tǒng)工程與電子技術, 2016, 38(4): 852-858.

[13] 陳成. 時間依賴調(diào)度方法及在敏捷衛(wèi)星任務規(guī)劃中的應用研究[D]. 國防科學技術大學. 2014.

[14] 付鑫, 張峰, 馮占林,等. 基于并行計算的混沌遺傳算法對反導預警雷達部署優(yōu)化研究[J]. 中國電子科學研究院學報, 2016(3):276-282.