基于遺傳-模擬退火算法的空間目標(biāo)地基監(jiān)視調(diào)度方法

鄢青青，沈懷榮，邵瓊玲

（1.裝備學(xué)院研究生管理大隊，北京101416；2.裝備學(xué)院航天裝備系，北京101416）

基于遺傳-模擬退火算法的空間目標(biāo)地基監(jiān)視調(diào)度方法

鄢青青1，沈懷榮2，邵瓊玲2

（1.裝備學(xué)院研究生管理大隊，北京101416；2.裝備學(xué)院航天裝備系，北京101416）

空間目標(biāo)監(jiān)視是航天任務(wù)得以順利開展的重要基礎(chǔ)。針對空間目標(biāo)地基監(jiān)視中的大規(guī)模復(fù)雜調(diào)度問題，建立了包含多種約束條件和優(yōu)化目標(biāo)的調(diào)度問題數(shù)學(xué)模型。探討了利用遺傳算法對全局解的一部分進(jìn)行局部優(yōu)化以提高資源利用率的算法混合策略，構(gòu)建了遺傳 模擬退火算法，其中對模糊需求使用了啟發(fā)式方法以構(gòu)造可行解的局部，并采用窗口修剪法進(jìn)行沖突處理。仿真結(jié)果表明，遺傳 模擬退火算法與窗口修剪法結(jié)合能夠在可接受的時間內(nèi)求得滿意的解，驗證了模型和算法的有效性。

空間監(jiān)視；優(yōu)化調(diào)度；模擬退火算法；遺傳算法

0 引 言

空間目標(biāo)監(jiān)視是航天任務(wù)得以順利開展的重要基礎(chǔ)。20世紀(jì)90年代以前，人們主要通過計算機(jī)輔助的人工調(diào)度方法來解決空間監(jiān)視網(wǎng)（space surveillance network，SSN）中的任務(wù)安排或資源分配問題［1］。但隨著外層空間里需要關(guān)注的空間目標(biāo)數(shù)目不斷增加，和人們航天活動的日益頻繁，以及對空間目標(biāo)監(jiān)視資源調(diào)度的質(zhì)量要求越來越高，人工調(diào)度已不能滿足需求。而基于任務(wù)規(guī)劃、資源調(diào)度和優(yōu)化方法的自動_調(diào)度方法在增加監(jiān)視網(wǎng)編目目標(biāo)數(shù)目、提高資源利用率、提高重點(diǎn)關(guān)注目標(biāo)的綜合編目精度等方面，具有明顯優(yōu)勢，能夠滿足更多數(shù)量和類型的航天任務(wù)對空間監(jiān)視的需求。1993年MITRE公司開發(fā)了一款基于貪婪算法和傳感器權(quán)重的自動傳感器規(guī)劃程序Prototype Tasker［1］，1994年文獻(xiàn)［2］使用模擬退火（simulated annealing，SA）算法優(yōu)化了傳感器權(quán)重的選擇過程。美國空間控制中心（space control center，SCC）在空間監(jiān)視網(wǎng)資源分配中正在使用的是第二代自動任務(wù)分配系統(tǒng)［3-4］，該系統(tǒng)將SSN傳感器任務(wù)規(guī)劃問題描述為經(jīng)典多資源分配問題，采用邊際分析法（marginal analysis）對其進(jìn)行分析和求解，并在實際應(yīng)用中與第一代系統(tǒng)進(jìn)行了對比，表明其在平衡目標(biāo)的跟蹤需求與SSN的跟蹤能力上的表現(xiàn)更優(yōu)秀。另外，文獻(xiàn)［5］提出用多傳感器互補(bǔ)式觀測的方法提高目標(biāo)編目定軌精度。文獻(xiàn)［6］采用數(shù)據(jù)驅(qū)動的方法來離散搜索空間以實現(xiàn)快速搜索，并采用基于約束的調(diào)度算法最大化調(diào)度的跟蹤次數(shù)。文獻(xiàn)［7］基于在線應(yīng)用STK Scheduler Online，提出了提高定軌精度和地面資產(chǎn)利用效率的SSA（space situational awareness）傳感器任務(wù)規(guī)劃方法。文獻(xiàn)［8］提出基于費(fèi)希爾信息矩陣的ad-hoc改進(jìn)規(guī)劃算法。文獻(xiàn)［9］專門研究了基于同步觀測的傳感器組合以提高軌道估計精度的調(diào)度方法。中國的學(xué)者也分別用貪婪算法［10］、隨機(jī)搜索算法［11］、線性規(guī)劃方法［12］等對空間目標(biāo)監(jiān)視的單站和全網(wǎng)資源調(diào)度進(jìn)行了研究。以上這些研究有的以監(jiān)視網(wǎng)的歷史數(shù)據(jù)為基礎(chǔ)進(jìn)行局部重調(diào)度，有的僅考慮了空間目標(biāo)的編目任務(wù)或單一的調(diào)度優(yōu)化目標(biāo)，有的則僅考慮了單個測站的資源調(diào)度問題，為了更接近空間目標(biāo)地基監(jiān)視調(diào)度的實際情況，需要對全網(wǎng)監(jiān)視資源在多任務(wù)、多優(yōu)化目標(biāo)和復(fù)雜約束情況下的調(diào)度問題進(jìn)行研究。

