基于自適應模擬退火的大規(guī)模星座測控資源調度算法

伍國華，王天宇

中南大學 交通運輸與工程學院，長沙 410073

目前廣泛使用的氣象預報衛(wèi)星、偵察資源衛(wèi)星、導航通信衛(wèi)星等人造衛(wèi)星為國家安全、社會經(jīng)濟和日常生活帶來了非常多的便利，因此受到了世界上各個國家的高度重視［1］。航天技術的持續(xù)發(fā)展，特別是小型微型衛(wèi)星技術的日趨成熟，使得衛(wèi)星可以在地質災害預報和測量、地面交通道路情況監(jiān)視和戰(zhàn)時戰(zhàn)場信息采集等方面提供越來越多的便利服務，因此各個國家特別是航天大國都在不斷增加發(fā)射衛(wèi)星的計劃，導致空間中在軌衛(wèi)星的種類和數(shù)量正處于激增的狀態(tài)，并且還會以更大的增速持續(xù)下去［2-3］。隨著大型衛(wèi)星群技術可行化之后，關于大規(guī)模星座的實現(xiàn)便獲得了越來越多的關注，因為大規(guī)模星座具有龐大的解構空間，可以容納數(shù)量巨大的衛(wèi)星群，在通信時延降低、導航信號增強、遙感精度提升等方面具有獨特的發(fā)展?jié)撃芎蛢?yōu)勢，并且其成本較低、風險較小。由SpaceX 公司打造的“星鏈”項目，計劃使用上萬顆衛(wèi)星，意圖打造衛(wèi)星寬帶互聯(lián)網(wǎng)，為全球提供高速度、低延遲的互聯(lián)網(wǎng)服務。中國提出的“新基建”領域內(nèi)也把空間互聯(lián)網(wǎng)大規(guī)模星座建設視為一個主要的組成部分，因此，未來大規(guī)模星座的發(fā)展將會非常迅猛［4］。

衛(wèi)星測控網(wǎng)是跟蹤、測量和控制航天器的地面系統(tǒng)，對大規(guī)模星座中的衛(wèi)星進行跟蹤，測量位置和坐標等信息，分析衛(wèi)星及星上設備的工作情況。衛(wèi)星沿著自身的軌道運行至測控站上方一定范圍內(nèi)時，測控站通過測控天線與衛(wèi)星建立相應的通信鏈路，實現(xiàn)對衛(wèi)星遙測、遙控和跟蹤定軌等相關工作［5］。由此可見，實現(xiàn)對衛(wèi)星的跟蹤和測量以及相應的控制，以及成功獲取星上搭載設備和荷載的狀態(tài)信息等操作必須通過衛(wèi)星和測控站的相互配合。由于測控站的建設成本比較高，同時建設周期比較長，需要投入很大的運行維護成本，以及受到國境地理范圍等限制，所以可利用的測控資源相對匱乏，不可避免地會產(chǎn)生測控資源無法滿足衛(wèi)星測控需求的問題，實質上屬于過度需求和稀缺資源之間的矛盾［6-7］。

目前國內(nèi)外關于衛(wèi)星測控的研究主要集中在測控天線與衛(wèi)星之間建立通信鏈路的過程，針對衛(wèi)星測控資源調度的研究相對偏少，而關于衛(wèi)星測控資源調度方法的研究主要分為精確性算法［8-9］、啟發(fā)式算法［10-11］和智能優(yōu)化算法［12-15］3 類調度算法，其中精確性算法一般針對較小規(guī)模情況使用，可以求得精確的最優(yōu)解，而啟發(fā)式算法通過構造一些啟發(fā)式規(guī)則或者利用一些啟發(fā)式信息，可以在較短的時間內(nèi)獲得一個可行解，智能優(yōu)化算法則對于求解組合優(yōu)化問題表現(xiàn)出了較強的尋優(yōu)效果，兼顧求解時間和求解精度的基礎上能夠搜索到一個質量較優(yōu)的最優(yōu)解。

Marinelli 等［8］將衛(wèi)星與地面站之間的測控調度問題表述為一個多處理器任務調度問題，建立了以總收益最大化為優(yōu)化目標的數(shù)學規(guī)劃模型，并且設計了基于混合整數(shù)規(guī)劃（Mixed Integer Program， MIP）啟發(fā)式的拉格朗日算法對于小規(guī)模的仿真場景進行求解。Zhang 等［12］通過建立可見弧和作業(yè)周期的獨立集模型，以最小化測控站的工作負載為優(yōu)化目標，設計了兩階段信息素軌跡更新的蟻群優(yōu)化算法求解多星測控資源調度問題。Chen 等［13］提出一種帶有種群擾動和消除策略的遺傳算法對衛(wèi)星測控的任務規(guī)劃問題進行求解，得到任務調度序列之后再用啟發(fā)式任務規(guī)劃算法生成最終的調度方案。Stottler［16］和Barbulescu［17］等主要以美國空軍的衛(wèi)星地面通信網(wǎng)為研究對象，并且針對專用設備的具體特點建立了一個數(shù)學整數(shù)規(guī)劃模型進行求解，得出一個無沖突的衛(wèi)星通信調度方案。Xhafa 等［18］則對于歐洲航天局的地面測控站網(wǎng)絡進行了相關研究，并且基于特定的地面控制網(wǎng)采用遺傳算法對于衛(wèi)星任務進行調度。Vazquez 等［19］通過構建一個關于天線和衛(wèi)星之間分配的整數(shù)線性規(guī)劃模型，針對二者之間的沖突進行消解，能夠得到最終不沖突的解決方案。Sarkheyli 等［20］結合圖理論對低軌衛(wèi)星和地面站之間進行通訊需要滿足的約束條件進行了分析，然后提出一種禁忌搜索算法對小規(guī)模的任務進行分配。Song 等［21］針對衛(wèi)星觀測環(huán)境的任務和地面站資源的分配問題進行研究，用遺傳算法得到初步解之后再用局部搜索策略改進得到最終調度方案。

康寧和武小悅［9］通過建立航天測控調度問題的整數(shù)規(guī)劃模型，運用次梯度優(yōu)化算法求得了拉格朗日對偶問題的上界解，并在小規(guī)模案例上進行了驗證。劉建平等［10］針對航天測控網(wǎng)調度問題提出一種基于混合啟發(fā)式的解構造算法，使初始解的質量有所提高。辛立強等［11］針對復雜衛(wèi)星任務之間的特殊關系提出了一種考慮全局需求的啟發(fā)式算法，相比傳統(tǒng)的貪婪啟發(fā)式算法效果更好。李玉慶等［14］在考慮測控弧段具有優(yōu)先級的基礎上，提出一種改進的遺傳算法，利用改進的交叉和變異算子進行求解。薛乃陽等［15］將傳統(tǒng)的國有測控資源和商業(yè)測控資源進行聯(lián)合調度，總結歸納二者各自的特點，針對不同的特定約束條件，設計了改進的遺傳算法進行求解，有效提高了不同類型的測控資源整體利用率。凌曉冬等［22］對于衛(wèi)星測控調度技術進行研究，通過分析問題的有關特點，建立了相應的CSP 模型。陳峰和武小悅［23-24］以可見測控弧段為對象進行編碼，改進遺傳算法進行分階段求解，并且開發(fā)了一個小型系統(tǒng)集成調度算法。宋彥杰等［25］對于衛(wèi)星任務分配到地面站資源的調度問題，設計了帶有局部優(yōu)化策略的遺傳算法求解得到任務調度序列，然后再用任務規(guī)劃算法生成最終調度方案。

