遺傳算法在成像衛(wèi)星計(jì)劃編制中的應(yīng)用

高朝暉，岳群彬，李 偉

(中國電子科技集團(tuán)公司第五十四研究所，河北石家莊 050081)

0 引言

隨著航天事業(yè)的不斷發(fā)展和衛(wèi)星種類數(shù)量的不斷增加，我國逐漸擁有數(shù)量眾多的多個系列成像觀測衛(wèi)星，如何有效地利用衛(wèi)星攝影資源和地面站跟蹤接收資源，制定高效可行的衛(wèi)星和地面站任務(wù)計(jì)劃將成為一個重要的問題。

由于星地資源的使用限制，通常用戶的攝影需求不能被全部滿足。如何在大量約束條件下，安排一個滿意的星地任務(wù)計(jì)劃，分配星地資源來完成更多的攝影任務(wù)，對于充分有效地發(fā)揮成像衛(wèi)星的能力是至關(guān)重要的。基于此，研究人工智能優(yōu)化算法領(lǐng)域中的遺傳算法在成像衛(wèi)星計(jì)劃編制問題中的應(yīng)用，實(shí)現(xiàn)星地資源的優(yōu)化分配。

1 問題描述

衛(wèi)星的計(jì)劃編制是指根據(jù)衛(wèi)星的可攝影時段和地面站的可接收時段，結(jié)合星上有效載荷的使用約束和業(yè)務(wù)規(guī)則，通過一系列的沖突消解和決策分析，最后安排出一個優(yōu)化合理的衛(wèi)星攝影計(jì)劃和地面站接收計(jì)劃。

星地資源分配問題的主要特點(diǎn)在于在決策分析過程中，目標(biāo)存在可見時間窗口和約束限制條件。只有在可見時間窗口內(nèi)且滿足約束條件，目標(biāo)才允許被攝影。因此，星地資源分配問題可描述為:從一個由目標(biāo)的可見時間窗口組成的龐大的搜索解空間中選取一個子集，使這個子集滿足所有的約束條件并使該次觀測方案的評價值為最大［1］。

考慮到星地資源分配問題是NP完全問題，通常的線性規(guī)劃方法不能有效地求解，基于上述約束，采用遺傳算法實(shí)現(xiàn)了星地資源的自動優(yōu)化分配，以獲得盡可能多、盡可能重要、攝影效果盡可能好且優(yōu)先滿足等級較高用戶的目標(biāo)影像數(shù)據(jù)，充分有效地發(fā)揮成像觀測衛(wèi)星的能力。

2 遺傳算法簡介

2.1 基本原理

遺傳算法是基于自然選擇和自然遺傳機(jī)制的搜索算法，它是一種有效的解決最優(yōu)化問題的方法。遺傳算法最早是由美國Michigan大學(xué)的John Holland和他的同事及學(xué)生提出的，它借鑒達(dá)爾文的物競天擇、優(yōu)勝劣汰、適者生存的自然選擇和自然遺傳的機(jī)理，其本質(zhì)是一種求解問題的高效并行全局搜索方法。算法從任一初始化的群體出發(fā)，通過隨機(jī)選擇、交叉和變異等遺傳操作，使群體一代一代地進(jìn)化到搜索空間中的優(yōu)化區(qū)域，最后抵達(dá)最優(yōu)解。算法的特點(diǎn)在于搜索過程中能夠自動獲取和積累有關(guān)搜索空間的知識，利用問題的固有知識來縮小搜索空間，并自適應(yīng)地控制搜索過程，從而得到最優(yōu)解或準(zhǔn)最優(yōu)解［2］。

遺傳算法與其他算法相比，主要有以下4個方面的不同:①遺傳算法所面向的對象是參數(shù)集的編碼，而不是參數(shù)集本身;② 遺傳算法的搜索是基于若干個點(diǎn)，而不是基于一個點(diǎn);③ 遺傳算法利用目標(biāo)函數(shù)的信息，而不是導(dǎo)數(shù)或者其他輔助信息;④遺傳算法的轉(zhuǎn)化規(guī)則是概率性的，而不是確定性的［3］。