為此，本文首先基于對空間目標(biāo)地基監(jiān)視調(diào)度問題中各要素的分析，建立了包含多任務(wù)、多優(yōu)化目標(biāo)和復(fù)雜約束條件的調(diào)度問題模型；根據(jù)不同監(jiān)視任務(wù)類型對監(jiān)視時間窗口的要求，設(shè)計了多種可行解構(gòu)造方法；并根據(jù)SA算法的收斂速度快和不依賴初始值等優(yōu)點(diǎn)［13］，將其與遺傳算法（genetic algorithm，GA）結(jié)合，利用遺傳算法尋優(yōu)能力更強(qiáng)的特點(diǎn)對可行解的局部進(jìn)行優(yōu)化，以提升資源更加緊張的部分空間目標(biāo)（空間目標(biāo)）的調(diào)度效果；結(jié)合提出的一種窗口修剪沖突處理方法，以獲得更多被成功調(diào)度的空間目標(biāo)；最后，通過仿真計算驗證了本文所用方法有效性。

1 調(diào)度問題的分析與建模

1.1 問題分析

空間目標(biāo)的地基監(jiān)視調(diào)度，是在滿足監(jiān)視任務(wù)需求和約束條件的基礎(chǔ)上，優(yōu)化分配地面觀測資源及其時間資源，以實現(xiàn)更好地監(jiān)視空間目標(biāo)為調(diào)度目標(biāo)的過程，該問題的描述中至少應(yīng)該包含5個要素，即地面觀測資源集、空間目標(biāo)集、監(jiān)視任務(wù)集、約束條件集以及調(diào)度優(yōu)化目標(biāo)。

其中，地面觀測資源是指以雷達(dá)天線或光學(xué)望遠(yuǎn)鏡為代表的空間目標(biāo)信息獲取和處理設(shè)備，包括其備份資源?？臻g目標(biāo)是指離地面高度150 km以上的所有人造或自然天體，空間目標(biāo)監(jiān)視的對象目前限定為離地40 000 km以內(nèi)的各類航天器、導(dǎo)彈、箭體、空間碎片等物體?？臻g目標(biāo)監(jiān)視任務(wù)是指由空間目標(biāo)監(jiān)視網(wǎng)的管理者或使用者提出，在一定時間范圍內(nèi)執(zhí)行的，對一個或多個目標(biāo)進(jìn)行的特定監(jiān)視活動，主要包括空域搜索和跟蹤測量兩種監(jiān)視方式，且該監(jiān)視活動需滿足任務(wù)提出的觀測條件、數(shù)據(jù)類型、觀測資源范圍等約束和要求，如航天器碰撞預(yù)警與規(guī)避、航天器故障處理、航天發(fā)射等活動中的支持監(jiān)視任務(wù)，及潛在威脅目標(biāo)動向監(jiān)視預(yù)警、空間目標(biāo)軌道信息編目等專門監(jiān)視任務(wù)。

另外，在空間目標(biāo)監(jiān)視中，跟蹤是指在觀測資源與空間目標(biāo)的一個相互幾何可見的時間窗口內(nèi)進(jìn)行的多次觀測。而一次觀測是觀測資源對空間目標(biāo)的一次定點(diǎn)測量，輸出一組與軌道參數(shù)、圖像、物理特性等相關(guān)的測量數(shù)據(jù)?？沼蛩阉鲃t是使用搜索設(shè)備（如相控陣?yán)走_(dá)、搜索望遠(yuǎn)鏡）對特定空域進(jìn)行的掃描式重復(fù)探測，以發(fā)現(xiàn)新目標(biāo)、查找失跟目標(biāo)等。

1.2 問題建模

根據(jù)上述分析，用一個5元組表示空間目標(biāo)地基監(jiān)視調(diào)度問題：｛S，O，M，C，T｝，其中S＝｛sj；j∈［1，M］｝表示地面觀測資源集合；O＝｛oi；i∈［1，N］｝表示需監(jiān)視的空間目標(biāo)集合；M＝｛ml；l∈［1，NM］｝表示監(jiān)視任務(wù)集合；C表示約束條件集合；T表示調(diào)度優(yōu)化目標(biāo)。

考慮調(diào)度成功的目標(biāo)數(shù)目最多、觀測質(zhì)量最高、綜合優(yōu)先級最高3個調(diào)度目標(biāo)，則目標(biāo)函數(shù)為

