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

國防科技大學(xué) 電子科學(xué)學(xué)院，長沙 410073

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

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

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

圖1 多地面站多衛(wèi)星數(shù)據(jù)傳輸問題示意圖Fig.1 Illustration of multiple satellites data transmission problem among multiple ground stations

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

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

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

在衛(wèi)星地面站資源規(guī)劃問題中，決策者的偏好信息可通過歷史規(guī)劃方案獲取。利用偏好MOEA可以直接求出決策者感興趣的部分Pareto解。考慮到偏好MOEA的這種優(yōu)勢，論文構(gòu)建了基于領(lǐng)域知識的啟發(fā)式策略，并將其與偏好MOEA相結(jié)合，用于求解衛(wèi)星地面站資源規(guī)劃的多目標(biāo)優(yōu)化問題。論文的主要貢獻(xiàn)在于：

1) 將衛(wèi)星地面站資源規(guī)劃問題建模為一個(gè)偏好多目標(biāo)優(yōu)化問題，并將領(lǐng)域知識抽象為偏好信息的設(shè)定，進(jìn)一步提升了問題求解的針對性。

2) 提出了一種基于領(lǐng)域知識的啟發(fā)式策略，能夠與偏好MOEA有效結(jié)合，從而更進(jìn)一步提升了問題求解的優(yōu)化性。

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

1 數(shù)學(xué)模型

衛(wèi)星地面站資源規(guī)劃問題是一個(gè)多約束條件下的復(fù)雜優(yōu)化問題，旨在解決多衛(wèi)星、多地面站的場景下如何合理規(guī)劃星地通信時(shí)間使得衛(wèi)星管理機(jī)構(gòu)所要求的多個(gè)優(yōu)化目標(biāo)效益最佳。在本節(jié)中，首先針對問題進(jìn)行必要的假設(shè)和形式化描述；然后構(gòu)建目標(biāo)優(yōu)化函數(shù)及偏好表達(dá)；最后對于問題的約束條件進(jìn)行描述和建模。

1.1 問題形式化描述

根據(jù)工程實(shí)踐和現(xiàn)行的技術(shù)條件，論文做合理假設(shè)如下：

1) 不考慮衛(wèi)星及地面站設(shè)備的各類突發(fā)事件，認(rèn)為在規(guī)劃周期內(nèi)所有的地面站設(shè)備以及衛(wèi)星均能正常工作。

2) 參與規(guī)劃的地面站天線均能無差別地支持各類衛(wèi)星任務(wù)。

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

根據(jù)以上假設(shè)條件對衛(wèi)星地面站資源規(guī)劃問題進(jìn)行數(shù)學(xué)建模，為了便于描述，首先給出模型中相關(guān)符號的定義，具體如下：

(1)

R_si為衛(wèi)星si在規(guī)劃周期內(nèi)的任務(wù)需求，?si∈S，R_si={rm∈R|rm.sID=si.sID}，|R_si|表示需求數(shù)量，即在規(guī)劃周期內(nèi)需要對衛(wèi)星si規(guī)劃|R_si|次任務(wù)。

[ST,ET]為規(guī)劃周期，其中ST表示規(guī)劃開始時(shí)間；ET表示規(guī)劃結(jié)束時(shí)間。

根據(jù)以上描述可知，問題的決策變量包括布爾邏輯變量select、r_ts時(shí)間變量以及r_te時(shí)間變量，其中select變量決定在哪些可見時(shí)間窗口內(nèi)執(zhí)行任務(wù)，而r_ts變量以及r_te變量分別決定在可見時(shí)間窗口的哪一個(gè)時(shí)間點(diǎn)開始與結(jié)束任務(wù)。

1.2 目標(biāo)函數(shù)及偏好表達(dá)

論文涉及的優(yōu)化目標(biāo)包括任務(wù)規(guī)劃失敗率和天線負(fù)載平衡度[20]，目標(biāo)函數(shù)的數(shù)學(xué)描述形式為

Y=min{y1,y2}

(2)

1)y1表示任務(wù)規(guī)劃失敗率，其物理含義為無法安排的數(shù)據(jù)傳輸任務(wù)數(shù)量占總?cè)蝿?wù)數(shù)量的百分比

(3)

式中：|F|表示規(guī)劃結(jié)果集中的任務(wù)數(shù)量，其數(shù)值為N；|R|表示任務(wù)集中的任務(wù)數(shù)量，其數(shù)值為M。

2)y2表示天線負(fù)載平衡度，其物理含義為天線工作時(shí)長的標(biāo)準(zhǔn)差與天線平均工作時(shí)長的比值：

