鄢青青，沈懷榮，邵瓊玲

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

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

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

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

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

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

0 引 言

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

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

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

1.1 問題分析

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

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

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

1.2 問題建模

根據(jù)上述分析，用一個(gè)5元組表示空間目標(biāo)地基監(jiān)視調(diào)度問題：｛S，O，M，C，T｝，其中S＝｛sj；j∈［1，M］｝表示地面觀測(cè)資源集合；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ù)目最多、觀測(cè)質(zhì)量最高、綜合優(yōu)先級(jí)最高3個(gè)調(diào)度目標(biāo)，則目標(biāo)函數(shù)為

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

問題中的約束條件如下：

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

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

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

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

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

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)、簡(jiǎn)單通用、不依賴初始解、適于并行處理等優(yōu)點(diǎn)，適合在大規(guī)模的調(diào)度問題中快速獲得次優(yōu)或滿意的全局解［16］。

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

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

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

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

步驟4 對(duì)S2中每個(gè)可行解的所有跟蹤時(shí)間窗口進(jìn)行沖突檢測(cè)和處理，計(jì)算S2中每個(gè)解的目標(biāo)函數(shù)值，并取最大值max（f（S2）），計(jì)算目標(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類計(jì)劃監(jiān)視任務(wù)，分別為：①在任務(wù)時(shí)段內(nèi)需安排盡量多的非重疊監(jiān)視時(shí)間的支持類監(jiān)視任務(wù)；②在任務(wù)時(shí)段內(nèi)需重點(diǎn)監(jiān)視（高精度、給定“跟蹤次數(shù)／測(cè)站數(shù)”需求）的專門監(jiān)視任務(wù)；③維護(hù)空間目標(biāo)編目信息庫(kù)所需的日常編目監(jiān)視任務(wù)；④空域搜索任務(wù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

④特性測(cè)量需求滿足。方法同上。

2.2.3 其他任務(wù)

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

2.3 沖突處理方法

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

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

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

3 算例仿真分析

3.1 仿真算例

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

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

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

算例1 設(shè)置6個(gè)計(jì)劃監(jiān)視任務(wù)：包括支持監(jiān)視任務(wù)3個(gè)、重點(diǎn)監(jiān)視任務(wù)1個(gè)、編目監(jiān)視任務(wù)1個(gè)、空域搜索任務(wù)1個(gè)；任務(wù)優(yōu)先級(jí)由高到低分別為10、9、8、6、2、1；任務(wù)執(zhí)行時(shí)間為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個(gè)），二是使用全部8 146個(gè)目標(biāo)。

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

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

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

3.2 計(jì)算結(jié)果分析

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

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

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

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

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

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

4 結(jié) 論

空間目標(biāo)地基監(jiān)視調(diào)度問題是一個(gè)多任務(wù)、多優(yōu)化目標(biāo)、多約束，且存在大量時(shí)間窗口沖突的復(fù)雜問題。通過對(duì)該問題基本要素的分析，建立了該問題的數(shù)學(xué)模型，并設(shè)計(jì)了遺傳-模擬退火算法進(jìn)行求解。經(jīng)過使用GA-SA和SA兩種算法、及兩種不同沖突處理方法在兩個(gè)算例中的計(jì)算表明，本文所提出的GA-SA算法和窗口修剪沖突處理方法在不同任務(wù)數(shù)目、不同空間目標(biāo)數(shù)量規(guī)模下，均具有較好的調(diào)度性能，說明了本文提出的方法在解決空間目標(biāo)地基監(jiān)視調(diào)度問題過程中是合理、有效的。另外，本文在建立模型和設(shè)計(jì)算例的時(shí)候做的很多假設(shè)并不符合空間目標(biāo)監(jiān)視調(diào)度的真實(shí)情況，因此今后的努力方向應(yīng)是結(jié)合更多空間目標(biāo)監(jiān)視的實(shí)際情況來研究高效的調(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.（徐忠超，黃永宣.基于貪婪算法的空間編目觀測(cè)任務(wù)調(diào)度方法［J］.飛行器測(cè)控學(xué)報(bào)，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)編目測(cè)量資源調(diào)度策略設(shè)計(jì)與實(shí)現(xiàn)［J］.飛行器測(cè)控學(xué)報(bào)，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］.飛行器測(cè)控學(xué)報(bào)，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)動(dòng)控制參數(shù)優(yōu)化中的應(yīng)用［J］.兵工學(xué)報(bào)，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- ），博士研究生，主要研究方向?yàn)楹教煅b備總體理論與技術(shù)。

E-mail：yqwork2013＠163.com

沈懷榮（195-4- ），教授，博士，主要研究方向?yàn)楹教煅b備總體理論與技術(shù)。

E-mail：shenhuair＠tom.com

邵瓊玲（1971- ），副教授，主要研究方向?yàn)楹教煅b備應(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

部委級(jí)項(xiàng)目資助課題