衛(wèi)星測控資源調度問題是NP-Hard 問題［26］，針對衛(wèi)星數(shù)量在500 以內(nèi)的中小規(guī)模衛(wèi)星測控資源調度問題，部分研究已經(jīng)取得了一些較好的成果［13，15，21］，可以完成多個天線對多顆衛(wèi)星的跟蹤測控任務。當衛(wèi)星數(shù)量超出此規(guī)模時，可認為是大規(guī)模星座測控資源調度問題，衛(wèi)星的測控需求大幅增加以及用戶需求多樣性增加，并且多星同時過境的次數(shù)也大幅增加，這時問題求解也會更加復雜［27］。使用傳統(tǒng)的調度方法對大規(guī)模的衛(wèi)星測控任務進行調度，會導致測控系統(tǒng)效率低下，無法保障大規(guī)模星座的功能實現(xiàn)，難以滿足實際需求［28］。

由當前研究現(xiàn)狀發(fā)現(xiàn)，雖然有部分文獻研究了衛(wèi)星測控資源調度問題，但是針對大規(guī)模星座測控資源調度問題的模型和算法研究依然缺乏。為充分保障大規(guī)模星座的功能實現(xiàn)，完成大規(guī)模衛(wèi)星測控任務的調度安排，衛(wèi)星測控調度系統(tǒng)面臨著新的挑戰(zhàn)，如何設計高效的調度算法，合理地進行資源調度，提高現(xiàn)有測控資源使用效率和測控任務完成收益，從而生成衛(wèi)星測控資源調度方案，對于充分利用有限的測控資源，提高地面站測控資源的利用率，緩解測控資源的緊張現(xiàn)狀，進一步實現(xiàn)大規(guī)模星座的價值，都具有重要的研究意義［29］。

在分析和研究大規(guī)模星座測控資源調度問題的基礎上，建立系統(tǒng)模型并且設計求解算法，主要貢獻和創(chuàng)新如下：

1） 分析了大規(guī)模星座測控資源調度問題中過度需求和稀缺資源的特點，以最大化任務完成收益為優(yōu)化目標，以任務需求相關約束和資源使用相關約束等為約束條件，構建了關于衛(wèi)星測控資源調度問題的約束滿足模型，提出一種任務選擇可用測控弧段可能發(fā)生沖突的風險概率評估方法，并且根據(jù)測控機會和沖突度2 個啟發(fā)式準則構造適應度函數(shù)，設計基于適應度的任務分配算法以生成一個質量較優(yōu)的初始可行解。

2） 設計了一種結合擾動策略和禁忌表的自適應模擬退火算法（Adaptive Simulated Annealing algorithm combined with Tabu list and Perturbation strategy， ASATP），其中自適應機制是指算法迭代運行過程中，溫度隨迭代次數(shù)的增加可以自適應地調整下降速率，同時提出考慮問題領域知識的高效鄰域算子，不同鄰域結構的選擇概率也會動態(tài)調整更新；禁忌表策略是指算法迭代優(yōu)化過程中將部分任務加入禁忌列表，避免短期內(nèi)重復搜索相同解，擴大算法搜索范圍，增強算法全局搜索能力；擾動策略是指對當前最優(yōu)解進行局部擾動，更好地平衡算法的全局和局部搜索能力，利于算法跳出局部最優(yōu)解。

3） 通過構建多組大規(guī)模衛(wèi)星測控任務的實驗用例來驗證算法的有效性。同時通過實驗將本文提出的算法與模擬退火算法（Simulated Annealing algorithm， SA）、遺傳算法（Genetic Algorithm， GA）、基于適應度的任務分配算法（Task Arrange Algorithm based on Fitness Value，TAAFV）和最大權重最先分配算法（High Weight First Arrange algorithm， HWFA）比較，結果表明，本文提出的算法能分別將任務收益率提高10.34%、23.59%、23.20%和46.51%。最后對算法進行性能測試和收斂性分析，驗證了其在任務收益率和資源利用率等方面的增益。

1 衛(wèi)星測控資源調度問題及模型

1. 1 問題描述與基本要素

衛(wèi)星測控資源調度過程如圖1 所示，衛(wèi)星測控業(yè)務系統(tǒng)主要由位于空間在軌運行的各用戶衛(wèi)星、位于地面的測控設備以及調度中心所組成。衛(wèi)星測控的業(yè)務流程主要包括：首先由用戶向調度中心發(fā)出關于在軌衛(wèi)星的測控任務請求，然后調度中心根據(jù)衛(wèi)星的測運控需求生成相應的測控資源調度計劃，并且統(tǒng)一調度部署在地面的測控站網(wǎng)設備，最后由測控設備執(zhí)行具體的測控任務，及時上注各項飛行狀態(tài)設置指令，并傳遞飛行數(shù)據(jù)至調度中心，對于大規(guī)模星座的功能實現(xiàn)具有不可替代的重要作用。

圖1 衛(wèi)星測控資源調度過程Fig.1 Satellite TT&C resource scheduling process

衛(wèi)星繞軌道運行，從某一時刻開始經(jīng)過測控站上空，此時地面站測控天線可以與衛(wèi)星之間建立通信鏈路，持續(xù)一段時間后，衛(wèi)星運行超出測控天線發(fā)射信號的接收范圍，通過測控過程實現(xiàn)對衛(wèi)星的遙測、遙控和跟蹤等相關工作，以滿足用戶的相關請求和維持衛(wèi)星的正常運行狀態(tài)，進一步保障大規(guī)模星座的功能實現(xiàn)。

測控站通常固定在地面某一位置，而衛(wèi)星繞地球運行的軌道會因為地球自轉產(chǎn)生偏移，因此在一個調度周期內(nèi)，只有在同時滿足最小仰角和通信頻段等要求的時間區(qū)間內(nèi)，測控天線與衛(wèi)星之間才可以建立通信鏈路，完成相關測控操作。將這些可見時段定義為可見測控弧段，如圖2 所示，當衛(wèi)星與測控站之間滿足最小仰角要求以及頻段相互符合等條件時，即t1和t2之間的可見測控弧段內(nèi)，測控天線進行角度調整后即可進行測控操作，完成測控任務需求，保障衛(wèi)星的正常運行和功能實現(xiàn)。

圖2 可見測控弧段示意圖Fig.2 Schematic of visible TT&C arc

此外用戶結合自身需求對于衛(wèi)星的測控請求往往具有一定的時效性要求，即衛(wèi)星測控任務完成的時間如果在用戶指定的時間區(qū)間內(nèi)，那么完成任務所獲得的價值最高，否則完成該任務不再具有價值或價值比較低。如圖3 所示，衛(wèi)星與測控站之間的可見測控弧段與測控任務允許執(zhí)行的測控時段的交集是該測控任務的可用測控弧段。可用測控弧段一定在可見測控弧段或者任務要求執(zhí)行的時間區(qū)間之內(nèi)，只有在可用測控弧段內(nèi)執(zhí)行該任務才能滿足用戶需求，獲得相應的收益，為實現(xiàn)大規(guī)模星座的功能提供價值。

圖3 可用測控弧段示意圖Fig.3 Schematic of available TT&C arc

通常安排測控任務時會把可用測控弧段的所有時間資源全部分配給一個任務，將整個可用測控弧段視為實際執(zhí)行該測控任務的時間段，不可再被其他任務占用。如圖4 所示，任務1 和任務3 分別被調度之后，任務2 沒有機會再進行調度，加劇了測控任務之間對于時間資源的競爭。

圖4 任務沖突Fig.4 Task conflict

