趙萍，陳志明

南京航空航天大學(xué) 航天學(xué)院, 南京 210016

應(yīng)用于衛(wèi)星自主任務(wù)調(diào)度的改進(jìn)遺傳算法

趙萍，陳志明﹡

南京航空航天大學(xué) 航天學(xué)院, 南京 210016

針對具有側(cè)擺能力的對地觀測衛(wèi)星的自主任務(wù)調(diào)度問題，對衛(wèi)星自主任務(wù)調(diào)度問題和約束條件進(jìn)行了描述，針對衛(wèi)星自主任務(wù)調(diào)度NP-hard的特點，構(gòu)建了基于目標(biāo)收益及多約束衛(wèi)星任務(wù)調(diào)度模型。設(shè)計了一種改進(jìn)的遺傳算法，從遺傳操作的各個部分進(jìn)行算法優(yōu)化。首先將小區(qū)間法應(yīng)用于初始種群生成，保證了種群的多樣性，并且交叉和變異算子均引入自適應(yīng)概率；同時采用兩代競爭技術(shù)來避免“早熟”現(xiàn)象，提高算法的效率和魯棒性。算法還采用最優(yōu)保留策略用來保存進(jìn)化中的最優(yōu)解，使得算法收斂于全局最優(yōu)。對局部多沖突觀測任務(wù)應(yīng)用該改進(jìn)遺傳算法，并針對區(qū)域密集目標(biāo)的觀測問題設(shè)計了仿真試驗，與傳統(tǒng)模擬退火算法及免疫蟻群遺傳混合算法進(jìn)行了比較，驗證了該算法的有效性和收斂效果。

對地觀測衛(wèi)星；衛(wèi)星側(cè)擺角；自主任務(wù)調(diào)度；建模；改進(jìn)遺傳算法；自適應(yīng)概率

觀測衛(wèi)星是利用星載傳感器，根據(jù)用戶的需求對地面目標(biāo)成像，具有觀測效果好、覆蓋區(qū)域廣、持續(xù)時間長等特點，已經(jīng)在環(huán)境監(jiān)測，災(zāi)害預(yù)報以及軍事作戰(zhàn)等領(lǐng)域得到了應(yīng)用[1]。

對地觀測衛(wèi)星調(diào)度問題的輸入是來自用戶的任務(wù)要求。每個任務(wù)有自己特定的有效時間窗口，在這些時間段以外，命令就沒有意義了。但是由于各種資源、時間等約束，不一定所有的任務(wù)都能夠被執(zhí)行。所以，衛(wèi)星在滿足各種約束的情況下，應(yīng)盡可能多完成請求的任務(wù)[2]。從衛(wèi)星接收的所有觀測任務(wù)請求中，根據(jù)星上資源以及衛(wèi)星對任務(wù)的時間窗口約束，利用算法快速選擇待觀測的任務(wù)序列，完成對衛(wèi)星觀測任務(wù)的調(diào)度。所以，對地觀測衛(wèi)星調(diào)度的輸出是無沖突待觀測的任務(wù)序列。

隨著衛(wèi)星數(shù)量和觀測任務(wù)數(shù)量的增多以及衛(wèi)星機(jī)動能力的增強(qiáng)，任務(wù)調(diào)度問題的規(guī)模呈指數(shù)的增長。觀測衛(wèi)星的調(diào)度問題已經(jīng)被證明是NP-hard問題，問題的指數(shù)爆炸特征明顯，很難求解[3]。觀測衛(wèi)星的任務(wù)調(diào)度問題涉及許多非線性約束，求解目標(biāo)不唯一，所以并不存在適用于所有問題的算法[4]?，F(xiàn)有的研究一般將衛(wèi)星的任務(wù)調(diào)度問題轉(zhuǎn)化成組合優(yōu)化問題進(jìn)行求解。