式中，Xi，m，j，k是0－1型決策變量，表示當(dāng)前解中，第i個目標(biāo)的屬于第m個計劃任務(wù)的第j個跟蹤時間窗口是否被當(dāng)前解接受，這個跟蹤時間窗口由第k個地面觀測資源執(zhí)行。p′m表示第i個目標(biāo)所屬第m個計劃任務(wù)的優(yōu)先級；pm為任務(wù)m指定優(yōu)先級；pa為該任務(wù)中目標(biāo)i的觀測質(zhì)量（對定軌精度的影響）評價值；ps為該目標(biāo)所用資源的優(yōu)先級之和；pi為目標(biāo)i的優(yōu)先級，根據(jù)目標(biāo)的“合作／非合作”特性、目標(biāo)類型、軌道類型、產(chǎn)生時間4個因素綜合評價產(chǎn)生。由于合作目標(biāo)一般由航天測控網(wǎng)中的合作測量資源觀測，因此在空間目標(biāo)監(jiān)視中給予較低優(yōu)先級，以節(jié)省更多觀測資源用于觀測非合作目標(biāo)；空間目標(biāo)主要有有效載荷、箭體、碎片3類，其優(yōu)先級由高到低；軌道分類采用改進(jìn)的Kaman分類［14］，包含97.252 4%的空間目標(biāo)，由于高軌和低軌采用不同的觀測資源，因此在低軌目標(biāo)（1～4類）中，軌道高度越低的目標(biāo)由于大氣阻力攝動影響，其軌道變化率越大，也就具有更高的優(yōu)先級，高軌目標(biāo)（5～7類）中，軌道高度越低的目標(biāo)具有更少的可見時間，因此也具有更高的優(yōu)先級；產(chǎn)生時間越晚的目標(biāo)，其軌道和狀態(tài)發(fā)生變化的概率越大，因此具有更高的優(yōu)先級。

問題中的約束條件如下：

（1）可見性約束，即跟蹤時間窗口必須在幾何可見時間窗口之內(nèi)，且對光學(xué)觀測而言，觀測時光學(xué)設(shè)備必須在地影內(nèi)、空間目標(biāo)必須在陽光照射下：

（2）觀測資源工作時段、作用范圍、輸出數(shù)據(jù)類型、同時可跟蹤目標(biāo)數(shù)目約束：

（3）任務(wù)要求執(zhí)行時段、觀測條件（最低觀測仰角、最短跟蹤時間窗口、最大采樣間隔）約束：

（4）任務(wù)觀測需求約束，是任務(wù)提出的對某個目標(biāo)的觀測總時長、窗口數(shù)目及在資源、時間上的分布、偏好的觀測資源范圍等約束條件，是在調(diào)度過程中構(gòu)造可行解的主要依據(jù)。

（5）優(yōu)先級約束，是多個對象之間相對重要程度的量化表示，并且優(yōu)先級高的在被選擇的過程中具有更高的優(yōu)先權(quán)或被選中概率。優(yōu)先級可以人為指定或根據(jù)相關(guān)知識計算，一般來說，人為指定的優(yōu)先級不可更改。優(yōu)先級約束是沖突處理的主要依據(jù)。本調(diào)度問題中，空間目標(biāo)、任務(wù)、觀測資源中均存在優(yōu)先級約束，必要時還可根據(jù)信噪比（雷達(dá)探測）或探測概率（光學(xué)探測）來計算跟蹤時間窗口的優(yōu)先級。

2 基于GA- SA的求解算法

2.1 求解算法

SA算法思想最早由Metropolis等提出，并由Kirkpatrick在1983年應(yīng)用于組合優(yōu)化中［15］。它通過解構(gòu)造和降溫條件判斷的自適應(yīng)迭代過程，并結(jié)合Metropolis準(zhǔn)則以跳出局部最優(yōu)，在解空間中概率性地搜索全局最優(yōu)解。SA算法具有魯棒性強(qiáng)、簡單通用、不依賴初始解、適于并行處理等優(yōu)點(diǎn)，適合在大規(guī)模的調(diào)度問題中快速獲得次優(yōu)或滿意的全局解［16］。

空間目標(biāo)地基監(jiān)視調(diào)度問題屬于大規(guī)模調(diào)度問題，為保證調(diào)度算法的時間性能，本文采用SA算法進(jìn)行全局優(yōu)化求解。同時，針對深空目標(biāo)所能利用的光學(xué)傳感器資源比較稀少的問題，利用GA對深空目標(biāo)所對應(yīng)的部分解進(jìn)行局部優(yōu)化，以在不對全局收斂速度產(chǎn)生較大影響的情況下，更加充分地利用光學(xué)傳感器資源完成對深空目標(biāo)的數(shù)目最大化地監(jiān)視。

步驟1初始化，給定初始溫度T0、Metropolis鏈長L、降溫速率q、初始種群S1，并對S1進(jìn)行沖突處理和計算種群中最大目標(biāo)函數(shù)值max（f（S1））。其中初始種群S1構(gòu)造時，首先對所有深空目標(biāo)構(gòu)造NGA個不同的部分解，再對所有近地目標(biāo)構(gòu)造一個部分解，并將后者復(fù)制NGA份與前者組成NGA個全局可行解，即種群大小為NGA。

步驟2 對每一溫度T及k∈［1，L］，循環(huán)進(jìn)行步驟3～步驟7。

