基于多目標(biāo)優(yōu)化的中繼衛(wèi)星重調(diào)度方法

龍運軍，李恒偉，尹 謙，郭 磊

(1.北京空間信息中繼傳輸技術(shù)研究中心，北京 100094；2.中南大學(xué) 交通運輸工程學(xué)院，湖南 長沙 410075)

0 引言

隨著衛(wèi)星數(shù)量增多，航天器之間的數(shù)據(jù)交流需求越來越大，對中繼衛(wèi)星的需求也變大。中繼衛(wèi)星的運行軌道在地面36 000 km之上，軌道高度高，覆蓋面廣。3顆中繼衛(wèi)星組成的衛(wèi)星網(wǎng)絡(luò)，能全部覆蓋300～2 000 km軌道上的衛(wèi)星，實現(xiàn)數(shù)據(jù)中繼和對衛(wèi)星的連續(xù)跟蹤，使得衛(wèi)星數(shù)據(jù)傳輸對地面測控站的依賴減小，節(jié)省衛(wèi)星數(shù)據(jù)傳輸?shù)某杀尽?/p>

隨著對中繼衛(wèi)星的需求增大，如何合理地調(diào)配中繼衛(wèi)星資源，滿足用戶的需求，成為提高整個系統(tǒng)利用效率的關(guān)鍵。當(dāng)前，對中繼衛(wèi)星的調(diào)度方法研究大多是在特定的理想情況下，對于單目標(biāo)需求進(jìn)行優(yōu)化。

現(xiàn)有中繼衛(wèi)星系統(tǒng)調(diào)度研究主要分為對應(yīng)用模式的研究和對算法的研究。在應(yīng)用模式方面，Hajghassem[1]對NASA的中繼衛(wèi)星系統(tǒng)在航天網(wǎng)絡(luò)的應(yīng)用模式進(jìn)行了分析。Reddy[2]針對單窗口和單根天線的約束調(diào)度問題進(jìn)行了求解，提出的動態(tài)算法能夠在約束條件下獲得優(yōu)化結(jié)果。Rojanasoonthon[3]針對多時間窗口和多址鏈路約束調(diào)度進(jìn)行求解，采用了分支定界法來進(jìn)行最優(yōu)解的求解。

在算法方面，顧中舜[4]將蟻群算法運用到調(diào)度問題中，與經(jīng)典的遺傳算法和模擬退火算法進(jìn)行比較，發(fā)現(xiàn)蟻群算法更適合中繼衛(wèi)星調(diào)度問題，無論是時間還是精度都更優(yōu)。Liu等[5]利用時間窗口的靈活范圍和數(shù)學(xué)特征，提出了一種調(diào)度算法，與其他經(jīng)典算法對比，提高了約11%的任務(wù)完成率。He等[6]基于中繼衛(wèi)星動態(tài)調(diào)度中的多址問題，構(gòu)建了一種基于隨機優(yōu)化的數(shù)學(xué)架構(gòu)，將問題轉(zhuǎn)化為一個天線內(nèi)嵌多個的形式，并利用了2種算法進(jìn)行求解。張彥等[7]主要針對新增任務(wù)和任務(wù)時間變化等動態(tài)擾動建立了中繼衛(wèi)星動態(tài)調(diào)度模型，并提出了動態(tài)擴(kuò)展/刪除樹搜索算法，以刪除任務(wù)和調(diào)整任務(wù)之比作為指導(dǎo)，提高了算法效率，并證明了其能夠在實際中運用。

上述研究主要側(cè)重于中繼衛(wèi)星系統(tǒng)靜態(tài)任務(wù)調(diào)度。隨著中繼衛(wèi)星的運用范圍越來越大，各類型用戶目標(biāo)對中繼衛(wèi)星系統(tǒng)資源需求動態(tài)性越來越高，而且在未來戰(zhàn)爭中，中繼衛(wèi)星系統(tǒng)作為重要戰(zhàn)略資源是敵人破壞摧毀的目標(biāo)。面對海量應(yīng)急中繼使用需求或資源受損時，如何快速重新進(jìn)行資源分配調(diào)整計劃，成為發(fā)揮或保持整個中繼衛(wèi)星系統(tǒng)效能的關(guān)鍵。當(dāng)前研究對中繼衛(wèi)星的調(diào)度方法大多是針對單目標(biāo)需求進(jìn)行優(yōu)化，如最大化任務(wù)完成度，對于多目標(biāo)情況的研究鮮有涉及。