文獻(xiàn)[3]針對敏捷衛(wèi)星提出的約束模型，比較了約束調(diào)度、動態(tài)調(diào)度以及局部搜索等求解算法。文獻(xiàn)[5]構(gòu)建了敏捷衛(wèi)星任務(wù)調(diào)度的數(shù)學(xué)模型，用模擬退火算法和遺傳算法相結(jié)合的混合遺傳算法進(jìn)行求解。文獻(xiàn)[6]針對多星對區(qū)域目標(biāo)的觀測調(diào)度問題設(shè)計了貪婪隨機(jī)變鄰域搜索算法、禁忌搜索和模擬退火算法，提高了算法的求解效率。文獻(xiàn)[7]設(shè)計了一種新的遺傳算法并將該優(yōu)化算法應(yīng)用于實際的衛(wèi)星任務(wù)調(diào)度問題模擬。偏置隨機(jī)密鑰遺傳算法[8](BRKGA)可以有效地解決組合優(yōu)化問題，文獻(xiàn)[8]提出了一種混合解碼的方法，并對敏捷地球觀測衛(wèi)星進(jìn)行了試驗。文獻(xiàn)[9]提出了一種基于指標(biāo)的多目標(biāo)局部搜索算法(IBMOLS)解決多目標(biāo)優(yōu)化問題，并且將IBMOLS的結(jié)果與偏置隨機(jī)密鑰遺傳算法的結(jié)果進(jìn)行比較。也有學(xué)者對各種算法性能進(jìn)行了比較分析，文獻(xiàn)[10]在衛(wèi)星任務(wù)調(diào)度中比較了模擬退火算法、遺傳算法、爬山算法等性能。

從現(xiàn)有的研究可以看出，智能優(yōu)化算法在求解衛(wèi)星任務(wù)調(diào)度問題上有很大的優(yōu)勢。同時，現(xiàn)有的研究中，任務(wù)的調(diào)度模型都較為簡單，沒有考慮或簡化了衛(wèi)星側(cè)擺角、轉(zhuǎn)換時間等約束；很少有針對密集任務(wù)的觀測調(diào)度算法[11]。針對這些問題，本文提出了快速計算觀測衛(wèi)星側(cè)擺角的方法，對衛(wèi)星自主任務(wù)調(diào)度問題構(gòu)建了基于目標(biāo)收益及多約束的任務(wù)調(diào)度模型，最后設(shè)計了一種改進(jìn)的自適應(yīng)遺傳算法應(yīng)用于衛(wèi)星局部沖突觀測任務(wù)的調(diào)度。并針對區(qū)域密集目標(biāo)的觀測問題設(shè)計了仿真試驗，將試驗結(jié)果與傳統(tǒng)模擬退火算法及其他改進(jìn)遺傳算法進(jìn)行了比較，驗證了算法的有效性。

1 衛(wèi)星對地觀測側(cè)擺角計算

為了擴(kuò)大衛(wèi)星對地觀測的范圍，通常在衛(wèi)星上采用側(cè)擺技術(shù)，使得衛(wèi)星能夠沿著垂直星下點軌跡的方向也進(jìn)行觀測[1]。衛(wèi)星的側(cè)擺角是指星載遙感器沿著垂直軌道方向轉(zhuǎn)動與星地連線之間形成的夾角。如圖1所示，假設(shè)觀測的目標(biāo)點在A(λ,φ)處，S是衛(wèi)星的位置，O為地心，S′(λs,φs)是星地連線與地面的交點，并且AS′垂直于星下點軌跡，H為衛(wèi)星的高度，Re為地球半徑，F(xiàn)OV視場角，β為側(cè)擺角。

圖1 衛(wèi)星對地覆蓋示意Fig.1 Illustration of ground coverage of satellite

文獻(xiàn)[1]給出了計算衛(wèi)星側(cè)擺角的方法。根據(jù)目標(biāo)點和星下點的經(jīng)緯度坐標(biāo)，利用文獻(xiàn)[12]中給出的方法求解側(cè)擺角。具體方法如下：

