孫剛,彭雙,陳浩,伍江江,李軍

國防科技大學 電子科學學院,長沙 410073

人造衛(wèi)星具有作用范圍廣、持續(xù)時間長且不受國界地形限制等獨特優(yōu)勢,已廣泛應用于科學研究、經(jīng)濟社會發(fā)展以及軍事等諸多領域。衛(wèi)星的跟蹤、測量、控制以及有效載荷數(shù)據(jù)的下傳等操作離不開衛(wèi)星地面站的支持,通常,將執(zhí)行衛(wèi)星的跟蹤、測量以及控制操作的任務稱為測控任務,以實現(xiàn)衛(wèi)星的軌道測量、軌道機動及姿態(tài)控制；將執(zhí)行衛(wèi)星有效載荷數(shù)據(jù)下傳的任務稱為數(shù)傳任務,數(shù)據(jù)經(jīng)處理后形成數(shù)據(jù)產(chǎn)品,以實現(xiàn)衛(wèi)星的價值。長期以來,由于受技術條件限制,地面站測控設備只能支持測控任務,數(shù)傳設備也只能支持數(shù)傳任務,二者不具備兼容性,無法實現(xiàn)對測控任務和數(shù)傳任務的相互支持和同步執(zhí)行,在一定程度上制約著地面站設備資源的利用效率。此外,隨著航天事業(yè)的迅速發(fā)展,在軌衛(wèi)星數(shù)量不斷增多,使得在星地通信中本就相對匱乏的地面站資源更加捉襟見肘,而衛(wèi)星地面站的建設、運行及維護又需要較高的成本投入。

針對星地通信中地面站資源相對匱乏的問題,著眼于資源調度優(yōu)化性,國內(nèi)外的相關機構和學者開展了大量卓有成效的研究。目前,用于衛(wèi)星地面站資源規(guī)劃問題常用求解算法包括：整數(shù)規(guī)劃算法、基于圖模型的搜索算法以及智能優(yōu)化算法。由于衛(wèi)星地面站資源規(guī)劃問題是一類典型的NP-hard問題,具有較高的復雜度,使得整數(shù)規(guī)劃算法無法適用于大規(guī)模規(guī)劃場景；基于圖模型的搜索算法通常會轉化為尋徑問題,算法的效率和優(yōu)化性在很大程度上取決于搜索策略的設計；智能優(yōu)化算法基于物理或生物學現(xiàn)象和行為建立啟發(fā)元信息引導搜索進程,具有很強的通用性,在求解衛(wèi)星地面站資源規(guī)劃問題中得到廣泛應用。此外,隨著在軌衛(wèi)星數(shù)量的不斷增加,地面站資源規(guī)劃問題的規(guī)模也隨之增大,衛(wèi)星管理機構關注的優(yōu)化目標也呈現(xiàn)出多元化特征。進化多目標優(yōu)化算法(Multi-Objective Evolutionary Algorithm, MOEA)是解決多目標優(yōu)化的主流智能優(yōu)化算法,近年來得到研究者的廣泛關注,尤以NSGA-II為最；此外,以決策者偏好信息引導MOEA優(yōu)化進程的偏好多目標進化算法(Preference-based Multi-Objective Evolutionary Algorithm, PMOEA)是當前進化計算領域的研究熱點,偏好信息的引入提升了多目標優(yōu)化問題求解的優(yōu)化性和針對性。MOEA以及PMOEA在衛(wèi)星地面站資源規(guī)劃中的應用也有相關報道。

