基于貪心算法的氣象修正表自動(dòng)分區(qū)擬合算法設(shè)計(jì)

趙明陽(yáng)，楊揆，王璟旻，陳捷

(1.中國(guó)船舶集團(tuán)有限公司系統(tǒng)工程研究院，北京 100094；2.海軍裝備部，陜西 西安 710030)

火炮實(shí)際射擊時(shí)的彈道、氣象條件和標(biāo)準(zhǔn)條件往往不一致，即非標(biāo)準(zhǔn)射擊條件。這些偏差使得按基本射表計(jì)算的射擊諸元擊發(fā)的彈丸可能不能命中目標(biāo)，為保證實(shí)際射擊條件的計(jì)算，通常需要進(jìn)行彈道、氣象等非標(biāo)條件的修正[1-2]。為避免計(jì)算機(jī)存儲(chǔ)大量氣象修正表數(shù)據(jù)以便快速準(zhǔn)確計(jì)算氣象修正量,目前常用連續(xù)解析函數(shù)盡可能準(zhǔn)確地逼近氣象修正表，然后把這些函數(shù)存入計(jì)算機(jī)代替氣象修正表[3-5]。實(shí)際逼近過程中，有時(shí)無(wú)論怎樣提高解析函數(shù)階數(shù)都無(wú)法通過一組多項(xiàng)式系數(shù)在整個(gè)定義域內(nèi)計(jì)算出滿足精度要求的修正量，此時(shí)需要分區(qū)處理[6]。不同類型的氣象參數(shù)，分區(qū)方式也不盡相同，區(qū)域的劃分是一個(gè)動(dòng)態(tài)過程，對(duì)數(shù)據(jù)量龐大的修正表進(jìn)行人工分區(qū)需要進(jìn)行反復(fù)的試探，效率低下，不易控制分區(qū)數(shù)量和殘差，目前業(yè)內(nèi)尚未對(duì)自動(dòng)分區(qū)方法進(jìn)行過深入研究。筆者設(shè)計(jì)了基于貪心算法的自動(dòng)分區(qū)擬合算法，實(shí)現(xiàn)了氣象修正表逼近函數(shù)系數(shù)的自動(dòng)分區(qū)計(jì)算，并且殘差可控，確保了逼近準(zhǔn)確性。

1 算法設(shè)計(jì)

逼近氣象修正表的主要工作是對(duì)修正表的修正量離散數(shù)據(jù)進(jìn)行擬合，求解逼近函數(shù)各個(gè)高階多項(xiàng)式的系數(shù)[7-8]，需要根據(jù)水平距離(或斜距離)或高度中的一個(gè)自變量分段擬合，或者選擇水平距離(或斜距離)和高度兩個(gè)自變量的方式分區(qū)擬合，分段擬合其實(shí)是分區(qū)擬合的一個(gè)特例。

1.1 算法選擇

算法設(shè)計(jì)的原則是在保證解析函數(shù)精度的情況下，盡量減少分區(qū)，使解析函數(shù)用單組擬合系數(shù)盡可能地逼近氣象修正表定義域中更大區(qū)域上的修正量數(shù)據(jù)，符合殘差要求的最大區(qū)域作為一個(gè)分區(qū)。在搜索最大區(qū)域時(shí)，采用自頂向下的設(shè)計(jì)，只需在每個(gè)決策點(diǎn)做出在當(dāng)前問題中的最優(yōu)選擇，直接加入局部最優(yōu)解集合，而不必考慮子問題的解。如果有剩余子問題，再將子問題作為當(dāng)前問題開始下一次的最大區(qū)域搜索?；谝陨显O(shè)計(jì)思想，適合選用貪心算法進(jìn)行自動(dòng)分區(qū)。貪心算法的顯著特點(diǎn)是每次對(duì)未知區(qū)域搜索都采取當(dāng)前狀態(tài)下的局部最優(yōu)解，通過選擇局部最優(yōu)產(chǎn)生出全部定義域上的全局最優(yōu)解。

貪心算法通用步驟如下[9]：

1)從全部定義域上的離散數(shù)據(jù)出發(fā)，根據(jù)貪心策略先得出當(dāng)前狀態(tài)的最優(yōu)解，縮小問題規(guī)模。

2)采用迭代方法，向剩余部分的定義域前進(jìn)，根據(jù)貪心策略得到剩余子問題的局部最優(yōu)解，逐步縮小問題規(guī)模。

3)將所有解綜合，驗(yàn)證結(jié)果。

1.2 分區(qū)原則