2.2 算法步驟

遺傳算法的運(yùn)行過程為—個典型的迭代過程，基本步驟如下:①選擇編碼方式;② 定義適應(yīng)度函數(shù)f(x);③確定遺傳策略，包括群體大小和選擇、交叉、變異方法，確定交叉概率和變異概率等遺傳參數(shù);④隨機(jī)初始化生成群體;⑤ 計(jì)算群體中個體位串解碼后的適應(yīng)值f(x);⑥ 按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成新一代群體;⑦判斷新群體性能是否滿足某一指標(biāo)或者是否已完成預(yù)定迭代次數(shù)，不滿足則返回步驟⑥或者修改遺傳策略再返回步驟⑥，滿足則退出［4］。

3 遺傳算法的應(yīng)用

在成像衛(wèi)星運(yùn)行管理控制中，需要合理安排星地資源，并滿足長條帶攝影、多站聯(lián)合接收及應(yīng)急處理等航天應(yīng)用的特點(diǎn)，具體地，在分析提煉衛(wèi)星攝影能力、星上存儲能力、地面接收能力、數(shù)據(jù)處理能力約束以及有效載荷使用規(guī)則的基礎(chǔ)上，基于遺傳算法實(shí)現(xiàn)了星上載荷資源和地面接收資源的優(yōu)化分配，據(jù)此編制出衛(wèi)星和地面站的任務(wù)計(jì)劃，從而提高了任務(wù)控制的合理性和資源使用的效率，獲取盡可能多的目標(biāo)區(qū)域影像數(shù)據(jù)，滿足了后續(xù)遙感數(shù)據(jù)處理應(yīng)用需求，增強(qiáng)了衛(wèi)星任務(wù)控制的科學(xué)性和時效性。

首先確定了計(jì)劃編制的時間區(qū)間、參與的地面站和目標(biāo)區(qū)域，然后進(jìn)行衛(wèi)星軌道預(yù)報(bào)計(jì)算，結(jié)合目標(biāo)區(qū)域的地理位置，計(jì)算出衛(wèi)星對各個目標(biāo)區(qū)域的訪問時間，即攝影任務(wù)。該攝影任務(wù)即可作為遺傳算法的輸入，然后根據(jù)算法流程，對這些攝影任務(wù)不斷進(jìn)行進(jìn)化迭代，達(dá)到預(yù)定迭代次數(shù)時即退出算法，遺傳算法迭代流程如圖1所示［5］。

圖1 遺傳算法的迭代流程

3.1 編碼方式

遺傳算法的編碼方式有多種，比如二進(jìn)制編碼、整數(shù)編碼、浮點(diǎn)數(shù)編碼和混合編碼等，這些編碼方式各有其特定適應(yīng)的問題，并且對遺傳算法的性能影響很大［6］。

每個攝影任務(wù)只有“執(zhí)行”和“不執(zhí)行”2種狀態(tài)，據(jù)此選擇了二進(jìn)制編碼。每一個基因位表示一個衛(wèi)星攝影任務(wù)，0表示不執(zhí)行，1表示執(zhí)行。每個個體(二進(jìn)制串)表示一個可實(shí)施的觀測方案，如 010111，表示只執(zhí)行第 2、4、5、6 個攝影任務(wù)。

3.2 產(chǎn)生初始種群

依據(jù)算法理論，初始時要隨機(jī)初始化一定數(shù)目的個體組成種群，但是由于計(jì)劃編制的過程中存在大量的約束條件，隨機(jī)初始化的個體很可能違反約束，導(dǎo)致所有個體的適應(yīng)度都為0，這樣在進(jìn)化時就很難跳出局部的谷底［7］。

