一種基于偏好MOEA的衛星地面站資源多目標優化算法

孫剛，陳浩，彭雙，杜春，李軍

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

人造衛星按預定軌道繞地球飛行，利用其空間優勢在氣象預報、環境監測、資源普查、通信導航以及軍事偵察等領域發揮著重要作用[1-2]。衛星平臺的正常工作離不開衛星地面站的支持，如對衛星的跟蹤、測量、控制以及有效載荷數據的下傳等，這些操作都需要衛星與地面站建立通信通道。衛星與地面站能否建立通信通道取決于二者之間的空間相對位置。對于某地面站，可根據衛星的軌道信息以及地面站的地理位置信息(經度、緯度、海拔)計算出指定時間段內的一系列可通信時間段，稱為衛星相對于該地面站的可見時間窗口。可見時間窗口長度與衛星的軌道高度相關，通常低軌衛星與地面站的可見時間窗口長度會短于中高軌衛星的可見時間窗口。

隨著各國航天事業的迅速發展，在軌衛星數量不斷增長，但衛星地面站的建設相對滯后，這種發展上的不平衡導致了星地通信中地面站資源相對匱乏。一般而言，地面站中一套數據傳輸設備在某一時刻只能服務于一顆衛星。在多衛星、多地面站情況之下，多顆衛星與同一地面站的可見時間窗口可能發生重疊，形成多星進站沖突；同時，同一顆衛星也可能同時與多個地面站形成可見時間窗口。因此，需要從全局角度優化選擇合適的地面站資源為衛星提供數據傳輸服務。

如圖1所示，衛星SAT-1、SAT-2、SAT-3同時進入了地面站GS-1的數據傳輸范圍，其與地面站GS-1的可見時間窗口重疊，發生多星進站沖突，地面站GS-1只能選擇其中之一提供服務。同理，SAT-2、SAT-3和SAT-4對于地面站GS-2發生多星進站沖突。另一方面，衛星SAT-2對地面站GS-1和GS-2同時可見，可選擇其中之一進行數據傳輸服務。

圖1 多地面站多衛星數據傳輸問題示意圖Fig.1 Illustration of multiple satellites data transmission problem among multiple ground stations

如何合理規劃星地通信時間使得更加充分地發揮衛星地面站資源的整體效益，即為衛星地面站資源規劃所研究的問題，該問題得到了國內外學者的高度關注。當前的研究工作主要集中在兩個方面：一是對于問題性質及復雜性的研究；二是對于問題求解方法的研究。在問題性質及復雜性這個研究方向上，Vazquez和Erwin[3]的研究工作具有典型性，該項研究不僅對問題的特征、約束條件及復雜性進行了分析，而且在理論上證明了問題的NP-hard特性。在問題求解方法上，大致可分為精確求解方法和啟發式求解方法兩個類型。在精確求解方法中，ILP[4](Integer Linear Programming)以及MIP[5-6](Mix Integer Programming)具有代表性，但隨著問題規模的增大，巨大的參數量和約束條件使得這類方法在求解問題時變得異常困難。針對精確求解方法的不足，結合啟發式策略或松弛技術的算法被引入到衛星地面站資源規劃問題中，用以得到問題近似解而非全局最優解，從而較大地降低了問題求解的計算復雜度，但其優化性難以保證。為了在可接受計算時間內求得問題的滿意解，基于元啟發算法的衛星地面站資源規劃方法得到了越來越多的關注。元啟發算法提供了一種通用的啟發式元信息對搜索進程進行引導，從而克服了針對特定問題構建特定啟發式策略的困難，取得了較好的效果。典型的用于衛星地面站資源規劃問題的元啟發算法包括：模擬退火方法[7](Simulated Annealing, SA)、進化計算方法[8-10](Evolutionary Algorithm， EA)、禁忌搜索方法[11](Tabu Searching，TS)、蟻群搜索方法[12-13](Ant Colony Algorithm, ACA)等，但這些算法僅以單個優化目標作為規劃方案的評價準則。