(4)

(5)

(6)

偏好信息的引入方式有多種，文獻(xiàn)[24]將其分為以下類型：參考點(diǎn)方式、參考方向方式、偏好函數(shù)方式、目標(biāo)區(qū)域方式、trade-off方式、目標(biāo)比較方式、候選解比較方式、outranking方式等。其中基于參考點(diǎn)方式引入偏好信息的應(yīng)用最為廣泛，這種方式由決策者在目標(biāo)空間中指定一個(gè)點(diǎn)表示其在每一個(gè)目標(biāo)函數(shù)上的期望值，從而引導(dǎo)偏好MOEA求出靠近參考點(diǎn)的部分最優(yōu)解。論文以參考點(diǎn)方式將偏好信息引入偏好MOEA，具體表達(dá)為

Pref=[y1-ref,y2-ref]

(7)

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

1.3 約束條件

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

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

2) 任務(wù)非沖突約束：同一天線相鄰任務(wù)之間滿足一定的時(shí)間間隔，即任務(wù)轉(zhuǎn)換時(shí)間，以供設(shè)備及操作人員進(jìn)行必要的準(zhǔn)備工作。

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

4) 可見時(shí)間窗口約束：任務(wù)起止時(shí)間要位于相應(yīng)的可見時(shí)間窗口之內(nèi)。

5) 任務(wù)最低持續(xù)時(shí)間約束：任務(wù)的持續(xù)時(shí)間不低于任務(wù)所要求的最低持續(xù)時(shí)間。

6) 規(guī)劃周期約束：任務(wù)起止時(shí)間要位于規(guī)劃周期之內(nèi)。

針對以上約束條件，其數(shù)學(xué)形式描述如下：

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)對應(yīng)于天線唯一性約束以及任務(wù)非沖突約束；式(9)確保衛(wèi)星唯一性約束得到滿足；式(10)對應(yīng)于可見時(shí)間窗口約束；式(11)和式(12)分別對應(yīng)于任務(wù)最低持續(xù)時(shí)間約束以及規(guī)劃周期約束。通過以上約束條件，可確保衛(wèi)星地面站資源規(guī)劃結(jié)果的合理性與可行性。

2 算法設(shè)計(jì)

在本節(jié)中，首先將介紹衛(wèi)星地面站資源規(guī)劃問題的偏好MOEA框架；然后對于編碼策略、交叉算子以及變異算子進(jìn)行介紹；最后描述基于領(lǐng)域知識的啟發(fā)式策略。

2.1 算法框架

衛(wèi)星地面站資源規(guī)劃問題的偏好MOEA框架如圖2所示。該算法框架主要包含兩個(gè)部分：一是偏好MOEA部分，二是基于領(lǐng)域知識的啟發(fā)式策略部分。其中，基于領(lǐng)域知識的啟發(fā)式策略嵌入在偏好MOEA中的“變異”與“個(gè)體適應(yīng)度計(jì)算”之間，通過啟發(fā)式策略引導(dǎo)種群向優(yōu)化目標(biāo)函數(shù)值較好的方向進(jìn)化。

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

在偏好MOEA部分，由于在數(shù)學(xué)模型中采用了參考點(diǎn)偏好表達(dá)方式，因此選擇基于參考點(diǎn)的偏好MOEA對問題進(jìn)行求解?？紤]文獻(xiàn)[24]中T-NSGA-II、T-SMS-EMOA、T-R2-EMOA算法的性能優(yōu)勢，論文擬以這3種算法為基礎(chǔ)嵌入基于領(lǐng)域知識的啟發(fā)式策略求解衛(wèi)星地面站資源規(guī)劃問題。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)為本體，在原算法基礎(chǔ)上增加了一層排序規(guī)則，即Chebyshev距離等級，解個(gè)體Chebyshev距離等級的分配與其距參考點(diǎn)的Chebyshev距離大小有直接關(guān)系，Chebyshev距離越小則賦予的等級越高，那么被選擇進(jìn)入下一代種群的概率就越高，因此距離參考點(diǎn)Chebyshev距離越近的個(gè)體就越容易被保留下來。

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

(13)

式中：Γ表示解集；Pref=[p1,p2,…,pΥ]表示參考點(diǎn)；Υ表示優(yōu)化目標(biāo)函數(shù)維度；Leb表示勒貝格測度。

R2-EMOA算法以最大化R2指標(biāo)為進(jìn)化方向，其他方面與SMS-EMOA基本相同，其中R2指標(biāo)定義為

R2(Γ,Θ,P*)=

(14)