步驟3 產(chǎn)生一個新種群S2。在近地目標(biāo)的部分解重構(gòu)中，對種群S1每個個體中經(jīng)沖突處理后成功保留下來的解單元（即每個空間目標(biāo)對應(yīng)的所有窗口的集合）按概率Pg重構(gòu)，對沒有成功調(diào)度的解單元全部重構(gòu)。而將種群S1經(jīng)沖突處理后的深空目標(biāo)部分解取出構(gòu)成子種群S′1，對其進(jìn)行選擇（Ps）、交叉（Pc）、變異（Pm）操作，得到新的子種群S′2，并將其與近地部分解重構(gòu)為新的種群S2。

步驟4 對S2中每個可行解的所有跟蹤時間窗口進(jìn)行沖突檢測和處理，計算S2中每個解的目標(biāo)函數(shù)值，并取最大值max（f（S2）），計算目標(biāo)函數(shù)增量Δf＝max（f（S2））－max（f（S1））。

步驟5 由于目標(biāo)函數(shù)表示為最大化問題，因此如果Δf＞0或e（Δf／T）＞rand，則接受新種群S2為當(dāng)前種群S1。

步驟6 判斷迭代終止條件，如達(dá)到最大迭代次數(shù)或連續(xù)若干次未更新當(dāng)前種群。

步驟7 降低溫度控制參數(shù)T，并判斷是否達(dá)到設(shè)定終止溫度Tend，否則轉(zhuǎn)步驟2。

2.2 可行解的構(gòu)造方法

本文假設(shè)4類計劃監(jiān)視任務(wù)，分別為：①在任務(wù)時段內(nèi)需安排盡量多的非重疊監(jiān)視時間的支持類監(jiān)視任務(wù)；②在任務(wù)時段內(nèi)需重點(diǎn)監(jiān)視（高精度、給定“跟蹤次數(shù)／測站數(shù)”需求）的專門監(jiān)視任務(wù)；③維護(hù)空間目標(biāo)編目信息庫所需的日常編目監(jiān)視任務(wù)；④空域搜索任務(wù)。

每個空間目標(biāo)對應(yīng)的所有窗口組成解的一個單元，全局可行解由所有空間目標(biāo)的解單元構(gòu)成。在解單元構(gòu)造時，對每個空間目標(biāo)所對應(yīng)的不同監(jiān)視任務(wù)進(jìn)行不同的解單元的子單元構(gòu)造，再對這些子單元進(jìn)行同時段合并（同一時段內(nèi)的窗口或窗口部分，保留優(yōu)先級最高的窗口），避免不必要的多個資源對同一目標(biāo)進(jìn)行跟蹤的情況，提高資源利用率。

2.2.1 支持監(jiān)視任務(wù)

這里設(shè)定支持監(jiān)視任務(wù)的跟蹤要求為在任務(wù)時段內(nèi)獲得一組重疊盡量少、監(jiān)視總時長盡量長的跟蹤窗口，可將這個任務(wù)需求視為一個優(yōu)化問題，采用啟發(fā)式方法來求解。該優(yōu)化問題可描述為：選取一組時間窗口，該組時間窗口構(gòu)成的總時間窗口完全或最大限度覆蓋整個任務(wù)時間段，并使這些時間窗口的重疊程度最小。

目標(biāo)函數(shù)：

式中，Tmax為任務(wù)時段長度；為構(gòu)成窗口集（即解單元的子單元）的第i個時間窗口的時長，為該窗口與前i－1個已被接受的窗口所構(gòu)成的窗口集合的重疊時長（見圖1）；NZ為該目標(biāo)該監(jiān)視任務(wù)的所有備選窗口數(shù)目；C為系數(shù)，隨迭代次數(shù)l增加呈指數(shù)下降，以在算法運(yùn)行早期提高解質(zhì)量，后期加快收斂速度。

圖1 第i個時間窗口與當(dāng)前時間窗口集合的關(guān)系示意

這是一個無約束優(yōu)化問題，采用基于概率禁忌表和貪婪準(zhǔn)則的啟發(fā)式方法產(chǎn)生滿足某目標(biāo)某計劃任務(wù)觀測跟蹤需求的一組時間窗口。具體算法步驟如下：

步驟1初始化：初始化最大迭代次數(shù)CTmax；初始化每次迭代時的尋優(yōu)計算次數(shù)L；初始化迭代終止條件中的連續(xù)無新解被接受次數(shù)M；窗口集合總時長TN初始化為0；隨機(jī)選擇一個時間窗口作為初始值，計算f（X），將該窗口移入路徑記錄和禁忌表中。

步驟2 在備選窗口集合中隨機(jī)選取L個窗口，分別計算目標(biāo)函數(shù)和其增量Δfj＝fj－fi－1，j∈［1，L］。

步驟3 選出使Δf最大的窗口，如果Δf＞0，則接受該窗口作為構(gòu)造解的一部分，記錄該窗口到路徑中，更新f（X），其余個窗口分別以概率pj＝／Tj，j∈［1，L－1］移入禁忌表，并置M為零；如果Δf≤0，則將這L個窗口分別以概率移入禁忌表，并更新M。