實際上，衛星管理機構所關注的優化目標往往不止一個，如任務規劃失敗率、天線負載平衡度、任務相對于參考時間的集中度等，這些優化目標之間往往存在一定的沖突，即提高某個優化目標的效益往往會導致另一些優化目標效益降低。因此，衛星地面站資源規劃問題本質上是一個多目標優化問題。目前，主流的求解多目標優化問題的方法是MOEA(Multi-Objective Evolutionary Algorithm)。相關研究工作已廣泛應用于數據挖掘[14]、移動網絡規劃[15]、物流配送[16]、通信與網絡優化[17]等領域，但將衛星地面站資源規劃問題抽象為多目標優化問題的研究工作還相對較少，不成體系。Song等[18]以最大化任務規劃收益和最小化任務規劃失敗率為優化目標，將學習引導機制與NSGA-II[19](Non-dominated Sorting Genetic Algorithm-II，該算法基于Pareto支配關系對進化種群進行分層并根據層的優先級構建下一代種群，通過聚集距離維持解群體的分布性和多樣性)算法相結合實施多目標優化，但優化目標之間存在正相關性。Du等[20]將MOEA與LS(Local Searching)相結合構建了一個算法框架用于求解衛星地面站資源規劃的雙目標(最小化任務規劃失敗率、最大化天線負載平衡度)優化問題，實驗表明，基于該框架的算法在多個性能指標上優于本體算法，但其最低任務規劃失敗率在多數實驗場景下均高于10%。

針對衛星地面站資源規劃的多目標優化問題，傳統的MOEA首先求得一系列在優化目標上的非支配解，決策者再根據實際需要(偏好信息)從中選擇一組符合決策者期望的解，這個過程由“優化”和“決策”兩步完成。基于偏好的MOEA將“優化”和“決策”有機結合，利用決策者提供的偏好信息引導算法搜索方向，使算法著重搜索能產生符合決策者偏好的部分Pareto解。Jaimes等[21]利用ASF(Achievement Scalarization Function)定義了一個ROI(Region of Interest)并提出Chebyshev支配關系用于解決機翼形狀優化問題，其中Chebyshev支配關系定義為：ROI之內的個體根據Pareto支配關系排序，ROI外部的個體根據ASF函數值排序。Mahbub等[22]提出基于目標區域的pNSGA-II(Preferred-region NSGA-II)算法并將其用于能源系統優化，該算法以某個優化維度上的多個區間表達偏好，以個體與偏好區間在這個維度上的距離為標準將個體與偏好區間關聯，在NSGA-II算法框架之內結合個體與偏好區間的距離實施優化。Oliveira等[23]提出了EvABOR-III(Evolutionary Algorithm Based on Outranking Relation-III)算法用于電網配置，該算法利用決策者設定的一組參數(一致性指數、失調指數、置信度等)定義outranking關系并將其引入MOEA的交叉、變異算子之中，在構建下一代種群時優先考慮Pareto支配關系，當基于Pareto支配關系選擇的種群不滿足要求時利用outranking關系予以處理。李龍梅[24]提出了T-MOEAs(Target region based Multi-Objective Evolutionary Algorithms)并將其用于對地觀測衛星任務規劃的多目標優化問題，該算法以點或區域表達決策者的偏好信息，在構造下一代種群策略中優先考慮Pareto支配關系以引導種群向Pareto前沿進化，其次考慮個體與偏好信息之間的Chebyshev距離等級以引導種群向偏好點或區域進化。目前，將偏好MOEA用于衛星地面站資源規劃問題的研究尚未見報道。

在衛星地面站資源規劃問題中，決策者的偏好信息可通過歷史規劃方案獲取。利用偏好MOEA可以直接求出決策者感興趣的部分Pareto解。考慮到偏好MOEA的這種優勢，論文構建了基于領域知識的啟發式策略，并將其與偏好MOEA相結合，用于求解衛星地面站資源規劃的多目標優化問題。論文的主要貢獻在于：

1) 將衛星地面站資源規劃問題建模為一個偏好多目標優化問題，并將領域知識抽象為偏好信息的設定，進一步提升了問題求解的針對性。

2) 提出了一種基于領域知識的啟發式策略，能夠與偏好MOEA有效結合，從而更進一步提升了問題求解的優化性。

3) 基于廣泛采用的benchmark數據集AFSCN(Air Force Satellite Control Network)(可通過http:∥www.cs.colostate.edu/sched/data.html下載 )設計了相關實驗，實驗結果表明，相比于現有方法，論文提出的方法能夠根據決策者指定的偏好信息更有針對性地求解符合決策者偏好的解，從而驗證了論文提出的方法的可用性和有效性。