該算法基于以下兩點前提：1)弧度為1′的弧長在地球上對應(yīng)的距離長度是1海里；2)1海里=1.852 km。首先，計算出AS′：

計算 arccos(·)的時候，如果是弧度要轉(zhuǎn)換成角度進(jìn)行計算AS′。

地心覆蓋角∠AOS：

則側(cè)擺角β：

2 任務(wù)調(diào)度問題的描述和模型建立

2.1 任務(wù)調(diào)度問題的描述

衛(wèi)星對地觀測的步驟如下：用戶給出成像任務(wù)要求，可能包括不同的任務(wù)類型，不同的優(yōu)先級等要求。衛(wèi)星任務(wù)觀測系統(tǒng)根據(jù)得到的任務(wù)信息，衛(wèi)星自身位置信息以及星上傳感器和可用能源約束進(jìn)行相應(yīng)的任務(wù)調(diào)度，最大限度地完成用戶提交的任務(wù)請求。從上述過程可知，任務(wù)調(diào)度在整個衛(wèi)星成像應(yīng)用過程中起著關(guān)鍵作用，主要解決衛(wèi)星資源的有效分配和調(diào)度。

傳統(tǒng)的任務(wù)調(diào)度大多由地面站直接進(jìn)行任務(wù)調(diào)度，然后向衛(wèi)星傳遞執(zhí)行指令。相比于傳統(tǒng)的依賴于地面站的任務(wù)調(diào)度，星上自主任務(wù)調(diào)度有自己的優(yōu)勢：1)衛(wèi)星的效能進(jìn)一步提高。2)能夠快速響應(yīng)任務(wù)沖突。3)提高緊急任務(wù)的應(yīng)對能力。4)減少對地面測控的依賴，衛(wèi)星具有較高的自主能力。此外，對軍用衛(wèi)星來說，自主任務(wù)調(diào)度能夠減少星地之間通信的概率，提高衛(wèi)星的生存能力。

為了提高衛(wèi)星的整體效能，本文采取一種星上自主調(diào)度算法，事先對衛(wèi)星的姿態(tài)機(jī)動角度和相機(jī)成像時刻進(jìn)行調(diào)度。對于敏捷衛(wèi)星而言，多目標(biāo)成像的時間和順序都不再唯一。因此，有必要對多個目標(biāo)的成像時間和順序進(jìn)行研究。同時對任務(wù)的優(yōu)先級進(jìn)行甄別，在任務(wù)出現(xiàn)沖突時，使高級別任務(wù)優(yōu)先于低級別任務(wù)。

觀測范圍以及問題的假設(shè)如下:

敏捷衛(wèi)星具有不止一維的自由度，能夠繞俯仰、滾轉(zhuǎn)、偏航三個軸變化。敏捷衛(wèi)星的觀測范圍遠(yuǎn)大于普通的衛(wèi)星，觀測的時間也更為靈活，目標(biāo)可以位于星下點之前或之后。所以任務(wù)成像的時間和順序都不再唯一。

敏捷衛(wèi)星自主任務(wù)調(diào)度問題是一個非常復(fù)雜的問題，涉及條件約束繁多，在解決問題時不可能考慮所有約束[14]。所以，在建立問題模型之前，做出以下合理假設(shè)。

1)假設(shè)衛(wèi)星只攜帶一個星載傳感器，并且任意時刻只能執(zhí)行一個任務(wù)，不考慮中斷去執(zhí)行其他任務(wù)。

2)只考慮衛(wèi)星的側(cè)擺能力。

3)不考慮云層遮擋，天氣變化等對任務(wù)調(diào)度的影響。

4)不考慮衛(wèi)星工作時發(fā)生故障等問題。

2.2 問題建模

衛(wèi)星自主任務(wù)調(diào)度問題建模主要是衛(wèi)星根據(jù)獲取的用戶觀測請求以及星上資源約束進(jìn)行任務(wù)的觀測調(diào)度，最大限度地完成觀測任務(wù)。下面兩部分主要介紹任務(wù)調(diào)度的星上約束以及任務(wù)調(diào)度的目標(biāo)函數(shù)。