實際上可用測控弧段內(nèi)并非所有時間都在執(zhí)行測控任務，以及測控傳輸技術的發(fā)展使得單次測控的執(zhí)行時間也在縮短，即實際測控執(zhí)行時間只占可用測控弧段的一部分。因此將可用測控弧段中空余的時間資源合理地分配給其他任務，可以有效提升測控資源利用率，進而提高系統(tǒng)整體效能。如圖5 所示，在滿足任務的最短測控時長等約束條件下，將原本分配給任務1 和任務3 的可用測控弧段所釋放的空余時間資源分配給任務2 之后，3 個任務全部成功調度，顯然提高了任務完成率，提升了測控資源使用效率。

圖5 任務沖突消解Fig.5 Task conflict resolution

1. 2 約束滿足模型構建

針對大規(guī)模星座測控資源調度問題，考慮其中涉及的諸多復雜要素，分析衛(wèi)星測控任務的需求，以及測控資源的相關約束條件，研究影響測控資源分配的合理因素，進行數(shù)學建模。為了便于進行數(shù)學化的描述，給出模型中相關符號的定義如下：

調度周期時間區(qū)間用[TS，TE，TD]表示，其中TS 指調度周期起始時間，TE 指調度周期結束時間，TD 指調度周期時段總時長，相關要素均限定在TD 內(nèi)。

星座衛(wèi)星集 合用S={ sk|k=1，2，…，K }表示，其中K 指衛(wèi)星數(shù)量，代表了星座的規(guī)模。?sk∈S，具體可以用sk=( idsk，frsk，task)表示。其中idsk表示星座中該衛(wèi)星對應的標識； frsk表示該衛(wèi)星所要求的測控頻段；task表示由該衛(wèi)星所產(chǎn)生的測控任務。

地面測控站集合用G={ gq|q=1，2，…，Q }表示，其中Q 指地面站數(shù)量。?gq∈G，具體可以用gq=( idgq，frgq)表示。其中idgq表示地面測控站對應的標識；frgq表示該地面站測控天線可以執(zhí)行的測控頻段。

衛(wèi)星測控任務集合用T={ti|i=1，2，…，N }表示，其中N 指任務數(shù)量。?ti∈T，具體可以用表示。其中idti表示與任務相對應的標識；表示該任務所屬的衛(wèi)星標識；pti表示成功執(zhí)行該任務所獲得的收益；dti表示該任務執(zhí)行時所需要的最短持續(xù)服務時長；adti表示執(zhí)行該任務時所需要的提前準備時間；即測控天線與衛(wèi)星之間建立通信鏈路需要的校準時間；nsti和neti分別表示該任務可接受服務時間范圍的最早開始時間和最晚結束時間。

測控天線資源集合用R={rj|j=1，2，…，M }表示，其中M 指測控天線數(shù)量。?rj∈R，具體可以由進行表示。其中idrj表示測控天線的編號；表示測控天線所屬的測控站標識；dgrj表示測控天線要求滿足的最小角度；trrj表示測控天線在連續(xù)執(zhí)行2 個測控任務之間所需要的姿態(tài)調整時間。

衛(wèi)星與測控站之間的測控弧段集合用Ai，j=表示，其中L 指任務i 與測控天線j 之間所具有的可見測控弧段數(shù)量，即i 代表了對應的任務標識，j 代表了對應的測控天線編號。，可 以由表示。其 中osali，j表示測控弧段的最早可見時間，即測控天線能夠與衛(wèi)星建立起通信鏈路的最早開始時間，oeali，j表示測控弧段的最晚結束時間；dgali，j表 示 測 控 天 線 與衛(wèi)星之間的（連線與地面水平線之間的）夾角。

調度結果集合用W={wi|i=1，2，…，N }表示。?wi∈W，具體可以用wi=(idti，yi，fsi，fei，idali，j，idsk，idrj，idgq)表示。其中idti表示對應的任務標識，決策變量用yi表示；當yi=1 的時候，表示任務被成功調度，否則yi=0；fsi表示任務實際執(zhí)行的開始時間；fei表示任務實際執(zhí)行的結束時間；idali，j表 示 任 務 執(zhí)行選擇的測控弧段標識；idsk表示任務所屬的衛(wèi)星標識；idrj表示任務執(zhí)行選擇的天線編號；idgq表示執(zhí)行天線所屬的測控站標識。

為了研究本質科學問題，在合理反映實際問題特點和情況的前提下，做出以下假設：在整個調度周期內(nèi)屬于靜態(tài)調度環(huán)境，不考慮動態(tài)新任務的產(chǎn)生和影響；不考慮由于測控資源設備的故障或者衛(wèi)星等航天器的故障所產(chǎn)生的影響；測控設備全部屬于固定測控站，并且具有足夠的電量及其他所需要的能量儲備；在調度過程中，測控資源與衛(wèi)星之間的通信鏈路從建立開始直到該任務處理完成期間不發(fā)生中斷和被搶占的情況。

綜上，衛(wèi)星測控資源調度問題的約束滿足模型建立如下：

其中，式（1）表示優(yōu)化模型的目標函數(shù)為最大化任務總收益值，f 代表調度方案的任務收益值。式（2）～式（14）表示衛(wèi)星測控資源調度問題的約束條件，是保證調度方案合理性與可行性的關鍵。具體包括，式（2）表示任務唯一性約束，即每個測控任務至多被執(zhí)行一次；式（3）～式（5）表示調度周期約束，即涉及的規(guī)劃要素均限定在規(guī)劃時間段之內(nèi)，包括測控任務允許服務的起止時間、可見測控弧段的起止時間和任務實際執(zhí)行的起止時間都要位于規(guī)劃周期之內(nèi)；式（6）表示衛(wèi)星測控能力唯一性約束，wsk代表調度結果集W 中屬于衛(wèi)星sk的子集，即任意時刻，衛(wèi)星至多與某一天線資源處于任務執(zhí)行狀態(tài)，同一衛(wèi)星至多只能與一個測控站天線建立通信鏈路；式（7）表示天線測控能力唯一性約束，wrj表示調度結果集W 中屬于天線資源rj的子集，即任意時刻，同一天線資源至多與某一顆衛(wèi)星建立通信通道并處于任務執(zhí)行狀態(tài)；式（8）表示測控角度約束，即測控弧段的角度滿足仰角最低要求時，衛(wèi)星和測控站之間才可以執(zhí)行測控任務；式（9）表示測控頻段約束，即只有當測控設備具備該頻段的通信條件時，才可完成對于該任務的測控；式（10）和式（11）表示任務實際執(zhí)行時間約束，即任務的實際測控開始時間應不早于可見測控弧段的最早開始時間和任務允許服務的最早開始時間，任務的實際測控結束時間應不晚于可見測控弧段的最晚結束時間和任務允許服務的最晚結束時間；式（12）表示任務最短持續(xù)時長約束，即任務的持續(xù)測控時間不短于任務所要求的最低服務時長；式（13）表示天線切換時間約束，即同一天線執(zhí)行2 次相鄰任務之間需要滿足一定的時間間隔，以供設備及操作人員進行必要的準備工作，天線資源切換任務狀態(tài)時必須滿足上一任務執(zhí)行完畢且時間間隔大于天線rj的最短任務準備時長；式（14）表示實際開始時間應該在衛(wèi)星與測控站建立通信鏈路所需要的姿態(tài)調整時間adti之后才能開始。