1 數學模型

衛星地面站資源規劃問題是一個多約束條件下的復雜優化問題，旨在解決多衛星、多地面站的場景下如何合理規劃星地通信時間使得衛星管理機構所要求的多個優化目標效益最佳。在本節中，首先針對問題進行必要的假設和形式化描述；然后構建目標優化函數及偏好表達；最后對于問題的約束條件進行描述和建模。

1.1 問題形式化描述

根據工程實踐和現行的技術條件，論文做合理假設如下：

1) 不考慮衛星及地面站設備的各類突發事件，認為在規劃周期內所有的地面站設備以及衛星均能正常工作。

2) 參與規劃的地面站天線均能無差別地支持各類衛星任務。

3) 同一天線在任意時刻至多只能支持一顆衛星的任務。不失一般性，若天線支持多通道工作模式，則將其視為多套單通道天線同址布署。

根據以上假設條件對衛星地面站資源規劃問題進行數學建模，為了便于描述，首先給出模型中相關符號的定義，具體如下：

(1)

R_si為衛星si在規劃周期內的任務需求，?si∈S，R_si={rm∈R|rm.sID=si.sID}，|R_si|表示需求數量，即在規劃周期內需要對衛星si規劃|R_si|次任務。

[ST,ET]為規劃周期，其中ST表示規劃開始時間；ET表示規劃結束時間。

根據以上描述可知，問題的決策變量包括布爾邏輯變量select、r_ts時間變量以及r_te時間變量，其中select變量決定在哪些可見時間窗口內執行任務，而r_ts變量以及r_te變量分別決定在可見時間窗口的哪一個時間點開始與結束任務。

1.2 目標函數及偏好表達

論文涉及的優化目標包括任務規劃失敗率和天線負載平衡度[20]，目標函數的數學描述形式為

Y=min{y1,y2}

(2)

1)y1表示任務規劃失敗率，其物理含義為無法安排的數據傳輸任務數量占總任務數量的百分比

(3)

式中：|F|表示規劃結果集中的任務數量，其數值為N；|R|表示任務集中的任務數量，其數值為M。

2)y2表示天線負載平衡度，其物理含義為天線工作時長的標準差與天線平均工作時長的比值：

(4)

(5)

(6)

偏好信息的引入方式有多種，文獻[24]將其分為以下類型：參考點方式、參考方向方式、偏好函數方式、目標區域方式、trade-off方式、目標比較方式、候選解比較方式、outranking方式等。其中基于參考點方式引入偏好信息的應用最為廣泛，這種方式由決策者在目標空間中指定一個點表示其在每一個目標函數上的期望值，從而引導偏好MOEA求出靠近參考點的部分最優解。論文以參考點方式將偏好信息引入偏好MOEA，具體表達為

Pref=[y1-ref,y2-ref]

(7)

式中：y1-ref表示決策者在目標函數y1上的期望值；y2-ref表示決策者在目標函數y2上的期望值。y1-ref、y2-ref的值可根據歷史規劃方案中的統計值進行設置，在不同的應用場景下其取值有所不同，例如在日常的衛星地面站資源規劃中，決策者可能會選擇一個相對折衷的數值，以兼顧任務規劃失敗率和天線負載平衡度，從而延長設備使用壽命；在執行重大保障任務時，決策者可能更加關注低的任務規劃失敗率，以最大限度完成任務。

1.3 約束條件

約束條件是保證規劃結果合理性與可行性的關鍵所在，論文涉及的約束條件主要包括：

1) 天線唯一性約束：任意時刻，同一天線至多只能與一顆衛星建立通信通道。

2) 任務非沖突約束：同一天線相鄰任務之間滿足一定的時間間隔，即任務轉換時間，以供設備及操作人員進行必要的準備工作。

3) 衛星唯一性約束：任意時刻，同一衛星至多只能與一個地面站天線建立通信通道。

4) 可見時間窗口約束：任務起止時間要位于相應的可見時間窗口之內。

5) 任務最低持續時間約束：任務的持續時間不低于任務所要求的最低持續時間。

6) 規劃周期約束：任務起止時間要位于規劃周期之內。

針對以上約束條件，其數學形式描述如下：

1) ?fu,fz∈F_ak，若fu.r_ts

fz.r_ts>fu.r_te+fz.rID.tvert

(8)