(1)約束條件

主要考慮的約束如下：

1)時間窗約束：

2)任意兩次成像操作之間不能有交疊，任意兩次拍攝之間必須有任務(wù)的準(zhǔn)備時間，包括開機(jī)準(zhǔn)備時間和衛(wèi)星角度變換需要的時間等。

式中：ski為從任務(wù)k結(jié)束到任務(wù)i開始的準(zhǔn)備時間。

3)側(cè)擺角約束:

式中：endi為任務(wù)i的結(jié)束時間；Anglei為觀測任務(wù)i時的側(cè)擺角；v為衛(wèi)星側(cè)擺時的角速度。式(6)表示當(dāng)前任務(wù)到下一次任務(wù)的時間要足夠多來完成側(cè)擺角轉(zhuǎn)換。

4)太陽高度角約束:

式中：ASun,min為完成任務(wù)的最小太陽高度角；ai(t)為t時刻衛(wèi)星執(zhí)行任務(wù)i的太陽高度角。

5)能量約束：

式中：ei為完成任務(wù)i消耗的能量；εki為從任務(wù)k結(jié)束到任務(wù)i開始的準(zhǔn)備操作消耗能量；E為可用的星上總能量；xi表示任務(wù)i是否被完成，1表示被完成，否則為0；xki表示從任務(wù)k到任務(wù)i的轉(zhuǎn)換，存在轉(zhuǎn)換則為1，否則為0。

6)星上存儲容量約束：

式中：M為星上總存儲容量；mi為完成任務(wù)i需要占用的容量。

(2)目標(biāo)函數(shù)

衛(wèi)星任務(wù)調(diào)度的目標(biāo)是在給定的時間范圍中，在滿足衛(wèi)星各類約束條件的情況下，盡可能獲得更多的衛(wèi)星任務(wù)完成收益。這里只考慮單一目標(biāo)函數(shù)。任務(wù)調(diào)度的目標(biāo)函數(shù)如下：

式中：Bi為完成任務(wù)i的收益，Bi≥0；αi是表示任務(wù)i的是否完成的二元變量，完成為1，否則為0。

最大化任務(wù)完成收益，這里面任務(wù)的收益Bi與觀測任務(wù)的優(yōu)先級成正比，優(yōu)先級大的任務(wù)收益相對應(yīng)較高。

(3)適應(yīng)度函數(shù)

遺傳算法中使用適應(yīng)度來評價個體的性能用以指導(dǎo)搜索。適應(yīng)度高的個體遺傳到下一代的概率大一些。本文的目標(biāo)函數(shù)是最大值函數(shù)，所以定義一個與目標(biāo)函數(shù)相近的適應(yīng)度函數(shù)來評價個體的性能。適應(yīng)度函數(shù)定義如下：

式中：Bi表示完成任務(wù)i的收益，Bi≥0；Ci表示任務(wù)i是否被選中，1表示被選中完成，0則表示沒有。

3 改進(jìn)的遺傳算法

衛(wèi)星的任務(wù)調(diào)度問題已經(jīng)被證明是一種NP-hard問題，很難通過解析或計算求解最優(yōu)解。許多研究已經(jīng)成功將各種改進(jìn)過的遺傳算法應(yīng)用于解決衛(wèi)星的任務(wù)調(diào)度問題[14-15]。遺傳算法的主要步驟是將問題的解空間進(jìn)行編碼，構(gòu)成染色體，再生成一個由染色體產(chǎn)生的初始種群，根據(jù)需要優(yōu)化問題的目標(biāo)函數(shù)來構(gòu)造適應(yīng)度函數(shù)，對種群對環(huán)境的適應(yīng)度進(jìn)行評估。適應(yīng)度高的個體被保留下來，經(jīng)過交叉、變異等遺傳算子產(chǎn)生新的更加優(yōu)異的種群，不斷進(jìn)行迭代，最終收斂到一個比較好的解，這個解接近問題的最優(yōu)解。遺傳算法作為一種優(yōu)化方法，也存在自身的局限性：1)遺傳算法容易出現(xiàn)過早收斂現(xiàn)象(早熟)；2)在快要接近最優(yōu)解時在最優(yōu)解附近收斂較慢等。本文在遺傳算法的基礎(chǔ)上進(jìn)行一定的改進(jìn)，提高算法的收斂性能。將該算法應(yīng)用到衛(wèi)星任務(wù)調(diào)度模型的求解。