步驟4 更新迭代次數(shù)CT，目標(biāo)函數(shù)系數(shù)C，構(gòu)建窗口集合總時長TN（重疊部分只計一次）。

步驟5 判斷是否符合算法終止條件，即構(gòu)建窗口總時長等于任務(wù)要求總時長，或M達(dá)到規(guī)定值，或迭代次數(shù)達(dá)到終止條件。

以一個算例驗證該局部優(yōu)化方法的有效性：選擇空間目標(biāo)TLE-25544，即國際空間站（ISS），作為第1種任務(wù)（在軌操作／維修支持）的監(jiān)視對象，監(jiān)視資源采用SSN中的23個測站［3］，任務(wù)持續(xù)時間為“8 Jan 2014 16∶20∶00.000～8 Jan 2014 17∶20∶00.000”，時長60 min，最大迭代次數(shù)為50次，M取為5次，L為2。最終獲得5個不同測站的5個時間窗口，總共約35.9 min的有重疊監(jiān)視時間（34.6 min的不重疊時間），其目標(biāo)函數(shù)進(jìn)化曲線和時間窗口分布如圖2所示。

圖2 空間目標(biāo)TLE-25544的支持監(jiān)視任務(wù)時間窗口組合優(yōu)化結(jié)果

2.2.2 重點(diǎn)監(jiān)視任務(wù)

假設(shè)重點(diǎn)監(jiān)視根據(jù)定軌精度的不同，按經(jīng)驗形成了一個監(jiān)視需求查詢表。首先通過查詢或計算得到針對該目標(biāo)的重點(diǎn)監(jiān)視，當(dāng)天應(yīng)該跟蹤的次數(shù)與使用的測站數(shù)，即“T／S”（Tracks／Stations）。然后采取如下方法，從某目標(biāo)、某任務(wù)的備選可見時間窗口中選擇并組合窗口以滿足跟蹤需求。

（1）對深空目標(biāo)（平均高度＞5 700 km）

①選擇測站。從備選可見窗口的所屬測站中隨機(jī)選擇S個獨(dú)立測站，如果備選獨(dú)立測站數(shù)小于S，則直接全選所有測站。

②規(guī)劃每個測站的跟蹤次數(shù)。先至少保證每個測站一次跟蹤，然后將剩余T－S次跟蹤隨機(jī)分配給所有測站。

（2）對低軌目標(biāo)（平均高度＜2 500 km）

①選擇測站。方法同上。保證所選測站的備選可見窗口數(shù)目總和大于等于需求的跟蹤次數(shù)T。

② 規(guī)劃每個測站的跟蹤次數(shù)。方法同上。

③ 選擇或截取跟蹤時間窗口。如采用跟蹤窗口與可見窗口等長方式，則直接為每個測站每次跟蹤，隨機(jī)選擇符合觀測條件的備用可見窗口。如采用不等長方式，則從隨機(jī)選擇的備用可見窗口中截取符合觀測條件的跟蹤時間窗口。

④特性測量需求滿足。方法同上。

2.2.3 其他任務(wù)

對編目監(jiān)視任務(wù)，參考文獻(xiàn)［14］，按Kaman軌道分類，第1類和第4類為每天跟蹤一次，第2類為每2天跟蹤一次，第3類為每3天跟蹤一次，第5～7類為每7天跟蹤一次，每次跟蹤應(yīng)保證跟蹤時間窗口長度大于2 min。對空域搜索任務(wù)，直接為其分配要求時長的搜索時間窗口。

2.3 沖突處理方法

沖突是指兩個同一資源的兩個跟蹤時間窗口存在重疊部分，或窗口之間的間隔時間小于該資源的狀態(tài)轉(zhuǎn)換時間。對同一觀測資源，同時有超過觀測資源最大同時可觀測目標(biāo)數(shù)的空間目標(biāo)要求進(jìn)行觀測，即會產(chǎn)生沖突。一般而言，機(jī)械掃描雷達(dá)只能同時跟蹤一個目標(biāo)，相控陣?yán)走_(dá)可同時跟蹤多至上百個目標(biāo)，光學(xué)望遠(yuǎn)鏡則只能觀測同時出現(xiàn)在視場內(nèi)的部分目標(biāo)。

沖突處理即是在出現(xiàn)沖突的兩個或多個跟蹤時間窗口之間進(jìn)行抉擇以消除沖突。這里采用兩種沖突處理方法，即選擇／放棄法、窗口長度修剪法。選擇／放棄法是根據(jù)對每個窗口的優(yōu)先級評價，在沖突的窗口中選擇要保留的窗口或刪除要放棄的窗口。窗口長度修剪法是根據(jù)窗口優(yōu)先級，對沖突的窗口中優(yōu)先級較小的窗口的沖突部分進(jìn)行修剪，留下無沖突且大于最小跟蹤窗口長度的部分。