2) ?fu,fz∈F，若fu.wID.sID=fz.wID.sID，則

[fu.r_ts,fu.r_te]∩[fz.r_ts,fz.r_te]=?

(9)

3) ?fu∈F，則

fu.r_ts≥fu.wID.ts且fu.r_te≤fu.wID.te

(10)

fu.r_te-fu.r_ts≥fu.rID.tmin

(11)

fu.r_ts≥ST且fu.r_te≤ET

(12)

式(8)對應于天線唯一性約束以及任務非沖突約束；式(9)確保衛星唯一性約束得到滿足；式(10)對應于可見時間窗口約束；式(11)和式(12)分別對應于任務最低持續時間約束以及規劃周期約束。通過以上約束條件，可確保衛星地面站資源規劃結果的合理性與可行性。

2 算法設計

在本節中，首先將介紹衛星地面站資源規劃問題的偏好MOEA框架；然后對于編碼策略、交叉算子以及變異算子進行介紹；最后描述基于領域知識的啟發式策略。

2.1 算法框架

衛星地面站資源規劃問題的偏好MOEA框架如圖2所示。該算法框架主要包含兩個部分：一是偏好MOEA部分，二是基于領域知識的啟發式策略部分。其中，基于領域知識的啟發式策略嵌入在偏好MOEA中的“變異”與“個體適應度計算”之間，通過啟發式策略引導種群向優化目標函數值較好的方向進化。

圖2 地面站資源規劃問題的偏好MOEA算法框架Fig.2 Preference-based MOEA framework for satellite range scheduling problem

在偏好MOEA部分，由于在數學模型中采用了參考點偏好表達方式，因此選擇基于參考點的偏好MOEA對問題進行求解。考慮文獻[24]中T-NSGA-II、T-SMS-EMOA、T-R2-EMOA算法的性能優勢，論文擬以這3種算法為基礎嵌入基于領域知識的啟發式策略求解衛星地面站資源規劃問題。T-NSGA-II、T-SMS-EMOA、T-R2-EMOA算法分別以NSGA-II、SMS-EMOA[26](S-Metric Selection Evolutionary Multi-objective Optimization Algorithm)和R2-EMOA(R2-indicator Evolutionary Multi-objective Optimization Algorithm)為本體，在原算法基礎上增加了一層排序規則，即Chebyshev距離等級，解個體Chebyshev距離等級的分配與其距參考點的Chebyshev距離大小有直接關系，Chebyshev距離越小則賦予的等級越高，那么被選擇進入下一代種群的概率就越高，因此距離參考點Chebyshev距離越近的個體就越容易被保留下來。

SES-EMOA算法以最大化超體積空間為進化方向，超體積空間越大表明算法所求解集越逼近Pareto前沿，其中超體積空間定義為解集與參考點在目標空間中圍成的體積,即

(13)

式中：Γ表示解集；Pref=[p1,p2,…,pΥ]表示參考點；Υ表示優化目標函數維度；Leb表示勒貝格測度。

R2-EMOA算法以最大化R2指標為進化方向，其他方面與SMS-EMOA基本相同，其中R2指標定義為

R2(Γ,Θ,P*)=

(14)

當這個參考點設置為決策者的偏好時，生成的解就位于偏好信息附近的Pareto前沿，從而體現決策者的偏好。Chebyshev距離計算方法為

(15)

式中：Φ=[f1,f2,…,fΥ]表示解個體；Pref=[p1,p2,…,pΥ]表示參考點。基于領域知識的啟發式策略部分詳見2.3節。

算法的終止條件可依據問題的復雜性和現實需求設置，通常為算法運行時間或者進化代數。算法的輸出結果為種群中的非支配個體以及對應的目標函數值。

2.2 編碼策略、交叉算子及變異算子

編碼策略即個體的編碼方式，常用的編碼方式包括二進制編碼、實值編碼以及排列方式。編碼方式的選擇與問題的數學模型相關，考慮到論文中數學模型的決策變量select為布爾類型，因此在編碼方式上選擇二進制編碼最為合理。如式(1) 所示，select變量的取值決定了執行任務的可見時間窗口。

對于可見時間窗口wl，當wl.select取值為False時，可見時間窗口被編碼為0；當wl.select取值為True時，可見時間窗口被編碼為1。因此，個體編碼方式可表示為

X={x1,x2,x3,…，xL}

