基于線性規(guī)劃的云南40米射電望遠(yuǎn)鏡短期觀測編排方法

戴 偉，衛(wèi)冰濤，郝龍飛，衛(wèi)守林*，梁 波

(1. 昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南 昆明 650500；2. 中國科學(xué)院云南天文臺，云南 昆明 650216；3. 云南省計(jì)算機(jī)應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650500)

為了減少電磁干擾對天文觀測的影響，射電望遠(yuǎn)鏡臺站一般選擇在高海拔、人跡稀少的地區(qū)，但這也限制了人工現(xiàn)場干預(yù)觀測的能力。當(dāng)前望遠(yuǎn)鏡正朝著巨型化、復(fù)雜化發(fā)展，望遠(yuǎn)鏡的正常運(yùn)轉(zhuǎn)需要多種組件協(xié)同工作[1]，依賴操作人員手工控制已變得越來越困難。因此，自主觀測是望遠(yuǎn)鏡觀測控制系統(tǒng)的共同需求。自主觀測是指根據(jù)觀測計(jì)劃自動(dòng)進(jìn)行調(diào)度的觀測模式，而觀測計(jì)劃的編排是望遠(yuǎn)鏡實(shí)現(xiàn)自動(dòng)化觀測控制的前提。

目前觀測計(jì)劃的編排主要集中于長期觀測申請調(diào)度，通常是望遠(yuǎn)鏡科學(xué)委員會(huì)根據(jù)科學(xué)目標(biāo)、不同的觀測申請賦予不同的科學(xué)價(jià)值權(quán)重后，通過優(yōu)化方法給出長期的計(jì)劃編排[2]。而對于40 m射電望遠(yuǎn)鏡，一個(gè)重要需求是給出一系列觀測目標(biāo)，使望遠(yuǎn)鏡盡可能在短時(shí)間內(nèi)完成所有目標(biāo)的觀測任務(wù)，通常是一天內(nèi)完成幾十顆射電源的短期觀測編排。顯然，目前其他望遠(yuǎn)鏡系統(tǒng)的長期觀測編排方法不能滿足40 m射電望遠(yuǎn)鏡短期編排的需求。

不同于長期觀測編排，短期編排需要給出目標(biāo)具體的開始和結(jié)束觀測時(shí)間，而時(shí)間變量是連續(xù)的，因此短期編排屬于連續(xù)最優(yōu)化問題。觀測目標(biāo)的位置隨時(shí)間不停變化，不同的觀測目標(biāo)一天內(nèi)在望遠(yuǎn)鏡視場中出現(xiàn)的時(shí)間有限，同時(shí)還需要考慮從一個(gè)觀測目標(biāo)轉(zhuǎn)動(dòng)到另一個(gè)目標(biāo)的過程中，由于望遠(yuǎn)鏡本身的機(jī)械問題，可能出現(xiàn)限位，以及望遠(yuǎn)鏡不同觀測方向?qū)τ^測數(shù)據(jù)質(zhì)量的影響，這些都是短期編排區(qū)別于長期編排的地方，也是優(yōu)化的難點(diǎn)。本文首先回顧當(dāng)前主要的觀測編排方法；接著介紹將望遠(yuǎn)鏡觀測源的編排轉(zhuǎn)換成混合整數(shù)線性規(guī)劃問題中的決策變量、目標(biāo)函數(shù)和約束條件的定義，給出了該方法在40 m射電望遠(yuǎn)鏡上的測試結(jié)果；最后總結(jié)并討論了40 m射電望遠(yuǎn)鏡觀測編排未來的研究工作。

1 相關(guān)工作

