趙超

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

0 引言

對(duì)地觀測衛(wèi)星是目前國際上發(fā)射數(shù)量最多，且極具代表性和應(yīng)用范圍最廣的衛(wèi)星類型。自1962年誕生空間遙感技術(shù)至今，據(jù)統(tǒng)計(jì)全球已發(fā)射對(duì)地觀測衛(wèi)星500多顆。在幾十年來的發(fā)展中，我國衛(wèi)星對(duì)地觀測事業(yè)獲得了長足發(fā)展，隨著成像任務(wù)需求的不斷增加，任務(wù)類型愈加多樣化復(fù)雜化，再加上對(duì)地觀測衛(wèi)星數(shù)量的增加，這些都很大程度上增加了衛(wèi)星任務(wù)規(guī)劃的復(fù)雜度。因此有必要對(duì)衛(wèi)星任務(wù)進(jìn)行綜合規(guī)劃，建立衛(wèi)星任務(wù)規(guī)劃系統(tǒng)[1]。對(duì)衛(wèi)星資源科學(xué)規(guī)劃合理調(diào)度，實(shí)現(xiàn)衛(wèi)星任務(wù)優(yōu)化配置，這是目前迫切需要解決的重要問題。結(jié)合以往的文獻(xiàn)分析，衛(wèi)星任務(wù)規(guī)劃問題屬于NP-hard問題，求解空間會(huì)隨著衛(wèi)星任務(wù)與資源數(shù)量的增加急劇增大，對(duì)于大規(guī)模任務(wù)規(guī)劃問題，無法在合理時(shí)間內(nèi)最優(yōu)求解[2]。對(duì)此，理論研究界認(rèn)為智能算法可以評(píng)價(jià)函數(shù)對(duì)解優(yōu)劣的判定結(jié)果，在目標(biāo)函數(shù)與約束要求方面比較寬松，與傳統(tǒng)算法相比智能算法效率更高，每一個(gè)群個(gè)體的能力都十分簡單，并且執(zhí)行時(shí)間也相對(duì)較短，實(shí)現(xiàn)了較強(qiáng)的魯棒性[3]。本文研究的粒子群算法就作為其中一類，因其卓有成效的最優(yōu)解求解問題被廣泛應(yīng)用于各領(lǐng)域，在此算法基礎(chǔ)上設(shè)計(jì)衛(wèi)星任務(wù)規(guī)劃系統(tǒng)，結(jié)合仿真實(shí)驗(yàn)證明本次系統(tǒng)的設(shè)計(jì)簡單靈活，經(jīng)過優(yōu)化之后的算法可以有效求解問題。

1 PSO算法原理

根據(jù)資源的具體分配特點(diǎn)，定義第i個(gè)粒子的當(dāng)前位置為：

當(dāng)前歷史p為當(dāng)前歷史最優(yōu)位置：

當(dāng)前群體最優(yōu)解標(biāo)識(shí)為：

定義粒子群方程式如下：

由此可見粒子會(huì)因?yàn)樽陨砟壳八幬恢煤途唧w速度，以及歷史最佳所在位形成的方位關(guān)系確定新速度。

2 DPSO資源調(diào)度優(yōu)化算法

根據(jù)上述對(duì)PSO算法原理的分析，提出DPSO資源調(diào)度優(yōu)化算法，通過將全部任務(wù)的集合根據(jù)任務(wù)的具體時(shí)間和接收資源劃分為多個(gè)子集，在資源調(diào)度后面臨的整個(gè)問題分解為多個(gè)子問題，這樣預(yù)處理子集后再進(jìn)行測控任務(wù)分組和DPSO算法優(yōu)化，如圖1所示為本次優(yōu)化DPSO的算法流程圖。

圖1 算法流程圖

2.1 確定適應(yīng)度函數(shù)

適應(yīng)度函數(shù)受以下四個(gè)因素的影響：（1）觀測任務(wù)的優(yōu)先級(jí)程度，優(yōu)先級(jí)越高越好；（2）完成的觀測任務(wù)的數(shù)量，數(shù)量越多越好；（3）完成觀測任務(wù)所用的接收時(shí)間間隔，間隔越小越好；（4）同時(shí)完成觀測任務(wù)所用的接收資源數(shù)量，接收資源數(shù)量越少越好。

具體收益公式如下：

2.2 求解步驟

（1）預(yù)處理。首先要確定完成本次任務(wù)的基礎(chǔ)信息，有衛(wèi)星名、觀測任務(wù)的開始結(jié)束時(shí)間、任務(wù)優(yōu)先級(jí)、記錄速率、地面站名稱、接收開始結(jié)束時(shí)間、回放速率等。離散粒子群類似于基本粒子群，粒子目前的具體狀態(tài)、粒子的歷史飛行最優(yōu)位置記錄、粒子群的最優(yōu)位置歷史記錄這三個(gè)因素都會(huì)影響更新粒子的所在位。在粒子群具體資源合理分配方面，粒子飛行速度根據(jù)粒子內(nèi)部的置換操作和粒子間的替換操作表示，在粒子的“慣性”操作狀態(tài)下，可以對(duì)粒子內(nèi)部結(jié)構(gòu)進(jìn)行調(diào)整，獲得粒子更新所在位。計(jì)算置換后粒子的適應(yīng)度結(jié)果，如果結(jié)果與最優(yōu)值更加接近，這個(gè)置換過程即代表優(yōu)勢置換，否則是劣勢置換，這就需要對(duì)i、j根據(jù)一定概率進(jìn)行置換[4]。