因此，本文針對中繼衛(wèi)星系統(tǒng)接收海量臨時申請或者中繼資源故障時如何快速進(jìn)行重調(diào)度問題進(jìn)行研究，以滿足最大化任務(wù)完成率和最小化動態(tài)擾動測度2個互相沖突的需求為優(yōu)化目標(biāo)，建立了調(diào)度過程中突發(fā)新增任務(wù)的動態(tài)調(diào)度的模型，基于NSGA-Ⅱ多目標(biāo)優(yōu)化算法，對中繼衛(wèi)星進(jìn)行動態(tài)重調(diào)度。

1 中繼衛(wèi)星應(yīng)用模式

1.1 系統(tǒng)工作原理和流程

中繼衛(wèi)星系統(tǒng)是指將中繼衛(wèi)星發(fā)射至地球的靜止軌道，并將地面站作為終端，對中低軌道衛(wèi)星進(jìn)行大面積覆蓋，提供測控通信和數(shù)據(jù)中繼的系統(tǒng)。

中繼衛(wèi)星系統(tǒng)概貌如圖1所示，可以將整個中繼衛(wèi)星系統(tǒng)分為3個部分：第1部分是中繼衛(wèi)星；第2部分是用戶層，由多種用戶航天器構(gòu)成；第3部分為地面設(shè)施，主要包含用戶航天器及中繼衛(wèi)星的管理中心和地面網(wǎng)絡(luò)終端。

圖1 中繼衛(wèi)星系統(tǒng)概貌Fig.1 Overview of relay satellite system

由于用戶層與地面可見時間較短，需要利用中繼衛(wèi)星進(jìn)行數(shù)據(jù)中轉(zhuǎn)，在用戶航天器與中繼衛(wèi)星的可見時間窗口內(nèi)，將需要傳給地面的數(shù)據(jù)信息傳給中繼衛(wèi)星。用戶航天器管理部門需要根據(jù)中繼衛(wèi)星管理部門對外發(fā)布的下一周期衛(wèi)星資源，以及自身的任務(wù)需求，向中繼衛(wèi)星的管理部門提交任務(wù)申請，中繼衛(wèi)星管理部門對用戶需求進(jìn)行整理，科學(xué)合理地分配有限的衛(wèi)星資源，并生成調(diào)度方案。對于突發(fā)情況，中繼衛(wèi)星管理部門會及時啟用相應(yīng)的動態(tài)調(diào)度算法進(jìn)行調(diào)整，保證中繼衛(wèi)星服務(wù)的正常運行，并獲得動態(tài)調(diào)度方案。最后，各部門依據(jù)最終方案，完成地面站和用戶航天器之間的數(shù)據(jù)傳輸任務(wù)。

1.2 系統(tǒng)應(yīng)用模式分析

本文的中繼衛(wèi)星系統(tǒng)應(yīng)用模式采用傳統(tǒng)的通用模式，可歸納如下[8-10]：

① 用戶管理部門提交的任務(wù)申請信息包括其任務(wù)的緊急程度、需求的服務(wù)時間和窗口等。提交的每一項任務(wù)只能所屬一個用戶航天器，通常對應(yīng)一個或多個中繼衛(wèi)星服務(wù)時間窗口，任務(wù)必須一次性完成。

② 在用戶申請完畢后，由中繼衛(wèi)星管理部門進(jìn)行統(tǒng)計，并通過靜態(tài)調(diào)度算法，根據(jù)用戶需求生成合理的衛(wèi)星調(diào)度方案，依據(jù)調(diào)度方案完成任務(wù)。

③ 對于在中繼衛(wèi)星執(zhí)行任務(wù)過程中可能出現(xiàn)的動態(tài)擾動，如緊急新增任務(wù)、資源失效等任務(wù)變化，導(dǎo)致靜態(tài)調(diào)度方案中部分任務(wù)可能無法按原有方案進(jìn)行執(zhí)行時，需要緊急啟用動態(tài)調(diào)度算法，進(jìn)行動態(tài)調(diào)度，來滿足任務(wù)需求；失效資源上已安排的任務(wù)均作為新增任務(wù)申請進(jìn)行重新分配。