3.1 編碼和初始種群生成

i∈1,2,…，N

染色體編碼結(jié)構(gòu)的一個簡單示例如下所示：

本文采用的產(chǎn)生初始群體的方法叫小區(qū)間生成法[17]。具體的步驟是：把優(yōu)化區(qū)間分成若干個小區(qū)間，在各個小區(qū)間內(nèi)隨機(jī)產(chǎn)生一個初始個體。這樣生成的初始群體會均勻分布在整個空間，保證了初始群體的豐富性，增強(qiáng)了搜索收斂于全局最優(yōu)的可能性。同時初始種群中保留全1個體，這是無約束下最優(yōu)解。

3.2 遺傳算子

(1)復(fù)制操作

為了保證較好的個體不會因為遺傳操作被破壞，采取兩代競爭遺傳算法[18]的操作。將父代的個體全部復(fù)制保留與子代一起進(jìn)行選擇操作。

(2)交叉算子

本文中采用的是優(yōu)選的交叉操作，在父代中隨機(jī)產(chǎn)生兩個個體，保留適應(yīng)度較大的個體，將上面的操作進(jìn)行兩次，得到兩個保留下來的個體。將得到的兩個體格進(jìn)行自適應(yīng)單點交叉。交叉概率表示如下:

(12)

式中：fc為兩個交叉?zhèn)€體中的適應(yīng)度較大的值；fmax,favg分別是群體中的個體適應(yīng)度最大值和平均值。

(3)變異算子

遺傳算法使用交叉算子從全局的角度出發(fā)找到了一些較好的個體編碼結(jié)構(gòu)，它們已經(jīng)接近最優(yōu)解了。但使用交叉算子無法對局部細(xì)節(jié)進(jìn)行搜索。使用變異算子能夠改善遺傳算法的局部搜索能力。本文采用基本位變異，以變異概率指定變異點做變異操作，在該算法中就是進(jìn)行取反操作，0變成1或者1變成0。在該算法中采用的是自適應(yīng)變異概率，即：

式中：Pm1=0.1；Pm2=0.001； fmax為群體的最大適應(yīng)度；favg為群體的平均適應(yīng)度值；fc為要變異的個體的適應(yīng)值。

(4)選擇算子

上文提到采用兩代競爭遺傳，將父代與產(chǎn)生的子代一起進(jìn)行選擇操作。具體的步驟如下：1)將最優(yōu)個體保存下來，將兩代個體中適應(yīng)度最大的個體直接保存下來。這種方法稱為精英保存策略[19]，研究表明，保留最優(yōu)個體的遺傳算法以概率1收斂到全局最優(yōu)解。該步驟保證了全局收斂性。2)兩兩競爭選擇，將除了最優(yōu)個體以外的全部個體進(jìn)行兩兩競爭選擇，隨機(jī)選出兩個個體，保留適應(yīng)度較大的。重復(fù)該操作，一直到產(chǎn)生完整的下一代。

(5)終止條件

該算法的終止條件為種群穩(wěn)定，規(guī)定最大迭代次數(shù)，若群體中最大適應(yīng)度與平均適應(yīng)度差值小于10-6或者達(dá)到最大迭代次數(shù)則終止。

4 算法仿真