因此，在初始群體的產(chǎn)生算法中引入了適當(dāng)?shù)摹斑x種”機(jī)制，以避免個體適應(yīng)度全部或大部分為0的情況。具體的方法是使初始個體的基因位全部為零，即 000000。隨著群體進(jìn)化的逐漸進(jìn)行，個體的適應(yīng)度會逐漸增大，基因位會逐漸由0變?yōu)?，即越來越多的攝影任務(wù)會被執(zhí)行，直至最優(yōu)。

3.3 計(jì)算適應(yīng)度

在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計(jì)要結(jié)合求解問題本身的要求而定。需要強(qiáng)調(diào)的是，適應(yīng)度函數(shù)評估是選擇操作的依據(jù)，適應(yīng)度函數(shù)的設(shè)計(jì)直接影響到遺傳算法的性能。個體的適應(yīng)度在優(yōu)勝劣汰的自然進(jìn)化過程中起關(guān)鍵性作用，若定義不當(dāng)則會直接誤導(dǎo)算法向壞的方向進(jìn)化。

成像衛(wèi)星的使用約束主要包括以下幾個方面:

①開機(jī)約束(最短和最長開機(jī)時間等);

②側(cè)視約束(側(cè)視速度、測試準(zhǔn)備時間等);

③存儲約束(固存容量限制等);

④聯(lián)合接收約束;

⑤回放約束。

實(shí)際應(yīng)用中，一個較優(yōu)的攝影計(jì)劃應(yīng)該能夠獲得盡可能多、盡可能重要、拍攝效果盡可能好且優(yōu)先滿足等級較高用戶的目標(biāo)的攝影數(shù)據(jù)，因此，采用了多準(zhǔn)則加權(quán)和的計(jì)劃評價方法，主要包括以下分評價值:

①目標(biāo)數(shù)目評價值f1;

②目標(biāo)重要性評價值f2(如任務(wù)緊急程度和目標(biāo)等級等);

③觀測效果評價值f3(如云量因素和太陽高度角等);

④附加影響評價值f4(如用戶等級和任務(wù)緊迫度等)。

基于此，定義個體的適應(yīng)度為:

式中，X1、X2、X3、X4分別為各準(zhǔn)則的權(quán)值;f1、f2、f3、f4可以根據(jù)觀測目標(biāo)的屬性得出。結(jié)合實(shí)際需要，可以通過提高某一個準(zhǔn)則的權(quán)重來獲得側(cè)重這一方向的觀測計(jì)劃［8］。

3.4 選擇算子

選擇是指從群體中選擇優(yōu)勝個體、淘汰劣質(zhì)個體的操作，其目的是把優(yōu)化的個體(或解)通過配對交叉產(chǎn)生新的個體再遺傳到下一代。常用的選擇算子有適應(yīng)度比例方法、最佳個體保存方法、期望值方法、排序選擇方法和排擠方法等［9］。

具體采用的是適應(yīng)度比例方法。在該方法中，各個個體的選擇概率和其適應(yīng)度值成正比，定義第i個個體被選擇的概率為［10］:即個體適應(yīng)度越大，其被選擇的概率就越高，反之亦然。

3.5 交叉算子

交叉是指把2個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。交叉關(guān)鍵是交叉次數(shù)的選擇，具體采用的方法是用交叉概率Pc作貝努利實(shí)驗(yàn)。如果實(shí)驗(yàn)成功，則選擇的2個父代個體交叉配對;否則不交叉，進(jìn)行下一輪選擇。

基本的交叉算子有單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉一致交叉、二維交叉和樹結(jié)構(gòu)交叉等［11］。具體采用了單點(diǎn)交叉，即在個體串中隨機(jī)設(shè)定一個交叉點(diǎn)。實(shí)行交叉時，該點(diǎn)后的2部分結(jié)構(gòu)進(jìn)行互換，并生成2個新的個體。

3.6 變異算子

變異是指對個體的某些基因位的值進(jìn)行變動，其目的是使遺傳算法具有局部搜索的能力和維持種群的多樣性。

