伍國華，王天宇

中南大學(xué) 交通運(yùn)輸與工程學(xué)院，長沙 410073

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 任務(wù)沖突Fig.4 Task conflict

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

圖5 任務(wù)沖突消解Fig.5 Task conflict resolution

1. 2 約束滿足模型構(gòu)建

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

調(diào)度周期時(shí)間區(qū)間用[TS，TE，TD]表示，其中TS 指調(diào)度周期起始時(shí)間，TE 指調(diào)度周期結(jié)束時(shí)間，TD 指調(diào)度周期時(shí)段總時(shí)長，相關(guān)要素均限定在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)星對應(yīng)的標(biāo)識； frsk表示該衛(wèi)星所要求的測控頻段；task表示由該衛(wèi)星所產(chǎn)生的測控任務(wù)。

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

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

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

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

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

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

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

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

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

2 ASATP 算法介紹

2. 1 算法流程

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

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

2. 2 算法復(fù)雜度

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

算法1 結(jié)合擾動策略和禁忌表的自適應(yīng)模擬退火算法1. 初始化設(shè)置算法參數(shù)2. 設(shè)置迭代計(jì)數(shù)器Itr=0，ConItr=0 3. 產(chǎn)生初始解S0，計(jì)算初始解目標(biāo)函數(shù)值f (S0)4. 設(shè)置最優(yōu)解S*，并且令S*=S0 5. While Itr ＜MaxItr & ConItr ＜MaxConItr 6. 迭代次數(shù)Itr=Itr+1 7. 動態(tài)更新鄰域結(jié)構(gòu)選擇概率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ù)鄰域選擇概率采用輪盤賭選擇鄰域結(jié)構(gòu)18. selk=selk+1 19. 根據(jù)鄰域結(jié)構(gòu)產(chǎn)生鄰域解S′20. If f (S)＜f (S′)21. 更新當(dāng)前解為新解S=S′22. suck=suck+1 23. 更新Ri=0 24. 更新禁忌表，將被替換的任務(wù)插入禁忌表25. 判斷禁忌表長度已滿，釋放最先加入的任務(wù)26. Elseif exp(( f (S′)-f (S))/θi)＞rand(0，1)27. 更新當(dāng)前解為新解S=S′28. 更新Ri=Ri+1 29. 更新禁忌表，將被替換的任務(wù)插入禁忌表30. 判斷禁忌表長度已滿，釋放最先加入的任務(wù)31. End if 32. 局部擾動策略33. If Itr%PItr=0 34. 對當(dāng)前解進(jìn)行局部擾動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)解

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

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

2.3.1 初始解生成

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

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

1） 測控機(jī)會準(zhǔn)則

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

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

2） 測控弧段沖突度準(zhǔn)則

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

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

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

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

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

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

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

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

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

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

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

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

3） 基于適應(yīng)度的任務(wù)分配算法

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

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

基于適應(yīng)度的任務(wù)分配算法偽代碼如算法2所示。

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

2.3.2 鄰域結(jié)構(gòu)設(shè)計(jì)

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

1） 基于貪婪準(zhǔn)則的交換鄰域結(jié)構(gòu)

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

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

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

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

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

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

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

2） 基于概率搜索的交換鄰域結(jié)構(gòu)

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

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

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

2.3.3 自適應(yīng)機(jī)制

1） 溫度自適應(yīng)更新

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

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

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

2） 鄰域結(jié)構(gòu)選擇概率動態(tài)調(diào)整

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

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

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

2.3.4 禁忌表策略

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

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

2.3.5 擾動策略

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

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

圖13 擾動策略Fig.13 Perturbation strategy

?

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

2.3.6 終止條件

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

準(zhǔn)則1 當(dāng)前的迭代次數(shù)超過了允許的最大迭代次數(shù)MaxItr。

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

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

3 實(shí)驗(yàn)與分析

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

3. 1 實(shí)驗(yàn)設(shè)置

因?yàn)槟壳安]有關(guān)于衛(wèi)星測控資源調(diào)度問題的標(biāo)準(zhǔn)測試集，所以考慮實(shí)際復(fù)雜的情況，利用STK 軟件進(jìn)行仿真，選取目前實(shí)際在軌運(yùn)行的衛(wèi)星以及測控站，生成仿真數(shù)據(jù)。場景中部分測控站和衛(wèi)星的分布概貌如圖14 所示。

圖14 仿真場景Fig.14 Simulation scenes

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

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

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

表1 實(shí)驗(yàn)測試用例Table 1 Cases for experiment

3. 2 靈敏度分析

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

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

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

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

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

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

3. 3 實(shí)驗(yàn)結(jié)果與分析

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

3.3.1 對比算法

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

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

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

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

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

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

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

3.3.2 實(shí)驗(yàn)結(jié)果

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

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

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

表7 Wilcoxon 有符號秩檢驗(yàn)結(jié)果Table 7 Wilcoxon signed-rank tests of ASATP and other algorithms

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

3.3.3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

圖17 調(diào)度方案甘特圖Fig.17 Scheduling scheme Gantt chart

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

3.3.4 算法收斂性

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

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

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

4 結(jié) 論

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

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

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

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