?i∈{1,2,…,L},xi∈{0,1}

(16)

式中：L的數值等于可見時間窗口的數量。

交叉算子和變異算子：選擇HUX[27](Half Uniform Crossover)交叉算子以及BF[28](Bit Flip)變異算子用于子代個體的生成。

2.3 基于領域知識的啟發式策略

由于個體編碼方式為二進制編碼，因此解空間的大小與編碼長度有關，當編碼長度為L時，解空間大小為2L，即隨著編碼長度的變化，解空間以2的指數次冪發生變化。當編碼長度較長時，解空間將非常巨大，如果以均等的概率搜索全部解空間，將極大地降低算法性能。為了解決這個問題，論文引入基于領域知識的啟發式策略，具體包括任務擴充策略、沖突消解策略以及任務縮減策略，這3種策略對于解空間的搜索范圍如圖3 所示。

圖3 解空間搜索范圍示意圖Fig.3 Illustration of search scope of solution space

2.3.1 任務擴充策略

根據編碼規則可知，個體編碼與可見時間窗口select變量相對應，其中個體編碼中數值為1的基因確定了一個可見時間窗口集合，即為潛在任務執行時間窗口集。在這個集合中，通常會存在兩種典型特征：① 用于執行某衛星任務的可見時間窗口數量可能小于該衛星的任務需求；② 在任務規劃過程中可能違背天線唯一性約束、衛星唯一性約束以及任務非沖突約束等條件。任務規劃失敗率一部分源于特征①，另一部分源于針對特征②進行的沖突消解操作。為了降低任務規劃失敗率，可通過任務擴充策略使得擴充后的潛在任務執行時間窗口集合不存在特征①，且提供一定的冗余以降低特征②對任務規劃失敗率的影響。

圖4 基于負載平衡的任務擴充策略示意圖Fig.4 Illustration of tasks expansion strategy based on load-balance

算法偽代碼如算法1所示，其中：si_req為衛星si的任務需求數量；η為擴充系數；|Wsi_sel|表示W中select變量為True的屬于衛星si的可見時間窗口數量；|Wsi_nsel|表示W中select變量為Flase的屬于衛星si的可見時間窗口數量。

算法1 任務擴充Algorithm 1 Tasks expansion

2.3.2 沖突消解策略

沖突消解策略以任務擴充策略處理后的潛在任務執行時間窗口集為輸入，首先進行地面站天線沖突消解，以使得在該集合上規劃的任務滿足式(8)、式(10)、式(11)的約束條件；其次進行衛星沖突消解，以滿足式(9)～式(11)的約束條件。

在地面站天線沖突消解中，以天線ID為依據將潛在任務執行時間窗口集劃分為多個子集，子集的數量與天線的數量是一致的，針對每個子集進行沖突消解。在進行沖突消解時，借鑒了滑動窗口的思想，即在滿足任務最低要求持續時間的前提下，任務的開始時間和結束時間可以在當前可見時間窗口內滑動。在初始化時，任務的開始時間和結束時間分別設置為當前可見時間窗口的開始時間和結束時間，在滿足任務最低要求持續時間的前提下，可以在當前可見時間窗口內確定任務的開始時間滑動區域和結束時間滑動區域，如圖5所示。

圖5 滑動窗口示意圖Fig.5 Illustration of sliding window

圖5中，可見時間窗口wi的開始時間和結束時間分別為ts和te，該可見時間窗口內的任務在初始化時，任務的開始時間和結束時間分別設為ts和te。由于任務的最低要求持續時間為tmin，因此任務的最晚開始時間不能超過latest_r_ts(latest_r_ts=te-tmin)，任務最早結束時間不能早于earliest_r_te(earliest_r_te=ts+tmin),即任務開始時間的可滑動范圍介于ts和latest_r_ts之間，任務結束時間的可滑動范圍介于earliest_r_te和te之間。

算法 2 天線沖突消解Algorithm 2 Conflicts-resolution of antenna

地面站天線沖突消解執行完畢后，為了確保任務規劃結果不違背式(9)的約束條件，需要進行衛星沖突消解。在衛星沖突消解過程中要同時確保規劃結果不違反式(10)、式(11)的約束條件。衛星沖突消解的過程與地面站天線沖突消解過程類似，不同之處在于衛星不存在任務轉換時間，只要確保同一衛星在同一時刻至多與一個天線建立通信通道即可。

