大型星座混合模擬退火遺傳算法測(cè)控任務(wù)規(guī)劃

馬林，秦 陽(yáng)，秦嘉豪，徐 明

（1.航天工程大學(xué)宇航科學(xué)與技術(shù)系，北京 101416；2.中國(guó)航天科技集團(tuán)有限公司，北京 100048；3.北京航空航天大學(xué)宇航學(xué)院，北京 102206）

0 引言

隨著大型星座的規(guī)模逐漸擴(kuò)大，星座的測(cè)控業(yè)務(wù)工作量激增。傳統(tǒng)的人工編排測(cè)控調(diào)度方案的方法由于耗時(shí)長(zhǎng)、任務(wù)完成度低，已經(jīng)無法適應(yīng)當(dāng)前大型星座測(cè)控業(yè)務(wù)調(diào)度管理的需求。多星測(cè)控調(diào)度問題（Multi-satellite TT&C scheduling，MSTCS）問題是指在多星測(cè)控需求和測(cè)控資源一定的條件下，研究如何對(duì)大量衛(wèi)星的各種測(cè)控需求進(jìn)行管理和調(diào)度，通過合理地分配測(cè)控資源，更好地滿足衛(wèi)星測(cè)控的需求，使得衛(wèi)星發(fā)揮最大的效能，并對(duì)星座的總體設(shè)計(jì)提供指導(dǎo)建議［1］。多星測(cè)控調(diào)度問題是一個(gè)經(jīng)典的NP-Hard 問題，是復(fù)雜調(diào)度問題的一個(gè)具體形式。復(fù)雜調(diào)度問題的可行解空間龐大，約束條件多樣，且具有關(guān)聯(lián)性。因此，通過遍歷可行解空間的方法難以在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)得到問題的滿意解。

為了解決多星調(diào)度問題，國(guó)內(nèi)外涌現(xiàn)出許多相關(guān)研究。關(guān)于多型調(diào)度的研究大多采用先建立數(shù)學(xué)模型，再采用合適的智能算法進(jìn)行求解的方法。現(xiàn)有研究中采用的數(shù)學(xué)模型包括數(shù)學(xué)規(guī)劃模型、約束滿足模型等，采用的智能算法包括粒子群算法、禁忌搜索、模擬退火算法、蟻群算法、遺傳算法以及機(jī)器學(xué)習(xí)和深度學(xué)習(xí)等方法。

針對(duì)多個(gè)點(diǎn)目標(biāo)的成像調(diào)度任務(wù)規(guī)劃研究。賀仁杰［2］進(jìn)行了成像衛(wèi)星有效載荷任務(wù)規(guī)劃的研究，提出了約束滿足模型和混合整數(shù)模型，并采用多種啟發(fā)式算法進(jìn)行了求解，但是沒有在任務(wù)規(guī)劃中考慮衛(wèi)星的測(cè)控問題。Liu 等［3］研究了多星有效載荷任務(wù)規(guī)劃問題，將任務(wù)規(guī)劃分解為任務(wù)分配和動(dòng)作序列生成兩個(gè)子過程，并采用啟發(fā)式算法進(jìn)行了求解。丁祎男等［4］提出一種多目標(biāo)變鄰域模擬退火算法，兼顧了成像星座觀測(cè)任務(wù)的完成度和成像質(zhì)量。韓鵬等［5］基于相對(duì)成像時(shí)刻編碼方式，提出了一種適用于敏捷成像衛(wèi)星任務(wù)規(guī)劃的自適應(yīng)遺傳算法。Kulkarni 等［6］將衛(wèi)星測(cè)控調(diào)度問題建模為0-1 背包問題，并采用智能算法進(jìn)行了求解，但是算法的收斂速度較慢。Zhang 等［7］，Wang 等［8］和Wu等［9］分別采用蟻群算法、啟發(fā)式算法和NSGA-III 對(duì)多星調(diào)度問題進(jìn)行了求解，但是沒有對(duì)算法進(jìn)行進(jìn)一步的優(yōu)化。Spangelo 等［10］研究了單衛(wèi)星多地面站通訊問題，但是不適用于大型星座多星測(cè)控問題的求解。Gao等［11］研究了采用并行計(jì)算的多星任務(wù)規(guī)劃算法，加快了算法收斂速度。Chang 等［12］研究了多星載荷任務(wù)規(guī)劃問題，采用了智能算法進(jìn)行求解，但是沒有考慮衛(wèi)星數(shù)傳。