近年來,隨著電子技術的發(fā)展,地面站測控設備與數(shù)傳設備逐漸趨同,呈現(xiàn)出功能一體化的特性(即同一設備可分時或同時執(zhí)行衛(wèi)星的測控任務和數(shù)傳任務),稱之為地面站資源的測控數(shù)傳一體化特性。由于在測控數(shù)傳一體化規(guī)劃場景下,測控任務和數(shù)傳任務可共享所有地面站設備資源,且同一衛(wèi)星的測控任務和數(shù)傳任務可同步執(zhí)行,因此可較大地提高地面站設備資源的利用率,進而緩解星地通信中地面站資源相對匱乏的現(xiàn)實難題。具體而言,其優(yōu)勢主要表現(xiàn)在以下幾個方面：一是在實施任務規(guī)劃過程中,任務對于地面站設備資源的選擇具有更高的自由度,從而降低由于任務間沖突導致的任務取消或者任務時長縮減；二是可以從全局角度對測控任務和數(shù)傳任務進行規(guī)劃,從而達到更好的全局優(yōu)化效果；三是可以將同一衛(wèi)星的測控任務和數(shù)傳任務規(guī)劃至同一地面站設備的同一個時窗內(nèi),使得二者同步實施,從而達到節(jié)約資源、事半功倍的效果。但是,傳統(tǒng)的衛(wèi)星地面站資源規(guī)劃方法只適用于測控資源規(guī)劃或者數(shù)傳資源規(guī)劃的情形,并沒有考慮二者趨于功能一體化的發(fā)展趨勢,導致在處理測控數(shù)傳資源一體化場景時只能分階段進行規(guī)劃,資源利用率低下,且規(guī)劃結果的全局優(yōu)化性也難以保證。目前,鮮有針對測控數(shù)傳資源一體化場景下的衛(wèi)星地面站資源規(guī)劃方法的相關研究報道,論文擬針對該問題建立多目標優(yōu)化模型并進行求解,設計了任務沖突時長最小化、天線負載均衡度最大化以及任務集聚度最大化3個獨立的優(yōu)化目標,其意義在于：一是在工程實踐中,對于存在沖突無法正常執(zhí)行的任務并不單純?nèi)∠?而是采用縮減任務執(zhí)行時長的方法以使得任務能夠部分執(zhí)行,故最小化任務沖突時長的優(yōu)化目標更符合工程實踐需要；二是在地面站設備高負載運行的情況下,最大化天線負載均衡度的優(yōu)化目標能夠使得設備間的負載相對均衡,以達到延長設備整體使用壽命的目的；三是最大化任務集聚度能夠使得規(guī)劃結果中的任務在設定的任務集聚區(qū)間內(nèi)分布相對聚集,區(qū)間外部的任務分布相對稀疏,以便于衛(wèi)星管理機構執(zhí)行例行設備維護操作或者避開某些執(zhí)行任務的高風險時段。

綜上所述,面向測控數(shù)傳資源一體化場景的衛(wèi)星地面站資源規(guī)劃是一個復雜約束條件下的多目標組合優(yōu)化問題,與傳統(tǒng)的衛(wèi)星地面站資源規(guī)劃問題相比,其難點主要體現(xiàn)在以下方面：首先,測控數(shù)傳資源一體化特性使得問題性質更為復雜,如何合理準確抽象數(shù)學模型是難點之一；其次,多維組合優(yōu)化問題具有更廣泛的解空間,而帕累托支配排序選擇方式的選擇壓力隨維度的增加驟降,導致優(yōu)化性不易保證,如何合理設計啟發(fā)式算子或引導機制以保證算法的優(yōu)化性是難點之二。本文的主要貢獻在于：

1) 根據(jù)測控數(shù)傳資源一體化場景下的衛(wèi)星地面站資源規(guī)劃問題特征和工程實踐需求,建立涵蓋最小化任務沖突時長、最大化天線負載均衡度以及最大化任務集聚度的多目標約束滿足問題模型。

2) 提出一種基于切比雪夫距離的膝點(Knee Point)定義方法,構建KG-NSGA-II-TTC&DT(Knee Guided Non-dominated Sorting Genetic Algorithm-II oriented integration of TT&C resources and Data Transmission resources)算法求解約束滿足模型以獲取在優(yōu)化目標上的最佳折衷解。該算法在迭代過程中以帕累托前沿(Pareto Front, PF)中的膝點為參考引導算法進程以提高算法的優(yōu)化性；同時,針對優(yōu)化目標設計負載均衡算子、任務集聚算子以及迭代修復沖突消解算子,從而進一步提升了問題求解的優(yōu)化性。

3) 建立模擬數(shù)據(jù)集并開展了實驗分析論證,實驗表明,負載均衡算子、任務集聚算子以及迭代修復沖突消解算子分別實現(xiàn)了31.50%、15.60%、70.57%的平均優(yōu)化性能提升；與基于NSGA-II算法構建的NSGA-II-TTC&DT相比,論文構建的KG-NSGA-II-TTC&DT在世代距離(Generational Distance, GD)指標上實現(xiàn)了16.75%的平均性能提升,在最小化任務沖突時長、最大化天線負載均衡度以及最大化任務集聚度3個優(yōu)化目標上分別實現(xiàn)了6.67%、9.28%以及1.87%的平均優(yōu)化性能提升。

1 問題描述及模型建立

相較于一般的衛(wèi)星地面站資源規(guī)劃問題,在測控數(shù)傳資源一體化場景下,其約束條件更多,需要考慮的要素也更為復雜。在本節(jié)中,首先符號化描述測控數(shù)傳資源一體化場景下的衛(wèi)星地面站資源規(guī)劃問題所涉及的要素；然后構建約束滿足模型,并給出優(yōu)化目標函數(shù)、決策變量以及約束條件的數(shù)學定義。

1.1 問題要素

1) 給定規(guī)劃時間段[,,Δ]。為規(guī)劃起始時間;為規(guī)劃結束時間；Δ為規(guī)劃時間段總時長。規(guī)劃要素均限定在給定規(guī)劃時間段內(nèi)。

2) 給定顆衛(wèi)星,,…,參與規(guī)劃,以表示衛(wèi)星集。?∈,≡>,其中id表示衛(wèi)星標識符。