調(diào)度問題已在電力、運(yùn)輸、航空、計(jì)算機(jī)以及工業(yè)生產(chǎn)等領(lǐng)域得到了廣泛的研究，望遠(yuǎn)鏡觀測目標(biāo)的編排是該問題在天文領(lǐng)域的實(shí)際應(yīng)用。哈勃空間望遠(yuǎn)鏡的Spike系統(tǒng)自1990年投入使用，系統(tǒng)的核心算法為迭代修正搜索算法[3]。迭代修正搜索算法的核心思路是將望遠(yuǎn)鏡時(shí)間分配問題抽象為一個(gè)約束優(yōu)化問題，通過3步進(jìn)行求解：(1)通過某種啟發(fā)式算法構(gòu)造初始解，該初始解可以違反約束條件，根據(jù)具體需求選擇啟發(fā)式算法，但啟發(fā)式過程均基于對約束程度的量化并且選擇容易計(jì)算的量化方式；(2)利用啟發(fā)式的修正算法減少約束的違反條件；(3)通過從時(shí)間分配表中去除存在沖突的活動(dòng)來消除沖突[4]。

綠岸射電望遠(yuǎn)鏡(Green Bank Telescope, GBT)采用一個(gè)自動(dòng)動(dòng)態(tài)調(diào)度系統(tǒng)[5]，核心思想是基于一種排序的算法確定觀測計(jì)劃之間的優(yōu)先次序。文[5]描述了綠岸射電望遠(yuǎn)鏡使用的包括預(yù)報(bào)天氣條件、觀測效率、目標(biāo)坐標(biāo)等變量的排序算法，以及調(diào)度觀測中使用的一些特定變量。

撒丁島射電望遠(yuǎn)鏡(Sardinia Radio Telescope, SRT)[6]參考綠岸射電望遠(yuǎn)鏡的動(dòng)態(tài)調(diào)度系統(tǒng)，考慮長期和短期編排問題，在模擬結(jié)果中，以48 h為周期，1 h作為一個(gè)時(shí)間槽。每個(gè)觀測計(jì)劃賦予一個(gè)科學(xué)價(jià)值，占用2～6 h，使用模擬退火算法優(yōu)化觀測編排，加入水汽和天氣等限制條件。

500 m口徑球面射電望遠(yuǎn)鏡(Five-hundred-meter Aperture Spherical radio Telescope, FAST)[7]以最小化尋址代價(jià)和最大化科學(xué)價(jià)值為目標(biāo)函數(shù)，限制條件考慮源的可見性、射頻干擾等因素，同時(shí)使用邊緣檢測方式減小問題空間，加快優(yōu)化速度。望遠(yuǎn)鏡使用中國虛擬天文臺在線觀測提案系統(tǒng)，本質(zhì)上還是中長期的觀測編排。

其他望遠(yuǎn)鏡系統(tǒng)的觀測編排也大多是觀測提案的編排，比如基于進(jìn)化算法的低頻陣列(Low Frequency Array, LOFAR)觀測調(diào)度[8]，基于模擬退火和動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)的阿塔卡馬大型毫米波/亞毫米波陣列(Atacama Large Millimeter/submillimeter Array, ALMA)觀測調(diào)度[9]。40 m射電望遠(yuǎn)鏡作為單碟射電望遠(yuǎn)鏡，在短期的觀測編排中，需要在更短的時(shí)間槽內(nèi)，按目標(biāo)源進(jìn)行分配，而不是按觀測提案進(jìn)行分配?，F(xiàn)有的中長期觀測提案的編排方法，顯然無法解決按目標(biāo)源進(jìn)行觀測時(shí)間分配的需求。

2 模型設(shè)計(jì)

2.1 問題描述

40 m射電望遠(yuǎn)鏡短期觀測目標(biāo)編排需求通常是在一天(或幾個(gè)小時(shí))內(nèi)給定一系列觀測目標(biāo)信息，包含觀測目標(biāo)的名稱(J2000紀(jì)元)、位置和所需觀測時(shí)長，如表1。

表1 云南40 m射電望遠(yuǎn)鏡觀測源信息樣例

短期編排的結(jié)果是得出每個(gè)目標(biāo)開始和結(jié)束的觀測時(shí)間，并最大化望遠(yuǎn)鏡的利用率。同時(shí)需要考慮：