（2）優(yōu)化任務(wù)安排。在離散粒子群的粒子擁有“自我認(rèn)知”，粒子可以依據(jù)歷史最優(yōu)飛行記錄調(diào)整自身所在位，在粒子“慣性”操作的基礎(chǔ)上執(zhí)行，疊加至粒子“慣性”操作之上，可以兩粒子間替換操作，獲得替換區(qū)間，并對(duì)此區(qū)間內(nèi)最有粒子“自我認(rèn)知”的部分內(nèi)容進(jìn)行替換，其中學(xué)習(xí)因子使粒子具有自我總結(jié)、向歷史最優(yōu)學(xué)習(xí)的能力。

（3）任務(wù)排序計(jì)算適應(yīng)值。判斷替換是否滿足性能約束條件，如果不滿足需要設(shè)置循環(huán)j=j-1直至滿足約束，或者i＜j；如果替換滿足約束條件，計(jì)算替換后粒子的適應(yīng)度，如果此適應(yīng)度遠(yuǎn)遠(yuǎn)大于目前適應(yīng)度，則作為優(yōu)勢替換，否則作為劣勢替換。粒子在整個(gè)粒子群的最優(yōu)歷史記錄，實(shí)現(xiàn)了粒子自身位置調(diào)整，此操作在上一步的基礎(chǔ)上完成。

3 構(gòu)建衛(wèi)星任務(wù)規(guī)劃系統(tǒng)

3.1 系統(tǒng)架構(gòu)

衛(wèi)星任務(wù)規(guī)劃系統(tǒng)在設(shè)計(jì)中需要考慮多方因素，包括衛(wèi)星目標(biāo)可見性、衛(wèi)星載荷使用規(guī)則、衛(wèi)星地面接收可見性、任務(wù)沖突、數(shù)據(jù)傳輸能力等。尤其近年來隨著不斷提升的衛(wèi)星靈巧度，給目標(biāo)觀測提供了諸多可選擇的機(jī)會(huì)，所以面對(duì)更復(fù)雜化的衛(wèi)星任務(wù)規(guī)劃需求，應(yīng)當(dāng)考慮多方因素。對(duì)衛(wèi)星運(yùn)行軌跡預(yù)報(bào)后，根據(jù)所獲取的特定目標(biāo)，對(duì)于可用時(shí)間窗口和衛(wèi)星，獲取衛(wèi)星任務(wù)時(shí)間窗口，建立任務(wù)規(guī)劃模型，選擇數(shù)據(jù)傳輸任務(wù)與目標(biāo)任務(wù)，具體安排任務(wù)時(shí)間從而消除沖突。如圖2所示為本次基于離散粒子群算法設(shè)計(jì)的衛(wèi)星任務(wù)規(guī)劃系統(tǒng)架構(gòu)圖，主要包括以下三個(gè)子系統(tǒng)。

圖2 衛(wèi)星任務(wù)規(guī)劃系統(tǒng)架構(gòu)圖

任務(wù)預(yù)處理環(huán)節(jié)：主要負(fù)責(zé)面向獲取的衛(wèi)星觀測任務(wù)和數(shù)傳接收窗口相關(guān)信息，對(duì)所接收的信息逐一驗(yàn)證之后，依據(jù)具體規(guī)則和標(biāo)準(zhǔn)來判斷計(jì)劃可行性，對(duì)無法安排的任務(wù)以及無法使用的接收資源直接舍棄，如在最后一個(gè)接收后面的觀測任務(wù)、在最早觀測任務(wù)前的接收資源、可利用時(shí)間過短的接收資源。

任務(wù)規(guī)劃環(huán)節(jié)：任務(wù)規(guī)劃環(huán)節(jié)是核心環(huán)節(jié)，依據(jù)業(yè)務(wù)規(guī)則和有關(guān)約束條件，對(duì)觀測任務(wù)進(jìn)行數(shù)傳窗口資源分配，隨機(jī)初始化種群，描述最優(yōu)目標(biāo)函數(shù)，迭代收斂至滿足終止條件后優(yōu)化形成合理的衛(wèi)星任務(wù)規(guī)劃方案。

計(jì)劃生成環(huán)節(jié)：依據(jù)任務(wù)規(guī)劃方案進(jìn)行解譯，最終生成衛(wèi)星可執(zhí)行的觀測和數(shù)傳動(dòng)作，同時(shí)完成接收任務(wù)時(shí)間的確定，統(tǒng)籌協(xié)調(diào)衛(wèi)星和地面站資源完成任務(wù)安排。