3) 給定個衛(wèi)星地面站,,…,參與規(guī)劃,以表示衛(wèi)星地面站集。?∈,≡>,其中id表示衛(wèi)星地面站標識符。

7) 給定任務集聚區(qū)間[-,+],其中表示參考時間;表示參考時間半徑。

(1)

(2)

(3)

1.2 約束滿足模型構建

在構建測控數(shù)傳資源一體化的衛(wèi)星地面站資源規(guī)劃問題約束滿足模型前,首先根據(jù)問題特點作假設如下：

1) 地面站天線資源能夠無差別地支持參與規(guī)劃的測控任務及數(shù)傳任務,且具備同步執(zhí)行同一衛(wèi)星的測控任務與數(shù)傳任務的能力,不考慮同步執(zhí)行不同衛(wèi)星測控任務與數(shù)傳任務的情況。

2) 只考慮靜態(tài)規(guī)劃情況,即在規(guī)劃時間段內(nèi)問題要素是確定不變的。

基于以上假設建立約束滿足模型,模型包括函數(shù)、決策變量以及約束條件,分別定義如下：

1) 函數(shù)

任務沖突總時長:

(4)

天線資源的工作時長:

(5)

式中:表示規(guī)劃結果集中屬于天線資源的子集。

(6)

天線資源,,…,工作時長標準差:

(7)

天線資源相對于任務集聚區(qū)間[-,+]的任務集聚度:

(8)

天線資源,,…,相對于任務集聚區(qū)間[-,+]的平均任務集聚度:

(9)

(10)

式(10)中以最小化形式表達優(yōu)化目標,最小化可表達最大化天線負載均衡度,最小化(1-)可表達最大化任務集聚度。

2) 決策變量

布爾邏輯變量select：

(11)

另有r_st為時間變量,決定的起始時間;r_et為時間變量,決定的結束時間。

3) 約束條件

C1為規(guī)劃要素約束。本文涉及的規(guī)劃要素均限定在規(guī)劃時間段[,, Δ]之內(nèi)。

[-,+]?[,]

(12)

?∈→[st,et]?[,]

(13)

?∈→[r_st,r_et]?[,]

(14)

C2為天線能力約束。任意時刻,天線資源至多與某一衛(wèi)星處于任務執(zhí)行狀態(tài),即要求在時間軸上無重疊,表示規(guī)劃結果集中屬于天線資源的子集。

(15)

C3為衛(wèi)星能力約束。任意時刻,衛(wèi)星至多與某一天線資源處于任務執(zhí)行狀態(tài),即要求在時間軸上無重疊,表示規(guī)劃結果集中屬于衛(wèi)星的子集。

→[r_st,r_et]∩[r_st,r_et]=?

?,∈

(16)

(17)

C5為任務切換約束。天線資源由任務狀態(tài)切換至任務狀態(tài)時必須滿足執(zhí)行完畢且二者的時間間隔大于的最短任務準備時長。

?,∈

(18)

C6為任務執(zhí)行時間約束。任意規(guī)劃結果的起止時刻均限定在相應的可見時間窗口之內(nèi)。

?∈→?∈

(19)

2 算法設計

在本節(jié)中,首先介紹測控數(shù)傳資源一體化場景的衛(wèi)星地面站資源規(guī)劃算法KG-NSGA-II-TTC&DT的設計框架；其次詳細描述算法設計框架中各部分的設計思路及其作用。

2.1 KG-NSGA-II-TTC&DT算法框架

KG-NSGA-II-TTC&DT算法設計框架如圖1 所示。算法以可見時間窗口集、待規(guī)劃測控任務集、待規(guī)劃數(shù)傳任務集以及任務集聚區(qū)間[-,+]為輸入,以隨機方式形成設定規(guī)模的初始種群并基于初始種群執(zhí)行迭代進化操作,當?shù)螖?shù)或運算時間滿足設定的結束條件時,迭代進化過程結束并輸出由末代種群中所有非支配解構成的帕累托前沿以及在優(yōu)化目標上具有最佳折衷性能的膝解,與膝解對應的個體經(jīng)解碼策略處理后形成規(guī)劃結果集。迭代進化過程中,以交叉、變異、個體適應度評估、膝點計算、以膝點為參考點更新種群等操作引導算法優(yōu)化進程；以負載均衡算子、任務集聚算子提升個體負載均衡度以及任務集聚度的優(yōu)化性能；以迭代修復沖突消解算子處理約束滿足模型的約束條件,最小化任務沖突時長的優(yōu)化目標也在此過程中得到優(yōu)化。

圖1 KG-NSGA-II-TTC&DT算法框架Fig.1 Framework of KG-NSGA-II-TTC&DT

2.2 KG-NSGA-II-TTC&DT設計思路

2.2.1 預處理