針對(duì)多個(gè)區(qū)域目標(biāo)或大范圍區(qū)域目標(biāo)的成像調(diào)度任務(wù)規(guī)劃研究，Zhu 等［13］提出了一種分階段的星座觀測(cè)大范圍區(qū)域目標(biāo)的任務(wù)規(guī)劃方法，但沒有考慮衛(wèi)星的星上存儲(chǔ)約束，沒有綜合考慮數(shù)據(jù)下傳。甘嵐等［14］針對(duì)太陽(yáng)同步圓軌道衛(wèi)星星座對(duì)地觀測(cè)任務(wù)，研究了在衛(wèi)星機(jī)動(dòng)情況下對(duì)多區(qū)域目標(biāo)的成像任務(wù)規(guī)劃算法，實(shí)現(xiàn)了星座對(duì)于多目標(biāo)區(qū)域覆蓋率的優(yōu)化。Zhao 等［15］提出了一種基于禁忌搜索的多星任務(wù)規(guī)劃方法，但僅針對(duì)多個(gè)點(diǎn)目標(biāo)，沒有考慮星上存儲(chǔ)約束。Li 等［16］提出了采用多目標(biāo)優(yōu)化的衛(wèi)星集群任務(wù)規(guī)劃方法，但沒有考慮衛(wèi)星星上存儲(chǔ)約束，沒有綜合規(guī)劃衛(wèi)星數(shù)據(jù)下傳。Chen等［17］提出了一種基于整數(shù)序列編碼的姿態(tài)敏捷衛(wèi)星任務(wù)規(guī)劃方法，給出了目標(biāo)可見窗口的分布規(guī)律以及沖突定義方法。Fan 等［18］提出了基于任務(wù)有向圖的多星任務(wù)規(guī)劃方法，考慮了任務(wù)之間的相關(guān)性，將多區(qū)域觀測(cè)問題建模為0-1 規(guī)劃問題，采用啟發(fā)式算法進(jìn)行求解，最大化任務(wù)時(shí)效性，但在任務(wù)規(guī)劃過程中沒有考慮衛(wèi)星的星上存儲(chǔ)資源以及能源約束，并且沒有綜合考慮觀測(cè)數(shù)據(jù)下傳。Wu等［19］將啟發(fā)式算法和精確算法相結(jié)合，采用分立-整合規(guī)劃框架，實(shí)現(xiàn)對(duì)地觀測(cè)星座針對(duì)區(qū)域目標(biāo)的任務(wù)規(guī)劃。Chen 等［20］采用有集成的多通道神經(jīng)網(wǎng)絡(luò)，通過神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)加單星本地規(guī)劃的方法，實(shí)現(xiàn)任務(wù)方案的快速生成，提高任務(wù)規(guī)劃的實(shí)時(shí)性，通過與高性能啟發(fā)式算法的比較，驗(yàn)證了多通道神經(jīng)網(wǎng)絡(luò)算法在任務(wù)方案生成效率以及任務(wù)效能上的優(yōu)勢(shì)。Song 等［21］建立了多星任務(wù)規(guī)劃的混合整數(shù)編碼模型，首先采用改進(jìn)的煙花算法進(jìn)行不可分割任務(wù)的規(guī)劃，之后采用啟發(fā)式規(guī)則進(jìn)行長(zhǎng)時(shí)連續(xù)跟蹤觀測(cè)任務(wù)的任務(wù)規(guī)劃。針對(duì)多星測(cè)控和數(shù)傳任務(wù)規(guī)劃問題，Chen 等［22］建立了最大化任務(wù)收益和任務(wù)完成率的多星任務(wù)規(guī)劃約束滿足模型，在遺傳算法中加入種群擾動(dòng)和低適應(yīng)度個(gè)體淘汰策略。采用遺傳算法獲得任務(wù)分配方案，之后采用本地任務(wù)規(guī)劃算法決定任務(wù)的實(shí)際執(zhí)行序列。Zhang等［23］提出了一種采用遺傳編程的多樹搜索算法，實(shí)現(xiàn)了考慮衛(wèi)星軌控的多星任務(wù)規(guī)劃。Khojah等［24］采用重力梯度算法實(shí)現(xiàn)多目標(biāo)優(yōu)化，并且采用粒子群方法增強(qiáng)了算法的全局搜索能力。Berger 等［25］采用二次規(guī)劃方法建立了多星任務(wù)規(guī)劃模型，提出了NP-Hard 問題的最優(yōu)上界，但是由于算法求解時(shí)間較長(zhǎng)，不適用于工程任務(wù)規(guī)劃使用。Xu 等［26］提出了基于高斯投影的大規(guī)模區(qū)域目標(biāo)動(dòng)態(tài)分解方法，并通過整數(shù)規(guī)劃實(shí)現(xiàn)星座對(duì)于大規(guī)模區(qū)域目標(biāo)成像的任務(wù)規(guī)劃，但是沒有考慮星座的成像數(shù)傳。

