【學術plus】 新添加號內搜索功能！
進入公眾號→點擊功能表【智庫掃描】→【搜搜文章】
→輸入關鍵字→一鍵檢索您需要的文章。 快來試試！
【兼職】神秘崗位正在向你招手， 敢來麼？
【厚度】學術plus年終巨獻：2017年 你不可以錯過的重磅報告們！（全文閱讀連結）
今日薦文
今日薦文的作者為中國電子科技集團公司第五十四研究所專家張超， 李豔斌， 陳金勇。 本篇節選自論文《基於並行架構的敏捷衛星任務調度優化演算法》， 發表於《中國電子科學研究院學報》第12卷第5期。 本文為論文下半部分。
摘 要：針對敏捷衛星任務規劃調度問題， 首先分析了敏捷衛星成像時間影響成像品質、調度和選擇相結合等調度特點， 構建了基於成像品質懲罰係數的敏捷衛星任務規劃組合優化模型；分別採用差分演化、粒子群和類比退火三種演算法進行求解和分析評價；並且採用全域-主從式模型和獨立-孤島模型分別實現了三種演算法的平行計算技術。
3 敏捷衛星任務調度優化演算法
① 敏捷衛星任務編碼設計
染色體結構由觀測目標的編碼和接收元任務的編碼拼接得到， 根據任務規劃需求採用整數編碼的方式。 傳統衛星一個觀測目標的基因位元取值只能是0到1兩種， 0代表對應的該點目標沒有被選中， 1代表該點目標會被安排進行觀測成像， 所有觀測目標和接收元任務的數量之和即為染色體的長度。 然而， 敏捷衛星根據不同任務觀測模式基因位元取值範圍不同， 對於觀測元任務數量不同。 對於多點目標連續成像模式， 每個點目標可以被觀測N次；對於立體成像模式， 每個目標至少被觀測2次；對於寬幅目標，
② 基於排序變異的差分演化演算法
DE演算法的核心運算元是差分變異運算元。 一般情況下， 變異運算元是從當前種群中隨機選擇。 在自然界中， 優良物種總是包含好的基因資訊， 因此， 它們有更多的機會被用來指導其他物種進化。 受這種現象啟發， 雙親個體被選中為變異運算元的概率是根據它們在當前種群中的評價值排名來決定的，
（12）
③ 遺傳類比退火混合演算法
本文針對類比退火演算法解的品質與求解時間長之間的矛盾， 將遺傳演算法與類比退火演算法結合起來， 提出了一種改進的遺傳類比退火演算法。 改進遺傳類比退火演算法的基本思想是：與傳統的類比退火演算法總體運行過程相類似， 從一組隨機產生的初始解（初始種群）開始全域最優解的搜索過程， 通過選擇、交叉、變異等遺傳操作來產生候選解，
④ 基於相似度和聚集度的粒子群演算法
根據標準PSO演算法的性能分析， 隨著演算法反覆運算運行， 粒子變得越來越相似， 演算法缺少多樣性， 從而影響演算法的全域搜索能力。 改進的粒子群演算法的基本思想是：根據每條染色體的基因位與最優染色體進行比較， 計算出每條染色體與最優染色體的相似度， 然後根據相似度計算出每一代種群的聚集度。 隨著反覆運算運行， 標準PSO演算法會越來越聚集在一起， 因為粒子最終都向最優點粒子靠近。 改進的粒子群通過相似度和聚集度，在染色體變異過程中，當種群聚集度大的時候，增加染色體的變異概率，從而使種群的多樣性增加，有利於尋找到更優的結果。
⑤ 約束處理
敏捷衛星任務調度優化是一個帶約束的優化問題，需要考慮諸多約束。演算法運行過程中產生的邏輯規劃物件很有可能是不合法的，必須要對這樣的邏輯規劃物件進行處理。演算法在產生邏輯規劃物件經約束處理模組，對組合元任務集進行處理，得到新的滿足約束的組合元任務集。然後通過編碼，生成對應的修正的邏輯規劃物件，即規劃結果。約束處理模組依次按照以下順序進行約束處理：觀測時間衝突約束、數傳模式約束、指令範本約束、工作時間約束、檔下傳約束、能源約束。
圖 3 約束處理流程
⑥ 模擬測試結果
針對差分演化演算法、類比退火演算法以及粒子群演算法三種演算法分別提出了改進演算法。為了測試改進演算法的效果，選取了5批工程資料，每批資料包含300個觀測元任務，分別從綜合評價值（完成任務數、優先順序之和、俯仰角之和）以及耗時比較改進前後的演算法效果。改進後的差分演化演算法是使用了rankDE策略的演算法，改進後的類比退火演算法是遺傳類比退火演算法，改進後的粒子群演算法是通過引入相似度和聚集度的概念來增大變異概率的演算法。
圖 4 改進前後演算法的綜合評價值
圖 5 改進前後演算法的耗時
通過以上圖表資料的展示，可以看出：使用rankDE策略的差分演化演算法，其規劃結果及耗時與改進前的演算法規劃結果及耗時比較接近，改進效果並不明顯；遺傳類比退火演算法的改進效果比較明顯，改進後的規劃結果明顯較優，雖然耗時相對較多，但演算法改進後的耗時與差分演化演算法接近，屬於可接受範圍；引入相似度和聚集度使變異概率增大之後的粒子群演算法，其規劃結果比未改進的粒子群演算法的規劃結果較優，雖然其耗時也相應的增加了，但綜合其他演算法來看，其耗時仍少於差分演化演算法和類比退火演算法，說明粒子群演算法的改進效果較明顯。
4 平行算法研究
① 平行算法模型
由於智慧優化演算法的內在並行性，其並行處理方式是很自然的解決途徑。本文中，衛星任務規劃演算法在並行模式上採用全域型和獨立型。為了應用平行計算，必須把演算法分解成相互獨立的若干問題[14]。
全域型—主從式模型（mast-slave model）首先統一三種智慧優化演算法的編碼格式，然後在主執行緒中進行搜索，然後將演算法的每一次反覆運算中得到的解分配到對應的處理器獨立進行的編碼解析、約束檢查、評價和計算解的適應值等操作，然後將其返回給調用執行緒。主從式模型示意圖如圖6。
圖6主從式模型的並行演化計算架構圖
獨立型—孤島模型（island model）進行並行處理，多個解用“種群”表示，將“種群”分為若干個“子種群”分配給對應的處理器，每個處理器不僅獨立計算適應度，而且獨立進行選擇、重組交叉和變異操作。每次反覆運算完成以後，選擇“種群”中所有解的評價值中最高的解作為當前最優解。判斷這個解是否滿足終止條件的要求，滿足則退出，不滿足則繼續反覆運算，如圖7所示。
圖7孤島模型的並行演化計算架構圖
② 平行算法測試
並行測試結果很大程度取決於並行環境，三種運行模式硬體採用四核Core（TM） i3-4150 3.5Ghz、記憶體4G。針對同一批測試資料，對主從式並行和孤島式並行進行測試，分別採用三種演算法運行10次求平均值，利用平均耗時與未加速的演算法耗時進行對比，具體的演算法耗時見表3，成像任務規劃性能加速比如圖8。
表 2 三種演算法並行模型執行時間表
圖8智慧優化演算法並行加速比圖
在沒有並行運算的情況下，三種演算法運行耗時均較多；在採用並行框架後，三種演算法執行時間均有明顯下降；在主從式並行模型下，加速比分別為類比退火演算法1.614、差分演化演算法1.911、粒子群演算法1.990；在孤島式並行模型下加速比分別為差分演化演算法1.960、類比退火演算法2.254、粒子群演算法2.478。綜合比較兩種模型，加速效果都很明顯，但就兩種模型來看，孤島式並行模型加速效果更明顯，三種演算法的加速效果都高於主從式並行模型的加速比。
結 語
本文針對敏捷衛星任務規劃調度問題的特點，構建了基於成像品質懲罰係數的敏捷衛星任務規劃組合優化模型；並對常見智慧優化演算法（差分演化、粒子群和類比退火三種演算法）進行改進實現和測試評價；在此基礎上採用全域-主從式模型和獨立-孤島模型分別實現了三種演算法單機多核平行計算技術。實驗結果驗證了提出的演算法是可行的和有效的。
【參考文獻】
[1] 徐雪仁, 宮鵬, 黃學智,等. 資源衛星(可見光)遙感資料獲取任務調度優化演算法研究[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] 韓 偉,張學慶. 一種基於離散粒子群的多星任務規劃演算法[J].無線電工程,2015,45(1):1-4.
[4] Lemaı̂tre M, Verfaillie G, Jouhaud F, et al. Selecting and scheduling observations of agile satellites[J]. Aerospace Science and Technology, 2002, 6(5): 367-381.
[5] Mancel C, Lopez P. Complex optimization problems in space systems[C].13Th International Conference on Automated Planning & Scheduling (ICAPS'03). 2003.
[6] 李玉慶, 徐敏強, 王日新. 三軸穩定衛星點目標觀測任務優化調度技術[J].吉林大學學報:工學版, 2008, 38(6):1447-1451.
[7] 餘婧, 喜進軍, 于龍江,等. 敏捷衛星同軌多條帶拼幅成像模式研究[J]. 航天器工程, 2015, 24(2):27-34.
[8] 張新偉, 戴君, 劉付強. 敏捷遙感衛星工作模式研究[J]. 航天器工程, 2011, 20(4):32-38.
[9] 王任享．三線陣CCD影像衛星攝影測量原理[M].北京：測繪出版社，2006:1-23
[10] 孫 凱，邢立甯，陳英武等.基於分解優化策略的多敏捷衛星聯合對地觀測調度[J].電腦集成製造系統, 2013, 19(1):127-136
[11] 郝會成，姜維，李一軍.基於混合遺傳演算法的敏捷衛星任務規劃求解 [J].科學技術與工程. 2013, 13(17) :4972-4978
[12] 何磊, 劉曉路, 陳英武, 邢立寧. 面向敏捷衛星任務規劃的雲層建模及處理方法[J]. 系統工程與電子技術, 2016, 38(4): 852-858.
[13] 陳成. 時間依賴調度方法及在敏捷衛星任務規劃中的應用研究[D]. 國防科學技術大學. 2014
[14] 付鑫, 張峰, 馮占林,等. 基於平行計算的混沌遺傳演算法對反導預警雷達部署優化研究[J]. 中國電子科學研究院學報, 2016(3):276-282.
《中國電子科學研究院學報》歡迎各位專家、學者賜稿！投稿連結 http://kjpl.cbpt.cnki.net
電話：010-68893411
郵箱：dkyxuebao@vip.126.com
改進的粒子群通過相似度和聚集度，在染色體變異過程中，當種群聚集度大的時候，增加染色體的變異概率，從而使種群的多樣性增加，有利於尋找到更優的結果。⑤ 約束處理
敏捷衛星任務調度優化是一個帶約束的優化問題，需要考慮諸多約束。演算法運行過程中產生的邏輯規劃物件很有可能是不合法的，必須要對這樣的邏輯規劃物件進行處理。演算法在產生邏輯規劃物件經約束處理模組，對組合元任務集進行處理，得到新的滿足約束的組合元任務集。然後通過編碼，生成對應的修正的邏輯規劃物件，即規劃結果。約束處理模組依次按照以下順序進行約束處理：觀測時間衝突約束、數傳模式約束、指令範本約束、工作時間約束、檔下傳約束、能源約束。
圖 3 約束處理流程
⑥ 模擬測試結果
針對差分演化演算法、類比退火演算法以及粒子群演算法三種演算法分別提出了改進演算法。為了測試改進演算法的效果，選取了5批工程資料，每批資料包含300個觀測元任務，分別從綜合評價值（完成任務數、優先順序之和、俯仰角之和）以及耗時比較改進前後的演算法效果。改進後的差分演化演算法是使用了rankDE策略的演算法，改進後的類比退火演算法是遺傳類比退火演算法，改進後的粒子群演算法是通過引入相似度和聚集度的概念來增大變異概率的演算法。
圖 4 改進前後演算法的綜合評價值
圖 5 改進前後演算法的耗時
通過以上圖表資料的展示，可以看出：使用rankDE策略的差分演化演算法，其規劃結果及耗時與改進前的演算法規劃結果及耗時比較接近，改進效果並不明顯；遺傳類比退火演算法的改進效果比較明顯，改進後的規劃結果明顯較優，雖然耗時相對較多，但演算法改進後的耗時與差分演化演算法接近，屬於可接受範圍；引入相似度和聚集度使變異概率增大之後的粒子群演算法，其規劃結果比未改進的粒子群演算法的規劃結果較優，雖然其耗時也相應的增加了，但綜合其他演算法來看，其耗時仍少於差分演化演算法和類比退火演算法，說明粒子群演算法的改進效果較明顯。
4 平行算法研究
① 平行算法模型
由於智慧優化演算法的內在並行性，其並行處理方式是很自然的解決途徑。本文中，衛星任務規劃演算法在並行模式上採用全域型和獨立型。為了應用平行計算，必須把演算法分解成相互獨立的若干問題[14]。
全域型—主從式模型（mast-slave model）首先統一三種智慧優化演算法的編碼格式，然後在主執行緒中進行搜索，然後將演算法的每一次反覆運算中得到的解分配到對應的處理器獨立進行的編碼解析、約束檢查、評價和計算解的適應值等操作，然後將其返回給調用執行緒。主從式模型示意圖如圖6。
圖6主從式模型的並行演化計算架構圖
獨立型—孤島模型（island model）進行並行處理，多個解用“種群”表示，將“種群”分為若干個“子種群”分配給對應的處理器，每個處理器不僅獨立計算適應度，而且獨立進行選擇、重組交叉和變異操作。每次反覆運算完成以後，選擇“種群”中所有解的評價值中最高的解作為當前最優解。判斷這個解是否滿足終止條件的要求，滿足則退出，不滿足則繼續反覆運算，如圖7所示。
圖7孤島模型的並行演化計算架構圖
② 平行算法測試
並行測試結果很大程度取決於並行環境，三種運行模式硬體採用四核Core（TM） i3-4150 3.5Ghz、記憶體4G。針對同一批測試資料，對主從式並行和孤島式並行進行測試，分別採用三種演算法運行10次求平均值，利用平均耗時與未加速的演算法耗時進行對比，具體的演算法耗時見表3，成像任務規劃性能加速比如圖8。
表 2 三種演算法並行模型執行時間表
圖8智慧優化演算法並行加速比圖
在沒有並行運算的情況下，三種演算法運行耗時均較多；在採用並行框架後，三種演算法執行時間均有明顯下降；在主從式並行模型下，加速比分別為類比退火演算法1.614、差分演化演算法1.911、粒子群演算法1.990；在孤島式並行模型下加速比分別為差分演化演算法1.960、類比退火演算法2.254、粒子群演算法2.478。綜合比較兩種模型，加速效果都很明顯，但就兩種模型來看，孤島式並行模型加速效果更明顯，三種演算法的加速效果都高於主從式並行模型的加速比。
結 語
本文針對敏捷衛星任務規劃調度問題的特點，構建了基於成像品質懲罰係數的敏捷衛星任務規劃組合優化模型；並對常見智慧優化演算法（差分演化、粒子群和類比退火三種演算法）進行改進實現和測試評價；在此基礎上採用全域-主從式模型和獨立-孤島模型分別實現了三種演算法單機多核平行計算技術。實驗結果驗證了提出的演算法是可行的和有效的。
【參考文獻】
[1] 徐雪仁, 宮鵬, 黃學智,等. 資源衛星(可見光)遙感資料獲取任務調度優化演算法研究[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] 韓 偉,張學慶. 一種基於離散粒子群的多星任務規劃演算法[J].無線電工程,2015,45(1):1-4.
[4] Lemaı̂tre M, Verfaillie G, Jouhaud F, et al. Selecting and scheduling observations of agile satellites[J]. Aerospace Science and Technology, 2002, 6(5): 367-381.
[5] Mancel C, Lopez P. Complex optimization problems in space systems[C].13Th International Conference on Automated Planning & Scheduling (ICAPS'03). 2003.
[6] 李玉慶, 徐敏強, 王日新. 三軸穩定衛星點目標觀測任務優化調度技術[J].吉林大學學報:工學版, 2008, 38(6):1447-1451.
[7] 餘婧, 喜進軍, 于龍江,等. 敏捷衛星同軌多條帶拼幅成像模式研究[J]. 航天器工程, 2015, 24(2):27-34.
[8] 張新偉, 戴君, 劉付強. 敏捷遙感衛星工作模式研究[J]. 航天器工程, 2011, 20(4):32-38.
[9] 王任享．三線陣CCD影像衛星攝影測量原理[M].北京：測繪出版社，2006:1-23
[10] 孫 凱，邢立甯，陳英武等.基於分解優化策略的多敏捷衛星聯合對地觀測調度[J].電腦集成製造系統, 2013, 19(1):127-136
[11] 郝會成，姜維，李一軍.基於混合遺傳演算法的敏捷衛星任務規劃求解 [J].科學技術與工程. 2013, 13(17) :4972-4978
[12] 何磊, 劉曉路, 陳英武, 邢立寧. 面向敏捷衛星任務規劃的雲層建模及處理方法[J]. 系統工程與電子技術, 2016, 38(4): 852-858.
[13] 陳成. 時間依賴調度方法及在敏捷衛星任務規劃中的應用研究[D]. 國防科學技術大學. 2014
[14] 付鑫, 張峰, 馮占林,等. 基於平行計算的混沌遺傳演算法對反導預警雷達部署優化研究[J]. 中國電子科學研究院學報, 2016(3):276-282.
《中國電子科學研究院學報》歡迎各位專家、學者賜稿！投稿連結 http://kjpl.cbpt.cnki.net
電話：010-68893411
郵箱：dkyxuebao@vip.126.com