貪心算法所得的局部解是否最優(yōu)，可用擬合殘差和擬合區(qū)域面積大小來(lái)判斷。擬合結(jié)果的驗(yàn)收依據(jù)是殘差極值和殘差均方差，可以針對(duì)每種氣象參數(shù)設(shè)置一個(gè)殘差極限門限和均方差門限。當(dāng)修正表當(dāng)前選擇區(qū)域的數(shù)據(jù)擬合殘差低于殘差門限和均方差門限時(shí)，可以擴(kuò)大選擇區(qū)域再次計(jì)算擬合系數(shù)和擬合殘差，直到殘差超過門限為止，滿足精度要求的最大區(qū)域?yàn)闅庀笮拚淼囊粋€(gè)分區(qū)，這就是貪心算法的貪心策略。

殘差門限應(yīng)合理設(shè)置，氣象修正表是通過實(shí)測(cè)和理論計(jì)算綜合處理得出，本身存在誤差，因此殘差門限設(shè)置過低不會(huì)帶來(lái)更多收益。一般選擇均方差不大于氣象修正表數(shù)據(jù)精度的5倍，最大殘差控制在不大于均方差的5倍[6]。

1.3 擬合方法

設(shè)Y=(y1,y2,y3,…,yp)T是修正表中的一組離散修正量數(shù)據(jù)，是自變量X=(X1,X2,X3,…,Xm;m?p)的連續(xù)函數(shù)，自變量X中的元素均由DaHb(a≥0,b≥0,a+b≤n)形式的二元基函數(shù)組成的向量[6]，n為逼近函數(shù)的階數(shù)，D為某個(gè)修正量數(shù)據(jù)所對(duì)應(yīng)的距離或斜距離，視計(jì)算結(jié)果的分區(qū)數(shù)量或擬合殘差的情況選擇距離或斜距離，H為相同修正量數(shù)據(jù)所對(duì)應(yīng)的高度。

根據(jù)維爾斯拉斯(Weierstrass)逼近定理，逼近函數(shù)的多項(xiàng)式項(xiàng)數(shù)越多，其逼近效果越好[10]，但實(shí)際計(jì)算中發(fā)現(xiàn)，各自變量多項(xiàng)式對(duì)于逼近函數(shù)的貢獻(xiàn)并不相同，部分項(xiàng)對(duì)結(jié)果的貢獻(xiàn)極其微弱，影響計(jì)算速度，而且項(xiàng)數(shù)過多時(shí)，雖然在逼近離散修正量時(shí)可降低殘差，但在計(jì)算修正表未定義的離散點(diǎn)修正量時(shí)，有時(shí)會(huì)出現(xiàn)修正量明顯正常范圍的不合理波動(dòng)[6]，這種不合理波動(dòng)需要通過驗(yàn)算發(fā)現(xiàn)。為避免過多的高階項(xiàng)，n一般不大于7，逼近函數(shù)多項(xiàng)式的項(xiàng)數(shù)不超過36。當(dāng)選擇4階逼近函數(shù)時(shí)，m=15，函數(shù)表達(dá)式為

y=f(D,H)=β1+β2D+β3H+β4D2+β5DH+
β6H2+β7D3+β8D2H+β9DH2+β10H3+β11D4+
β12D3H+β13D2H2+β14DH3+β15H4+ε，

(1)

式中，ε為逼近殘差。

B=(β1,β2,β3,…,β15)T是一組待求系數(shù)，寫為矩陣形式為Y=XB+ε。

(2)

采用最小二乘法擬合數(shù)據(jù)。最小二乘法是使殘差平方和Q(B)達(dá)到最小。根據(jù)極值定理B應(yīng)滿足：

(3)

可得非齊次線性方程組系數(shù)矩陣：

(4)

1.4 自動(dòng)分區(qū)

分區(qū)擬合過程中，每次迭代開始前，要在氣象修正表內(nèi)選定一塊尚未擬合的連續(xù)區(qū)域M，為便于規(guī)定該區(qū)域的定義域范圍，連續(xù)區(qū)域最好是規(guī)則形狀，本文選擇矩形區(qū)域。再根據(jù)區(qū)域的距離和高度范圍，篩選區(qū)域M內(nèi)的修正量數(shù)據(jù)，作為本次迭代的Y向量，然后對(duì)篩選的數(shù)據(jù)進(jìn)行擬合并計(jì)算殘差。如果在區(qū)域M內(nèi)，存在寬度和長(zhǎng)度足夠大的連續(xù)子區(qū)域Pi(Pi?M)，使Pi內(nèi)的全部數(shù)據(jù)的擬合精度滿足要求，則將精度滿足的區(qū)域標(biāo)記為已擬合，縮小氣象修正表待擬合區(qū)域的范圍，選取面積最大的區(qū)域作為一個(gè)分區(qū)。然后繼續(xù)根據(jù)貪心策略遍歷所有剩余連續(xù)矩形區(qū)域，將貪心搜索所得的下一個(gè)精度合格的最大區(qū)域作為一個(gè)分區(qū)，進(jìn)一步縮小問題范圍。