在STK中設(shè)置仿真場景，總共設(shè)置了500個觀測目標(biāo)，500個待觀測目標(biāo)主要是針對單圈次觀測，某塊區(qū)域的密集觀測，示意如圖2所示。算法用Matlab 2013a在1.8 GHz CPU,4G內(nèi)存的計算機(jī)上實現(xiàn)。設(shè)定衛(wèi)星的高度為500 km，衛(wèi)星的視場角為8°，側(cè)擺能力為40°，衛(wèi)星機(jī)動角速度為2(°)/s。衛(wèi)星模型是J4擾動模型，考慮可見光對觀測影響。將STK與Matlab互聯(lián)，在Matlab中獲取衛(wèi)星和目標(biāo)點的參數(shù)，用上面提出的算法進(jìn)行仿真。同時將改進(jìn)的遺傳算法的仿真結(jié)果與傳統(tǒng)的模擬退火算法以及文獻(xiàn)[13]中提出的免疫遺傳蟻群混合算法仿真結(jié)果進(jìn)行比較。

圖2 500個觀測目標(biāo)與星下點軌跡示意Fig.2 Illustration of 500 targets and ground track

500個目標(biāo)點中單圈次只有96個目標(biāo)點在給定的時間內(nèi)可以觀測到。對于可觀測96個目標(biāo)，按照可見時間窗口的開始時間進(jìn)行排序得到任務(wù)序列。對應(yīng)于每個觀測目標(biāo)，給定對應(yīng)的任務(wù)收益進(jìn)行仿真。

圖3是該算法一次仿真迭代的過程，是種群平均適應(yīng)度和最大適應(yīng)度隨著迭代次數(shù)的變化。從圖3可以看出初始種群因為保留了所有任務(wù)均選中的全1個體，所以最大適應(yīng)度值最大。因不滿足條件很快被放棄，種群迭代初始的適應(yīng)度比較低，但是經(jīng)過上述改進(jìn)的遺傳算法，一段時間內(nèi)上升幅度較大，但到迭代最后則趨于平穩(wěn)。

表1是為了比較該算法與模擬退火算法(SA)與免疫遺傳蟻群混合算法(IACOGA)的仿真結(jié)果，采用同樣的數(shù)據(jù)源進(jìn)行模擬退火算法和免疫遺傳蟻群混合算法進(jìn)行仿真。從表1可以看出，改進(jìn)遺傳算法的收益百分比>免疫遺傳蟻群混合算法收益百分比>模擬退火算法收益百分比。而達(dá)到全局收斂的時間關(guān)系則是，改進(jìn)遺傳算法收斂時間<模擬退火算法收斂時間<免疫遺傳蟻群混合算法收斂時間。由表1可以看出，模擬退火算法的收益百分比最差，而免疫遺傳蟻群混合算法的收益百分比與本文提出的改進(jìn)遺傳算法相近，但是，IACOGA算法的運行時間較長，使用蟻群算法改進(jìn)遺傳算法，雖然可以得到較好的初始解，但是時間代價很大。而本文的算法在達(dá)到較好的收益率的同時，運行時間很少，收斂速度很快。

圖3 種群最大適應(yīng)度和平均適應(yīng)度的變化值Fig.3 Maximum fitness and average fitness of every population

仿真次數(shù)AGA仿真時間/sAGA收益百分比/%SA仿真時間/sSA收益百分比/%IACOGA仿真時間/sIACOGA收益百分比/%10 9993 81 6787 9347 6293 621 0194 41 7688 5316 6491 131 1195 21 7589 9333 6793 441 0393 31 6886 2336 0093 351 0195 41 7186 4319 0591 861 0395 81 7086 8334 0192 271 0695 41 7487 8339 7091 681 1292 11 6888 0335 6192 690 9693 51 6985 2314 4291 8101 2092 91 6485 9316 7291 9

5 結(jié)束語