當(dāng)這個(gè)參考點(diǎn)設(shè)置為決策者的偏好時(shí)，生成的解就位于偏好信息附近的Pareto前沿，從而體現(xiàn)決策者的偏好。Chebyshev距離計(jì)算方法為

(15)

式中：Φ=[f1,f2,…,fΥ]表示解個(gè)體；Pref=[p1,p2,…,pΥ]表示參考點(diǎn)?；陬I(lǐng)域知識的啟發(fā)式策略部分詳見2.3節(jié)。

算法的終止條件可依據(jù)問題的復(fù)雜性和現(xiàn)實(shí)需求設(shè)置，通常為算法運(yùn)行時(shí)間或者進(jìn)化代數(shù)。算法的輸出結(jié)果為種群中的非支配個(gè)體以及對應(yīng)的目標(biāo)函數(shù)值。

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

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

對于可見時(shí)間窗口wl，當(dāng)wl.select取值為False時(shí)，可見時(shí)間窗口被編碼為0；當(dāng)wl.select取值為True時(shí)，可見時(shí)間窗口被編碼為1。因此，個(gè)體編碼方式可表示為

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

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

(16)

式中：L的數(shù)值等于可見時(shí)間窗口的數(shù)量。

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

2.3 基于領(lǐng)域知識的啟發(fā)式策略

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

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

2.3.1 任務(wù)擴(kuò)充策略

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

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

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

算法1 任務(wù)擴(kuò)充Algorithm 1 Tasks expansion

2.3.2 沖突消解策略

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

在地面站天線沖突消解中，以天線ID為依據(jù)將潛在任務(wù)執(zhí)行時(shí)間窗口集劃分為多個(gè)子集，子集的數(shù)量與天線的數(shù)量是一致的，針對每個(gè)子集進(jìn)行沖突消解。在進(jìn)行沖突消解時(shí)，借鑒了滑動(dòng)窗口的思想，即在滿足任務(wù)最低要求持續(xù)時(shí)間的前提下，任務(wù)的開始時(shí)間和結(jié)束時(shí)間可以在當(dāng)前可見時(shí)間窗口內(nèi)滑動(dòng)。在初始化時(shí)，任務(wù)的開始時(shí)間和結(jié)束時(shí)間分別設(shè)置為當(dāng)前可見時(shí)間窗口的開始時(shí)間和結(jié)束時(shí)間，在滿足任務(wù)最低要求持續(xù)時(shí)間的前提下，可以在當(dāng)前可見時(shí)間窗口內(nèi)確定任務(wù)的開始時(shí)間滑動(dòng)區(qū)域和結(jié)束時(shí)間滑動(dòng)區(qū)域，如圖5所示。

圖5 滑動(dòng)窗口示意圖Fig.5 Illustration of sliding window

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

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

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

2.3.3 任務(wù)縮減策略

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

在任務(wù)縮減策略中，對于規(guī)劃方案中任務(wù)時(shí)長大于任務(wù)需求的情況，以任務(wù)開始時(shí)間為起始點(diǎn)進(jìn)行截?cái)?；對于在?guī)劃方案中任務(wù)數(shù)量大于任務(wù)需求的衛(wèi)星執(zhí)行任務(wù)縮減操作時(shí)，論文使用了基于負(fù)載平衡的縮減方式，這種縮減方式通過計(jì)算執(zhí)行某衛(wèi)星任務(wù)的各天線的工作時(shí)長，選擇工作時(shí)長最大的天線所對應(yīng)的該衛(wèi)星的任務(wù)進(jìn)行刪除，直至滿足該衛(wèi)星的任務(wù)需求，從而使得負(fù)載平衡度這一優(yōu)化目標(biāo)得到進(jìn)一步的改善。

3 實(shí)驗(yàn)研究

論文實(shí)驗(yàn)基于開源多目標(biāo)優(yōu)化算法程序庫MOEAFramework[29]實(shí)現(xiàn)。硬件配置：Intel(R) Core(TM) i5-2430M處理器、4 GB RAM、Windows 8(64位)操作系統(tǒng)。

3.1 實(shí)驗(yàn)場景

以AFSCN標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)集包含7個(gè)獨(dú)立的實(shí)驗(yàn)場景，統(tǒng)計(jì)信息如表1所示。

表1 AFSCN數(shù)據(jù)集Table 1 Datasets of AFSCN

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

3.2 基于領(lǐng)域知識的啟發(fā)式策略實(shí)驗(yàn)分析

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

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

圖6 基于領(lǐng)域知識的啟發(fā)式策略實(shí)驗(yàn)分析Fig.6 Experimental analysis of heuristic strategies based on domain-knowledge

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