單次迭代中，為避免出現(xiàn)碎片區(qū)域，每個(gè)被搜索子區(qū)域的距離和高度的上限或下限均與區(qū)域M的邊界重合，即從區(qū)域M的距離邊界和高度邊界開始搜索，在每一整塊子區(qū)域Pi內(nèi)遍歷計(jì)算每個(gè)高度也連續(xù)的子區(qū)域Qi(Qi?P)的擬合殘差，如果被搜索的區(qū)域Qi面積小于本次迭代中已搜索到的最大區(qū)域，則放棄計(jì)算，選擇下一個(gè)可處理的子區(qū)域Qi+1或Pi+1，直到遍歷整個(gè)區(qū)域M，精度滿足要求的最大區(qū)域作為一個(gè)分區(qū)。

貪心搜索最大區(qū)域時(shí)，每次移動(dòng)距離或高度游標(biāo)，可同時(shí)計(jì)算兩個(gè)游標(biāo)到各自起始點(diǎn)共4個(gè)區(qū)域的擬合殘差，移動(dòng)游標(biāo)，實(shí)現(xiàn)遍歷搜索。

貪心搜索程序設(shè)計(jì)如下：

GetDataArea//區(qū)域M

for i←startD to stopD//子區(qū)域Pi

for j←startH to stopH//子區(qū)域Qi

//距離上的前進(jìn)搜索高度上的前進(jìn)搜索

GetDataAndFit(startD, i , startH , j)

//距離上的前進(jìn)搜索高度上的后退搜索

GetDataAndFit( startD , i , j , stopH )

//距離上的后退搜索高度上的前進(jìn)搜索

GetDataAndFit( i , stopD , startH , j )

//距離上的后退搜索高度上的后退搜索

GetDataAndFit( i , stopD , j , stopH )

end

end

return maxArea

1.5 算法流程

在上述關(guān)鍵處理環(huán)節(jié)的基礎(chǔ)上，設(shè)計(jì)如圖1所示的完整算法流程。

計(jì)算開始后進(jìn)行參數(shù)初始化。首先加載氣象修正表數(shù)據(jù)，將其存儲(chǔ)于可以讀取任意距離和高度范圍內(nèi)所有修正量數(shù)據(jù)的二維數(shù)組中；建立一個(gè)映射表，該表記錄氣象修正表定義域上的已經(jīng)擬合過的數(shù)據(jù)，下次迭代前會(huì)通過該表查詢未擬合的區(qū)域；選擇當(dāng)前要擬合的參數(shù)類型，例如氣溫變化引起的距離修正量；選擇基函數(shù)形式和函數(shù)階數(shù)；根據(jù)修正表數(shù)據(jù)精度設(shè)置貪心策略。然后開始迭代，自動(dòng)搜索低于殘差門限的最大區(qū)域進(jìn)行分區(qū)。如果某次迭代的區(qū)域長(zhǎng)度或?qū)挾炔蛔悖瑒t無(wú)法保證自變量多項(xiàng)式的線性無(wú)關(guān)性，可能導(dǎo)致逼近函數(shù)不連續(xù)、不平滑的錯(cuò)誤結(jié)果，對(duì)于這種情況需增加區(qū)域長(zhǎng)度或?qū)挾龋匾獣r(shí)可將已擬合的區(qū)域包含進(jìn)來(lái)。如果某次迭代的數(shù)據(jù)定義域與上次相同，表明上次沒有搜索到滿足精度要求的區(qū)域，需退出程序，對(duì)該區(qū)域人工擬合后檢查殘差分布。

2 算法驗(yàn)證

