高朝暉，岳群彬，李 偉

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

0 引言

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

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

1 問題描述

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

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

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

2 遺傳算法簡介

2.1 基本原理

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

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

2.2 算法步驟

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

3 遺傳算法的應用

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

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

圖1 遺傳算法的迭代流程

3.1 編碼方式

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

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

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

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

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

3.3 計算適應度

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

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

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

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

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

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

⑤回放約束。

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

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

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

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

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

基于此，定義個體的適應度為:

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

3.4 選擇算子

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

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

3.5 交叉算子

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

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

3.6 變異算子

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

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

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

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

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

3.7.1 精英解保留

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

3.7.2 自適應變異

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

4 仿真實驗與結(jié)果分析

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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

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

［8］戴曉暉，李敏強，寇紀松.遺傳算法的性能分析研究［J］.軟件學報，2001，12(5):742 －750.

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

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

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

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

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