基于貪心—線性規(guī)劃算法的敏捷衛(wèi)星觀測時段選取

孫 慧，李 暉，趙 曼，張 超，應(yīng) 文

(1.中國地質(zhì)大學(xué)(武漢) 計算機學(xué)院，湖北 武漢 430074； 2.中國電子科技集團公司航天信息應(yīng)用技術(shù)重點實驗室，河北 石家莊 050081； 3.中電科海洋信息技術(shù)研究院(北京)有限公司，北京 100041)

0 引言

21世紀是我國全面發(fā)展的時代，經(jīng)濟、科學(xué)等方面的發(fā)展突飛猛進，航天技術(shù)方面也取得了一定的成績。對地觀測是衛(wèi)星通過一定的傳感裝置對地球進行觀測，獲取地球表面信息并對其進行一定的處理過程。為了更有效地利用衛(wèi)星資源，須結(jié)合實際任務(wù)需求進行資源的優(yōu)化規(guī)劃，即衛(wèi)星任務(wù)規(guī)劃。衛(wèi)星技術(shù)不斷發(fā)展，具有三維調(diào)整能力的敏捷衛(wèi)星成為目前重要的對地觀測衛(wèi)星之一[1]，這使得衛(wèi)星的觀測較之前更為靈活和復(fù)雜，同時也意味著增加了任務(wù)規(guī)劃的復(fù)雜性。在敏捷衛(wèi)星任務(wù)規(guī)劃中，當觀測目標是點目標時，衛(wèi)星對目標的實際觀測時間比較短，不會占用整個可視窗口，因此，在敏捷衛(wèi)星的任務(wù)規(guī)劃過程中，還需要為每個點目標規(guī)劃出觀測時間段，即觀測時間片段的選取問題[2]。

大多數(shù)衛(wèi)星任務(wù)規(guī)劃問題都是優(yōu)化問題[3]，研究者采用各種優(yōu)化算法對衛(wèi)星任務(wù)規(guī)劃問題進行求解[4]。許多研究表明，這些優(yōu)化算法(例如差分演化算法)在解決衛(wèi)星任務(wù)規(guī)劃問題中凸顯了自身的優(yōu)勢，得到了廣泛應(yīng)用[5]。因此，本文以差分演化算法為主要求解算法。在衛(wèi)星任務(wù)規(guī)劃過程中，存在很多約束條件，由差分演化算法直接迭代產(chǎn)生個體并不一定滿足實際需求，需要對算法產(chǎn)生的個體進行沖突消解[6]，以滿足衛(wèi)星任務(wù)規(guī)劃中的各項約束條件，該過程稱為約束處理。本文在約束處理過程解決觀測時間片段選取的問題，提出按最早可開始時間的貪心算法(以下簡稱貪心算法[7])和基于線性規(guī)劃問題的求解方式(以下簡稱線性規(guī)劃算法[8])進行求解，并將二者相結(jié)合，尋找出較好的求解方法。

1 敏捷衛(wèi)星任務(wù)規(guī)劃基本原理

1.1 敏捷衛(wèi)星工作原理及對地觀測過程

攜帶有傳感器的敏捷衛(wèi)星在圍繞地球旋轉(zhuǎn)的過程中以一定的姿態(tài)(俯仰、測擺和偏航)通過影像獲取其星下點附近的地面信息，即衛(wèi)星對地觀測過程，如圖1所示。衛(wèi)星要獲取的地面信息，即衛(wèi)星的觀測任務(wù)[9]。衛(wèi)星對其星下點的觀測可視范圍，即可視時間窗口。

敏捷衛(wèi)星運行包括許多復(fù)雜環(huán)節(jié)，其中對目標任務(wù)的圖像采集是許多工作中十分重要的一個，其典型流程如下：首先明確觀測目標與需求，確定觀測任務(wù)的優(yōu)先級和需求屬性；對分級后形成的候選任務(wù)集進行任務(wù)規(guī)劃，根據(jù)需求安排衛(wèi)星資源；將確定好的規(guī)劃過程轉(zhuǎn)化為衛(wèi)星控制指令；衛(wèi)星根據(jù)程序指令執(zhí)行相應(yīng)的動作，完成成像工作[10]。