具體地，首先在群體中所有個體的基因串范圍內(nèi)隨機(jī)確定基因位，然后用變異概率Pm作貝努利實(shí)驗(yàn)。如果實(shí)驗(yàn)成功，則對這些基因位的值進(jìn)行變異，否則不變異。變異操作定義為對基因位的值進(jìn)行逆轉(zhuǎn)，即0→1或1→0。

在遺傳算法中，交叉算子具有全局搜索能力，而變異算子具有局部搜索能力，通過交叉和變異的相互配合可使其兼顧全局和局部的均衡搜索能力［12］。

3.7 附加優(yōu)化方法

在基本遺傳算法的基礎(chǔ)上，還采用了若干方法來優(yōu)化算法的執(zhí)行過程，使算法能更快地找到最優(yōu)解。

3.7.1 精英解保留

精英解保留是指把群體中適應(yīng)度高的個體不進(jìn)行交叉變異而直接復(fù)制到下一代中，優(yōu)點(diǎn)在于能保證算法終止時得到的最后結(jié)果一定是歷代出現(xiàn)過的最高適應(yīng)度的個體。具體的實(shí)現(xiàn)過程如下:取出新種群中的的最差個體s1適應(yīng)度f1、舊種群中的最佳個體s2適應(yīng)度f2。如果f1＜f2，則將s1替換為s2，同時將 f2置為0，然后更新 s1、f1、s2和 f2，返回步驟①，否則退出。

3.7.2 自適應(yīng)變異

變異率在保持固定不變的情況下，一旦陷入局部最優(yōu)，就很難跳出來。為了避免這種情況，根據(jù)交叉所得的2個個體的海明距離進(jìn)行變化，使變異概率隨著群體中的多樣性程度而自適應(yīng)調(diào)整，海明距離越小，概率越大，反之亦然。

4 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證計(jì)劃編制模型和算法的有效性及效率，設(shè)計(jì)和實(shí)現(xiàn)了一個基于遺傳算法的成像衛(wèi)星計(jì)劃編制原型系統(tǒng)［13］。針對實(shí)際的不同觀測任務(wù)數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，依據(jù)實(shí)際需求對成像衛(wèi)星進(jìn)行任務(wù)調(diào)度，主要包括以下方面:①衛(wèi)星參數(shù)參考實(shí)際衛(wèi)星特性設(shè)定;②衛(wèi)星軌道數(shù)據(jù)由STK工具仿真計(jì)算得出;③衛(wèi)星觀測任務(wù)來自模擬的用戶請求，觀測任務(wù)數(shù)量為200;④地面站使用北京站、廣州站、烏魯木齊站和長春站，地理坐標(biāo)依據(jù)城市坐標(biāo)而定;⑤計(jì)劃編制的時間段設(shè)為2013－03－2202:00:00到2013－03－2308:00:00;⑥使用隨機(jī)生成的云量等級。

經(jīng)過計(jì)算得出遺傳算法的輸入，即衛(wèi)星攝影預(yù)案和地面站跟蹤接收預(yù)案，如表1和表2所示。

表1 遺傳算法輸入—衛(wèi)星1攝影預(yù)案

表2 遺傳算法輸入—地面站跟蹤接收預(yù)案

設(shè)定遺傳算法參數(shù)為:交叉概率0.85、變異概率0.08、最大世代數(shù)500代、群體規(guī)模100、染色體長度200。經(jīng)過星地資源的沖突消解和優(yōu)化分配，得到了最佳的觀測方案，適應(yīng)度值為7640.28，對應(yīng)的衛(wèi)星攝影計(jì)劃和地面站跟蹤接收計(jì)劃如表3和表4所示。由于星上資源和地面接收資源的限制，算法自動將任務(wù)Task2、Task3和Task4的攝影預(yù)案刪除，只保留了Task1和Task5，這樣能保證整體的適應(yīng)度值最大。

表3 遺傳算法輸出—衛(wèi)星1攝影計(jì)劃