沖突處理的步驟是，將當(dāng)前解中的所有時間窗口按所屬觀測資源進(jìn)行集中；對每一集合中的每一窗口檢測其與其他所有窗口是否沖突，并記錄沖突信息（如兩兩沖突狀態(tài)、沖突時間區(qū)間）；評價所有窗口的優(yōu)先級；按沖突次數(shù)和優(yōu)先級，對每個窗口進(jìn)行逐個沖突處理和更新沖突信息。

3 算例仿真分析

3.1 仿真算例

目前，全世界只有美國和俄羅斯具有日常更新空間目標(biāo)監(jiān)視編目信息的能力。這里，以美國的SSN中的23個測站［3］作為仿真用的空間目標(biāo)監(jiān)視網(wǎng)，包括17個雷達(dá)測站和6個光學(xué)測站，且規(guī)定其中有多個傳感器資源的測站只能同時使用一個測站，其余作為備份。機(jī)械雷達(dá)轉(zhuǎn)換時間為5 min，光學(xué)傳感器轉(zhuǎn)換時間為10 s。另假設(shè)在空間目標(biāo)監(jiān)視網(wǎng)中，專用傳感器資源每天24小時均能參與監(jiān)視，兼用傳感器資源每天可提供隨機(jī)產(chǎn)生的連續(xù)12小時監(jiān)視時間，可用傳感器資源每天可提供隨機(jī)產(chǎn)生的連續(xù)6小時監(jiān)視時間。

空間目標(biāo)軌道參數(shù)采用2014年1月7日的TLE數(shù)據(jù)，包括8 146個獨(dú)立的空間目標(biāo)，其中深空目標(biāo)1 523個，近地目標(biāo)6 623個。

為了便于比較和分析，本文設(shè)計了兩個算例，場景時間均為2014年1月8日08∶00至1月9日08∶00，采用GA-SA算法和SA算法，每種算法中分別用兩種沖突處理方法處理時間窗口沖突。

算例1 設(shè)置6個計劃監(jiān)視任務(wù)：包括支持監(jiān)視任務(wù)3個、重點(diǎn)監(jiān)視任務(wù)1個、編目監(jiān)視任務(wù)1個、空域搜索任務(wù)1個；任務(wù)優(yōu)先級由高到低分別為10、9、8、6、2、1；任務(wù)執(zhí)行時間為18∶00－20∶30、16∶20－17∶20、10∶00－12∶00、8日08∶00－9日08∶00、8日08∶00－9日08∶00、11∶00－11∶30；分別隨機(jī)加入監(jiān)視空間目標(biāo)，其數(shù)目為7、3、3、163、8146，空域搜索設(shè)定搜索空域；重點(diǎn)監(jiān)視任務(wù)監(jiān)視需求統(tǒng)一設(shè)為“4／2”；其中支持監(jiān)視任務(wù)和重點(diǎn)監(jiān)視任務(wù)限制了可用資源范圍、包含的監(jiān)視目標(biāo)、要求的數(shù)據(jù)類型和跟蹤條件等。編目監(jiān)視任務(wù)給出兩種目標(biāo)數(shù)目，一是根據(jù)第2.2.3小節(jié)的方法隨機(jī)產(chǎn)生的目標(biāo)數(shù)（加上其他任務(wù)要求的目標(biāo)共約獨(dú)立目標(biāo)3 500個），二是使用全部8 146個目標(biāo)。

算例2 僅設(shè)置一個編目監(jiān)視任務(wù)，參數(shù)同算例1，目標(biāo)數(shù)目也為根據(jù)第2.2.3小節(jié)的方法隨機(jī)產(chǎn)生的目標(biāo)數(shù)和全部目標(biāo)。

仿真驗證實驗系統(tǒng)配置為Intel（R）Core i5-4440 CPU＠3.10GHz×4，Windows 7（64位），采用Matlab軟件實現(xiàn)。GA-SA和SA兩種算法參數(shù)設(shè)置如表1所示。

表1 算法參數(shù)設(shè)置

3.2 計算結(jié)果分析

圖3為算例1的仿真結(jié)果，由圖中可以看出，當(dāng)有6個計劃任務(wù)時，即使在成功被調(diào)度的空間目標(biāo)數(shù)目相當(dāng)或更少的情況下，GA-SA算法和窗口修剪法在獲得的目標(biāo)函數(shù)值上，均比同等條件下SA算法和窗口刪除法表現(xiàn)更好。再通過對表2中的結(jié)果的分析，表明GA-SA算法和窗口修剪法能夠成功調(diào)度更多的高優(yōu)先級任務(wù)中的空間目標(biāo)。

圖3 算例1（共有6個計劃任務(wù)）仿真結(jié)果

表2 算例仿真結(jié)果