圖1 敏捷衛(wèi)星對地觀測過程

1.2 敏捷衛(wèi)星任務(wù)規(guī)劃原理及過程

敏捷衛(wèi)星任務(wù)規(guī)劃就是在衛(wèi)星成像之前，通過軌道方程計算，得出每個點目標的可視窗口(本文實驗通過STK仿真軟件計算[11])，然后通過各種算法，在滿足各種約束的情況下，確定每個點目標的成像時間和觀測順序，得出滿足需求的規(guī)劃方案[12]。本文研究的問題是對點目標成像時間片段的選取，是敏捷衛(wèi)星觀測任務(wù)規(guī)劃中的一部分，因此首先要實現(xiàn)對敏捷衛(wèi)星觀測任務(wù)的規(guī)劃[13]。

衛(wèi)星在對目標進行實際觀測的過程中有很多約束條件，例如由于敏捷衛(wèi)星對點目標的可視范圍較大，窗口時間比較長，距離相近的點目標的窗口會出現(xiàn)重疊的情況，存在任務(wù)沖突；由于衛(wèi)星工作需要指令控制，在一次觀測過程中涉及一系列的指令如圖2所示，因此在選片段的過程中要預(yù)留指令模板的時間，來避免指令模板沖突。此外，衛(wèi)星的整個規(guī)劃過程中還有許多約束要考慮，包括能量約束、單圈次觀測時長約束和固存約束等。很多約束條件十分復(fù)雜，涉及到多個學(xué)科領(lǐng)域的專業(yè)知識，要將這些約束條件全部考慮進來會大大增加規(guī)劃的難度。

圖2 衛(wèi)星觀測過程指令序列示意

本文所涉及的規(guī)劃只包含觀測部分，因此只考慮指令模板約束。指令模板沖突是指在2個連續(xù)觀測任務(wù)之間時間間隔小于2個觀測任務(wù)所需的指令模板時間之和，即在上一個任務(wù)的指令模板還未執(zhí)行結(jié)束，下一個任務(wù)的指令模板卻已開始。

1.3 敏捷衛(wèi)星任務(wù)規(guī)劃模型

一個觀測可見時間窗口對應(yīng)一個觀測元任務(wù)。對需求中的每個點目標計算出對應(yīng)的觀測元任務(wù)，得到元任務(wù)集。選用差分演化算法對元任務(wù)集進行規(guī)劃，并采取貪心—線性規(guī)劃算法為每個元任務(wù)選擇觀測時間片段，以盡可能多地安排點目標。根據(jù)以上目標，建立任務(wù)規(guī)劃模型的假設(shè)及約束變量的定義為：

③ 觀測元任務(wù)可視時間窗口的開始時間和結(jié)束時間分別用s，e表示，第j個元任務(wù)的窗口開始時間變量為sj，結(jié)束時間變量為ej；元任務(wù)的實際觀測開始時間和結(jié)束時間用sa，ea表示，第j個元任務(wù)的實際開始時間為saj，實際結(jié)束時間為eaj；

④ 定義觀測元任務(wù)決策變量x，如果元任務(wù)j能夠完成，則xj=1，2…，反之，xj=0；

⑤ 側(cè)擺所需時間用Tcs表示，單位為s；側(cè)擺角度用c表示；指令模板間隔計算公式為：Tcs=k*c+d，k，d為常數(shù)，可以根據(jù)實際情況進行配置。對于連續(xù)側(cè)擺10°與側(cè)擺30°的模板間隔為(k*10+d)+(k*30+d)，對于n個元任務(wù)，指令模板時間間隔集合表示為Tcs=Tcs1，Tcs2，…，Tcsn；

⑥ 整個規(guī)劃開始時間用TS表示，截止時間用TE表示。

基于以上的假設(shè)，建立相應(yīng)數(shù)學(xué)模型：

(1) 規(guī)劃目標

共有n個點目標要規(guī)劃，為每個點目標選取合適的成像片段，使完成元任務(wù)數(shù)最多，表示方式如式(1)所示：

(1)

(2) 考慮約束