表4 遺傳算法輸出—地面站跟蹤接收計(jì)劃

經(jīng)遺傳算法優(yōu)化后的各觀測方案很好地體現(xiàn)了在多個目標(biāo)準(zhǔn)則間的均衡考慮，優(yōu)化解的分布性很好，不同的觀測方案體現(xiàn)了各種目標(biāo)準(zhǔn)則下的優(yōu)化結(jié)果和綜合優(yōu)化結(jié)果，有利于決策人員選擇最終的衛(wèi)星和地面任務(wù)計(jì)劃。使用遺傳算法來安排計(jì)劃的效率遠(yuǎn)高于其他方法(如窮舉法、貪婪法等)，基本有效地解決了在大量約束條件下合理安排衛(wèi)星觀測任務(wù)的問題，且制定的衛(wèi)星攝影計(jì)劃和地面站接收計(jì)劃經(jīng)過檢驗(yàn)合理可行。

5 結(jié)束語

通過分析成像衛(wèi)星計(jì)劃編制中的星地資源分配問題，提出了一種復(fù)雜約束條件下成像衛(wèi)星的資源調(diào)度方法，在此基礎(chǔ)上設(shè)計(jì)了一種帶約束的遺傳算法應(yīng)用模型，并將其應(yīng)用于優(yōu)化衛(wèi)星任務(wù)計(jì)劃的制定。原型系統(tǒng)仿真實(shí)驗(yàn)結(jié)果表明，該算法應(yīng)用可滿足成像衛(wèi)星觀測任務(wù)的多目標(biāo)規(guī)劃需求，很好地解決了成像衛(wèi)星計(jì)劃編制中的優(yōu)化調(diào)度問題，提升了用戶請求的滿足程度，提高了衛(wèi)星攝影資源及地面站跟蹤接收資源的利用率。 ■

［1］陳國良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用［M］.北京:人民郵電出版社，2001.

［2］玄光男，程潤偉.遺傳算法與工程優(yōu)化［M］.北京:清華大學(xué)出版社，2004.

［3］汪定偉，王俊偉.智能優(yōu)化方法［M］.北京:高等教育出版社，2007.

［4］賀仁杰，李菊芳，姚 鋒，等.成像衛(wèi)星任務(wù)規(guī)劃技術(shù)［M］.北京:科學(xué)出版社，2010.

［5］玄光男，程潤偉，唐加福.遺傳算法與工程設(shè)計(jì)［M］.北京:科學(xué)出版社，2000.

［6］周 明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京:國防工業(yè)出版社，1999.

［7］楊啟文，蔣靜坪，張國宏.遺傳算法優(yōu)化速度的改進(jìn)［J］.軟件學(xué)報(bào)，2000，12(2):270 －275.

［8］戴曉暉，李敏強(qiáng)，寇紀(jì)松.遺傳算法的性能分析研究［J］.軟件學(xué)報(bào)，2001，12(5):742 －750.

［9］錢志勤，騰宏飛，孫治國.人機(jī)交互的遺傳算法及其在約束布局優(yōu)化中的應(yīng)用［J］.計(jì)算機(jī)學(xué)報(bào)，2001，24(5):553－558.

［10］周 明，孫樹棟，彭炎午.用遺傳算法規(guī)劃移動機(jī)器人路徑［J］.西北工業(yè)大學(xué)學(xué)報(bào)，1998，16(4):242 －246.

［11］周 明，孫樹棟，彭炎午.基于遺傳模擬退火算法的機(jī)器人路徑規(guī)劃［J］.航空學(xué)報(bào)，1998，19(1):118 －120.

［12］劉大有，盧奕南，王 飛.遺傳程序設(shè)計(jì)方法［J］.計(jì)算機(jī)研究與發(fā)展，2001，38(2):213 －222.

［13］張學(xué)慶，馬萬權(quán)，高朝暉，等.衛(wèi)星管理控制體系結(jié)構(gòu)研究［J］.無線電工程，2006，36(5):36－38.