為了提供專門應(yīng)用于多星測(cè)控任務(wù)規(guī)劃的有效方法，本文提出了基于擁擠度的混合模擬退火多層編碼遺傳算法。遺傳算法具有全局尋優(yōu)能力，且算法結(jié)構(gòu)清晰，便于針對(duì)具體問題進(jìn)行修改，而且模塊化的算法結(jié)構(gòu)便于在算法流程中加入其他啟發(fā)式操作，以提升算法性能。模擬退火可以通過設(shè)置降溫速率調(diào)節(jié)收斂速度，以每一代最優(yōu)個(gè)體為起點(diǎn)進(jìn)行模擬退火，提高算法收斂速度和種群多樣性。通過在真實(shí)衛(wèi)星系統(tǒng)中的實(shí)驗(yàn)驗(yàn)證了本文提出方法的可行性和高效性。

1 多星測(cè)控問題描述

多星測(cè)控調(diào)度問題可以描述為：包含m個(gè)各類測(cè)控天線的天線集合，為包含n個(gè)衛(wèi)星的大型星座提供時(shí)段 內(nèi)的測(cè)控服務(wù)。每個(gè)衛(wèi)星在這一時(shí)段內(nèi)需要安排若干個(gè)測(cè)控弧段。每個(gè)衛(wèi)星的測(cè)控只能由固定一種或幾種天線進(jìn)行，需要的測(cè)控時(shí)間長(zhǎng)度各不相同。每個(gè)天線在同一時(shí)刻只能對(duì)一顆衛(wèi)星進(jìn)行測(cè)控。多星測(cè)控問題涉及的數(shù)學(xué)符號(hào)的定義如表1所示。

表1 數(shù)學(xué)符號(hào)定義Table 1 Definition of mathematical symbols

采用約束滿足模型（Constraints Satisfy Problem，CSP）對(duì)多星測(cè)控問題進(jìn)行數(shù)學(xué)建模，其CSP 模型包括目標(biāo)函數(shù)和約束條件兩部分，數(shù)學(xué)形式為

目標(biāo)函數(shù)為最大化綜合收益，形式化描述為式（1）。目標(biāo)函數(shù)是指標(biāo)f1，f2，f3的線性組合，各個(gè)優(yōu)化指標(biāo)的形式及其對(duì)方案優(yōu)劣的影響分析如下。代表最大化調(diào)度方案的任務(wù)完成率。多星測(cè)控任務(wù)規(guī)劃的目標(biāo)是采用有限的測(cè)控天線資源，在有限時(shí)間內(nèi)盡量滿足更多衛(wèi)星的測(cè)控任務(wù)，因此需要計(jì)算待安排測(cè)控任務(wù)的完成率，作為表征任務(wù)規(guī)劃結(jié)果方案優(yōu)劣的指標(biāo)代表最大化所有安排任務(wù)的優(yōu)先級(jí)之和，其中pi為任務(wù)i的優(yōu)先級(jí)。由于任務(wù)的重要程度不同，僅考慮全局的任務(wù)完成率并不足以完全反應(yīng)任務(wù)方案的優(yōu)劣，還需要進(jìn)一步計(jì)算歸一化的任務(wù)優(yōu)先級(jí)之和，作為評(píng)價(jià)指標(biāo)之一，擴(kuò)大高優(yōu)先級(jí)任務(wù)的成功安排對(duì)任務(wù)規(guī)劃結(jié)果方案評(píng)價(jià)函數(shù)的影響。f3=E(θ)-S(θ)代表最大化所有任務(wù)弧段仰角的均值，并最小化仰角的方差，其中θ代表任務(wù)弧段的最大仰角。在測(cè)控任務(wù)中，高仰角的弧段不僅可用測(cè)控時(shí)間更長(zhǎng)，而且通信受云層、大氣衰減的影響更小，因此計(jì)算所有安排任務(wù)的弧段仰角作為方案優(yōu)劣的評(píng)價(jià)指標(biāo)之一。但僅考慮所有弧段的仰角之和最大并不能保證任務(wù)方案最優(yōu)，一些大仰角弧段的安排可能對(duì)測(cè)控方案仰角之和產(chǎn)生較大影響，但同時(shí)擠占測(cè)控天線資源，并導(dǎo)致其他多個(gè)任務(wù)的測(cè)控仰角過小。因此，需要同時(shí)計(jì)算所有任務(wù)仰角的方差，作為懲罰項(xiàng)，防止任務(wù)間弧段仰角差異過大。可行調(diào)度方案必須滿足五個(gè)約束條件，各個(gè)約束條件的含義如下。第一，顆衛(wèi)星的測(cè)控必須由指定類型天線進(jìn)行，如式（2）。第二，同一衛(wèi)星不能同時(shí)占用多個(gè)天線，如式（3）。第三，同一天線上安排的相鄰測(cè)控任務(wù)時(shí)間間隔必須大于最小任務(wù)切換間隔，如式（4）。第四，測(cè)控弧段的時(shí)長(zhǎng)必須大于測(cè)控任務(wù)所需的最小時(shí)長(zhǎng)，如式（5）。第五，測(cè)控任務(wù)必須安排在任務(wù)最早開始時(shí)間和任務(wù)最晚開始時(shí)間內(nèi)，如式（6）。