④ 在靜態(tài)調(diào)度方案和動態(tài)方案生成完畢后，獲得一個新的方案，中繼衛(wèi)星將按新的方案執(zhí)行任務(wù)。同時，中繼衛(wèi)星管理部門需要將任務(wù)執(zhí)行情況下達(dá)至各個用戶及所對應(yīng)的地面站。

2 考慮任務(wù)擾動的中繼衛(wèi)星重調(diào)度模型

中繼衛(wèi)星系統(tǒng)調(diào)度問題復(fù)雜，涉及變量眾多，約束條件繁雜，因此本文在構(gòu)建模型時做了適當(dāng)簡化，降低求解難度。

2.1 問題假設(shè)

為降低問題建模與求解難度，對中繼衛(wèi)星任務(wù)調(diào)度問題做了簡化，做如下基本假設(shè)[11-13]：

① 不考慮不同任務(wù)間可能存在的相關(guān)性；

② 所有任務(wù)被執(zhí)行時必須一次性完成；

③ 用戶申請的服務(wù)時間窗口為固定的時間窗口，不具備彈性。

2.2 變量符號說明

本文構(gòu)建的中繼衛(wèi)星重調(diào)度模型將要用到的變量定義如表1所示。

表1 符號定義Tab.1 Symbol definition

2.3 模型決策變量和優(yōu)化目標(biāo)

2.3.1 決策變量

在本文選定的應(yīng)用模式下，整個問題實際上就是對用戶申請的任務(wù)確定6個要素的信息：任務(wù)的執(zhí)行緊急程度、任務(wù)執(zhí)行的最早開始時間和最晚結(jié)束時間、任務(wù)的執(zhí)行所需時間、任務(wù)能被執(zhí)行的天線和任務(wù)對應(yīng)用戶航天器。故模型的決策變量為xtrj,actstrj和acdtrj。

決策變量xtrj的值只有0或1兩種，用來表示任務(wù)是否被成功執(zhí)行，成功其值為1，不成功則為0。決策變量actstrj表示在可見窗口j內(nèi)，任務(wù)t在被資源r執(zhí)行的開始時間，為一個連續(xù)變量。決策變量acdtrj，表示在可見窗口j內(nèi)，任務(wù)t在被資源r執(zhí)行的實際持續(xù)時間，為一個連續(xù)變量。

2.3.2 優(yōu)化目標(biāo)

在中繼衛(wèi)星重調(diào)度模型中，選取最大化任務(wù)執(zhí)行率和最小化動態(tài)擾動測度為目標(biāo)函數(shù)。最大化任務(wù)完成率是指算法求解時，在滿足約束條件的情況下，向任務(wù)完成率最大的解靠近。

動態(tài)擾動測度(DDM)是指當(dāng)動態(tài)擾度發(fā)生后，經(jīng)過算法產(chǎn)生的動態(tài)調(diào)度方案與之前靜態(tài)調(diào)度的方案的差異程度[14]：

ψ(s0,snew)=λdelndel+λcnc，

(1)

式中，s0表示靜態(tài)調(diào)度的方案；snew表示動態(tài)調(diào)度后產(chǎn)生的新方案；ndel表示從靜態(tài)至動態(tài)調(diào)度刪除的任務(wù)與除新增任務(wù)外另增加的任務(wù)數(shù)量之和；nc表示從靜態(tài)調(diào)度到動態(tài)調(diào)度的任務(wù)調(diào)整數(shù)量(比如任務(wù)從第1個衛(wèi)星調(diào)整到第2個衛(wèi)星執(zhí)行)數(shù)量；λ表示任務(wù)的權(quán)重。重調(diào)度的目標(biāo)函數(shù)為：

(2)

minf2=λdelndel+λcnc。

(3)

本文建立的中繼衛(wèi)星重調(diào)度模型中，將最大化任務(wù)完成率作為本文的優(yōu)化目標(biāo)，即希望通過算法求解時，在滿足約束條件的情況下，向任務(wù)完成率最大的解靠近。

2.4 約束條件

在中繼衛(wèi)星系統(tǒng)調(diào)度問題中，主要涉及兩方面約束：一方面為資源約束；另一方面為任務(wù)需求約束。

2.4.1 資源約束

資源約束包括可見時間窗口約束和資源的使用約束。