(1)所有觀測目標(biāo)安排觀測。每顆目標(biāo)源的觀測時(shí)長要求集中在24～48 min，保證編排時(shí)間滿足觀測時(shí)長要求。

(2)分配時(shí)間粒度。時(shí)間分配粒度太大，造成時(shí)間片的浪費(fèi)；時(shí)間分配粒度太小，造成參數(shù)空間膨脹，直接影響最優(yōu)化求解的性能。

(3)望遠(yuǎn)鏡硬件的限位條件。在觀測過程中，源的位置不斷變化，而望遠(yuǎn)鏡只能在一定范圍內(nèi)轉(zhuǎn)動(dòng)，因此須滿足在源的編排時(shí)間內(nèi)，望遠(yuǎn)鏡可以轉(zhuǎn)動(dòng)到目標(biāo)源，即滿足望遠(yuǎn)鏡硬件的限位條件。

(4)最優(yōu)觀測時(shí)間。根據(jù)40 m射電望遠(yuǎn)鏡的觀測經(jīng)驗(yàn)，天線俯仰角在40～60°內(nèi)觀測比較好，這時(shí)增益較大，且增益變化不大，觀測源受地面噪聲影響相對較小，觀測獲取的數(shù)據(jù)質(zhì)量更好。因此編排時(shí)，優(yōu)先考慮這個(gè)位置范圍內(nèi)的源，源的位置高度可用Airmass衡量，Airmass值近似等于1/sinα，其中α為源的高度角。圖1顯示了2020年12月21日，源2055+3630，0837-4135和0358+5413的Airmass隨時(shí)間變化的曲線。

圖1 源2055+3630, 0837-4135和0358+5413在2020年12月21日不同時(shí)刻的Airmass值

根據(jù)40 m射電望遠(yuǎn)鏡短期觀測目標(biāo)編排的需求和限制條件，我們假設(shè)總共有K個(gè)觀測目標(biāo)，一個(gè)觀測目標(biāo)在觀測過程中需要考慮觀測時(shí)長以及望遠(yuǎn)鏡從第1顆源的跟蹤狀態(tài)切換到第2顆源的跟蹤狀態(tài)消耗的時(shí)間。因此，一個(gè)觀測目標(biāo)t占用的時(shí)間窗為轉(zhuǎn)向時(shí)間Ts+觀測時(shí)間To，可以表示為

(1)

其中，轉(zhuǎn)向時(shí)間依賴上一個(gè)觀測目標(biāo)結(jié)束時(shí)望遠(yuǎn)鏡的位置(方位、俯仰角度)。如果是首個(gè)觀測目標(biāo)，則轉(zhuǎn)向時(shí)長根據(jù)望遠(yuǎn)鏡初始方位角和高度角進(jìn)行計(jì)算。

2.2 決策變量

在望遠(yuǎn)鏡短期觀測編排中，時(shí)間是最主要的變量，時(shí)間直接決定了源的位置，也間接影響源的觀測時(shí)長。在40 m射電望遠(yuǎn)鏡的短期目標(biāo)編排中，目標(biāo)源觀測時(shí)長的單位是min，我們將時(shí)間的分配粒度設(shè)置為min，整個(gè)觀測計(jì)劃的總時(shí)間M為24 × 60 ×dmin，其中，d為編排計(jì)劃的天數(shù)。

圖2 源0922+0638和1136+1551在2020年12月21日的可用時(shí)間槽

dij=arccos[sinδ1sinδ2+cosδ1cosδ2cos(α1-α2)].

(2)

根據(jù)40 m射電望遠(yuǎn)鏡的經(jīng)驗(yàn)值，最大的源目標(biāo)切換時(shí)間約為6 min，這里源切換時(shí)間矩陣近似為

(3)

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

基于最大化望遠(yuǎn)鏡的利用率、減少源切換時(shí)間的原則，目標(biāo)函數(shù)定義為