預處理主要包括中高軌衛(wèi)星可見時間窗口分割操作以及測控數(shù)傳任務的匹配操作,其中高軌衛(wèi)星可見時間窗口分割操作的執(zhí)行對象為可見時間窗口集中屬于中高軌衛(wèi)星的部分,分割過程如圖2所示,測控數(shù)傳任務的匹配操作以待規(guī)劃測控任務集以及待規(guī)劃數(shù)傳任務集為執(zhí)行對象,匹配過程如圖3所示。

圖2 中高軌衛(wèi)星可見時間窗口分割示意圖Fig.2 Illustration of visible time window segmentation for medium and high orbit satellites

圖3 任務匹配示意圖Fig.3 Illustration of task matching

在測控數(shù)傳資源一體化規(guī)劃場景中,天線資源具備一體化執(zhí)行測控任務和數(shù)傳任務的能力,但要滿足約束條件C4。測控數(shù)傳任務匹配操作的目的是在滿足C4約束條件的前提下使得盡可能多的測控任務與數(shù)傳任務一體化執(zhí)行,以節(jié)約天線資源,達到事半功倍的效果。在圖3中,以A、B、C等字母表示任務序列中的衛(wèi)星標識符,以數(shù)傳任務集為參考,針對測控任務集逐個執(zhí)行衛(wèi)星標識符匹配操作,將劃分為匹配集與失配集,分別以黑色虛線和紅色虛線指示,藍色虛線指示占位符,以使得匹配集與數(shù)傳任務集具有一致的排列次序。

2.2.2 編碼策略

編碼策略是以某種形式的個體編碼為媒介建立待求解問題與數(shù)值序列的一一對應關系。本文以相關聯(lián)的個體編碼對形式建立待規(guī)劃數(shù)傳任務集及測控任務集與可見時間窗口集之間的數(shù)值對應關系。編碼策略以待規(guī)劃數(shù)傳任務集以及經(jīng)匹配處理后的測控任務集為輸入,輸出以實數(shù)形式表示的一對個體編碼,稱為染色體對,其中實數(shù)的數(shù)值表示執(zhí)行任務id的可見時間窗口在支持任務id的可見時間窗口集中的序號,如圖4所示。

圖4 編碼策略Fig.4 Encoding strategy

在圖4中,測控任務集經(jīng)匹配處理后形成的匹配集以藍色背景表示,失配集以橙色背景表示,執(zhí)行任務的可見時間窗口以紅色表示,編碼規(guī)則為：數(shù)傳任務集序列與匹配集序列關聯(lián)編碼,二者在匹配位數(shù)值一致；匹配集序列中的占位符以數(shù)值0編碼；非匹配集獨立編碼。為了更易理解,以數(shù)傳任務序列中衛(wèi)星標識符為A、C的任務以及失配集中衛(wèi)星標識符為T的任務為例予以說明,支持衛(wèi)星標識符為A的數(shù)傳任務的可見時間窗口共計5個,分別為A1、A2、A3、A4、A5,以隨機方式選擇其中一個(A4被選擇)執(zhí)行任務,A4處于第4位,故編碼數(shù)值為4,匹配集序列中的匹配位關聯(lián)編碼為4；支持衛(wèi)星標識符為C的數(shù)傳任務的可見時間窗口共計4個,其中C4被隨機選擇執(zhí)行任務,編碼數(shù)值為4,匹配序列中的占位符編碼為0；失配集中的衛(wèi)星標識符為T的測控任務在可見時間窗口T2執(zhí)行,編碼數(shù)值為2。

2.2.3 交叉、變異算子

KG-NSGA-II-TTC&DT算法的每一次迭代進化過程中,父代種群在設定概率的控制下通過交叉、變異算子聯(lián)合作用產(chǎn)生子代種群,子代種群規(guī)模與父代種群規(guī)模一致。交叉算子以二元錦標賽方式在父代種群中選擇個體,在交叉概率的控制下執(zhí)行交叉操作,其過程如圖5所示。在圖5中,交叉算子以隨機方式確定交叉點1、交叉點2,通過交換父個體1、2中由交叉點1、2確定的染色體片段產(chǎn)生子個體。

圖5 交叉算子Fig.5 Crossover operator

變異算子以交叉算子輸出的子個體為父個體,在變異概率的控制下執(zhí)行變異操作產(chǎn)生下一代子個體,其過程如圖6所示。在圖6中,父個體即為交叉算子輸出的子個體,在變異概率的控制下選擇部分位置執(zhí)行變異操作(以紅色背景標示),當變異點位于數(shù)傳任務序列對應的個體編碼部分時執(zhí)行聯(lián)動變異；當變異點位于測控任務失配集對應的個體編碼部分時執(zhí)行隨機變異操作,即隨機更改變異點編碼數(shù)值。以下重點介紹聯(lián)動變異操作的過程。

圖6 變異算子Fig.6 Mutation operator