① 可見時間窗口約束

中繼衛(wèi)星與用戶航天器之間可以傳輸數(shù)據(jù)的時間稱為可見時間窗口，要求在任務(wù)被執(zhí)行的過程中，必須與其所屬的用戶航天器對應(yīng)的與中繼衛(wèi)星的可見時間窗口匹配。由此可得約束條件C1,C2：

(4)

(5)

C1表示任務(wù)執(zhí)行的開始時間不能小于其所屬的用戶航天器與中繼衛(wèi)星的可見時間窗口的開始時間。C2表示任務(wù)執(zhí)行的結(jié)束時間不能大于其所屬的用戶航天器與中繼衛(wèi)星的可見時間窗口的結(jié)束時間。

② 天線資源約束

在中繼衛(wèi)星重調(diào)度問題中，一個天線資源在任意時刻只能執(zhí)行一個任務(wù)，得到約束C3：

C3:(adjust+Dmr+rec)∩(adjust+Dnr+rec)=φ,

?t∈T,r∈R,m∈T。

(6)

2.4.2 任務(wù)需求約束

任務(wù)方面的約束包括任務(wù)執(zhí)行時間約束和任務(wù)執(zhí)行約束。

① 任務(wù)服務(wù)時長約束

在中繼衛(wèi)星重調(diào)度問題中，任務(wù)在被調(diào)度時，分配的任務(wù)時長必須等于任務(wù)需求的服務(wù)時長，可得約束C4：

(7)

② 任務(wù)時間窗口約束

與可見時間窗口相似，任務(wù)不是時時都能夠被執(zhí)行，每個任務(wù)都有一個能被執(zhí)行的窗口，稱為服務(wù)時間窗口，因此任務(wù)的執(zhí)行時間都應(yīng)在任務(wù)服務(wù)時間窗口內(nèi)?？傻眉s束C5,C6：

(8)

(9)

C5表示任務(wù)的執(zhí)行時刻應(yīng)遲于其對應(yīng)的服務(wù)時間窗口的開始時間。C6表示任務(wù)的執(zhí)行結(jié)束時刻應(yīng)早于其對應(yīng)的服務(wù)時間窗口的結(jié)束時刻。

③ 任務(wù)執(zhí)行約束

在中繼衛(wèi)星重調(diào)度問題中，中繼衛(wèi)星執(zhí)行的任務(wù)只能被一個天線選擇執(zhí)行，同時也只能選擇一個可見時間窗口被執(zhí)行，可得約束C7,C8：

(10)

(11)

2.5 重調(diào)度數(shù)學(xué)模型

本文所構(gòu)建的中繼衛(wèi)星多目標(biāo)重調(diào)度模型以任務(wù)完成率最大化和動態(tài)擾動測度最小化為目標(biāo)，以資源和任務(wù)需求為約束，構(gòu)建的具體數(shù)學(xué)模型如下：

minf2=λdelndel+λcnc，

3 基于多目標(biāo)優(yōu)化的重調(diào)度算法

本文研究的內(nèi)容為多目標(biāo)優(yōu)化下的中繼衛(wèi)星的重調(diào)度?；诙嗄繕?biāo)優(yōu)化，選取NSGA-Ⅱ這一多目標(biāo)優(yōu)化領(lǐng)域內(nèi)的流行算法作為本文動態(tài)調(diào)度問題的優(yōu)化算法，探究其對中繼衛(wèi)星動態(tài)調(diào)度的優(yōu)化效果。

3.1 算法簡介

NSGA-Ⅱ作為優(yōu)化算法的一種，基于遺傳算法改進(jìn)而來。遺傳算法作為經(jīng)典的智能優(yōu)化算法，是以達(dá)爾文生物學(xué)中“優(yōu)勝劣汰”為背景，以自然選擇和遺傳作為原理，模擬生物進(jìn)化的一種算法。NSGA-Ⅱ算法繼承了遺傳算法優(yōu)勝劣汰的思想，同時引進(jìn)了Pareto支配關(guān)系和非支配排序、種群擁擠度和精英保留策略等思想[15]。Pareto支配關(guān)系和非支配排序主要是為多目標(biāo)優(yōu)化服務(wù)，種群擁擠度的提出是為了得到最優(yōu)解在空間中形成均勻的分布，精英保留策略則是為了更方便地選擇出更為優(yōu)秀的個體，遺傳至下一代。