2.3.3 任務縮減策略

由個體編碼確定的潛在任務執行時間窗口集經過任務擴充策略以及沖突消解策略處理后，形成了初步的規劃方案。但是，在這個規劃方案中，某些衛星的已規劃任務數量或任務時長可能大于任務需求，這將造成衛星地面站資源的浪費，因此需要采取任務縮減策略以保證在規劃方案中所有衛星的任務數量不超過其任務需求且任務時長也恰好滿足要求。

在任務縮減策略中，對于規劃方案中任務時長大于任務需求的情況，以任務開始時間為起始點進行截斷；對于在規劃方案中任務數量大于任務需求的衛星執行任務縮減操作時，論文使用了基于負載平衡的縮減方式，這種縮減方式通過計算執行某衛星任務的各天線的工作時長，選擇工作時長最大的天線所對應的該衛星的任務進行刪除，直至滿足該衛星的任務需求，從而使得負載平衡度這一優化目標得到進一步的改善。

3 實驗研究

論文實驗基于開源多目標優化算法程序庫MOEAFramework[29]實現。硬件配置：Intel(R) Core(TM) i5-2430M處理器、4 GB RAM、Windows 8(64位)操作系統。

3.1 實驗場景

以AFSCN標準數據集進行實驗，該數據集包含7個獨立的實驗場景，統計信息如表1所示。

表1 AFSCN數據集Table 1 Datasets of AFSCN

此外，需要說明的是：① AFSCN數據集并未給出衛星信息，論文假定衛星數量與任務數量一致，且在規劃周期內每顆衛星的任務需求為1次；② 場景S1～S7中，地面站數量為9個，天線數量為19個；③ AFSCN數據集規定了任務轉換時間，具體為：低軌任務的轉換時間為20 min，高軌任務轉換時間為15 min；④ 任務最低持續時間設置：低軌衛星任務最低持續時間等于可見時間窗口的持續時間，高軌衛星任務最低持續時間等于任務要求的持續時間。

3.2 基于領域知識的啟發式策略實驗分析

為了驗證論文提出的基于領域知識的啟發式策略的有效性，選擇無偏好的NSGA-II、SMS-EMOA、R2-EMOA這3種MOEA為本體，嵌入基于領域知識的啟發式策略構建了NSGA-II-H、SMS-EMOA-H、R2-EMOA-H算法用于解決衛星地面站資源規劃問題。將NSGA-II-H、SMS-EMOA-H、R2-EMOA-H的規劃結果與相同參數設置下的NSGA-II、SMS-EMOA、R2-EMOA的規劃結果進行比較。NSGA-II-H、SMS-EMOA-H、R2-EMOA-H的參數設置：種群規模100；交叉概率0.7；變異概率0.01；任務擴充系數2。在S1～S7實驗場景，使用NSGA-II-H、SMS-EMOA-H、R2-EMOA-H、NSGA-II、SMS-EMOA、R2-EMOA各獨立運行30次，每次運行10 min(M×Υs，其中M代表任務數量，Υ代表優化目標函數維度，計算得S1～S7平均運行時間約為10 min)。隨機抽取運行結果進行比較，比較結果如圖6所示。

在圖6中，橫坐標代表任務規劃失敗率，縱坐標代表天線的負載平衡度。NSGA-II-H、SMS-EMOA-H、R2-EMOA-H均使用了基于領域知識的啟發式策略，而NSGA-II、SMS-EMOA、R2-EMOA未使用該策略，對比發現NSGA-II、SMS-EMOA、R2-EMOA在S1～S7實驗場景中任務規劃失敗率均高于0.1；在相同的任務規劃失敗率條件下，NSGA-II-H、SMS-EMOA-H、R2-EMOA-H在負載平衡度這一優化目標上優于相應的NSGA-II、SMS-EMOA、R2-EMOA，即NSGA-II-H、SMS-EMOA-H、R2-EMOA-H能夠獲得質量更高的解；NSGA-II-H、SMS-EMOA-H、R2-EMOA-H在所有實驗場景下均拓展了任務規劃失敗率在0.1%以下的部分，即能夠在兼顧天線負載平衡度的情況下規劃更多的任務，這對于衛星管理部門非常重要(相比于天線負載平衡度，衛星管理部門更加偏重對任務規劃失敗率的關注)；NSGA-II、SMS-EMOA、R2-EMOA雖然在任務規劃失敗率0.25以上仍然找到了部分解，但如此高的任務規劃失敗率對于衛星管理部門而言往往不易接受。