綜上所述，以最大化任務總收益為目標函數(shù)，考慮任務需求和資源使用等相關約束條件，構建衛(wèi)星測控資源調度問題的約束滿足模型式（1）～式（14）。可以看出該模型具有組合優(yōu)化問題的特征，通常對于組合優(yōu)化問題的數(shù)學模型求解難度較大，而且其解空間會隨著任務規(guī)?；蛘哔Y源數(shù)量的增長呈指數(shù)增長［30-31］。這一問題的難點在于過度任務需求和稀缺測控資源之間的矛盾，難以保證全部任務都可以成功執(zhí)行。此外，模型具有的決策變量維度和約束條件非常復雜，一般的通用算法難以直接用于求解該模型。因此，針對問題和模型特點設計了結合擾動策略和禁忌表的自適應模擬退火算法。

2 ASATP 算法介紹

2. 1 算法流程

ASATP 算法的整體流程如圖6 所示。算法以星座衛(wèi)星集合S、地面測控站集合G、衛(wèi)星測控任務集合T、測控天線資源集合R、測控弧段集合Ai，j和調度周期區(qū)間[TS，TE]為輸入，以基于適應度的任務分配算法生成質量較優(yōu)的初始解，然后基于初始解進行迭代優(yōu)化，當?shù)螖?shù)滿足設定的終止條件時，算法結束并輸出全局最優(yōu)解，將最優(yōu)解處理得到調度計劃W。迭代優(yōu)化過程中以自適應機制更新溫度，采用基于貪婪準則和概率搜索的鄰域結構產(chǎn)生鄰域解，并且動態(tài)調整鄰域結構的選擇概率，結合禁忌表避免短期內(nèi)重復搜索，以局部擾動策略跳出局部最優(yōu)解等引導算法朝著優(yōu)化目標不斷優(yōu)化。

圖6 ASATP 算法流程Fig.6 Algorithm process of ASATP

2. 2 算法復雜度

結合擾動策略和禁忌表的自適應模擬退火算法框架和偽代碼如算法1 所示。

算法1 結合擾動策略和禁忌表的自適應模擬退火算法1. 初始化設置算法參數(shù)2. 設置迭代計數(shù)器Itr=0，ConItr=0 3. 產(chǎn)生初始解S0，計算初始解目標函數(shù)值f (S0)4. 設置最優(yōu)解S*，并且令S*=S0 5. While Itr ＜MaxItr & ConItr ＜MaxConItr 6. 迭代次數(shù)Itr=Itr+1 7. 動態(tài)更新鄰域結構選擇概率8. If Itr%NItr=0 9. For k=1 →2 10. pro′k=ωprok+(1-ω)(suck/selk)11. End for 12. For k=1 →2 13. prok=pro′k/∑k=1，2 pro′k 14. End for 15. selk=0，suck=0 16. End if 17. 根據(jù)鄰域選擇概率采用輪盤賭選擇鄰域結構18. selk=selk+1 19. 根據(jù)鄰域結構產(chǎn)生鄰域解S′20. If f (S)＜f (S′)21. 更新當前解為新解S=S′22. suck=suck+1 23. 更新Ri=0 24. 更新禁忌表，將被替換的任務插入禁忌表25. 判斷禁忌表長度已滿，釋放最先加入的任務26. Elseif exp(( f (S′)-f (S))/θi)＞rand(0，1)27. 更新當前解為新解S=S′28. 更新Ri=Ri+1 29. 更新禁忌表，將被替換的任務插入禁忌表30. 判斷禁忌表長度已滿，釋放最先加入的任務31. End if 32. 局部擾動策略33. If Itr%PItr=0 34. 對當前解進行局部擾動35. End if 36. 更新最優(yōu)解37. If f (S*)＜f (S)38. S*=S 39. 更新ConItr=0 40. Else 41. ConItr=ConItr+1 42. End if 43. 更新溫度44. θi=θm+μ ln(1+Ri/λ)45. End while 46. Return S*輸出最優(yōu)解

觀察上述算法框架可知，初始解生成階段算法復雜度為O(N+Nw)，其中w 表示每個任務的測控弧段數(shù)量，由于w 是一個常數(shù)，所以初始解生成階段算法時間復雜度為O(N )。同理，算法迭代優(yōu)化階段的復雜度為O(Itr(1+N ))，其中Itr 表 示 算 法 迭 代 次 數(shù)，且Itr ≤10N，即O(Itr(1+N ))＜O(N2)。故所提出算法的時間復雜度為O(N2)，可以在多項式時間內(nèi)執(zhí)行完畢。

2. 3 算法設計

2.3.1 初始解生成

已經(jīng)有大量的研究表明［32-34］，初始解的選取對于模擬退火算法的收斂速度和最終效果具有比較大的影響，初始解選取的越恰當，模擬退火算法迭代優(yōu)化的最終收斂效果越好。

針對大規(guī)模星座的測控資源調度問題，設計一種基于適應度的任務分配算法，提出測控機會和測控弧段沖突度2 個啟發(fā)式準則，根據(jù)測控機會和沖突度構造適應度函數(shù)，按照輪盤賭思想將任務優(yōu)先分配到適應度大的資源上，從而生成質量較優(yōu)的初始可行解。

1） 測控機會準則

由于衛(wèi)星在一個調度周期內(nèi)繞地球運行多圈，即多次經(jīng)過地面測控站，所以每個任務在測控資源下的可用測控弧段可能有多個。考慮每個任務在不同測控資源下的可用測控弧段數(shù)量也不一樣，即任務和不同測控資源之間可選擇的執(zhí)行機會不同。

對測控機會進行量化，在一個調度周期內(nèi)，任務在測控資源下的測控機會，在數(shù)值上等于任務在該測控資源下的可用測控弧段數(shù)量。

2） 測控弧段沖突度準則

不同測控任務可選擇的可用測控弧段之間可能存在一定的交叉關系，同時每個任務的實際執(zhí)行時間在滿足約束條件的前提下可以在測控弧段內(nèi)滑動。由于測控資源的能力限制，即同一時間測控天線只能對于一顆衛(wèi)星進行測控，不能同時進行多個任務，而且每個任務的執(zhí)行過程必須完整且連續(xù)，即從開始到結束不能中斷。因此，任務選擇不同的可用測控弧段，以及在滑動的實際執(zhí)行時間過程中發(fā)生沖突的可能性也不一樣。

如果2 個任務選擇的測控弧段本身不存在交集或者屬于不同的測控資源，則它們發(fā)生沖突的概率為0。如圖7 所示，任務1 選擇的測控弧段和任務2 選擇的測控弧段之間沒有重疊，所以2 個任務的實際測控弧段之間一定不會發(fā)生沖突。

圖7 無沖突示意圖Fig.7 No conflict schematic

如果2 個任務選擇的測控弧段幾乎完全重疊且屬于同一個測控資源，那么2 個任務發(fā)生沖突的概率也會非常大。如圖8 所示，任務1 選擇的測控弧段和任務2 選擇的測控弧段基本上完全重疊，無論2 個任務的實際測控弧段如何滑動，它們都會發(fā)生沖突。

圖8 必然沖突示意圖Fig.8 Inevitable conflict schematic

然而大多數(shù)情況是2 個任務選擇的測控弧段之間有部分重疊，那么2 個任務的實際測控弧段之間可能會發(fā)生沖突，也可能無沖突。如圖9 所示，任務1 選擇的測控弧段和任務2 選擇的測控弧段存在部分交集，如果任務1 的實際測控弧段和任務2 的實際測控弧段沒有交叉，就不會發(fā)生沖突，都可以成功執(zhí)行，否則會發(fā)生沖突，導致有的任務不能執(zhí)行。

圖9 可能沖突示意圖Fig.9 Possible conflict schematic