(4)

2.4 約束條件

根據(jù)40 m射電望遠(yuǎn)鏡短期觀測目標(biāo)編排的問題描述，在最優(yōu)化目標(biāo)函數(shù)的過程中需要滿足以下約束：

(1)滿足每個(gè)目標(biāo)的觀測時(shí)長要求，即滿足結(jié)束調(diào)度時(shí)間減去開始調(diào)度時(shí)間大于等于觀測時(shí)長Pj，用公式表示為

(5)

圖3 第2個(gè)約束條件限制示意圖

(6)

(3)保證每個(gè)目標(biāo)觀測開始時(shí)間和結(jié)束時(shí)間沒有相互重疊，即

(7)

如果yij=1，表示完成源Ti的觀測后轉(zhuǎn)動(dòng)到源Tj，需要滿足源Tj的開始時(shí)間大于等于源Ti的結(jié)束時(shí)間加上源Ti到源Tj的轉(zhuǎn)換時(shí)間Sij。

3 實(shí) 驗(yàn)

本文的實(shí)驗(yàn)數(shù)據(jù)來自40 m射電望遠(yuǎn)鏡的真實(shí)觀測源，短期編排的時(shí)間區(qū)間為1天，共有24顆觀測源，每顆源所需觀測時(shí)長為24～48 min。實(shí)驗(yàn)的硬件環(huán)境為1臺配置為Intel Xeon CPU E5-2660 v4 CPU@3.4 GHz處理器(56核)，512 GB RAM的高性能服務(wù)器，求解器使用Gurobi 9.1。以2020年12年21日為例，如圖4，24顆目標(biāo)源全部編排，并不存在時(shí)間交叉的情況，經(jīng)過驗(yàn)證都在可觀測的時(shí)間槽內(nèi)。

圖4 24顆觀測源在2020年12月21日的觀測時(shí)間分配

Gap即百分比界差，是求解大規(guī)?；旌险麛?shù)規(guī)劃問題時(shí)非常重要的參數(shù)，可視為在去除問題參數(shù)整數(shù)取值的限制后，問題松弛解與最優(yōu)解之間的絕對差距，

(8)

其中，OPT為當(dāng)前最優(yōu)解；LP為去掉整數(shù)約束后的松弛最優(yōu)解。實(shí)驗(yàn)使用56個(gè)線程，模型可在300 s內(nèi)將Gap控制在0.1以下。

4 總 結(jié)

本文利用線性規(guī)劃方法對40 m射電望遠(yuǎn)鏡的短期觀測目標(biāo)編排問題進(jìn)行了建模，詳述了在短期觀測編排過程中遇到的限制條件，利用非線性混合整形線性規(guī)劃解決了這一約束優(yōu)化問題。實(shí)驗(yàn)結(jié)果證明方法的可用性。

短期觀測目標(biāo)編排問題中，機(jī)會(huì)源臨時(shí)插入觀測，整個(gè)觀測計(jì)劃就需要重新編排，因此求解速度是短期觀測目標(biāo)編排的重要考量。未來我們研究使用其他的優(yōu)化算法進(jìn)一步提高編排性能，減少望遠(yuǎn)鏡等待編排的時(shí)間，同時(shí)考慮加入目標(biāo)源的權(quán)重，在望遠(yuǎn)鏡空閑時(shí)間對權(quán)重高的目標(biāo)多次觀測。此外，利用已觀測的脈沖星數(shù)據(jù)反演天線干擾情況與方位和俯仰之間的關(guān)系圖，在編排目標(biāo)源時(shí)優(yōu)先安排干擾較小的源。在目前的模型中，源切換的時(shí)間使用球面距離近似估計(jì)，不完全準(zhǔn)確，未來我們研究如何在優(yōu)化過程中根據(jù)源的方位角和高度角以及望遠(yuǎn)鏡的實(shí)時(shí)指向位置動(dòng)態(tài)計(jì)算源的切換時(shí)間。