(17)

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

由圖7可知，在10 min的運(yùn)行時(shí)間內(nèi)NSGA-II-H、SMS-EMOA-H、NSGA-II、SMS-EMOA均已收斂，R2-EMOA-H及R2-EMOA未收斂，這是由于R2指標(biāo)的計(jì)算較為耗時(shí)，導(dǎo)致在10 min的運(yùn)行時(shí)間內(nèi)算法對解空間的搜索不足；NSGA-II、SMS-EMOA、R2-EMOA在世代距離這一指標(biāo)上均劣于相應(yīng)的NSGA-II-H、SMS-EMOA-H、R2-EMOA-H；NSGA-II-H、SMS-EMOA-H、R2-EMOA-H在迭代初期與末期的世代距離變化范圍在0.015之內(nèi)，這表明論文提出的基于領(lǐng)域知識的啟發(fā)式策略能夠?qū)⑺惴▽饪臻g的搜索范圍約束到具有優(yōu)質(zhì)解的解空間之內(nèi)，從而提高了算法的搜索效率。

圖7 S4實(shí)驗(yàn)場景下算法的收斂性分析Fig.7 Convergence analysis of algorithms in S4 scenario

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

圖8 負(fù)載平衡策略實(shí)驗(yàn)分析Fig.8 Experimental analysis of load-balance strategy

3.3 偏好MOEA實(shí)驗(yàn)分析

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

在參考點(diǎn)的選擇上，通?？梢愿鶕?jù)歷史規(guī)劃方案的統(tǒng)計(jì)值以及應(yīng)用場景進(jìn)行設(shè)置。論文模擬設(shè)置了(0.01,0.3)、(0.05,0.25)以及(0.1,0.2)3組 參考點(diǎn)用于引導(dǎo)算法的搜索進(jìn)程，其中(0.01, 0.3)的參考點(diǎn)更注重任務(wù)規(guī)劃失敗率這一優(yōu)化目標(biāo)；(0.1,0.2)的參考點(diǎn)更注重負(fù)載平衡度這一優(yōu)化目標(biāo)；(0.05,0.25)的參考點(diǎn)代表二者的折衷偏好。在S1、S4、S7場景中使用參考點(diǎn)(0.01,0.3)，S2、S5場景使用參考點(diǎn)(0.05,0.25)， S3、S6場景中使用參考點(diǎn)(0.1,0.2)，實(shí)驗(yàn)結(jié)果如圖9所示。

由圖9可知，T-NSGA-II-H、T-SMS-EMOA-H、T-R2-EMOA-H在S1～S7實(shí)驗(yàn)場景下，均能找到參考點(diǎn)附近的解，即能夠提供決策者偏好的規(guī)劃方案，提升了問題求解的針對性；與未引入偏好信息的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在多數(shù)場景下能夠找到?jīng)Q策者偏好的質(zhì)量更好的解，這體現(xiàn)了偏好算法在求解衛(wèi)星地面站資源規(guī)劃問題上的優(yōu)化性。在相同的運(yùn)行時(shí)間內(nèi)(10 min)，以R2-EMOA構(gòu)建的R2-EMOA-MA算法在S1～S7實(shí)驗(yàn)場景下均未收斂，這是因?yàn)镽2指標(biāo)的計(jì)算比較耗時(shí)；R2-EMOA-H基本收斂，這表明論文提出的基于領(lǐng)域知識的啟發(fā)式策略的求解效率高于文獻(xiàn)[20]的局部搜索策略；T-R2-EMOA-H完全收斂，這說明偏好算法具有更高的求解效率。

圖9 偏好MOEA算法實(shí)驗(yàn)分析Fig.9 Experimental analysis of preference-based MOEA

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

(18)

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

由于衛(wèi)星地面站資源規(guī)劃問題的參考集未知，故獨(dú)立運(yùn)行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次，每次運(yùn)行10 min，以算法生成的所有非支配解構(gòu)建一個(gè)復(fù)合參考集用于IGD-CF指標(biāo)的計(jì)算。論文中設(shè)定的ROI定義為邊長0.1的矩形，針對上述各算法分別獨(dú)立運(yùn)行30次，每次運(yùn)行10 min，各算法的IGD-CF指標(biāo)統(tǒng)計(jì)結(jié)果如表2所示。

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

表2 IGD-CF指標(biāo)性能分析Table 2 Performance analysis of IGD-CF

4 結(jié) 論

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

2) 基于領(lǐng)域知識的啟發(fā)式策略構(gòu)建的偏好MOEA算法與無偏好算法相比，在解的優(yōu)化性上有一定的提升。

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