3.2 流程設(shè)計

① 生成靜態(tài)調(diào)度方案

首先，根據(jù)用戶提交的任務(wù)信息和中繼衛(wèi)星資源信息，利用靜態(tài)調(diào)度算法生成初始的靜態(tài)調(diào)度方案。主要是通過任務(wù)的服務(wù)窗口和中繼衛(wèi)星與用戶航天器的可見時間窗口的交集生成任務(wù)的可用時間，運用算法進(jìn)行初步的任務(wù)調(diào)度，得到靜態(tài)調(diào)度方案，方便后續(xù)動態(tài)擾度測定計算。

② 對第一代種群進(jìn)行非支配排序

靜態(tài)調(diào)度后進(jìn)行動態(tài)調(diào)度初始方案的生成。在動態(tài)調(diào)度中，要保證新增任務(wù)必須執(zhí)行，然后考慮執(zhí)行新增任務(wù)后，資源和任務(wù)的匹配生成動態(tài)調(diào)度的初始解，即整個進(jìn)化算法的初始種群。然后計算種群中每個個體的目標(biāo)函數(shù)值，本文考慮的多目標(biāo)為最大化任務(wù)完成率和最小化動態(tài)擾動測度，依據(jù)多目標(biāo)函數(shù)值，對每個個體進(jìn)行非支配排序。

③ 選擇、交叉、變異

選擇是指從父代中選出優(yōu)秀的個體，進(jìn)行交配產(chǎn)生下一代。在遺傳算法中選擇的方式有很多，如輪盤賭和錦標(biāo)賽選擇法等。NSGA-Ⅱ中運用的錦標(biāo)賽選擇法，即從種群N個個體中，選出k個個體，一般取N的一半，然后根據(jù)個體的適應(yīng)度(Pareto等級和擁擠度)，將表現(xiàn)最好的個體放入交配集。

交叉之前進(jìn)行編碼，將每個任務(wù)和執(zhí)行任務(wù)的衛(wèi)星都用二進(jìn)制的方式表達(dá)出來。染色體編碼示意如圖2所示。

將所有的任務(wù)編碼完畢后，一個任務(wù)及其執(zhí)行情況將會對應(yīng)一段同樣長度的編碼，然后進(jìn)行交叉，產(chǎn)生新的2段不同的編碼，本文選用兩點交叉法，實現(xiàn)過程不復(fù)雜，也有較好的隨機性。兩點交叉法示意如圖3所示。

圖3 兩點交叉法示意Fig.3 Schematic diagram of two-point crossover method

④ 精英選擇

將輸出的子代與父代合并為同一個種群，計算種群中每個個體的目標(biāo)函數(shù)值，即最大化任務(wù)完成率和最小化動態(tài)擾動測度，依據(jù)多目標(biāo)函數(shù)值，對每個個體進(jìn)行非支配排序，然后對恰好無法全部放入種群的那層Pareto層級個體進(jìn)行擁擠度計算，保留擁擠度較大的個體進(jìn)入下一代。精英選擇示意如圖4所示。

圖4 精英選擇示意Fig.4 Schematic diagram of elite selection

⑤ 算法結(jié)束

將上面的4個步驟循環(huán)一次，代表整個種群進(jìn)化了一次，持續(xù)循環(huán)直到滿足輸出條件，得到最后的優(yōu)化結(jié)果，即重調(diào)度的最終結(jié)果。

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

4.1 任務(wù)需求信息

① 任務(wù)編號

在實驗中，為了方便，任務(wù)直接從1開始編號。

② 任務(wù)對應(yīng)航天器

任務(wù)實際能夠被執(zhí)行的時間，實際上為任務(wù)對應(yīng)航天器和中繼衛(wèi)星的可見時間窗口和任務(wù)的執(zhí)行時間窗口的交集。每一個任務(wù)相應(yīng)地對應(yīng)一個航天器，在本文的實驗中，采用均勻生成隨機數(shù)的方法，將任務(wù)與航天器一一匹配。

ust=ceil(λ*us)，

(12)

式中，ust表示任務(wù)的航天器編號；ceil表示向上取整；λ表示(0，1)的隨機數(shù)；us表示每個實驗中用戶航天器的數(shù)量。

③ 任務(wù)服務(wù)時間