2 混合模擬退火遺傳算法求解多星測(cè)控問題

為求解多星測(cè)控問題，首先，需要獲取任務(wù)規(guī)劃時(shí)段內(nèi)所有衛(wèi)星與所有地面站之間的可用測(cè)控弧段，作為任務(wù)方案的搜索空間。第二，通過設(shè)計(jì)編解碼規(guī)則，建立任務(wù)方案到多層編碼整數(shù)序列之間的映射。第三，通過設(shè)計(jì)遺傳算子實(shí)現(xiàn)任務(wù)方案的進(jìn)化和全局搜索。第四，通過加入基于擁擠度的模擬退火操作，在進(jìn)化過程中平衡星間任務(wù)擁擠度，提高任務(wù)方案優(yōu)化速度與任務(wù)方案質(zhì)量。

2.1 衛(wèi)星可用測(cè)控弧段計(jì)算模型

進(jìn)行大規(guī)模星座數(shù)傳任務(wù)規(guī)劃的前提是獲取星座與地面站系統(tǒng)中所有地面站之間的可見弧段，作為星座數(shù)傳任務(wù)規(guī)劃的搜索空間。本節(jié)給出地面站對(duì)目標(biāo)航天器的可見弧段計(jì)算方法。地面站位于地球表面，與衛(wèi)星的可見性取決于地面站相對(duì)于航天器的仰角，如果仰角大于一個(gè)最小臨界值，并小于一個(gè)最大臨界值，則地面站與航天器之間物理可見，反之則地面站與航天器之間不可見。如圖1所示。

圖1 地面站與衛(wèi)星可見性示意圖Fig.1 Diagram of visibility between ground station and satellite

設(shè)地面站經(jīng)緯度位置為(λ，φ)，高程為H，可以計(jì)算得到地面站在地球固連坐標(biāo)系下的坐標(biāo)(xT，yT，zT)，即

根據(jù)航天器當(dāng)前軌道根數(shù)，可以計(jì)算航天器在地心固連坐標(biāo)系下的坐標(biāo)(xS，yS，zS)，因此，航天器與地面站之間的距離為

由圖1 的三角形關(guān)系，可由d，Re和航天器的地心距r計(jì)算出地面站與航天器連線和地面戰(zhàn)與地心連線之間的張角α1，即

顯然，如果αmin≤α1-90° ≤αmax，則地面站與航天器之間物理可見，且滿足測(cè)控連通性要求，否則兩衛(wèi)星物理不可見，地面站當(dāng)前時(shí)刻不能實(shí)現(xiàn)對(duì)航天器的測(cè)控。采用遞推方法可以獲得一個(gè)圈次內(nèi)地面站對(duì)目標(biāo)航天器的可見弧段。以Δt作為時(shí)間步長(zhǎng)進(jìn)行衛(wèi)星的軌道外推，采用上述方法判斷軌道外推的各個(gè)時(shí)間節(jié)點(diǎn)地面站與衛(wèi)星是否可見，在一個(gè)圈次的軌道外推過程中，地面站與衛(wèi)星的初始可見時(shí)刻與末端可見時(shí)刻之間的時(shí)段即為本圈次衛(wèi)星與地面站的可見弧段。可見弧段的計(jì)算精度主要取決于仿真推進(jìn)的時(shí)間步長(zhǎng)，步長(zhǎng)越小精度越高，步長(zhǎng)越大獲得的可見窗口精度越低。在本文中，推進(jìn)步長(zhǎng)取Δt=1s。

2.2 可行解編解碼規(guī)則設(shè)計(jì)