① 所有任務(wù)的窗口開始和結(jié)束時間必須在整個規(guī)劃的時間段TS，TE之內(nèi)，表示方式如下：

對?j，1≤j≤n，滿足

TS≤sj≤TE，TS≤ej≤TE。

(2)

② 所有的觀測元任務(wù)的實際觀測片段必須在觀測可見時間窗口內(nèi)，表示方式為：

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

(3)

③ 相鄰2個觀測元任務(wù)ai、aj之間的實際觀測開始時間間隔不小于這2個元任務(wù)所需的指令模板時間之和，表示方式如下：

saj-eai≥Tcsi+Tcsj，?i，j1≤i，j≤n，

assume： saj>sai。

(4)

2 基于差分演化算法的觀測時間片段選取問題求解

基于差分演化算法在解決衛(wèi)星任務(wù)規(guī)劃問題上已有很多應(yīng)用，本文使用差分演化算法作為任務(wù)規(guī)劃的主要求解算法[15]。首先將衛(wèi)星任務(wù)數(shù)據(jù)對應(yīng)到染色體中，形成染色體種群；然后對每個染色體對應(yīng)的元任務(wù)進行約束處理(沖突消解)，使得該染色體對應(yīng)的解可行，本文在該過程中進行成像片段的選擇；再對每條染色體進行適應(yīng)值評價，并將當前代的最優(yōu)染色體保存下來，然后通過差分演化算法迭代產(chǎn)生下一代種群，重復(fù)上面的步驟，直到迭代結(jié)束，選出最優(yōu)的染色體，最后對最優(yōu)染色體進行解析，對應(yīng)到衛(wèi)星規(guī)劃問題中，得出每個點目標的成像片段，并得出規(guī)劃的點目標數(shù)[16]。算法規(guī)劃流程如圖3所示。

圖3 算法規(guī)化流程

2.1 基于最早可開始時間的貪心算法選擇成像片段

為了規(guī)劃完成的任務(wù)數(shù)最大，在選擇成像片段過程中，需要盡可能地避免模板上的沖突。本文采用的貪心算法就是通過調(diào)整觀測元任務(wù)所選取的成像片段來減少它對其他任務(wù)的影響[17]。

選擇成像片段的算法實現(xiàn)過程如圖4所示。首先將觀測元任務(wù)按照窗口時間先后進行排序，選取每個窗口的最后時間片段作為初始選擇；由于沒有其他任務(wù)的限制，可將第一個元任務(wù)的時間片段調(diào)整到可視窗口的開始位置；然后按順序獲取下一個元任務(wù)，判斷該任務(wù)與上一個任務(wù)是否有指令模板沖突，如果有則刪除該任務(wù)，如果沒有，則調(diào)整該元任務(wù)的觀測開始時間；繼續(xù)上面的步驟，獲取下一個元任務(wù)，選擇時間片段，直到所有的任務(wù)都遍歷完，則結(jié)束選成像片段過程。

圖4 基于最早可開始時間選擇成像片段的貪心算法流程

在上述流程中，主要通過判斷是否有指令模板沖突來調(diào)整觀測時間片段，具體過程如圖5所示。

圖5 調(diào)整成像片段示意

從圖5中可以看出，從左到右有4個點目標，分別記為目標1、目標2、目標3和目標4，這些目標的順序按其可視窗口的時間先后而定，假設(shè)目標1是當前一批目標中可視窗口最早的目標，點目標要求的觀測時長為t。對于每個觀測元任務(wù)，初始時均選取可視窗口的最后t時段作為選取的成像片段，如圖5中的灰色部分；該窗口開始時間是觀測的最晚開始時間，否則不能滿足觀測時長要求。然后根據(jù)約束，進行成像片段的調(diào)整，如圖5中的黑色部分，調(diào)整順序按窗口排序依次進行。對于當前批的第1個元任務(wù)，其時間片段的選取不會受前面元任務(wù)的影響，因此可將成像片段調(diào)整到窗口開始t時段。