圖6 基于領域知識的啟發式策略實驗分析Fig.6 Experimental analysis of heuristic strategies based on domain-knowledge

在圖7中，選擇S4實驗場景對上述算法的收斂性做了進一步分析，其中橫坐標表示個體評估次數，縱坐標表示世代距離[30](Generational Distance, GD)，世代距離的值越小表明算法的收斂性越好，即

(17)

式中：Γ表示待評估解集；PFref表示參考Pareto前沿；d(x,PFref)表示Γ中解個體距PFref的最小歐氏距離。

由圖7可知，在10 min的運行時間內NSGA-II-H、SMS-EMOA-H、NSGA-II、SMS-EMOA均已收斂，R2-EMOA-H及R2-EMOA未收斂，這是由于R2指標的計算較為耗時，導致在10 min的運行時間內算法對解空間的搜索不足；NSGA-II、SMS-EMOA、R2-EMOA在世代距離這一指標上均劣于相應的NSGA-II-H、SMS-EMOA-H、R2-EMOA-H；NSGA-II-H、SMS-EMOA-H、R2-EMOA-H在迭代初期與末期的世代距離變化范圍在0.015之內，這表明論文提出的基于領域知識的啟發式策略能夠將算法對解空間的搜索范圍約束到具有優質解的解空間之內，從而提高了算法的搜索效率。

圖7 S4實驗場景下算法的收斂性分析Fig.7 Convergence analysis of algorithms in S4 scenario

在圖8中，選擇S6實驗場景對基于領域知識的啟發式策略中的負載平衡策略進行了有效性分析，其中“無負載平衡”指在任務擴充階段和任務縮減階段均采取隨機處理方式。實驗結果表明，負載平衡策略可以有效提高解的質量，這是因為在任務擴充階段，負載平衡策略能夠產生負載平衡度相對較好的初始潛在任務執行時間窗口集合；在任務縮減階段，負載平衡策略在縮減任務數量過程中總是縮減工作時長最長的天線所對應的任務，這使得負載平衡程度得到進一步改善。綜上所述，論文提出的基于領域知識的啟發式策略的有效性得到驗證。

圖8 負載平衡策略實驗分析Fig.8 Experimental analysis of load-balance strategy

3.3 偏好MOEA實驗分析

將論文提出的基于領域知識的啟發式策略嵌入T-NSGA-II、T-SMS-EMOA、T-R2-EMOA這3種偏好MOEA算法中，構建了T-NSGA-II-H、T-SMS-EMOA-H、T-R2-EMOA-H算法用于解決衛星地面站資源規劃問題。為了說明上述偏好算法在求解問題上的針對性和優化性，選擇兩組算法進行實驗比較：一是基于領域知識的啟發式策略構建的無偏好NSGA-II-H、SMS-EMOA-H、R2-EMOA-H算法；二是基于文獻[20]提出的衛星地面站資源規劃多目標優化算法框架構建的NSGA-II-MA、SMS-EMOA-MA、R2-EMOA-MA算法(“MA”代表“Memetic Algorithm”)。在算法的參數設置上，考慮到偏好MOEA只關注偏好相關的解，因此不需要求出全部解集，故種群規模設置為15，其他參數與NSGA-II-H、SMS-EMOA-H、R2-EMOA-H設置一致。

在參考點的選擇上，通常可以根據歷史規劃方案的統計值以及應用場景進行設置。論文模擬設置了(0.01,0.3)、(0.05,0.25)以及(0.1,0.2)3組 參考點用于引導算法的搜索進程，其中(0.01, 0.3)的參考點更注重任務規劃失敗率這一優化目標；(0.1,0.2)的參考點更注重負載平衡度這一優化目標；(0.05,0.25)的參考點代表二者的折衷偏好。在S1、S4、S7場景中使用參考點(0.01,0.3)，S2、S5場景使用參考點(0.05,0.25)， S3、S6場景中使用參考點(0.1,0.2)，實驗結果如圖9所示。