采用多層編碼方法，染色體為一個(gè)整數(shù)序列。若待安排衛(wèi)星的數(shù)量為n，每個(gè)衛(wèi)星的待安排測(cè)控任務(wù)數(shù)量為pi，則染色體的長(zhǎng)度為染色體的前半段的基因位是衛(wèi)星的序號(hào)，后半段的基因位是對(duì)相應(yīng)位置上衛(wèi)星進(jìn)行測(cè)控的天線。在同一條染色體中，某一衛(wèi)星的序號(hào)出現(xiàn)的第k次，代表該衛(wèi)星的第k次測(cè)控任務(wù)。例如3 個(gè)衛(wèi)星，每個(gè)衛(wèi)星需要安排3 次測(cè)控任務(wù)，則衛(wèi)星序列可以為（3，1，2，2，1，3，1，2，3）。其中1，2，3 分別表示不同的衛(wèi)星，序列中從左到右的三個(gè)1 代表衛(wèi)星1 的三次測(cè)控任務(wù)，2和3與1類似。

解碼方法將染色體轉(zhuǎn)化成一個(gè)可行調(diào)度方案。在本文的算法中采用啟發(fā)式規(guī)則進(jìn)行解碼。首先，將個(gè)體基因的編碼整數(shù)串解碼為各個(gè)天線上待安排的任務(wù)序列。染色體組成如圖2 中（a）所示。按照染色體前半段的衛(wèi)星序列逐一進(jìn)行解碼，將任務(wù)按照順序加入對(duì)應(yīng)天線的待安排任務(wù)序列，獲得每個(gè)天線的任務(wù)弧段安排順序，如圖2（b）所示。其次，按照每個(gè)天線上衛(wèi)星序列的先后順序，選擇可行弧段，并記錄衛(wèi)星和天線已占用的時(shí)長(zhǎng)。解碼弧段分配規(guī)則如圖3所示。

圖2 待安排任務(wù)序列解碼過程示意圖Fig.2 Decoding of task sequences to be preformed

圖3 解碼過程中的弧段分配規(guī)則Fig.3 Feasible window allocation algorithm in decoding process

按照衛(wèi)星測(cè)控任務(wù)的特性，針對(duì)中低軌道衛(wèi)星，一般情況下使用整軌安排模式。首先讀取天線當(dāng)前已占用時(shí)段的終止時(shí)刻TM，并搜索TM之后的待安排衛(wèi)星可用弧段，將整段弧段安排給當(dāng)前任務(wù)。針對(duì)中高軌道衛(wèi)星，由于衛(wèi)星軌道周期較大，與地面站的可見窗口經(jīng)常長(zhǎng)達(dá)數(shù)小時(shí)，浪費(fèi)了天線測(cè)控資源。此時(shí)繼續(xù)采用整軌安排的方法不合理，因此需要通過最短任務(wù)時(shí)長(zhǎng)進(jìn)行解碼。針對(duì)每個(gè)任務(wù)，首先判斷任務(wù)時(shí)間區(qū)間內(nèi)地面站與該衛(wèi)星有無可見區(qū)間，當(dāng)?shù)孛嬲九c衛(wèi)星無可用弧段時(shí)，表明該任務(wù)在當(dāng)前規(guī)劃時(shí)段內(nèi)無法完成，放棄該任務(wù)。TM為衛(wèi)星當(dāng)前解碼已占用時(shí)段的終止時(shí)刻。當(dāng)TM早于或晚于所有可見弧段時(shí)，表明任務(wù)在當(dāng)前規(guī)劃時(shí)段內(nèi)無法完成，放棄該任務(wù)。當(dāng)TM不在某一可見弧段內(nèi)部時(shí)，通過向后尋找大于最短測(cè)控時(shí)間需求的弧段安排該測(cè)控任務(wù)。如果TM恰好在當(dāng)前待安排衛(wèi)星任務(wù)的某個(gè)測(cè)控窗口內(nèi)，首先判斷剩余的弧段是否滿足最短測(cè)控時(shí)間要求。在當(dāng)前測(cè)控時(shí)段不滿足最短測(cè)控時(shí)間要求時(shí)，向后搜索后續(xù)可見弧段，直至任務(wù)成功安排。

2.3 遺傳算子設(shè)計(jì)

在本文設(shè)計(jì)算法中，選擇算子采用輪盤賭方法。輪盤賭選中某個(gè)子代個(gè)體的概率與該個(gè)體的適應(yīng)度成正比，適應(yīng)度較大的染色體被選中的概率大，適應(yīng)度較低的染色體被選中的概率小。輪盤賭既保證了種群向著適應(yīng)度提高的方向進(jìn)化，又保留了種群的多樣性，防止遺傳算法早熟。交叉算子采用隨機(jī)單點(diǎn)交叉。在兩染色體交換某一片段之后，可能會(huì)出現(xiàn)衛(wèi)星序列中基因的缺失或冗余，因此需要對(duì)染色體進(jìn)行合法性檢查，并修復(fù)不合法的染色體。變異算子采用隨機(jī)基因座變異，即隨機(jī)交換兩個(gè)衛(wèi)星編號(hào)的順序。在變異之后可能會(huì)出現(xiàn)天線基因不合法的情況，因此也需要進(jìn)行染色體合法性檢查，并修復(fù)不合法的染色體。各個(gè)遺傳算子的具體操作在2.3.1至2.3.3中詳細(xì)描述。