3.2 任務(wù)規(guī)劃建模

根據(jù)衛(wèi)星任務(wù)優(yōu)化方向構(gòu)建對(duì)應(yīng)的優(yōu)化目標(biāo)函數(shù)，在設(shè)計(jì)衛(wèi)星任務(wù)規(guī)劃系統(tǒng)時(shí)，一般情況下會(huì)選擇在滿足衛(wèi)星固存容量、衛(wèi)星能源、執(zhí)行任務(wù)時(shí)間間隔等約束條件下，獲得最大化任務(wù)完成收益，包括盡可能多地安排任務(wù)，同時(shí)保證安排的數(shù)傳窗口盡可能靠前，公式如下：

4 模擬仿真

對(duì)本文基于離散粒子群算法的衛(wèi)星任務(wù)規(guī)劃系統(tǒng)進(jìn)行仿真算例分析，將離散粒子群算法對(duì)比窮舉算法，驗(yàn)證多星任務(wù)規(guī)劃中應(yīng)用此系統(tǒng)的離散粒子群算法能力。對(duì)于對(duì)地觀測衛(wèi)星任務(wù)規(guī)劃領(lǐng)域中，驗(yàn)證沒有標(biāo)準(zhǔn)的數(shù)據(jù)集，運(yùn)用STK工具包仿真生成模擬衛(wèi)星及對(duì)應(yīng)的地面站，與衛(wèi)星對(duì)地觀測的任務(wù)特點(diǎn)相結(jié)合，對(duì)一定時(shí)間窗口內(nèi)進(jìn)行任務(wù)場景匹配，模擬生成對(duì)應(yīng)的觀測任務(wù)和數(shù)傳窗口，隨機(jī)為任務(wù)賦值對(duì)應(yīng)的優(yōu)先級(jí)，每個(gè)觀測目標(biāo)均為正整數(shù)任務(wù)優(yōu)先級(jí)，利用衛(wèi)星模擬軟件仿真生成衛(wèi)星任務(wù)[6-7]。設(shè)定本次模擬衛(wèi)星對(duì)地觀測任務(wù)數(shù)目，分別為20、30、35、40、50、60、80、100，對(duì)應(yīng)數(shù)傳窗口數(shù)量為10、10、25、40、40、40、50、60。分別采用窮舉算法與離散粒子群算法，進(jìn)行同組數(shù)據(jù)求解，設(shè)定離散粒子群共計(jì)500個(gè)粒子數(shù)，進(jìn)行一萬次迭代尋求最優(yōu)解，設(shè)置0.9為慣性權(quán)重，3個(gè)置換門限值設(shè)為0.0005，得到仿真模擬結(jié)果如表1所示。

根據(jù)表1模擬仿真處理結(jié)果，可以發(fā)現(xiàn)隨著衛(wèi)星任務(wù)數(shù)量的不斷增加，應(yīng)用本文設(shè)計(jì)的基于離散粒子群算法的系統(tǒng)完成任務(wù)的具體時(shí)間幾乎表現(xiàn)為線性增長，而窮舉法耗時(shí)則呈現(xiàn)指數(shù)增長。由于面對(duì)多星任務(wù)規(guī)劃時(shí)，應(yīng)當(dāng)從根源認(rèn)識(shí)這一約束規(guī)劃問題，而約束規(guī)劃作為NP問題，在面對(duì)較大問題規(guī)模的情況下，使用窮舉算法的處理效率就不高。離散粒子群算法的具體執(zhí)行時(shí)間也會(huì)隨著問題規(guī)模的增加而增長，這也在一定程度上證明了本次設(shè)計(jì)的衛(wèi)星任務(wù)規(guī)劃系統(tǒng)的良好拓展性。同時(shí)，由于離散粒子群算法利用不同粒子迭代過程中本身具備良好的并行可操作性，可以對(duì)大規(guī)模多星任務(wù)規(guī)劃問題進(jìn)行有效處理。

5 結(jié)語

綜上所述，本文基于離散粒子群算法，設(shè)計(jì)了包括任務(wù)預(yù)處理、任務(wù)規(guī)劃、計(jì)劃生成三大功能的衛(wèi)星任務(wù)規(guī)劃系統(tǒng)。根據(jù)構(gòu)建的任務(wù)規(guī)劃模型，運(yùn)用粒子群算法優(yōu)化模擬求解，通過模擬結(jié)果發(fā)現(xiàn)，離散粒子群算法可以對(duì)大規(guī)模多星任務(wù)規(guī)劃問題進(jìn)行有效處理，特別是在任務(wù)及數(shù)傳窗口數(shù)量較大的情況下，能夠快速收斂，從而有效解決大規(guī)模的衛(wèi)星任務(wù)規(guī)劃問題。