圖4為算例2（僅有編目任務(wù)）的仿真結(jié)果，由圖中可以看出，當(dāng)需要監(jiān)視的空間目標(biāo)數(shù)目較多時，在目標(biāo)函數(shù)值和成功調(diào)度的空間目標(biāo)數(shù)目上，窗口修剪法均比窗口刪除法表現(xiàn)好得多，但GA-SA算法相對SA算法優(yōu)勢不太明顯。而當(dāng)需要監(jiān)視的空間目標(biāo)數(shù)目較少時，GA-SA算法相對SA算法在獲得的目標(biāo)函數(shù)值上表現(xiàn)較好，但成功調(diào)度的空間目標(biāo)數(shù)目差別較小。結(jié)合表2中的數(shù)據(jù)可知，當(dāng)需要監(jiān)視的空間目標(biāo)數(shù)目較多、資源較為緊張時，窗口修剪法可以使更多的空間目標(biāo)被調(diào)度成功，從而也保證了得到更大的目標(biāo)函數(shù)值，此時被成功調(diào)度的目標(biāo)數(shù)目是目標(biāo)函數(shù)值的主要影響因素；而當(dāng)需要監(jiān)視的空間目標(biāo)數(shù)目較少、資源較為富余時，窗口修剪法不再有優(yōu)勢，但GA-SA算法仍然可以通過局部尋優(yōu)來獲得更大的目標(biāo)函數(shù)值，且與窗口修剪法結(jié)合使用后效果更好。

圖4 算例2（僅有編目任務(wù)）仿真結(jié)果

由于支持監(jiān)視任務(wù)和重點(diǎn)監(jiān)視任務(wù)具有較高的優(yōu)先級，因此在算例1的計算結(jié)果中可能出現(xiàn)調(diào)度成功的空間目標(biāo)數(shù)目更多而目標(biāo)函數(shù)值更小的情況，這也是算例1中的調(diào)度成功的深空目標(biāo)數(shù)目普遍比算例2中少的原因。由于在算例設(shè)定時，支持監(jiān)視任務(wù)和重點(diǎn)監(jiān)視任務(wù)中的目標(biāo)都是隨機(jī)選擇的，并沒有考慮其在任務(wù)時段內(nèi)是否有足夠的可用時間窗口，因此造成了這兩個任務(wù)的調(diào)度成功空間目標(biāo)數(shù)目始終不足90%。經(jīng)計算，算例1的第一條結(jié)果中這兩種任務(wù)的成功目標(biāo)數(shù)目占比基本達(dá)到任務(wù)中擁有足夠可見窗口的空間目標(biāo)數(shù)目的最大比例。從計算結(jié)果可以看出，由于對深空目標(biāo)進(jìn)行探測的傳感器可用資源較少、且每個傳感器資源可同時探測的目標(biāo)數(shù)目太少，導(dǎo)致深空目標(biāo)探測在加入更多任務(wù)、更多目標(biāo)時，能夠被成功探測的目標(biāo)數(shù)目無法完全滿足設(shè)計算例的跟蹤需求。由于問題規(guī)模較大，表2中的算法運(yùn)行時間可以認(rèn)為在可接受范圍內(nèi)，當(dāng)在實際應(yīng)用中進(jìn)入周期性重調(diào)度后利用歷史經(jīng)驗數(shù)據(jù)即可大幅減少算法運(yùn)行時間；且算法運(yùn)行采用了并行計算的方式，運(yùn)行平臺的增強(qiáng)也有助于算法計算效率的提高。

4 結(jié) 論

空間目標(biāo)地基監(jiān)視調(diào)度問題是一個多任務(wù)、多優(yōu)化目標(biāo)、多約束，且存在大量時間窗口沖突的復(fù)雜問題。通過對該問題基本要素的分析，建立了該問題的數(shù)學(xué)模型，并設(shè)計了遺傳-模擬退火算法進(jìn)行求解。經(jīng)過使用GA-SA和SA兩種算法、及兩種不同沖突處理方法在兩個算例中的計算表明，本文所提出的GA-SA算法和窗口修剪沖突處理方法在不同任務(wù)數(shù)目、不同空間目標(biāo)數(shù)量規(guī)模下，均具有較好的調(diào)度性能，說明了本文提出的方法在解決空間目標(biāo)地基監(jiān)視調(diào)度問題過程中是合理、有效的。另外，本文在建立模型和設(shè)計算例的時候做的很多假設(shè)并不符合空間目標(biāo)監(jiān)視調(diào)度的真實情況，因此今后的努力方向應(yīng)是結(jié)合更多空間目標(biāo)監(jiān)視的實際情況來研究高效的調(diào)度方法。

［1］Cherry P R.Sensor tasking by the space defense operations center［C］∥Proc.of the Space Surveillance Workshop，1993：93- 98.

［2］Petrick B L.Weighting scheme for the space surveillance network automated tasker［D］.Ohio，USA：Air Force Institute of Tech Wright-Patterson AFB OH School of Engineering，1994.

［3］Berger J M，Moles J B，Wilsey D G.An analysis of USSPACECOM’s space surveillance network（ssn）sensor tasking methodology［D］.Ohio，USA：Air Force Institute of Technology Wright-Patterson AFB OH School of Engineering，1992.

［4］Miller J G G.A new sensor allocation algorithm for the space surveillance network［J］.Military Operations Research，2007，12（1）：57- 70.