針對以上情況，基于風險概率的知識，提出一種計算任務選擇可用測控弧段的沖突度評估方法，即在二維坐標軸空間內(nèi)，用橫軸和縱軸分別表示2 個可用測控弧段的時間軸，用虛線表示測控活動實際執(zhí)行的開始和結束時間。如圖10 所示，[a1，b1]和[a2，b2]分別代表了2 個具有交叉關系的可用測控弧段，a1和a2分別表示最早開始時間，b1和b2分別表示最晚結束時間，橫軸對應的實際開始時間在[a1，b1-dur1]范圍內(nèi)滑動，縱軸對應的實際開始時間在[a2，b2-dur2]范圍內(nèi)滑動，由A，B，C，D所圍成的四邊形就是2 個測控弧段的交集部分，也是它們可能會發(fā)生沖突的部分，通過計算陰影部分的面積與四邊形面積之比來量化沖突度［35-37］。

圖10 沖突度評估Fig.10 Conflict degree evaluation

假設橫軸對應測控弧段的實際開始時刻為start1，測控時長為dur1，縱軸對應測控弧段的實際開始時刻為start2，測控時長為dur2，測控資源所需要的姿態(tài)轉換時間為tran。當滿足以下條件之一時

則2 個實際執(zhí)行測控的弧段不會發(fā)生沖突，都可以成功執(zhí)行；當滿足以下任一條件時則在實際執(zhí)行測控的過程中會發(fā)生沖突，導致有的測控任務不能成功執(zhí)行。

根據(jù)以上分析，測控活動的實際執(zhí)行區(qū)間如果位于陰影部分時，必然會發(fā)生沖突，如果位于陰影以外的部分時，不會發(fā)生沖突。假設由A，B，C，D 所圍成的四邊形面積為S，由2 條虛線所圍成的陰影部分面積為Sw，通過計算Sw/S 的值來量化沖突度，表示發(fā)生沖突的可能性。

3） 基于適應度的任務分配算法

基于上述分析，提出一種基于適應度的任務分配算法以生成一個質量較優(yōu)的初始解。適應度綜合考慮了任務與測控資源之間的測控機會和測控弧段沖突度的準則。

基于適應度的任務分配原則是：優(yōu)先安排收益值較大的任務進行調度；優(yōu)先選擇測控機會較多的測控資源進行分配；優(yōu)先選擇沖突度較小的可用測控弧段進行安排。

基于適應度的任務分配算法偽代碼如算法2所示。

算法2 基于適應度的任務分配算法1. 初始化調度方案P 2. 按照收益值大小將所有任務排序得到任務集合O 3. For each i ∈O 4. 計算任務對應多個可用測控資源的測控機會5. 根據(jù)輪盤賭選擇測控機會較多的測控資源6. End for 7. For each i ∈O 8. 計算任務對應多個可用測控弧段的沖突度9. 根據(jù)輪盤賭選擇沖突度較小的測控弧段10. 確定實際開始時間的可滑動選擇范圍[a，b-dur]11. 在[a，b-dur]內(nèi)隨機確定實際開始時間fs 12. If [fs，fs+dur]∩P=?與調度方案不沖突13. 將該任務按照[fs，fs+dur]加入調度方案P 14. End if 15. End for 16. Return P 生成初始解

2.3.2 鄰域結構設計

解的多樣性能夠增強模擬退火算法的尋優(yōu)性能，通過設計不同的鄰域結構，對當前解產(chǎn)生不同的鄰域變換，從而生成多樣化的新解。為增強搜索過程中鄰域解方案的多樣性，針對大規(guī)模星座測控資源調度問題，設計了2 種主要的鄰域結構，分別是基于貪婪準則的交換鄰域結構和基于概率搜索的交換鄰域結構，分別從任務帶來收益的角度和任務消耗潛在資源的角度考慮，利用剩余測控機會和測控弧段沖突度準則，結合高效的插入和替換鄰域操作算子，增大算法的有效搜索范圍，提高算法迭代優(yōu)化的效率。

1） 基于貪婪準則的交換鄰域結構

算法3 基于貪婪準則的交換鄰域結構1. 從待調度任務集合中選擇一個收益值最大的任務t 2. 計算任務可選測控資源的剩余測控機會3. 根據(jù)輪盤賭選擇剩余測控機會較大的測控資源4. 計算任務對應多個可用測控弧段的沖突度5. 根據(jù)輪盤賭選擇沖突度較小的可用測控弧段6. 確定實際開始時間的可滑動選擇范圍[a，b-dur]7. 在[a，b-dur]內(nèi)隨機確定實際開始時間fs 8. If [fs，fs+dur]∩S=?與調度方案不沖突9. 將任務按照[fs，fs+dur]插入調度方案S 10. Else 11. 將任務按照[fs，fs+dur]替換加入調度方案S 12. End if

基于貪婪準則的交換鄰域結構具體執(zhí)行過程偽代碼如算法3 所示。剩余測控機會是指，任務可選擇的測控資源未被調度方案中已安排任務所占用的剩余測控能力，計算過程為

式中：numtj表示調度方案中已安排到資源j 上的任務數(shù)量。由于測控資源的執(zhí)行能力有限，所以優(yōu)先考慮將任務安排到剩余測控機會較大的測控資源上，避免與已調度任務發(fā)生沖突，進一步提高衛(wèi)星測控資源利用率。

插入是指將未成功調度的任務直接加入調度方案，從而提高調度方案的任務完成總收益。如圖11 所示，針對將要插入的任務5，判斷該插入機會是否與調度方案沖突，如果沒有沖突就可以將其直接加入調度序列。

圖11 插入示意圖Fig.11 Insert operation schematic

替換是指將已分配的資源安排給收益值更大的任務，從而提高調度方案的任務完成總收益。如圖12 所示，針對不能直接插入的待調度任務5，首先找到與其發(fā)生沖突的任務4，然后將調度方案中與之沖突的任務刪除，最后將待調度任務5 加入調度序列。

圖12 替換示意圖Fig.12 Replacement operation schematic

2） 基于概率搜索的交換鄰域結構

基于概率搜索的交換鄰域結構具體執(zhí)行過程偽代碼如算法4 所示。

算法4 基于概率搜索的交換鄰域結構1. 計算待調度任務集合的優(yōu)先級指標Index 2. 根據(jù)輪盤賭選擇一個優(yōu)先級指標較大的任務t 3. 計算任務可選測控資源的剩余測控機會4. 根據(jù)輪盤賭選擇剩余測控機會較大的測控資源5. 計算任務對應多個可用測控弧段的沖突度6. 根據(jù)輪盤賭選擇沖突度較小的可用測控弧段7. 確定實際開始時間的可滑動選擇范圍[a，b-dur]8. 在[a，b-dur]內(nèi)隨機確定實際開始時間fs 9. If [fs，fs+dur]∩S=?與調度方案不沖突10. 將任務按照[fs，fs+dur]插入調度方案S 11. Else 12. 將任務按照[fs，fs+dur]替換加入調度方案S 13. End if

優(yōu)先級指標是指，綜合考慮任務的收益值和完成任務所需要潛在消耗的時間資源，即統(tǒng)籌計算任務收益值和任務測控時長所得到的一個綜合性評價指標，為每個任務tk計算一個優(yōu)先級指標indexk的計算過程為：

2.3.3 自適應機制

1） 溫度自適應更新

模擬退火算法在搜索過程中的尋優(yōu)行為主要受到溫度參數(shù)的影響，而且Metropolis 準則對于劣解的接受概率與溫度有直接關系，因此溫度對于模擬退火算法在每一次迭代搜索過程中的影響非常關鍵，同時溫度下降的速度也會影響模擬退火算法的收斂性能和求解效率［38］。采用溫度單調遞減的方式，接受概率也隨之單調遞減，容易陷入局部最優(yōu)解，為增強算法尋優(yōu)能力，提出一種自適應的溫度更新機制，即