由圖9可知，T-NSGA-II-H、T-SMS-EMOA-H、T-R2-EMOA-H在S1～S7實驗場景下，均能找到參考點附近的解，即能夠提供決策者偏好的規劃方案，提升了問題求解的針對性；與未引入偏好信息的NSGA-II-H、SMS-EMOA-H、R2-EMOA-H以及NSGA-II-MA、SMS-EMOA-MA、R2-EMOA-MA相比，基于偏好的T-NSGA-II-H、T-SMS-EMOA-H、T-R2-EMOA-H在多數場景下能夠找到決策者偏好的質量更好的解，這體現了偏好算法在求解衛星地面站資源規劃問題上的優化性。在相同的運行時間內(10 min)，以R2-EMOA構建的R2-EMOA-MA算法在S1～S7實驗場景下均未收斂，這是因為R2指標的計算比較耗時；R2-EMOA-H基本收斂，這表明論文提出的基于領域知識的啟發式策略的求解效率高于文獻[20]的局部搜索策略；T-R2-EMOA-H完全收斂，這說明偏好算法具有更高的求解效率。

圖9 偏好MOEA算法實驗分析Fig.9 Experimental analysis of preference-based MOEA

為了客觀地評價各算法的性能，選擇IGD-CF[31]指標對算法進行比較，該指標以參考集中距離參考點最近的解為中點定義一個ROI，并在此ROI中計算經典的IGD[32](Inverted Generational Distance)指標，即

(18)

式中：PROI表示算法落入ROI內部的解集；PFROI表示ROI內部的參考解集；d(x,PROI)表示PFROI中解個體距PROI的最小歐氏距離。

由于衛星地面站資源規劃問題的參考集未知，故獨立運行T-NSGA-II-H、T-SMS-EMOA-H、T-R2-EMOA-H、NSGA-II-H、SMS-EMOA-H、R2-EMOA-H、NSGA-II-MA、SMS-EMOA-MA、R2-EMOA-MA各10次，每次運行10 min，以算法生成的所有非支配解構建一個復合參考集用于IGD-CF指標的計算。論文中設定的ROI定義為邊長0.1的矩形，針對上述各算法分別獨立運行30次，每次運行10 min，各算法的IGD-CF指標統計結果如表2所示。

表2中IGD-CF指標的描述方式為“a(b)”，其中“a”代表30次運行結果的中位值，“b”代表標準差，“—”代表無效值(算法運行結果未落入ROI，導致計算IGD-CF指標的中位值或者標準差時數值為無窮大)。對比各算法的IGD-CF指標可知，偏好算法T-NSGA-II-H、T-SMS-EMOA-H、T-R2-EMOA-H在該指標上優于無偏好的NSGA-II-H、SMS-EMOA-H、R2-EMOA-H及NSGA-II-MA、SMS-EMOA-MA、R2-EMOA-MA算法，即偏好算法生成的解在ROI內具有更好的收斂性和分布性，且3種偏好算法在性能上差別不大；NSGA-II-H、SMS-EMOA-H、R2-EMOA-H算法在該指標上優于相應的NSGA-II-MA、SMS-EMOA-MA、R2-EMOA-MA算法，這表明論文提出的基于領域知識的啟發式策略與文獻[20]相比具有一定的優勢；比較T-R2-EMOA-H、R2-EMOA-H、R2-EMOA-MA這3種基于R2-EMOA構建的算法在IGD-CF指標上的性能可知，T-R2-EMOA-H完全收斂且性能與T-NSGA-II-H、T-SMS-EMOA-H相當，R2-EMOA-H在該指標上的數值約為T-R2-EMOA-H的2倍，R2-EMOA-MA在多數場景下生成的解未能收斂至ROI導致其IGD-CF指標為無效值，這更進一步地說明了論文提出的基于領域知識的啟發式策略的有效性和基于該啟發式策略構建的偏好算法的優化性。

表2 IGD-CF指標性能分析Table 2 Performance analysis of IGD-CF

4 結 論

1) 論文提出的基于領域知識的啟發式策略與偏好MOEA算法相結合能夠有效提升地面站資源規劃問題求解的針對性。

2) 基于領域知識的啟發式策略構建的偏好MOEA算法與無偏好算法相比，在解的優化性上有一定的提升。

3) 與現有算法相比，論文提出的算法更符合地面站資源規劃問題的現實需求，能夠根據決策者指定的偏好信息更有針對性地求解問題，有很好的應用前景。