2.3.1 選擇算子

選擇算子在任務(wù)方案種群進(jìn)化過程中起著決定性作用。選擇操作淘汰掉種群中適應(yīng)度較低的部分個(gè)體，并使得適應(yīng)度較高的個(gè)體具有更大的生存機(jī)會(huì)，使其基因在種群中占有更高的支配地位。為了防止初始化過程中適應(yīng)度較高的部分個(gè)體的基因占優(yōu)而導(dǎo)致種群提前收斂到局部最優(yōu)解，而無法抵達(dá)全局最優(yōu)，本文采用輪盤賭方法進(jìn)行選擇操作，個(gè)體的適應(yīng)度值按照其目標(biāo)函數(shù)值進(jìn)行線性排列分配，并按照適應(yīng)度值構(gòu)造輪盤，即保證了高適應(yīng)度個(gè)體的基因占優(yōu)，又保證了種群多樣性，避免局部收斂。

2.3.2 交叉算子

交叉操作是遺傳算法進(jìn)化的核心機(jī)制，種群中個(gè)體通過交叉獲得基因的重新組合，優(yōu)秀的重組個(gè)體在下一代的選擇操作中更容易存活。在通過選擇操作生成子代種群之后，通過交叉概率pc決定種群中的個(gè)體是否進(jìn)行交叉操作，對(duì)進(jìn)行交叉操作的部分個(gè)體，進(jìn)行隨機(jī)兩兩匹配，采用單點(diǎn)交叉的方法，在任務(wù)序列段隨機(jī)產(chǎn)生交叉點(diǎn)位，并完全交換兩個(gè)體在交叉點(diǎn)位之后的任務(wù)序列和天線序列。由于兩個(gè)體的基因序列無關(guān)，而在交換了序列之后，會(huì)出現(xiàn)部分任務(wù)在任務(wù)序列中多次出現(xiàn)，這與單個(gè)任務(wù)只能由某一資源執(zhí)行一次的任務(wù)規(guī)劃約束，即式（3），發(fā)生了沖突，因此必須修復(fù)不合法的交叉結(jié)果。如圖4 所示，首先遍歷基因中各個(gè)衛(wèi)星測(cè)控任務(wù)數(shù)量與待安排任務(wù)數(shù)量是否一致。針對(duì)不一致的冗余任務(wù)，找到對(duì)應(yīng)的缺失任務(wù)，并采用缺失任務(wù)的基因?qū)θ哂嗳蝿?wù)進(jìn)行替換。

圖4 交叉操作及其染色體修復(fù)過程示意圖Fig.4 Crossover operation and chromosome restoration

2.3.3 變異算子

變異操作是遺傳算法種群中個(gè)體產(chǎn)生新性狀的核心操作，種群中個(gè)體的基因點(diǎn)位通過隨機(jī)的變異產(chǎn)生新的基因組成，維持種群基因的多樣性，增強(qiáng)算法全局搜索能力。在交叉操作之后，種群的基因組成已經(jīng)進(jìn)行了重組，為產(chǎn)生新的基因組成，還需要進(jìn)行變異操作。通過變異概率pm決定種群個(gè)體是否發(fā)生變異。變異過程為隨機(jī)基因點(diǎn)位變異，即隨機(jī)選擇兩個(gè)任務(wù)序列中的基因點(diǎn)位，并交換其基因。

由于變異過程僅交換了衛(wèi)星基因，而沒有交換對(duì)應(yīng)的機(jī)器基因，可能引起變異點(diǎn)位的機(jī)器基因超出該衛(wèi)星的可用測(cè)站集合上限，這與測(cè)控任務(wù)必須由衛(wèi)星的可選天線集合中的天線執(zhí)行的約束條件，即式（2）沖突，因此必須對(duì)變異后的染色體進(jìn)行檢查和修復(fù)。修復(fù)過程如圖5所示。判斷變異衛(wèi)星基因?qū)?yīng)的機(jī)器基因是否超出了該衛(wèi)星可用機(jī)器集合數(shù)目上限，如果判斷超出上限，則重新初始化對(duì)應(yīng)的機(jī)器基因。

圖5 變異操作及其染色體修復(fù)過程Fig.5 Mutation operation and chromosome restoration