式中：θm表示溫度的最小值；μ 是權重系數(shù)；Ri表示當前解的目標函數(shù)值沒有改進的代數(shù)，具體計算規(guī)則為

式中：Δf 表示新生成的鄰域解和當前解的目標函數(shù)差值，如果Δf ＞0 表示鄰域解改進了當前調度方案，將Ri重置為0；如果Δf=0 表示鄰域解和當前調度方案具有相同的質量，Ri保持不變；如果Δf ＜0 表示鄰域解降低了當前調度方案的質量，令Ri值增加。為了避免Ri值過大，影響算法的搜索性能，引入系數(shù)λ 調整升溫速率，即溫度自適應更新機制為

2） 鄰域結構選擇概率動態(tài)調整

考慮到在算法迭代過程中對解改進成功次數(shù)較多的鄰域結構，可能在接下來的迭代過程中對解改進成功的概率也會更大。提出一種自適應的鄰域結構動態(tài)選擇機制，即在算法的迭代搜索過程中，動態(tài)更新不同鄰域結構的選擇概率，從而實現(xiàn)算法自適應地選擇鄰域結構。即根據(jù)歷史表現(xiàn)選擇鄰域結構，而不是為每個鄰域結構分配一個固定不變的選擇概率。在算法迭代優(yōu)化的過程中，不同鄰域結構在不同階段所體現(xiàn)出的重要性不同，合理利用各鄰域結構的特點，能夠提高算法迭代優(yōu)化的搜索效率。鄰域結構k 由Nk(k=1，2，3)表示，該鄰域結構的選擇概率由prok表示。算法初始化時為每一鄰域結構分配相同的選擇概率，經(jīng)過一定的迭代次數(shù)NItr 后，更新鄰域結構k 的選擇概率，具體計算過程為

式中：ω 是慣性權重，表示慣性保持之前選擇概率的比重；(1-ω)是學習權重，表示學習鄰域結構最近NItr 代表現(xiàn)的比重。selk是指最近NItr 次迭代過程中選擇第k 個鄰域結構的次數(shù)，suck是指最近NItr 次迭代過程中使用第k 個鄰域結構成功改進解方案的次數(shù)。對于第k 個鄰域結構，將計算出的新概率值pro′k歸一化得到該鄰域結構新的選擇概率。

基于動態(tài)更新的鄰域結構選擇概率，采用輪盤賭策略選擇鄰域結構，生成新的鄰域解。通過結合鄰域結構的歷史情況和最近表現(xiàn)，有利于增加產(chǎn)生更優(yōu)解方案的鄰域結構被選擇的次數(shù)，從而提高算法的尋優(yōu)效率。

2.3.4 禁忌表策略

模擬退火算法缺乏對搜索過程中解變換的操作記憶，有可能陷入局部循環(huán)。通過構造Tabu表，將禁忌搜索與模擬退火算法相結合，能夠有效彌補其迭代搜索過程中缺乏記憶能力的不足之處。通過避免短期內(nèi)對于已經(jīng)訪問過的任務進行重訪，減少重復搜索所造成的資源浪費，有利于引導算法尋找全局最優(yōu)解。

鄰域解根據(jù)上述的鄰域結構產(chǎn)生，如果鄰域解的目標函數(shù)值優(yōu)于當前解，則將當前解更新為新產(chǎn)生的鄰域解；如果鄰域解的目標函數(shù)值劣于當前解，則以一定的概率將當前解更新為鄰域解。一旦新產(chǎn)生的鄰域解被接受，就把解方案變化所導致刪除的任務依次添加到Tabu 表中，用L 表示Tabu 表的長度。Tabu 表的作用是對近期執(zhí)行的搜索操作進行記憶，并對某些操作進行禁忌和解禁。Tabu 表中的任務除非被釋放，否則不允許進行調度和安排。如果Tabu 表中任務的長度達到了L，則依次釋放最先加入Tabu 表中的任務。

2.3.5 擾動策略

為了避免算法在迭代優(yōu)化過程中陷入局部最優(yōu)解，Metropolis 準則以一定概率接受劣解，但是仍然難以完全逃離局部最優(yōu)解，因此結合擾動策略對算法進行一定程度的局部擾動，在擾動結果的基礎上繼續(xù)搜索，有可能增進解的質量，擴大算法的搜索范圍，引導算法跳出局部最優(yōu)，朝著全局最優(yōu)解的方向不斷優(yōu)化。

擾動策略通過對測控資源進行重新分配實現(xiàn)對解的局部擾動。如果任務所對應的可用測控弧段不唯一，考慮將其從當前安排的位置轉移到另一位置，所釋放的當前占用資源可能會使其他未調度任務得以成功調度，從而提高任務完成總收益。如圖13 所示，針對調度方案中已安排好的任務5，可以將其重新安排到同一測控資源上的不同測控弧段，或者是另一測控資源上的一個測控弧段。

圖13 擾動策略Fig.13 Perturbation strategy

?

擾動策略執(zhí)行過程的偽代碼如算法5 所示。

2.3.6 終止條件

為提高算法的優(yōu)化效率，設置了2 個終止準則。

準則1 當前的迭代次數(shù)超過了允許的最大迭代次數(shù)MaxItr。

準則2 最優(yōu)解的目標函數(shù)值沒有改進的連續(xù)迭代次數(shù)超過MaxConItr。

在算法迭代搜索的過程中，若滿足以上2 個準則中的任何一個，算法結束并輸出全局最優(yōu)解。

3 實驗與分析

為了驗證本文所提出算法的適用性和有效性，針對大規(guī)模星座測控資源調度問題，設置了多組不同規(guī)模的仿真實驗測試用例，并且應用不同的優(yōu)化算法分別進行求解，最后根據(jù)實驗結果進行對比分析。

3. 1 實驗設置

因為目前并沒有關于衛(wèi)星測控資源調度問題的標準測試集，所以考慮實際復雜的情況，利用STK 軟件進行仿真，選取目前實際在軌運行的衛(wèi)星以及測控站，生成仿真數(shù)據(jù)。場景中部分測控站和衛(wèi)星的分布概貌如圖14 所示。

圖14 仿真場景Fig.14 Simulation scenes

實驗場景中調度周期設置為1 天，利用STK軟件計算衛(wèi)星與測控站之間的可見測控弧段，經(jīng)過預處理之后作為算法輸入，即按照測控任務的允許測控時段和持續(xù)測控時長等要求將可見測控弧段處理為可用測控弧段數(shù)據(jù)。

通過設置2 組不同的實驗情境，它們的區(qū)別在于測控站的分布情況。由于中國境內(nèi)建造的測控站存在測控盲區(qū)，為實現(xiàn)全天候的測控和跟蹤，中國在國外也建立了部分測控站以提升測控能力和覆蓋范圍，并且由衛(wèi)星測控系統(tǒng)的部門負責統(tǒng)一管理。所以在第1 組實驗情境下，假定測控站分布于全球，屬于均勻分布，在第2 組實驗情境下，測控站則全部集中分布于中國境內(nèi)，屬于密集分布，同時可以測試本文提出的算法在測控站集中分布時是否有效。考慮“星鏈”計劃是目前規(guī)模最大的星座項目，并且成功發(fā)射了超過2 000 顆衛(wèi)星，但是由于部分衛(wèi)星的可靠性不高，存在一些衛(wèi)星報廢和墜毀的情況，所以選擇其目前正常在軌運行的衛(wèi)星數(shù)據(jù)作為實驗測試。