然后對第2個元任務(wù)進行調(diào)整，處理方法是在第1個元任務(wù)選中的成像片段結(jié)束時間加上該任務(wù)的結(jié)束指令模板時間和第2個任務(wù)的開始指令模板時間，得到一個允許的最早開始時刻t1。t1時刻存在的區(qū)間有3種情況：① 晚于第2個任務(wù)的窗口開始時間但早于第2個任務(wù)初始選中片段的開始時間；② 早于第2個任務(wù)的窗口開始時間；③ 晚于第2個任務(wù)初始選中片段的開始時間。針對以上3種情況的調(diào)整情況是：將時間片段調(diào)整到t1時刻；將時間片段調(diào)整到窗口開始時刻；刪除任務(wù)。分別對應(yīng)圖5中的目標2、目標3和目標4。

2.2 基于線性規(guī)劃問題的求解方法選擇成像片段

線性規(guī)劃問題是在一系列線性約束條件下，對目標函數(shù)求最優(yōu)解的過程[18]。由此可將求解線性規(guī)劃問題的方法應(yīng)用到衛(wèi)星任務(wù)規(guī)劃中，以此來選出點目標合適的觀測時間片斷[19]。要運用線性規(guī)劃的解決算法，首先要對衛(wèi)星規(guī)劃問題采用線性規(guī)劃問題的建模方式進行模型的建立[20]，在本文的研究中，主要考慮的約束條件是時間窗口約束和指令模板約束，即元任務(wù)的實際觀測時間要在可視窗口的時間范圍內(nèi)，觀測元任務(wù)之間的時間安排要符合指令模板約束。假設(shè)每個點目標的觀測時間只需要5 s，以上約束關(guān)系可表示為：

(5)

式中，xi和xj分別表示第i和j個觀測元任務(wù)的實際開始觀測時間，xi≥0，xj≥0且j≠i；ti_start和ti_end分別表示第i個觀測元任務(wù)某個可視時間窗口的開始時間和結(jié)束時間；ΔT表示元任務(wù)i和元任務(wù)j之間指令模板間的時間間隔。

但是上述約束條件不能運用線性規(guī)劃的求解方式來求解，因為線性規(guī)劃問題中，線性約束條件之間是相與的關(guān)系，即所有的關(guān)系必須同時滿足[21]。而式(5)中存在相或的關(guān)系，因此，對衛(wèi)星規(guī)劃中的約束條件做如下改進，即

(6)

式中，xi≥0，xj≥0且xj>xi。

式(6)在式(5)的基礎(chǔ)上進行一定的修改，去掉表示指令模板約束的式子中的絕對值，并且要求xj>xi，即任務(wù)j的實際觀測開始時間早于任務(wù)i的實際觀測開始時間，這意味著假設(shè)存在某一個可行的規(guī)劃方案，任務(wù)j可以安排在任務(wù)i之后進行，但這個規(guī)劃結(jié)果會被線性規(guī)劃解決方法遺漏，可能會使線性規(guī)劃得到的解并不是衛(wèi)星規(guī)劃中的最優(yōu)解。雖然存在上述的不足，但是在單純形算法解決線性規(guī)劃問題的時候，如果問題有解，那么找到的一定是最優(yōu)解。針對這一特性，利用線性規(guī)劃的思想解決衛(wèi)星規(guī)劃問題還是有一定研究意義的。

在確定好約束條件后，需要構(gòu)造對應(yīng)的目標函數(shù)。衛(wèi)星規(guī)劃的優(yōu)化目標是一次規(guī)劃安排的點目標的個數(shù)，對應(yīng)到線性規(guī)劃問題中，就是當目標函數(shù)有解時對應(yīng)的x個數(shù)[22]。由此發(fā)現(xiàn)，實際目標函數(shù)是X={x1，x2，x3，......xn}，其中，X中xi的個數(shù)最多，即最多個點目標被規(guī)劃。但是，該目標函數(shù)無法用線性公式表示，不符合線性規(guī)劃要求。因此，構(gòu)造式(7)所示目標函數(shù)，當該目標函數(shù)有解，即實際目標函數(shù)達到最大值。

ymin=x1+x2+x3+x4+x5+…+xn，

(7)

式中，n為所有點目標的個數(shù)。

根據(jù)以上目標函數(shù)，當目標函數(shù)有解時，對應(yīng)x的解即可得到每個點目標的成像片段。