由用戶提交任務(wù)能夠被執(zhí)行的開始時間和結(jié)束時間。在本文的仿真實驗中，通過隨機數(shù)和正態(tài)分布來生成。

stst=λ*86 400，

(13)

stet=stst+abs(normrnd(mean,std))，

(14)

式中，stst表示開始時間；stet表示結(jié)束時間；mean表示整個服務(wù)時間正態(tài)分布的均值；std表示整個服務(wù)時間正態(tài)分布的標(biāo)準(zhǔn)差；abs表示取絕對值。

④ 任務(wù)服務(wù)時長

用戶根據(jù)其需求對任務(wù)進(jìn)行評估后提交的信息。在本文的實驗中，根據(jù)隨機數(shù)和正態(tài)分布來生成。任務(wù)服務(wù)時長為：

dt=abs(normrnd(mean,std))。

(15)

部分任務(wù)數(shù)據(jù)信息如表2所示。

表2 任務(wù)數(shù)據(jù)信息表Tab.2 Task data information

4.2 仿真實驗參數(shù)設(shè)定

在本文的實驗中，選擇86 400 s作為調(diào)度周期。然后根據(jù)不同的變量構(gòu)建實驗，觀察不同變量的變化對整個動態(tài)調(diào)度優(yōu)化效果的影響。最大參數(shù)規(guī)?？梢赃_(dá)到500個任務(wù)申請、3顆中繼衛(wèi)星、10個航天器。本次實驗的環(huán)境參數(shù)如表3所示。

表3 環(huán)境參數(shù)Tab.3 Environmental parameters

4.3 優(yōu)化結(jié)果展示與算法性能分析

為研究NSGA-Ⅱ算法對中繼衛(wèi)星動態(tài)調(diào)度的優(yōu)化效果以及不同中繼衛(wèi)星數(shù)量、用戶航天器數(shù)量和新增任務(wù)數(shù)量對優(yōu)化效果的影響，本文選擇300個任務(wù)規(guī)模，做新增任務(wù)和用戶航天器數(shù)量變化實驗，在500個任務(wù)規(guī)模做中繼衛(wèi)星數(shù)量變化實驗，并在相同條件下選取了經(jīng)典的多目標(biāo)算法SPEA-Ⅱ算法進(jìn)行優(yōu)化效果對比。

在本文中選用超體積指標(biāo)(HV)做算法性能評價[16]，在雙目標(biāo)優(yōu)化問題中，HV的運算方法為獲得的非支配解集的每個個體與參照點(最大值個體)在空間中圍成的矩形的面積之和，HV值越大，說明算法的綜合性能越好。

(16)

4.3.1 300個任務(wù)申請

在300個任務(wù)規(guī)模時，將中繼衛(wèi)星數(shù)量固定為2，考慮此基礎(chǔ)上的優(yōu)化效果以及不同新增任務(wù)數(shù)量和不同用戶航天器數(shù)量對優(yōu)化效果的影響。

① 新增任務(wù)數(shù)量對算法的影響

不同新增任務(wù)優(yōu)化效果對比如圖5所示。

(a) 2個新增任務(wù)

(b) 4個新增任務(wù)

(c) 6個新增任務(wù)

(d) 8個新增任務(wù)

(e) 10個新增任務(wù)

(f) 12個新增任務(wù)

(g) 14個新增任務(wù)

(h) 16個新增任務(wù)

(i) 18個新增任務(wù)

(j) 20個新增任務(wù)圖5 優(yōu)化效果對比Fig.5 Optimization effect comparison

不同新增任務(wù)優(yōu)化數(shù)據(jù)對比如表4所示。

表4 優(yōu)化數(shù)據(jù)對比Tab.4 Optimized data comparison

圖6展現(xiàn)了在300個任務(wù)、2顆中繼衛(wèi)星、10個用戶航天器的條件下，不同新增任務(wù)的優(yōu)化效果，輸出的為在同樣迭代次數(shù)下SPEA-Ⅱ和NSGA-Ⅱ算法優(yōu)化后種群的Pareto最優(yōu)值。

圖6 HV值對比Fig.6 HV value comparison

由圖6可以看出，在新增任務(wù)數(shù)量不同時，NSGA-Ⅱ算法輸出的Pareto最優(yōu)解在空間上分布的均勻性、收斂性和廣泛性相較SPEA-Ⅱ算法都更加優(yōu)秀。