在每一組實驗情境下，通過設置不同規(guī)模的衛(wèi)星和任務數(shù)量，并且按照衛(wèi)星的測控需求，即衛(wèi)星測控需求分為單次或者多次，分別設置了5組和7 組實驗用例，總共生成24 組不同的測試集。測試用例的具體規(guī)模如表1 所示，以Task 表示測控任務的數(shù)量，以Sat 表示星座中衛(wèi)星的數(shù)量，以Station 表示測控站的數(shù)量，以Distribution表示地面測控站的分布情況。

表1 實驗測試用例Table 1 Cases for experiment

3. 2 靈敏度分析

通常元啟發(fā)式算法的性能在很大程度上會受到其參數(shù)值的影響，因此通過大量仿真實驗分析參數(shù)不同取值時算法的性能表現(xiàn)，得到ASATP 算法的相關參數(shù)設置如表2 所示，其中N代表了實驗場景中的任務規(guī)模。

表2 ASATP 參數(shù)Table 2 Parameters of ASATP

由于ASATP 算法涉及的參數(shù)較多，因此主要分析對算法性能影響較大的關鍵參數(shù)。首先根據(jù)部分析因實驗設計方法，確定每個參數(shù)的合理取值范圍以及初始值，然后基于坐標局部搜索方法，分析每個參數(shù)的最佳取值。每次實驗僅調整一個參數(shù)的取值，其他參數(shù)值保持不變，通過比較每個參數(shù)不同取值下的目標函數(shù)值，確定不同參數(shù)的最佳取值。各參數(shù)的具體取值范圍如表3 所示。

表3 參數(shù)取值范圍Table 3 Candidate values of parameters

通過選擇具有代表性的實驗用例，可以具體分析參數(shù)取值對算法性能的影響。選擇具體的實驗用例可以從以下2 個方面進行考慮，一是實驗用例的規(guī)模適中，二是分別針對測控站均勻分布和密集分布的情況。因此，給出在實驗用例Case4 和Case15 下每個參數(shù)的不同取值對算法性能的影響結果，如圖15 所示。分析單個參數(shù)對算法性能的影響時，其他參數(shù)值保持不變。顯然每個參數(shù)的不同取值對算法性能的影響較大，以參數(shù)ω 為例進行分析，隨著ω 的取值從0.1～0.9依次變化，算法性能隨之提升后又有所下降，當ω=0.6 時，算法可以在2 個實驗用例上都產(chǎn)生最佳結果，通過進一步分析參數(shù)ω 在其他實驗用例上的敏感性，由此確定參數(shù)ω 的最佳取值為0.6，對于其他參數(shù)的分析過程也是如此。

圖15 參數(shù)不同取值對算法性能的影響Fig.15 Effects of different parameter values on the performance of algorithm

3. 3 實驗結果與分析

實驗所用的計算機配置是Inter（R） Core（TM） i5-10400 CPU @ 2.90 GHz，內(nèi)存為16.0 GB，在Windows 10 操作系統(tǒng)上使用MATLAB R2018b 編程實現(xiàn)并進行測試。

3.3.1 對比算法

為了驗證本文提出算法的通用性以及算法機制和策略的有效性，采用結合擾動策略和禁忌表的自適應模擬退火算法（ASATP）與模擬退火算法（SA）、遺傳算法（GA）、基于適應度的任務分配算法（TAAFV）和最大權重最先分配算法（HWFA）分別對上述實驗用例進行測試，并且對實驗結果進行對比分析。

第1 種對比算法是為了驗證本文設計的算法機制和策略能夠有效提升算法的尋優(yōu)性能。模擬退火算法（SA）作為本文提出算法的基礎版本，采用經(jīng)典的溫度下降機制和Metropolis 準則，以及本文所設計的鄰域結構，以貪婪算法生成初始解，具體算法參數(shù)設置如表4 所示。

表4 模擬退火算法參數(shù)Table 4 Parameters of simulated annealing algorithm

第2 種對比算法是為了驗證本文提出的算法能夠有效提升大規(guī)模星座測控資源調度問題求解的針對性。遺傳算法（GA）［13，15］作為衛(wèi)星測控資源調度常用的傳統(tǒng)方法，采用標準的算法框架，包括實數(shù)編碼方式，隨機初始化種群，二元錦標賽選擇策略，OX 交叉算子和單點變異算子，具體算法參數(shù)設置如表5 所示。

表5 遺傳算法參數(shù)Table 5 Parameters of genetic algorithm

第3 種對比算法是為了驗證本文提出的算法能夠高效的迭代優(yōu)化初始解方案。基于適應度的任務分配算法（TAAFV）作為生成初始解的方法，按照測控機會和測控弧段沖突度的啟發(fā)式準則對任務進行調度。

第4 種對比算法是為了驗證本文提出的算法能夠更好的適用于大規(guī)模星座測控資源調度問題。最大權重最先分配算法（HWFA）作為資源調度問題常用的經(jīng)典方法，根據(jù)任務收益值大小，采用簡單的貪婪思想對任務進行調度。

3.3.2 實驗結果

為保證實驗結果的可靠性，在所有實驗用例下對所有算法都重復運行20 次，并對20 次的求解結果取平均值、計算標準差、以及統(tǒng)計運行時間，具體實驗結果如表6 所示。表中Avg 代表任務總收益的平均值，Std 表示標準差，Times 表示算法的平均運行時間。表中最后1 列是關于t 檢驗的結果，檢驗算法產(chǎn)生的結果在顯著性水平為0.05 時，具有的顯著性差異?！?”表示ASATP 算法明顯優(yōu)于其他對比算法（在統(tǒng)計學上具有意義）。根據(jù)表中數(shù)據(jù)可以發(fā)現(xiàn)，ASATP 算法在不同規(guī)模的測試用例下都具有最好的性能表現(xiàn)，顯著的將SA、GA、TAAFV 和HWFA 的任務收益率提升了10.34%、23.59%、23.20%和46.51%。

表6 不同測試用例下各算法求解結果對比Table 6 Comparison of solution results of various algorithms with different scales

此外，通過Wilcoxon 有符號秩檢驗，評估ASATP 算法與其他對比算法之間的顯著性差異，結果如表7 所示，顯然，ASATP 算法相比其他算法具有顯著的優(yōu)勢。

表7 Wilcoxon 有符號秩檢驗結果Table 7 Wilcoxon signed-rank tests of ASATP and other algorithms

結果表明在所有實驗用例中，相比其他對比算法，ASATP 算法能夠取得更優(yōu)的解，p-value值顯示在95%的置信度水平下，ASATP 算法的優(yōu)化性能顯著優(yōu)于對比算法。

3.3.3 實驗分析

衛(wèi)星測控任務完成總收益值越大，即任務收益率越高，說明測控資源利用越充分，證明算法對于大規(guī)模星座測控資源調度問題的求解質量越高。通過對比所有實驗用例下不同算法的求解效果，如圖16 所示，進一步討論實驗結果和對比分析算法的性能表現(xiàn)。

圖16 不同算法的任務收益值對比Fig.16 Comparison of task values with different algorithms

根據(jù)表6 中給出的數(shù)據(jù)以及圖16 中顯示的對比結果可以發(fā)現(xiàn)，與其他算法相比，ASATP 算法在每個實驗用例下都獲得了最佳的目標函數(shù)值，生成了更好的解方案，而且隨著規(guī)模的增大，ASATP 算法優(yōu)于其他算法的效果更加明顯，說明ASATP 算法不僅性能上優(yōu)于其他對比算法，而且能更好地適用于求解大規(guī)模星座測控資源調度問題。同時針對測控站均勻分布和密集分布的不同情況，ASATP 算法也都能獲得最佳的求解效果，特別是在測控站密集分布的情況下，衛(wèi)星以及任務對于測控資源的競爭更加激烈，導致其他對比算法容易陷入局部最優(yōu)解，說明ASATP 算法能夠適用于不同的測控站分布情況。