當構(gòu)造的目標函數(shù)無解時，意味著在該約束條件下，目標函數(shù)中涉及的x變量所對應(yīng)的點目標不能全部被安排[8]。需要刪除某些點目標，重構(gòu)目標函數(shù)。

本文引用沖突量概念作為刪除依據(jù)，計算每個點目標與其后目標的窗口沖突時長，沖突時間越長，沖突量越大。刪除沖突量最大的點目標，繼續(xù)上述規(guī)劃算法，求最優(yōu)解。重復(fù)上述過程，直到目標函數(shù)有解。

3 實驗測試與分析

算法的參數(shù)會一定程度上影響算法的計算效果。在實驗過程中，要根據(jù)不同的實驗數(shù)據(jù)規(guī)模來確定算法參數(shù)。本文測試過程中選取了不同數(shù)據(jù)量的測試實例對算法進行測試，選取了以下2類具有代表性的測試用例對測試結(jié)果進行分析。2個測試實例的元任務(wù)數(shù)及參數(shù)設(shè)置如表1所示。

表1 測試實例元任務(wù)個數(shù)及差分演化算法參數(shù)設(shè)置

測試實例觀測元任務(wù)數(shù)種群大小迭代次數(shù)變異概率拉伸因子測試實例118100500.80.7測試實例22873002000.80.7

3.1 規(guī)劃結(jié)果對比分析

本文中的實驗對基于最早可開始時間選擇觀測片段的貪心算法和基于線性規(guī)劃選擇時間片段的算法進行了組合測試，即在程序設(shè)計上，將這2個算法可以分別運用到2個地方：① 在差分演化算法迭代過程中，在每次迭代中運用上述之一的算法進行成像片段選取及指令模板約束處理；② 在迭代結(jié)束后對選擇出評價結(jié)果最好的染色體進行解析，計算出成像時間片段。

對2個算法進行組合，共有4種實驗方案：

① 基于最早可開始時間的貪心算法(G)+基于最早可開始時間的貪心算法(G)；

② 基于最早可開始時間的貪心算法(G)+基于線性規(guī)劃問題的求解算法(L)；

③ 基于線性規(guī)劃問題的求解算法(L)+基于最早可開始時間的貪心算法(G)；

④ 基于線性規(guī)劃問題的求解算法(L)+基于線性規(guī)劃問題的求解算法(L)；

在上述4項選擇中，“+”前面表示在差分演化算法迭代過程中運用，“+”面表示在最后解析最優(yōu)染色體過程中運用。

2組測試實例針對4種實驗方案的規(guī)劃結(jié)果(即安排的點目標個數(shù))對比如表2所示。

表2 結(jié)果對比表

測試實例組合方式差分演化算法結(jié)束后規(guī)劃元任務(wù)數(shù)解析后規(guī)劃元任務(wù)數(shù)任務(wù)完成率/%測試實例1G+G5527.777 8G+L5844.444 4L+G10316.666 7L+L101055.555 6測試實例2G+G20520571.428 6G+L20519266.899 0L+G26018965.853 7L+L25825889.895 5

根據(jù)以上測試結(jié)果可以看出，在第1組測試實例中，方案基于線性規(guī)劃問題的求解算法+基于線性規(guī)劃問題的求解算法(L+L)的規(guī)劃結(jié)果最好，完成任務(wù)率最高，其次是方案②、方案①和方案③。通過對比可以發(fā)現(xiàn)，在解析最優(yōu)染色體階段使用線性規(guī)劃的解決方法一般可以規(guī)劃較多的任務(wù)數(shù)，并且可以優(yōu)化貪心算法得出的結(jié)果；而用貪心算法解析線性規(guī)劃得出的最優(yōu)染色體則會使原本的結(jié)果變差。如果單純某一種算法，沒有優(yōu)化的效果。