觀測衛(wèi)星的自主任務(wù)調(diào)度涉及到多種組合約束問題，同時要求衛(wèi)星能夠快速對得到的任務(wù)請求進(jìn)行調(diào)度，所以對任務(wù)調(diào)度算法的要求較高。對于任務(wù)可見窗口有重疊，任務(wù)比較密集的衛(wèi)星觀測調(diào)度問題，應(yīng)該要考慮衛(wèi)星側(cè)擺能力與到達(dá)指定側(cè)擺角度需要的機(jī)動時間等約束。本文給出了快速計算側(cè)擺角的方法，并且對衛(wèi)星對地觀測問題進(jìn)行基于各類約束以及任務(wù)完成收益的建模，設(shè)計了改進(jìn)遺傳算法來求解，使用小區(qū)間法保留初始種群的多樣性，并且對于遺傳算子均引入自適應(yīng)概率，同時采用兩代競爭算法保證優(yōu)的個體被保存，實施最優(yōu)保存策略。試驗驗證，該算法相較于傳統(tǒng)的模擬退火算法以及免疫遺傳蟻群混合算法，具有更好的收斂速度和全局收斂性。

References)

[1] 賈志軍,楊敏,孫洋,等. 衛(wèi)星對地觀測中的側(cè)擺策略[J]. 四川兵工學(xué)報,2014(7):128- 130.

JIA Z J, YANG M, SUN Y, et al.Swinging strategy on Earth observing satellites[J]. Journal of Sichuan Ordnance, 2014(7):128-130(in Chinese).

[4] 賀仁杰, 高鵬,白保存,等. 成像衛(wèi)星任務(wù)規(guī)劃模型、算法及其應(yīng)用[J]. 系統(tǒng)工程理論與實踐,2011(3):411-422.

HE R J, GAO P, BAI B C, et al. Models,algorithms and applications to the mission planning system of imaging satellites[J]. Systems Engineering-Theory & Practice,2011(3):411-422(in Chinese).

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

LI Y Q, XU M Q,WANG R X, et al. Scheduling observations of spot object of three-axis stabilized satellites[J]. Journal of Jilin University (Engineering and Technology Edition), 2008, 38(6):1447-1451(in Chinese).

[6] 阮啟明. 面向區(qū)域目標(biāo)的成像偵察衛(wèi)星調(diào)度問題研究[D].長沙:國防科技大學(xué),2005.

[7] BAEK S, HAN S, CHO K, et al. Development of a scheduling algorithm and GUI for autonomous satellite missions[J]. Acta Astronautica, 2011, 68(7): 1396-1402.

[8] TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P. Multi-objective optimization for selecting and scheduling observations by agile Earth observing satellites[M]∥Parallel Problem Solving from Nature-PPSN XII. Berlin: Springer, 2012: 112-121.

[9] TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P. A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite[J]. European Journal of Operational Research, 2015, 245(2): 542-554.

[10] GLOBUS A, CRAWFORD J, LOHN J, et al. Scheduling Earth observing fleets using evolutionary algorithms: problem description and approach[C]∥Proceedings of the 3rd International NASA Workshop on Planning and Scheduling for Space, 2002:27-29.

[11] 郭浩,邱滌珊,伍國華,等. 基于改進(jìn)蟻群算法的敏捷成像衛(wèi)星任務(wù)調(diào)度方法[J]. 系統(tǒng)工程理論與實踐,2012(11):2533-2539.

GUO H, XIU D S,WU G H, et al. Tasks scheduling method for an agile imaging satellite based on improved ant colony algorithm[J]. Systems Engineering-Theory & Practice, 2012(11): 2533-2539(in Chinese).

[12] Geoscience Australia. Distance calculation algorithms[EB/OL].(2013-05)[2016-01-08].http:∥www.ga.gov.au/sc-entific-topics/positioning-navigation/geodesy/geodetic-techniques/distance-calculation-algorithms.

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

HAO H C, LI W, LI Y J. Mission planning for agile Earth observation satellites based on hybrid genetic algorithm[J]. Science Technology and Engineering, 2013,17: 4972-4978(in Chinese).