2.4 基于擁擠度的快速模擬退火

通過2.3節(jié)所述的單純遺傳算法機(jī)制可以對(duì)多星測(cè)控問題的優(yōu)秀調(diào)度方案進(jìn)行搜索，但經(jīng)過對(duì)遺傳算子的分析可以發(fā)現(xiàn)，對(duì)于種群的進(jìn)化起重要作用的交叉算子僅改變了每個(gè)天線對(duì)應(yīng)衛(wèi)星序列的先后順序，而不同天線之間的衛(wèi)星序列沒有交流。只有變異過程可能引起不同天線的衛(wèi)星序列之間的交流。而變異操作是不定向的，不能保證染色體向著適應(yīng)度高的方向改變。變異概率過高會(huì)導(dǎo)致種群穩(wěn)定性變差。通過提高變異概率增加不同天線之間衛(wèi)星序列交流的方法并不可取。這意味著，每個(gè)天線安排的測(cè)控任務(wù)數(shù)量很大程度上由初始化過程隨即決定。如果一些天線在初始化時(shí)擁擠度較高，則在整個(gè)優(yōu)化過程中始終保持著高擁擠度，各個(gè)任務(wù)之間容易發(fā)生沖突。

為了解決單純遺傳算法存在的問題，提出了基于擁擠度的鄰域生成策略，如圖6 所示。該方法將擁擠度高的天線上安排的測(cè)控任務(wù)分配給擁擠度低的天線，以減少?zèng)_突。將天線的衛(wèi)星序列長(zhǎng)度定義為該天線的擁擠度ci(1 ≤i≤m)為每個(gè)天線上安排的任務(wù)數(shù)量。鄰域生成的過程如下。首先，計(jì)算所有天線的擁擠度。然后，以擁擠度的值構(gòu)造輪盤，抽取代替換的高擁擠度天線ai(1 ≤i≤m)。其次，以擁擠度倒數(shù)的值構(gòu)造輪盤，抽取低擁擠度的天線基因aj(1 ≤j≤m)。最后，用aj代替ai。基于擁擠度的鄰域生成策略意味著低擁擠度的天線容易作為補(bǔ)位天線，使各個(gè)測(cè)站之間的擁擠度盡量平均。基于擁擠度的模擬退火過程如圖7所示。在遺傳算法每一代進(jìn)化完成以后，從種群中抽取適應(yīng)度最高的部分個(gè)體進(jìn)行模擬退火。首先，對(duì)于抽取的每一個(gè)個(gè)體，設(shè)置模擬退火初始溫度η0。然后，采取基于擁擠度的鄰域生成策略生成擾動(dòng)解，計(jì)算擾動(dòng)解和原解適應(yīng)度的差。如果擾動(dòng)解更優(yōu)，則接受擾動(dòng)解，如果原始解更優(yōu)，則按照Metropolis 準(zhǔn)則判斷是否接受擾動(dòng)解。逐步降溫，重復(fù)以上過程，直至達(dá)到結(jié)束溫度。最后，將經(jīng)過模擬退火的染色體放回原種群。

圖6 基于擁擠度的鄰域生成策略Fig.6 Congestion-based neighborhood generation method

圖7 基于擁擠度的模擬退火流程Fig.7 Diagram of congestion-based simulated annealing

2.5 基于擁擠度的SA-GA完整算法流程

綜合2.1 至2.4 節(jié)內(nèi)容，形成的混合模擬退火遺傳算法的完整流程如圖8 所示。第一步，設(shè)置遺傳算法和模擬退火參數(shù)，并初始化種群。第二步，對(duì)種群中所有個(gè)體進(jìn)行解碼并計(jì)算適應(yīng)度。第三步，輪盤賭方法選擇子代個(gè)體，并進(jìn)行選擇、交叉、變異的遺傳操作，生成子代種群。第四步，基于擁擠度對(duì)適應(yīng)度最高的部分個(gè)體進(jìn)行模擬退火，結(jié)束后放回子代種群。不斷重復(fù)迭代上述過程，直至達(dá)到最大遺傳代數(shù)。輸出最優(yōu)解并結(jié)束算法。

圖8 基于擁擠度的混合模擬退火遺傳算法協(xié)調(diào)邏輯Fig.8 Diagram of HSAGA based on congestion

3 工程應(yīng)用結(jié)果與分析