對比圖5可以看出，HV值相較SPEA-Ⅱ要更大，說明NSGA-Ⅱ算法在中繼衛(wèi)星動態(tài)調(diào)度優(yōu)化方面性能更好，能優(yōu)化出收斂性和多樣性更佳的非支配個體。

② 對算法的影響

不同用戶航天器數(shù)量優(yōu)化效果對比如圖7所示。

(a) 2個用戶航天器

(b) 4個用戶航天器

(c) 6個用戶航天器

(d) 8個用戶航天器

(e) 10個用戶航天器

(f) 12個用戶航天器

(g) 14個用戶航天器圖7 優(yōu)化效果對比Fig.7 Optimization effect comparison

不同用戶航天器數(shù)量優(yōu)化數(shù)據(jù)對比如表5所示。

表5 優(yōu)化數(shù)據(jù)對比Tab.5 Optimized data comparison

圖8展示了在300個任務(wù)、2顆中繼衛(wèi)星、10個新增任務(wù)的情況下，不同用戶航天器數(shù)量對優(yōu)化效果的影響。

由圖8可以看出，在300個任務(wù)條件下，僅用2個用戶航天器承載任務(wù)會導(dǎo)致任務(wù)的完成率減少，這是由于任務(wù)的服務(wù)時間和航天器與衛(wèi)星的可見時間匹配隨機概率減少。在不同的用戶航天器情況下，NSGA-Ⅱ算法展現(xiàn)了較強的優(yōu)化性能，得到的Pareto最優(yōu)解適應(yīng)性、均勻性和收斂性都較好。

圖8 HV值對比Fig.8 HV value comparison

4.3.2 500個任務(wù)申請

500個任務(wù)時，將用戶航天器數(shù)量固定為10個，考慮此基礎(chǔ)上的優(yōu)化效果及不同中繼衛(wèi)星數(shù)量對優(yōu)化效果的影響。500個任務(wù)規(guī)模也和300個形成對比，展現(xiàn)不同任務(wù)數(shù)量時，對優(yōu)化結(jié)果的影響，優(yōu)化效果對比如圖9所示，優(yōu)化數(shù)據(jù)對比如表6所示。

(a) 2顆中繼衛(wèi)星

(b) 3顆中繼衛(wèi)星

(c) 4顆中繼衛(wèi)星圖9 優(yōu)化效果對比Fig.9 Optimization effect comparison

表6 優(yōu)化數(shù)據(jù)對比Tab.6 Optimized data comparison

圖10展示了在500個任務(wù)、10個用戶航天器、10個新增任務(wù)的動態(tài)擾動環(huán)境下，變化中繼衛(wèi)星數(shù)量，對算法優(yōu)化效果的影響。

圖10 HV值對比Fig.10 HV value comparison

隨著資源數(shù)量的增加，任務(wù)完成率也隨之增加，且NSGA-Ⅱ算法的優(yōu)化結(jié)果分布更均勻，種群多樣性更高，同時NSGA-Ⅱ算法的性能，即HV值，要優(yōu)于SPEA-Ⅱ算法。

5 結(jié)束語

在中繼衛(wèi)星單址天線調(diào)度問題基礎(chǔ)上，考慮調(diào)度需求多樣性，構(gòu)建了多目標(biāo)函數(shù)的中繼衛(wèi)星重調(diào)度模型，在生成初始調(diào)度方案后，運用NSGA-Ⅱ算法對初始調(diào)度方案進(jìn)行優(yōu)化。仿真實驗中，本文對比了在實驗參數(shù)，如任務(wù)規(guī)模和資源數(shù)量等變化的情況下，NSGA-Ⅱ算法的優(yōu)化情況。其總能優(yōu)化得到一個收斂性、均勻性和廣泛性較好的Pareto最優(yōu)解。在對比SPEA-Ⅱ這一經(jīng)典多目標(biāo)算法時，NSGA-Ⅱ展現(xiàn)了更強的適用性，基于多目標(biāo)優(yōu)化的NSGA-Ⅱ算法輸出的Pareto最優(yōu)解，為調(diào)度方案提供了多樣化的選擇，為中繼衛(wèi)星管理部門和用戶建立了一個較佳的選擇空間。