[14] 向仍湘. 敏捷衛(wèi)星任務(wù)調(diào)度技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué),2010.

[15] DJAMAL H, MICHEL V. Saturated and consistent neighborhood for selecting and scheduling photographs of agile Earth observing satellite[C]. MIC2003: The Fifth Metaheuristics International Conference.

[16] VERFAILLIE G, LEMATRE M. Selecting and scheduling observations for agile satellites: some lessons from the constraint reasoning community point of view[C]. The Seventh International Conference on Practical and Principles of Constraint Programming. France, 2001.

[17] 高瑋,尹志喜. 現(xiàn)代智能仿生算法及其應(yīng)用[M].北京:科學(xué)出版社,2011: 58-61.

[18] 于海斌,王浩波,徐心和.兩代競爭遺傳算法及其應(yīng)用研究[J].信息與控制,2000,29(4): 309-314.

YU H B, WANG H B, XU X H. A genetic algorithm with competitive selection between adjacent two generations and its applications to tsp[J]. Information and Control, 2000,29(4): 309-314 (in Chinese).

[19] 李小平, 王風(fēng)儒. 優(yōu)解保留遺傳算法收斂性研究[J].電機(jī)與控制學(xué)報,2000,4(1): 52- 54.

LI X P, WANG F R. Research on convergence of elitist genetic algorithm[J]. Electric Machines And Control, 2000, 4(1): 52-54 (in Chinese).

(編輯：高珍)

An adapted genetic algorithm applied to satellite autonomous task scheduling

ZHAO Ping，CHEN Zhiming*

College of Astronautics, Nanjing University of Aeronautics & Astronautics, Nanjing 210016, China

Aiming at solving the problem of autonomous task scheduling of earth observing satellites with the ability of swinging,satellite autonomous task scheduling problem and constraints were described.A single-objective multi-constraints model was built according to the NP-hard character of satellite autonomous task scheduling problem.An adapted genetic algorithm was designed.All of the genetic operations of genetic algorithms were optimized. Firstly, mini-region method was applied to generate of the original population to ensure the diversity of population. Adaptive probabilities were used for crossover and mutation operation. Two generations competitive technology was used to avoid the premature and improve the efficiency and the robustness of the algorithm. The algorithm also uses the optimization reserved strategy to preserve the optimal solution, which makes the algorithm converge to the global.The adapted genetic algorithm was applied to the local multi-conflict tasks observation and designed simulation experiments of the observation of regional dense targets. The results are compared with results of simulated annealing algorithm and immune ant colony genetic algorithm,and it shows that the proposed algorithm is more effective and it has a better convergence.

Earth observation satellite；satellite swinging angle；autonomous task scheduling；modeling；adapted genetic algorithm;adaptive probability

10.16708/j.cnki.1000-758X.2016.0064

2016-05-04；

2016-07-13；錄用日期：2016-08-22；

時間：2016-12-16 11:29:09

http:∥www.cnki.net/kcms/detail/11.1859.V.20161216.1129.006.html

國家自然科學(xué)基金(61403197)；江蘇省自然科學(xué)基金(BK20130816/BK20140830)

趙萍(1991-)，女，碩士研究生，zhaoping_nuaa@163.com,研究方向為編隊衛(wèi)星在軌自主任務(wù)規(guī)劃

*通訊作者：陳志明(1984-)，男，講師，lchenzhiming@nuaa.edu.cnl，研究方向為分布式衛(wèi)星測控技術(shù)、星載計算機(jī)設(shè)計管理

趙萍,陳志明.應(yīng)用于衛(wèi)星自主任務(wù)調(diào)度的改進(jìn)遺傳算法[J].中國空間科學(xué)技術(shù),2016,36(6)：47-54.

ZHAOP,CHENZM.Anadaptedgeneticalgorithmappliedtosatelliteautonomoustaskscheduling[J].ChineseSpaceScienceandTechnology, 2016,36(6)：47-54(inChinese).

TP301.6

A

http:∥zgkj.cast.cn