聯(lián)動變異操作首先以變異點數(shù)傳任務的協(xié)同標識符查詢與之協(xié)同的其他數(shù)傳任務；其次比較協(xié)同組(具有相同協(xié)同標識符的所有數(shù)傳任務)內(nèi)所有數(shù)傳任務的執(zhí)行時窗,以起始時刻最早的執(zhí)行時窗作為參考時窗；最后以輪盤選擇方式確定協(xié)同組內(nèi)其他數(shù)傳任務的變異數(shù)值,輪盤選擇概率與距參考時窗的時間距離成反比。由上述描述可知,聯(lián)動變異操作的目的在于縮減協(xié)同組內(nèi)數(shù)傳任務之間的時間間隔,提高協(xié)同任務執(zhí)行的時效性。

2.2.4 負載均衡算子

負載均衡算子以最大化天線資源的負載均衡度為目標,通過有限次的循環(huán)操作使得參與規(guī)劃的天線資源具有相對一致的工作時長,循環(huán)次數(shù)等于天線資源的數(shù)量。在每次的循環(huán)操作中均以具有最大工作時長和最小工作時長的天線資源為執(zhí)行對象,平衡二者之間的工作時長,在此平衡過程中,優(yōu)先將最大工作時長天線資源中距參考時間較遠的任務調整至最小工作時長天線資源中距參考時間較近的位置。負載均衡算子的執(zhí)行過程如圖7所示。

在圖7中,步驟 ① 平衡天線資源6、7的工作時長,在此過程中,優(yōu)先將天線資源6中距離參考時間較遠的任務調整至天線資源7,并將其安排在天線資源7中距離較近的位置,以使得由天線資源6調整而來的任務盡量在天線資源7的任務集聚區(qū)間內(nèi)執(zhí)行；步驟 ② 平衡天線資源3、4的工作時長,步驟 ③ 平衡天線資源2、8的工作時長,后續(xù)操作不再贅述。通過柱狀圖可以清晰地看出,負載均衡算子可以較好地平衡參與規(guī)劃的天線資源的工作時長。

圖7 負載均衡算子示意圖Fig.7 Illustration of load-balance operator

2.2.5 任務集聚算子

任務集聚算子針對最大化任務集聚度的優(yōu)化目標而設計,以使得任務在設定的任務集聚區(qū)間[-,+]內(nèi)分布相對聚集,區(qū)間外分布相對稀疏。該算子分別作用于參與規(guī)劃的每個天線資源的任務子集(任務子集由個體編碼確定),將處于任務集聚區(qū)間外部的任務調整至距離參考時間最近的位置,如圖8所示。

圖8 任務集聚算子示意圖Fig.8 Illustration oftask-clustering operator

在圖8中,以柱狀色塊表示任務,其中虛線邊框的任務均執(zhí)行了調整操作,部分任務被調整至任務集聚區(qū)間內(nèi)部(以黑色實箭頭線指示),部分任務由于在任務集聚區(qū)間內(nèi)沒有支持其的可見時間窗口而被調整至區(qū)間外部距離參考時間最近的位置(以紅色實箭頭線指示)。

由2.2.4節(jié)可知,負載均衡算子在執(zhí)行平衡操作過程中涉及天線資源之間的任務調換,且優(yōu)先將距離參考時間較遠的任務調整至其他天線資源中距離參考時間較近的位置,在一定程度上有利于任務集聚度的提升；而任務集聚算子只作用于參與規(guī)劃的每個天線資源的任務子集,即只執(zhí)行天線資源內(nèi)部的任務調整操作,天線資源之間無任務調換,不影響負載均衡算子的作用效果。

2.2.6 迭代修復沖突消解算子

迭代修復沖突消解算子針對最小化任務沖突時長的優(yōu)化目標而設計,并處理約束條件C2、C3、C5、C6,以確保規(guī)劃結果的可行性,其執(zhí)行過程如圖9所示。

在圖9中,迭代修復沖突消解算子首先針對個體編碼確定的待執(zhí)行任務序列執(zhí)行沖突消解處理,并將該任務序列劃分為沖突集和非沖突集；其次針對沖突集中的每個任務,以收益高低的優(yōu)先級順序,隨機選擇一定數(shù)量的支持該任務的可見時間窗口并計算每個可見時間窗口與非沖突集之間的沖突時長,選擇具有最小沖突時長的可見時間窗口執(zhí)行該任務并插入非沖突集,沖突時長的計算方式由式(1)～式(3)確定。迭代修復沖突消解算子的執(zhí)行過程也是以式(15)～式(18)為準則確定決策變量r_st、r_et的過程。

圖9 迭代修復沖突消解算子示意圖Fig.9 Illustration ofconflict-resolution operator based on iterative repair

2.2.7 基于切比雪夫距離的膝點定義方法