在分區(qū)結(jié)束后，修正表所有的修正量都可通過逼近函數(shù)計(jì)算得出，可驗(yàn)算全部分區(qū)的擬合函數(shù)系數(shù)。由于有貪心策略控制，氣象修正表中的所有值域數(shù)據(jù)的擬合殘差都已低于殘差門限，驗(yàn)算時(shí)遍歷全部值域。通過值域數(shù)據(jù)對(duì)應(yīng)的水平距離和高度查找其所在分區(qū)的擬合系數(shù)，用逼近函數(shù)結(jié)合該組系數(shù)計(jì)算所得的修正量計(jì)算出擬合殘差。除殘差外，還需檢查逼近函數(shù)的連續(xù)性[13]。調(diào)用逼近函數(shù)，通過距離不變、高度步進(jìn)和高度不變、距離步進(jìn)的方法，計(jì)算修正表中未給出的離散點(diǎn)數(shù)據(jù)，檢查步進(jìn)過程中的修正量增量是否存在不合理波動(dòng)。如果自變量超出定義域，則增量置為0。觀察增量數(shù)據(jù)曲線，曲線應(yīng)隨距離或高度的增加平滑變化。雖然各區(qū)域均為閉區(qū)間，相鄰分區(qū)的邊界重合，但氣象修正表本身存在誤差，區(qū)域間結(jié)合處附近的函數(shù)值仍可能存在跳點(diǎn)，如出現(xiàn)米級(jí)以上的增量變化，必定是區(qū)域間結(jié)合處的增量不連續(xù)，則需滑動(dòng)兩區(qū)域的分界線，重新分區(qū)，直到新分區(qū)的擬合系數(shù)可實(shí)現(xiàn)增量連續(xù)。

圖2、3為殘差分布圖，一般情況下，受試驗(yàn)現(xiàn)場(chǎng)氣象測(cè)量精度、彈道測(cè)量精度和隨機(jī)因素的影響，在氣象修正表定義域最大距離或最大高度附近的數(shù)值隨機(jī)誤差較大，殘差也較大，可適當(dāng)提高門限，也可能存在擬合殘差總是超過門限的點(diǎn)或極個(gè)別殘差明顯偏大的“賊點(diǎn)”數(shù)據(jù)，可將“賊點(diǎn)”附近的數(shù)據(jù)做平滑處理，用插值數(shù)據(jù)替代“賊點(diǎn)”數(shù)據(jù)[6]。

圖4為5條在高度不變條件下的氣溫距離修正量隨目標(biāo)水平距離步進(jìn)的增量曲線，曲線表示目標(biāo)分別為高度H=500,600,700,800,900 m時(shí)，逼近函數(shù)計(jì)算出的目標(biāo)在水平距離為sd時(shí)，水平距離每增加0.1 m時(shí)的距離修正量的增量，即Δsd=f(sd+0.1,H)-f(sd,H)，sd為修正表水平距離定義域內(nèi)的任一數(shù)值。

圖5為5條在距離不變條件下的氣溫距離修正量隨目標(biāo)高度步進(jìn)的增量曲線，曲線表示目標(biāo)水平距離分別為SD=0.5，1.0，1.5，2.0，2.5 km時(shí)，逼近函數(shù)計(jì)算出的目標(biāo)在高度為h時(shí)，高度每增加0.1 m時(shí)的距離修正量的增量，即Δsd=f(SD,h+0.1)-f(SD,h)，h為修正表高度定義域內(nèi)的任一數(shù)值。

圖6為5條在高度不變條件下的氣溫高度修正量隨水平距離步進(jìn)的增量曲線，圖7為5條在距離不變條件下的氣溫高度修正量隨高度步進(jìn)的部分增量曲線。圖6和圖7中的每條曲線代表隨水平距離或高度按0.1 m步進(jìn)的修正量增量走勢(shì)。

由圖4～7可知，每條曲線連續(xù)平滑，沒有拐點(diǎn)、不合理波動(dòng)或“毛刺”。在定義域內(nèi)如若所有增量曲線均連續(xù)平滑，則表明擬合系數(shù)正確可用，分區(qū)方式合理，逼近函數(shù)可用于非標(biāo)條件的修正。

3 結(jié)束語(yǔ)

基于貪心算法的自動(dòng)分區(qū)擬合算法可以根據(jù)殘差門限自動(dòng)搜索滿足精度要求的區(qū)域自動(dòng)進(jìn)行分區(qū)，通過對(duì)離散數(shù)據(jù)的擬合計(jì)算出逼近函數(shù)系數(shù)，從而實(shí)現(xiàn)對(duì)氣象修正量的快速計(jì)算。驗(yàn)算結(jié)果表明，在修正表的定義域內(nèi)，逼近函數(shù)可以準(zhǔn)確逼近修正表已給出的離散修正量數(shù)據(jù)，對(duì)于修正表未給出的任意距離和高度上的修正量可正確計(jì)算。