在對測試實例2的大量實驗過程中，大部分實驗結(jié)果符合上述針對測試實例1的實驗結(jié)論，但也存在一些結(jié)果并非與上述結(jié)論完全一致，如表2中關(guān)于測試實例2的結(jié)果中，方案②在解析階段使用線性規(guī)劃求解問題的方法并沒有得出像測試實例1中的優(yōu)化效果，這是由于線性規(guī)劃處理階段存在隨機性，有時會有優(yōu)化效果，有時效果反而變差。因此，在實際規(guī)劃過程中，可以先采用貪心算法得出規(guī)劃結(jié)果，然后用線性規(guī)劃求解算法進行解析，如果結(jié)果變好，則用優(yōu)化后的規(guī)劃結(jié)果，如果沒有優(yōu)化，則用之前的規(guī)劃結(jié)果。因此，說明采用線性規(guī)劃的算法是一種可選的優(yōu)化方案，但得到的結(jié)果并不一定是最優(yōu)的，在實際應(yīng)用中，可以將線性規(guī)劃的結(jié)果作為一個參考項與貪心算法結(jié)果進行比較，擇優(yōu)選擇解決方法。

3.2 規(guī)劃時間及算法收斂性對比分析

與上述實驗方法相同，對2組測試實例在運行時間和算法收斂性方面進行分析總結(jié)。2組實例的時間對比情況如表3所示。

表3 各項運行時間對比 (s)

由表3可以看出，在整個規(guī)劃過程中，差分演化算法迭代會占用較多的時間，解析過程所占的時間比重十分??；線性規(guī)劃算法耗時比較長，貪心算法耗時比較短。因此，一般只在解析階段使用線性規(guī)劃對結(jié)果進行優(yōu)化，不會用到演化過程中，而貪心算法在演化過程中的效率比較高。

對2組測試結(jié)果進行對比分析可以得出，在數(shù)據(jù)量小的情況下，在差分演化算法過程中使用線性規(guī)劃算法的耗時還在一定的可以接受范圍內(nèi)，但當數(shù)據(jù)量即要規(guī)劃的點目標個數(shù)增大時，線性規(guī)劃的耗時對整個算法的運行效率影響很大，在實際工程應(yīng)用中是無法接受的，這也說明線性規(guī)劃使用在差分演化算法過程中是不適用的，只適合最后的優(yōu)化選項過程。

對測試實例2進行收斂性分析，分別用方案①(貪心算法+貪心算法)和方案④(線性規(guī)劃算法+線性規(guī)劃算法)的規(guī)劃組合進行實驗，2種不同的策略對應(yīng)差分演化算法的收斂情況如圖6所示。

圖6 2種策略收斂情況對比

由圖6可以看出，貪心算法在100代左右收斂，而此時線性規(guī)劃還在優(yōu)化過程中，直到160代左右收斂，由此可見，二者收斂速度都較快，貪心算法比線性規(guī)劃算法使差分演化算法收斂相對更快些。

3.3 實驗結(jié)論

結(jié)合上述對規(guī)劃結(jié)果、運行時間和算法收斂速度3個方面的對比測試可以發(fā)現(xiàn)，在選擇成像片段的過程中，如果采用線性規(guī)劃的解決方法則可以較多地規(guī)劃任務(wù)數(shù)，但是線性規(guī)劃的耗時十分長，是貪心算法的10倍以上，會影響整個程序的性能。相比之下，貪心算法收斂速度快并且耗時少；在選擇成像片段的過程中，為了能夠盡可能多地規(guī)劃任務(wù)并且使耗時在可接受的范圍內(nèi)，可以將耗時少的貪心算法運用到差分演化迭代過程中來選擇最優(yōu)染色體，在得出一個結(jié)果后，選擇線性規(guī)劃方法嘗試優(yōu)化，如果結(jié)果比原來的好，則采用該方法選片段，否則，維持原來已有的結(jié)果。

4 結(jié)束語

本文提出基于貪心—線性規(guī)劃相結(jié)合的方式進行敏捷衛(wèi)星任務(wù)規(guī)劃過程中觀察時間片段的選取。在差分演化算法迭代過程中采用貪心算法可以比較快速地得出點目標的成像片段，在解析最優(yōu)染色體的過程中采用線性規(guī)劃算法多數(shù)情況下可以優(yōu)化規(guī)劃結(jié)果，安排更多的點目標。該方法提高了整個衛(wèi)星規(guī)劃的效果，更好地利用衛(wèi)星資源，有著很好的研究價值和應(yīng)用前景。