隨著實驗場景中衛(wèi)星及測控任務規(guī)模不斷增加，衛(wèi)星和測控任務對于測控資源的競爭持續(xù)加劇，相應的解空間規(guī)模呈指數(shù)級增大，導致所有算法求解獲得的任務總收益值上升速度都有所變緩。由于HWFA 算法只是采用了簡單的貪婪準則，所以在每個案例下都只得到了相對較差的解方案，但是所用的求解時間最短；TAAFV 算法利用測控機會和測控弧段沖突度的啟發(fā)式準則信息，相比HWFA 算法總能獲得更好的求解效果；GA 算法基于種群進行迭代優(yōu)化，所以在每個實驗用例下都耗費了最長的求解時間，而且隨著種群規(guī)模的增大，算法求解消耗的時間也會繼續(xù)增加；SA 算法采用Metropolis 準則以一定的概率接受劣解，從而有可能跳出局部最優(yōu)，所以能夠獲得比較不錯的求解效果，但是隨著規(guī)模的增大越來越容易陷入局部最優(yōu)解，導致求解效果變差；ASATP 算法利用提出的擾動策略和禁忌表以及自適應機制增強了算法的全局搜索尋優(yōu)能力，搜索到問題的全局最優(yōu)解或者近似最優(yōu)解的概率增大，所以在合理的時間內(nèi)可以得到質量最優(yōu)的調度方案，實現(xiàn)最佳的求解效果。

綜上，對比算法在解的迭代優(yōu)化過程中，新解的產(chǎn)生以及解的更新機制只采用簡單的貪婪思想或者對于大規(guī)模問題的針對性不強，而本文提出算法所設計的鄰域結構充分考慮了問題領域知識，有效提升了對于大規(guī)模星座測控資源調度問題求解的針對性；對比算法缺乏算法關鍵參數(shù)的自適應更新機制，算法參數(shù)在迭代優(yōu)化過程中對算法性能影響比較大，而且在各階段的重要性也不同，而本文提出的算法能夠根據(jù)算法表現(xiàn)對算法的關鍵參數(shù)進行動態(tài)調整和自適應更新，提高算法迭代搜索最優(yōu)解的效率；對比算法沒有結合禁忌表和局部擾動策略，而本文所提算法利用禁忌表的短期記憶功能，可以減少算法重復搜索的過程，以及通過對算法進行一定程度的擾動，可能增進解的質量，避免陷入局部最優(yōu)，或者增大跳出局部最優(yōu)解的概率；對比算法不能很好地達到全局搜索和局部搜索之間的均衡利用，對于全局最優(yōu)解的探索性不強，容易陷入局部最優(yōu)解，所以對于大規(guī)模星座測控資源調度問題的求解效果差。

ASATP 算法的運行時間隨著實驗規(guī)模增大，近似呈線性增加趨勢。ASATP 算法的計算效率不是最好的，處于中等水平，正是因為算法中的自適應機制和多樣化的鄰域搜索策略等，幫助ASATP 算法避免早熟和逐漸向最優(yōu)解搜索，而其他對比算法則容易陷入局部最優(yōu)，提前結束搜索或者收斂太慢。ASATP 算法的優(yōu)點是能夠在合理的時間內(nèi)，為衛(wèi)星測控資源的周期性調度計劃生成高質量的調度方案，能夠滿足實際業(yè)務需求。在實際過程中如果對于計算時間有特別要求，也可以在運行過程中提前中斷ASATP 算法，輸出當前的最優(yōu)解以滿足計算效率的要求，從而權衡計算效率和調度收益之間的關系。

根據(jù)測試用例Case5 下采用ASATP 算法求解得到的最優(yōu)解，選取部分時段的調度方案以甘特圖形式進行可視化展示。如圖17 所示，縱坐標代表地面測控站的編號，橫坐標代表調度周期的測控時間，不同顏色的矩形方塊表示不同的衛(wèi)星測控任務，每個方塊的A/B 標號表示第A 個測控任務在該測控資源上的第B 個弧段。

圖17 調度方案甘特圖Fig.17 Scheduling scheme Gantt chart

從圖17 可以直觀地感受到每個任務的測控時間長短以及對應的測控資源切換時間，每一個方塊的寬度代表任務需要的測控持續(xù)時長，起點表示測控實際開始時間，終點表示測控實際結束時間，方塊之間的間隔為測控資源需要的姿態(tài)調整時間?？梢钥闯稣{度方案合理地利用了各測控資源完成測控任務需求，并且滿足相關約束條件，說明本文提出的算法是十分有效的。

3.3.4 算法收斂性

為了驗證算法在優(yōu)化效率和收斂速度方面的改進，將結合擾動策略和禁忌表的自適應模擬退火算法（ASATP）與模擬退火算法（SA）和遺傳算法（GA）在迭代優(yōu)化過程中的收斂曲線進行對比分析，給出在實驗用例Case2、Case4、Case8和Case11 上的實驗結果，如圖18 所示。從圖中可以看出，ASATP 算法能以更快的速度收斂至更優(yōu)的解，正是因為ASATP 算法所采用的算法機制和策略更好地引導了算法迭代優(yōu)化的搜索過程。如圖18（a）所示，ASATP 算法相比SA 算法有更快的收斂速度，GA 算法收斂雖然較快，但是收斂的結果較差；如圖18（b）所示，ASATP算法相比其他算法能夠收斂至效果更好的解，SA 算法和GA 算法都陷入了局部最優(yōu)解；如圖18（c）所示，ASATP 算法相比SA 算法收斂速度更快，GA 算法較早地陷入了局部最優(yōu)解，導致解的效果較差；如圖18（d）所示，ASATP 算法相比其他算法的收斂結果更好，SA 算法和GA 算法都沒有跳出局部最優(yōu)解，導致收斂效果較差。

圖18 不同算法的迭代優(yōu)化收斂過程Fig.18 Convergence process of different algorithms

綜上，ASATP 算法相比其他算法表現(xiàn)出了較快的收斂速度，以及更好的收斂結果，針對大規(guī)模星座測控資源調度問題能夠在合理時間內(nèi)提供較優(yōu)的調度方案。

4 結 論

本文在分析大規(guī)模星座測控資源調度問題的具體特征和任務需求以及資源約束等基礎上，構建了以任務完成總收益最大化為優(yōu)化目標的約束滿足模型，并且設計了改進的自適應模擬退火算法進行求解，獲得以下結論：

1） 針對大規(guī)模星座測控資源調度問題，建立約束滿足模型，提出任務選擇可用測控弧段時可能發(fā)生沖突的風險概率評估方法，能夠有效提升衛(wèi)星測控資源調度問題求解的針對性。

2） 設計了結合擾動策略和禁忌表的自適應模擬退火算法，通過自適應更新溫度和動態(tài)調整鄰域結構選擇概率等算法機制和策略，能分別將任務收益率提高10.34%、23.59%、23.20% 和46.51%，有效提升了衛(wèi)星測控系統(tǒng)的應用效能。

3） 提出的改進自適應模擬退火算法，更符合大規(guī)模星座測控資源調度問題的現(xiàn)實需求，求解問題更加高效，可以更好地滿足衛(wèi)星測控中心的調度管理需求，有很好的應用前景。