為了驗(yàn)證算法的可行性與高效性，下面進(jìn)行了單純遺傳算法和混合模擬退火遺傳算法的算法對(duì)比實(shí)驗(yàn)。算法實(shí)驗(yàn)在真實(shí)衛(wèi)星和地面站系統(tǒng)的數(shù)據(jù)庫(kù)上進(jìn)行。共有衛(wèi)星180顆，地面站天線32，任務(wù)規(guī)劃周期為24 小時(shí)，每顆衛(wèi)星安排2 到4 個(gè)不等的測(cè)控弧段。兩種算法都取不同的參數(shù)進(jìn)行了10 次仿真實(shí)驗(yàn)，各取最優(yōu)結(jié)果。最優(yōu)解情況下，單純遺傳算法參數(shù)設(shè)置：種群規(guī)模1 000，選擇概率0.9，交叉概率0.8，變異概率0.5。混合模擬退火遺傳算法的參數(shù)設(shè)置：種群規(guī)模500，選擇概率0.9，交叉概率0.9，變異概率0.5，模擬退火比例0.01，初始溫度1 × 108，結(jié)束溫度1 × 103，降溫速率0.1。

兩種算法優(yōu)化軌跡的對(duì)比關(guān)系如圖9 所示，其中圖9（a）為算法歷代以來的最優(yōu)個(gè)體的進(jìn)化軌跡，圖9（b）為每一代種群的平均水平的進(jìn)化軌跡。分析圖9（a）可以發(fā)現(xiàn)，在加入模擬退火操作之后，算法的收斂速度得到很大提升。混合模擬退火遺傳算法在迭代到第50 代時(shí)，綜合收益已經(jīng)達(dá)到單純遺傳算法迭代500 代左右的水平，耗時(shí)縮短為原來的10%。并且，在達(dá)到最大遺傳代數(shù)時(shí)，混合模擬退火遺傳算法的綜合收益也顯著高于遺傳算法，綜合收益達(dá)到0.918，任務(wù)完成率達(dá)到99.7%。分析圖9（b）可以發(fā)現(xiàn)，整個(gè)進(jìn)化歷程中，加入混合模擬退火操作顯著提升了整個(gè)種群的表現(xiàn)。實(shí)驗(yàn)驗(yàn)證了混合模擬退火算法的可行性與高效性。

圖9 算法對(duì)比試驗(yàn)進(jìn)化軌跡Fig.9 Evolution trace of the algorithm comparison test

為了進(jìn)一步驗(yàn)證在加入基于擁擠度的模擬退火操作之后星間任務(wù)分配是否變得更加均衡，將單純遺傳算法（GA）優(yōu)化獲得的最優(yōu)結(jié)果方案與基于擁擠度的混合模擬退火遺傳算法（SA-GA）計(jì)算得到的最優(yōu)結(jié)果方案進(jìn)行對(duì)比。

如圖10 所示，圖10（a）為沒有加入基于擁擠度模擬退火操作時(shí)的各個(gè)天線上安排任務(wù)數(shù)量的分布情況，各個(gè)天線之間任務(wù)數(shù)量差異較大，圖10（b）為加入了基于擁擠度模擬退火操作之后各個(gè)天線上安排任務(wù)數(shù)量的分布情況，各星上安排的任務(wù)數(shù)量分布在均值附近。將各個(gè)天線上安排任務(wù)數(shù)量的方差作為評(píng)價(jià)指標(biāo)，如表2所示，在加入基于擁擠度的模擬退火操作之后，任務(wù)擁擠度方差降低為未加入該操作的47.81%。

圖10 加入基于擁擠度的模擬退火前后任務(wù)擁擠度對(duì)比Fig.10 Comparison of congestion before and after incorporation of congestion-based simulated annealing

表2 GA和HSAGA任務(wù)擁擠度方差對(duì)比Table 2 Congestion deviation comparison between GA and HSAGA

4 結(jié)論

為了解決大型星座的測(cè)控調(diào)度問題，建立了大型星座多星測(cè)控任務(wù)規(guī)劃約束滿足模型。采用多層編碼方法實(shí)現(xiàn)多星、多測(cè)控天線測(cè)控任務(wù)分配編碼。通過對(duì)多層編碼遺傳算法中算子特性的分析，提出了基于擁擠度的模擬退火操作方法，彌補(bǔ)了單純遺傳算法天線擁擠度高的問題，提高了算法效率。通過算法對(duì)比實(shí)驗(yàn)驗(yàn)證了混合模擬退火遺傳算法的有效性和高效性。具體表現(xiàn)為：算法耗時(shí)減少為單純遺傳算法的10%；任務(wù)完成率達(dá)到99.7%；綜合收益達(dá)到0.918，顯著高于單純遺傳算法。并且，在加入基于擁擠度的混合模擬退火之后，各個(gè)天線的任務(wù)擁擠度均衡性顯著改善，加入該操作后，天線間任務(wù)數(shù)量方差降低為未加入該操作時(shí)的47.81%。