［5］Stottler R，Thompson R.Globally optimized scheduling for space object tracking［C］∥Proc.of the Infotech＠Aerospace Conference，2011：1- 8.

［6］Mohammed J L，Stottler D.Rapid scheduling of multi-tracking sensors for a responsive satellite surveillance network［C］∥Proc.of the Infotech＠Aerospace Conference，2010：1- 12.

［7］Herz A F，Stoner F，Hall R，et al.SSA sensor tasking approach for improved orbit determination accuracies and more efficient use of ground assets［C］∥Proc.of the Advanced Maui Optical and Space Surveillance Technologies Conference，2013：1- 10.

［8］Erwin R S，Albuquerque P，Jayaweera S K，et al.Dynamic sensor tasking for space situational awareness［C］∥Proc.of the A-merican Control Conference，2010：1153- 1158.

［9］Hobson T A，Clarkson I V L.Collaborative sensor scheduling for space situational awareness［C］∥Proc.of the Statistical Signal Processing Workshop，2012：640- 643.

［10］Xu Z C，Huang Y X.A scheduling method for cataloging observation tasks based on greedy algorithm［J］.Journal of Spacecraft TT&C Technology，2012，31（1）：89- 94.（徐忠超，黃永宣.基于貪婪算法的空間編目觀測任務(wù)調(diào)度方法［J］.飛行器測控學(xué)報，2012，31（1）：89- 94.）

［11］Liang H，Niu W.Design and implementation of measurement resource scheduling for space object catalog［J］.Journal of Spacecraft TT&C Technology，2012，31（1）：84- 88.（梁華，牛威.空間目標(biāo)編目測量資源調(diào)度策略設(shè)計與實現(xiàn)［J］.飛行器測控學(xué)報，2012，31（1）：84- 88.）

［12］Wang X.Scheduling strategy for electro-optical tracking of space objects［J］.Journal of Spacecraft TT&C Technology，2013，32（1）：89- 94.（王歆.空間目標(biāo)光電跟蹤的調(diào)度策略［J］.飛行器測控學(xué)報，2013，32（1）：89- 94.）

［13］Sun Y S，Li Y M，Zhang Y H，et al.Improved simulated annealing algorithm and its application in adjusting of S plane parameters in AUV motion control［J］.Acta Armamentarii，2013，34（11）：1418- 1423.（孫玉山，李岳明，張英浩，等.改進(jìn)的模擬退火算法在水下機(jī)器人S面運(yùn)動控制參數(shù)優(yōu)化中的應(yīng)用［J］.兵工學(xué)報，2013，34（11）：1418- 1423.）

［14］Barker W N，Casali SJ，Wallner R N.The accuracy of general perturbations and semianalvtic satellite ephemeris theories［C］∥Proc.of the AAS／AIAA Astrodynamics Conference，1995：1967- 1985.

［15］Kirkpatrick S，Jr D G，Vecchi M P.Optimization by simmulated annealing.［J］.Science，1983，42（3）：671- 680.

［16］Liang X，Huang M.The modern intelligent optimization algorithm and its application［M］.Beijing：Publishing House of E-lectronics Industry，2012：107- 113.（梁旭，黃明.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用［M］.北京：電子工業(yè)出版社，2012：107- 113.）

Space object ground-based surveillance scheduling based on genetic-simulated annealing algorithm

YAN Qing-qing1，SHEN Huai-rong2，SHAO Qiong-ling2
（1.Department of Graduate Management，Equipment Academy，Beijing 101416，China；2.Department of Space Equipment，Equipment Academy，Beijing 101416，China）

Space object surveillance has a vital role in the smooth development of space mission.To solve the large-scale and complex scheduling problem of space object ground-based surveillance，a mathematical model with multiple constraints and optimal objectives is established.Through discussing a hybrid strategy of algorithms to local optimize a part of the global solution using the genetic algorithm to improve utilization of sensor resources，a hybrid algorithm with genetic algorithm and simulated annealing algorithm is constructed.A heuristic method is used to construct parts of solution for vague requirements，and a method named window trimming is used to solve time window conflicts in the hybrid algorithm.Simulation results show that the geneticsimulated annealing algorithm and window trimming method can receive a satisfactory solution in the acceptable term，which verifies that the model and algorithm are validity.

space surveillance；optimized scheduling；simulated annealing algorithm；genetic algorithm

V 556

A

10.3969／j.issn.1001-506X.2015.12.16

鄢青青（198-6- ），博士研究生，主要研究方向為航天裝備總體理論與技術(shù)。

E-mail：yqwork2013＠163.com

沈懷榮（195-4- ），教授，博士，主要研究方向為航天裝備總體理論與技術(shù)。

E-mail：shenhuair＠tom.com

邵瓊玲（1971- ），副教授，主要研究方向為航天裝備應(yīng)用。

E-mail：zzy5678＠126.com

1001-506X（2015）12-2764-08

2014- 12- 24；

2015- 06- 12；網(wǎng)絡(luò)優(yōu)先出版日期：2015- 09- 21。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150921.2135.024.html

部委級項目資助課題