對于多目標優(yōu)化問題而言,膝點指具有最佳性能折衷的解。Deb和Gupta通過對一系列回歸、排序、聚類以及工程設計問題進行論證得出結論：常用的問題求解方法產(chǎn)生的解往往位于膝點。長期以來,由于缺乏對“最佳性能折衷”的嚴格定義導致膝點具有多種定義方式。Branke等基于角度(Reflex Angle)測度和基于邊際效用函數(shù)(Marginal Utility Function)測度定義膝點。Das提出基于法向邊界相交(Normal Boundary Intersection)的膝點定義方法。Rachmawati和Srinivasan提出基于加權和函數(shù)變換的膝點定義方法。Chiu等以帕累托前沿與理想點(Ideal Point)之間的曼哈頓距離為準則定義膝點。以上關于膝點的定義方式存在不唯一或不具備全局性的缺點。本節(jié)中,定義了一種基于切比雪夫距離的膝點,即

(20)

(23)

2.2.8 KG-NSGA-II-TTC&DT種群更新策略

KG-NSGA-II-TTC&DT算法基于T-NSGA-II構建,其中T-NSGA-II算法是一種基于目標區(qū)域的偏好多目標進化算法,該算法在二維及三維優(yōu)化問題上性能優(yōu)異,亦支持參考點的偏好表達方式。當T-NSGA-II工作在參考點模式時,其種群更新策略為：① 合并父代種群與子代種群形成合并種群；② 根據(jù)帕累托非支配排序準則對合并種群執(zhí)行分層操作,按優(yōu)先級順序逐層加入下一代種群,直至臨界層；③ 計算臨界層個體與設定的參考點之間的切比雪夫距離并分配等級,根據(jù)切比雪夫距離等級優(yōu)先級選擇進入下一代種群的臨界層個體,直至達到下一代種群規(guī)模。

KG-NSGA-II-TTC&DT的種群更新策略與T-NSGA-II基本一致,不同之處在于KG-NSGA-II-TTC&DT不需要設置參考點,而是以每次迭代過程中帕累托前沿的膝點為參考點引導算法進程,使得算法在膝點附近具有更好的收斂性,即KG-NSGA-II-TTC&DT引入了參考點動態(tài)更新機制。

3 實驗與分析

MOEAFramework是JAVA環(huán)境下的多目標進化算法開源程序庫,本文實驗基于此開源程序庫實現(xiàn)。實驗平臺的硬件配置：Windows 8(64位)操作系統(tǒng)、Intel(R) Core(TM) i5-2430M處理器、4 GB RAM。

3.1 實驗設置

規(guī)劃時間段設置為2020/3/5 00∶00∶00—2020/3/6 00∶00∶00,參與規(guī)劃的衛(wèi)星集及天線資源集均選自STK數(shù)據(jù)庫,并利用STK計算可見時間窗口集,以確保約束條件C1中的式(13)和式(14)得到滿足。天線資源集均位于中國境內(nèi)(佳木斯、北京、青島、渭南、喀什、廈門、南寧、三亞)。測試用例如表1所示,在表1中,以“Sat”表示衛(wèi)星集的數(shù)量,涉及的中高軌衛(wèi)星數(shù)量在小括號中予以表示；以“GS”表示天線資源集的數(shù)量；以“Win”表示可見時間窗口集的數(shù)量；以“DT-Task”表示待規(guī)劃數(shù)傳任務集的數(shù)量,其中小括號中的2項數(shù)值分別表示獨立數(shù)傳任務數(shù)量和協(xié)同數(shù)傳任務數(shù)量；以“TTC-Task”表示待規(guī)劃測控任務集的數(shù)量；以“Rev”表示任務總收益。

表1 測試用例Table 1 Scenarios for experiment

參考時間設置為2020/3/5 15∶00∶0,參考時間半徑設置為32 400 s；中高軌衛(wèi)星可見時間窗口分割時間間隔Δ設置為300 s；種群規(guī)模設置為100；交叉概率設置為0.9；變異概率設置為0.02。KG-NSGA-II-TTC&DT算法的結束條件通過以下方式確定：針對每個測試用例運行(+)s(其中表示優(yōu)化目標數(shù)量,這里取值為3),繪制算法的收斂曲線,根據(jù)收斂曲線設置算法結束條件。圖10繪制了S1～S5測試用例在指定運行時間內(nèi)的收斂特性,根據(jù)收斂特征設置S1～S4測試用例的算法結束條件為50 000次個體評估次數(shù),設置S5測試用例的算法結束條件為25 000次個體評估次數(shù)。

圖10 KG-NSGA-II-TTC&DT算法收斂曲線Fig.10 Convergence curves of KG-NSGA-II-TTC&DT

3.2 實驗分析

測控數(shù)傳資源一體化場景下的衛(wèi)星地面站資源規(guī)劃問題無標準參考集,為了解決參考集的問題,以NSGA-II算法的種群更新策略替代KG-NSGA-II-TTC&DT算法的種群更新策略構建了NSGA-II-TTC&DT算法,針對S1～S5測試用例分別以KG-NSGA-II-TTC&DT、NSGA-II-TTC&DT算法各獨立運行15次,收集帕累托非支配解形成各測試用例的近似參考集。針對S1～S5測試用例,以KG-NSGA-II-TTC&DT各獨立運行30次進行實驗分析。

3.2.1 負載均衡算子有效性驗證

本節(jié)分析驗證KG-NSGA-II-TTC&DT算法中負載均衡算子的有效性。針對測試用例S1～S5,以無負載均衡算子的KG-NSGA-II-TTC&DT算法各獨立運行30次,實驗結果如圖11 所示。

圖11 負載均衡算子實驗分析Fig.11 Experimental analysis of load-balance operator

在圖11(a)中,縱坐標表示天線資源工作時長標準差,越小則表示天線資源的負載均衡度越大,橫坐標表示測試用例,以黑色表示KG-NSGA-II-TTC&DT算法在無負載均衡算子條件下的實驗結果,以紅色表示含負載均衡算子時的實驗結果。對比分析實驗結果可知,負載均衡算子在S1～S5測試用例中均降低了天線資源工作時長標準差,有效提升了天線資源的負載均衡度；無負載均衡算子時,S1～S5在30次獨立運行結果中的平均值分別為0.041 74、0.040 33、0.042 69、0.038 95、0.041 18,含負載均衡算子時,S1～S5在30次獨立運行結果中的平均值分別為0.024 16、0.020 41、0.025 56、0.031 62、0.038 27,計算可知負載均衡算子在S1～S5測試用例分別實現(xiàn)了42.11%、49.39%、40.13%、18.82%、7.07%的性能提升,平均性能提升為31.50%。在圖11(b)中分析了負載均衡算子對于規(guī)劃收益率的影響,實驗結果顯示負載均衡算子對規(guī)劃收益率的影響甚微。

3.2.2 任務集聚度算子有效性驗證

本節(jié)分析驗證KG-NSGA-II-TTC&DT算法中任務集聚算子的有效性。針對測試用例S1～S5,以無任務集聚算子的KG-NSGA-II-TTC&DT算法各獨立運行30次,實驗結果如圖12 所示。

在圖12(a)中,縱坐標表示優(yōu)化目標(1-),其中表示平均任務集聚度,橫坐標表示測試用例。對比分析實驗結果可知,任務集聚算子在S1～S5測試用例中均有效提升了任務集聚度；無任務集聚算子時,S1～S5在30次獨立運行結果中(1-)的平均值分別為0.044 63、0.044 10、0.079 73、0.098 67、0.135 31,含任務集聚算子時,S1-S5在30次獨立運行結果中(1-)的平均值分別為0.040 98、0.038 04、0.065 00、0.078 30、0.112 35,計算可知任務集聚算子在S1～S5測試用例分別實現(xiàn)了8.18%、13.74%、18.47%、20.64%、16.97%的性能提升,平均性能提升為15.60%。圖12(b)分析了任務集聚算子對于規(guī)劃收益率的影響,實驗結果顯示該算子在一定程度上降低了規(guī)劃收益率,在S1～S5測試用例上分別引起了0.12%、0.04%、0.20%、0.25%、0.37%收益損失,平均收益損失為0.20%,與15.60%的平均任務集聚度性能提升相比是可接受的。

圖12 任務集聚算子實驗分析Fig.12 Experimental analysis of task-clustering operator

3.2.3 迭代修復沖突消解算子有效性驗證

本節(jié)分析驗證KG-NSGA-II-TTC&DT算法中迭代修復沖突消解算子的有效性。針對測試用例S1～S5,以無迭代修復沖突消解算子的KG-NSGA-II-TTC&DT算法各獨立運行30次,實驗結果如圖13所示。

圖13中,縱坐標表示規(guī)劃收益率,橫坐標表示測試用例。對比分析實驗結果可知,迭代修復沖突消解算子在S1～S5測試用例中均有效提高了規(guī)劃結果的收益率；無迭代修復沖突消解算子時,S1～S5在30次獨立運行結果中的規(guī)劃收益率平均值分別為66.92%、62.53%、57.93%、55.13%、51.01%,含迭代修復沖突消解算子時,S1～S5在30次獨立運行結果中的規(guī)劃收益率平均值分別為99.80%、99.88%、99.59%、99.23%、97.97%,平均收益率為99.29%,與無迭代修復沖突消解算子的運行結果相比,平均性能提升為70.57%。

圖13 迭代修復沖突消解算子實驗分析Fig.13 Experimental analysis of conflict-resolution operator based on iterative repair

3.2.4 KG-NSGA-II-TTC&DT性能分析

為驗證KG-NSGA-II-TTC&DT算法的有效性,引入NSGA-II-TTC&DT、NSGA-II-H以及NSGA-II-MA進行對比分析。其中,NSGA-II-TTC&DT算法以NSGA-II算法的種群更新策略替代KG-NSGA-II-TTC&DT的種群更新策略,無膝點引導機制；NSGA-II-H、NSGA-II-MA算法是針對測控場景或者數(shù)傳場景的衛(wèi)星地面站資源規(guī)劃算法,以最小化規(guī)劃失敗率和最大化負載均衡度為優(yōu)化目標,論文加以改進使得其能夠適用于測控數(shù)傳資源一體化場景。針對S1-S5測試用例,分別以KG-NSGA-II-TTC&DT、NSGA-II-TTC&DT、NSGA-II-H、NSGA-II-MA各獨立運行30次。

圖14 KG-NSGA-II-TTC&DT實驗分析Fig.14 Experimental analysis of KG-NSGA-II-TTC&DT

為了定量分析算法性能,以求得的近似參考集為參考,計算KG-NSGA-II-TTC&DT、NSGA-II-TTC&DT在S1～S5測試用例上的世代距離(Generational Distance, GD)指標,GD值越小表明算法的收斂性越好,其中GD指標的計算方法如式(24)所示,統(tǒng)計結果如表2所示。

(24)

由表2可知,KG-NSGA-II-TTC&DT算法在S1～S5測試用例上的GD指標均優(yōu)于NSGA-II-TTC&DT算法,分別實現(xiàn)了7.70%、2.12%、31.70%、26.44%、15.80%的GD性能提升,平均性能提升約16.75%,即KG-NSGA-II-TTC&DT算法具有更好的收斂性。

表2 GD指標性能分析Table 2 Performance analysis of GD

表3 優(yōu)化目標數(shù)值分析Table 3 Computational analysis of optimization objectives

3.2.5 KG-NSGA-II-TTC&DT膝點規(guī)劃效果

本節(jié)以測試用例S1、S5對KG-NSGA-II-TTC&DT算法的規(guī)劃效果予以分析,隨機選擇KG-NSGA-II-TTC&DT算法在S1、S5測試用例下求得的膝點,規(guī)劃效果如圖15～圖17所示。圖15分析了S1、S5測試用例在膝點處的負載均衡情況,以JMS、BJ、QD等命名天線資源,由圖可知,KG-NSGA-II-TTC&DT算法無論在任務量相對低的S1測試用例還是在任務量相對較高的S5測試用例,均實現(xiàn)了較好的負載均衡效果,S1、S5測試用例下天線資源工作時長最大值與最小值之間的時差分別為39.48、119.88 min。圖16分析了S1、S5測試用例在膝點處的任務集聚情況,縱坐標表示任務集聚區(qū)間[-,+]外的任務占比,實驗中設置的任務集聚區(qū)間外的時間段占規(guī)劃時間段的25%,由圖可知,S1、S5測試用例中膝點處的任務集聚區(qū)間外的任務占比顯著低于25%,此外,隨著任務量的增加(與S1相比,S5任務量增加了88.89%),任務集聚區(qū)外的任務占比變大,這是由于隨著任務量的增加,任務集聚區(qū)內(nèi)的任務沖突程度加重,導致部分任務只能規(guī)劃于任務集聚區(qū)外部,圖17也證實了這一點。由圖17可知,S1、S5測試用例在膝點處的天線資源平均沖突時長分別為1.06、24.60 min,與S1、S5測試用例在膝點處的天線資源平均工作時長470.85、803.70 min相比,沖突時長占比分別為0.225%、3.061%。

圖15 膝點的負載均衡效果Fig.15 Result of load-balance in knee point

圖16 膝點的任務集聚效果Fig.16 Result of tasks clustering inknee point

圖17 膝點的沖突時長Fig.17 Conflict time in knee point

4 結 論

1) 論文針對測控數(shù)傳資源一體化場景下的衛(wèi)星地面站資源規(guī)劃問題特征和工程實踐需求,抽象建立涵蓋最小化任務沖突時長、最大化天線負載均衡度以及最大化任務集聚度優(yōu)化目標的約束滿足模型,提出一種基于切比雪夫距離的膝點定義方法,構建了求解約束滿足模型的KG-NSGA-II-TTC&DT算法,該算法以膝點為參考引導算法收斂進程,可以有效提升解的優(yōu)化性。

2) KG-NSGA-II-TTC&DT算法針對優(yōu)化目標設計了負載均衡算子、任務集聚算子以及迭代修復沖突消解算子以進一步提升求解的優(yōu)化性。實驗結果表明,負載均衡算子、任務集聚算子以及迭代修復沖突消解算子分別實現(xiàn)了31.50%、15.60%、70.57%的平均優(yōu)化性能提升。

3) KG-NSGA-II-TTC&DT算法在膝點處具有最佳的性能折衷,可以更好滿足衛(wèi)星管理機構的需求,具有很強的現(xiàn)實針對性。