動態(tài)規(guī)劃在多源遙測參數(shù)優(yōu)選中的應(yīng)用

王萬金 張志國

（91550 部隊(duì)94 分隊(duì) 遼寧省大連市 116023）

飛行器飛行試驗(yàn)采集的遙測數(shù)據(jù)反映了其各系統(tǒng)工作狀態(tài)和結(jié)構(gòu)力學(xué)特性，數(shù)據(jù)準(zhǔn)確的解析、有效的判讀是試驗(yàn)完整性的重要組成，解析是基礎(chǔ)、判讀是關(guān)鍵。解析依據(jù)數(shù)據(jù)幀編碼協(xié)議和行業(yè)普遍采用的“剝洋蔥”式解析法逐層解析，依次獲取參數(shù)類別數(shù)據(jù)塊和參數(shù)原碼。判讀需要考慮眾多因素，通常依據(jù)系統(tǒng)狀態(tài)指標(biāo)閾值開展，數(shù)據(jù)的可讀性即數(shù)據(jù)的真實(shí)性是判讀的重要前提。數(shù)據(jù)解析包括預(yù)處理和處理過程，預(yù)處理是處理的基礎(chǔ)，具體又涉及單源數(shù)據(jù)的檢測和多源數(shù)據(jù)的優(yōu)選等環(huán)節(jié)。通常依據(jù)數(shù)據(jù)幀標(biāo)識碼開展檢測，進(jìn)一步通過多源數(shù)據(jù)采集的有效段落優(yōu)選并合并數(shù)據(jù)，從而開展后續(xù)的處理工作。為能有效開展判讀工作，通常需要在數(shù)據(jù)聚集操作即計(jì)算均值、均方差、均方根、極值等環(huán)節(jié)時(shí)規(guī)避非理性數(shù)據(jù)，即剔除參數(shù)值中的異常或野點(diǎn)值。在數(shù)據(jù)采集和傳輸質(zhì)量良好情況下，數(shù)據(jù)源誤碼率較低，異常或野點(diǎn)值少，通過有效的異常或野點(diǎn)值剔除方法[1]即可消除其影響，不影響數(shù)據(jù)的聚集操作和試驗(yàn)的判讀工作。在特殊情況下，受多種因素影響數(shù)據(jù)源的誤碼率增高，數(shù)據(jù)質(zhì)量嚴(yán)重下降，常規(guī)的多源數(shù)據(jù)優(yōu)選方法不能夠最大化消除異常或野點(diǎn)值，數(shù)據(jù)的解析和判讀策略受到嚴(yán)重考驗(yàn)，探尋更為有效的解析方法和處理手段變得尤為緊迫。本文從數(shù)據(jù)解析的預(yù)處理環(huán)節(jié)入手，采取動態(tài)規(guī)劃的方式對多源數(shù)據(jù)進(jìn)行優(yōu)選，結(jié)合常規(guī)的異常或野點(diǎn)值剔除方法，最大化地提取多源數(shù)據(jù)中的有效數(shù)據(jù)，為飛行器試驗(yàn)判讀工作奠定基礎(chǔ)。

1 優(yōu)選目標(biāo)和約束邊界

關(guān)于遙測數(shù)據(jù)預(yù)處理過程多源數(shù)據(jù)優(yōu)選問題，在數(shù)據(jù)源誤碼率較小情況下，通常采取多源數(shù)據(jù)整體加權(quán)優(yōu)選法，即根據(jù)試驗(yàn)有效時(shí)段對數(shù)據(jù)源加以劃分，并按時(shí)間先后和主備原則給各數(shù)據(jù)源以權(quán)值，時(shí)間靠前的主源數(shù)據(jù)權(quán)值較大，以此類推。實(shí)現(xiàn)過程中，根據(jù)各數(shù)據(jù)源的權(quán)值進(jìn)行數(shù)據(jù)段落選擇，進(jìn)而實(shí)現(xiàn)多源數(shù)據(jù)優(yōu)選合并全程有效數(shù)據(jù)的目的。針對誤碼率較大情況下，上述方法過于粗獷，難以獲取目標(biāo)數(shù)據(jù)，需要結(jié)合工程實(shí)際，對多源數(shù)據(jù)按時(shí)間段落進(jìn)行多網(wǎng)格劃分（圖1所示），采取類似積分的原理依次優(yōu)選合并數(shù)據(jù)。該方法在實(shí)現(xiàn)過程中，往往采用全域遍歷的模式，按照約定的邊界條件窮盡所有時(shí)間段落，實(shí)為暴力枚舉，實(shí)現(xiàn)數(shù)據(jù)的優(yōu)選。方法理論上可行，實(shí)際執(zhí)行的時(shí)間復(fù)雜度較高，在多源數(shù)據(jù)較長的情況下，計(jì)算消耗成本高，需要進(jìn)一步改進(jìn)。

圖1：時(shí)間網(wǎng)格劃分多源數(shù)據(jù)圖

動態(tài)規(guī)劃（dynamic programming，簡稱DP）是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程的一個(gè)最優(yōu)方法。采用DP 需要滿足兩個(gè)重要特性，即無后效性和最優(yōu)子結(jié)構(gòu)。

1.1 無后效性

一旦目標(biāo)函數(shù)f(n)確立，如何求出f(n)的過程不再重要。嚴(yán)格來講，如果給定某一階段狀態(tài)，則在這一階段以后過程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響。

1.2 最優(yōu)子結(jié)構(gòu)

大問題的最優(yōu)解可由小問題的最優(yōu)解推出，即最優(yōu)子結(jié)構(gòu)。

根據(jù)這兩個(gè)性質(zhì)，我們分析上述多源數(shù)據(jù)優(yōu)選過程是否能夠采用DP 加以解決。采用網(wǎng)格劃分的時(shí)間段落，結(jié)合約束邊界條件，我們只關(guān)心當(dāng)前時(shí)間段落的最優(yōu)值，至于這個(gè)最優(yōu)過程涉及哪些先前的時(shí)間段落，這不是需要考慮的問題，即滿足DP 過程的無后效性。每一階段時(shí)間段落內(nèi)多源數(shù)據(jù)的優(yōu)選結(jié)果一定是整個(gè)優(yōu)選過程的一部分，即滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。可以看出，暴力枚舉方法存在一定的冗余信息，動態(tài)規(guī)劃則是其求解的子過程，即在可能的解空間內(nèi)尋求最優(yōu)解，但時(shí)間復(fù)雜度卻相差很大，若枚舉方法為指數(shù)級，DP 方法則為多項(xiàng)式級。確定多源數(shù)據(jù)優(yōu)選過程可以采用DP 后，需要進(jìn)一步確定優(yōu)選的目標(biāo)和約束邊界。

1.3 優(yōu)選目標(biāo)

假定多源數(shù)據(jù)為S(i)(i=1,2,…n)，借助一定的先驗(yàn)信息，S(i)的時(shí)間段落可以劃分為di(k)(k=1,2,…m)，每一di(k)對應(yīng)的權(quán)值為pi(k)，其映射關(guān)系為f(di(k))=pi(k)，則優(yōu)選目標(biāo)可以簡化為下述方程的求解：

其中，pm為每個(gè)多源數(shù)據(jù)末段的權(quán)值。

1.4 約束邊界

式（1）中，S(i)的時(shí)間段落di(k)(k=1,2,…m)劃分的區(qū)間數(shù)m設(shè)定原則應(yīng)考慮如下幾方面：

A.假定當(dāng)前源數(shù)據(jù)S(i)時(shí)間段落內(nèi)的異常或野點(diǎn)值數(shù)共計(jì)為j，則劃分區(qū)間數(shù)為m=d/j+1；

B.pi應(yīng)包含兩個(gè)維度，即當(dāng)前時(shí)間段落di(k)內(nèi)異常或野點(diǎn)值數(shù)和當(dāng)前源數(shù)據(jù)的序列值。

2 DP模型建立和算法實(shí)現(xiàn)

動態(tài)規(guī)劃是求解最優(yōu)過程的策略，只給出了規(guī)則，如上節(jié)優(yōu)選目標(biāo)的分析設(shè)計(jì)過程，即設(shè)計(jì)狀態(tài)和設(shè)計(jì)轉(zhuǎn)移，沒有一概統(tǒng)一的方法而言，需要根據(jù)工程實(shí)際問題具體分析，制定切實(shí)可行的方法加以實(shí)現(xiàn)。我們從DP 的基本性質(zhì)角度分析，上述多源數(shù)據(jù)優(yōu)選問題滿足無后效性和最優(yōu)子結(jié)構(gòu)的特性，可以采用DP 過程，結(jié)合該工程實(shí)際設(shè)計(jì)具體算法模型并進(jìn)行實(shí)現(xiàn)。

上面我們對多源數(shù)據(jù)S(i)(i=1,2,…n)按照時(shí)間段落進(jìn)行了網(wǎng)格劃分，根據(jù)權(quán)值來選取最優(yōu)數(shù)據(jù)。深入研究分析，我們的優(yōu)選目標(biāo)來源于以權(quán)值為基本元素的數(shù)值序列，可以將時(shí)間網(wǎng)格劃分的共同時(shí)間基點(diǎn)抽象為一點(diǎn)，而數(shù)據(jù)優(yōu)選的過程可以抽象為如圖2所示的拓?fù)浣Y(jié)構(gòu)圖。至此，我們對具體工程問題進(jìn)行了抽象，下面重點(diǎn)研究如何從一個(gè)拓?fù)浣Y(jié)構(gòu)中抽取最優(yōu)子結(jié)構(gòu)。

圖2：網(wǎng)格劃分多源數(shù)據(jù)拓?fù)涑橄髨D

上面給出了優(yōu)選目標(biāo)和問題抽象的解決思路，針對優(yōu)選目標(biāo)，問題是具體算法如何設(shè)定和實(shí)現(xiàn)。設(shè)計(jì)狀態(tài)即DP 過程在求解問題算法面對問題的解決途徑。假設(shè)面對的局面為x，則解決局面的過程f(x)就是設(shè)計(jì)狀態(tài)。

2.1 設(shè)計(jì)狀態(tài)

圖2中，由P 到S 的過程，可選擇的路徑有P->s1->S，P->s2->S，…，P->sk->S，從而f(S)=min{f(P)+ps1,f(P)+ps2,…,f(P)+psm}，m=1,2,…,k，psm 表示P->S 路徑的權(quán)值。

2.2 設(shè)計(jì)轉(zhuǎn)移

設(shè)計(jì)狀態(tài)解決了DP 算法實(shí)現(xiàn)的目標(biāo)設(shè)定問題，即上節(jié)優(yōu)選目標(biāo)的具體化，那如何實(shí)現(xiàn)目標(biāo)即是解析算法實(shí)現(xiàn)過程的問題，設(shè)計(jì)轉(zhuǎn)移就是解決具體問題的途徑。

針對上述問題，顯然，設(shè)計(jì)轉(zhuǎn)移即狀態(tài)轉(zhuǎn)移方程為：

其中，Q 為到P 點(diǎn)的所有節(jié)點(diǎn)，ωQ→P表示Q->P 的權(quán)值。

2.3 算法實(shí)現(xiàn)

從設(shè)計(jì)狀態(tài)到狀態(tài)轉(zhuǎn)移，實(shí)現(xiàn)了多源數(shù)據(jù)優(yōu)選問題算法設(shè)計(jì)過程，下面重點(diǎn)開展算法實(shí)現(xiàn)。

算法多源數(shù)據(jù)優(yōu)選計(jì)算

輸入經(jīng)網(wǎng)格劃分的多源數(shù)據(jù)段落S(i)(i=1,2,…n)的序列di(k)(k=1,2,…m)全集合。

輸出最優(yōu)子結(jié)構(gòu)序列索引

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

以某次飛行器飛行試驗(yàn)采集的多源遙測數(shù)據(jù)為例，對其加入隨機(jī)的誤碼信號，采用傳統(tǒng)方法對含有誤碼的多源遙測數(shù)據(jù)進(jìn)行優(yōu)選合并，并做進(jìn)一步的處理，得到還原后的物理量參數(shù)數(shù)據(jù)。

圖3為采用傳統(tǒng)方法得到的存在誤碼以及真實(shí)情況下的某振動信號物理量的時(shí)間歷程圖。可以看出，受誤碼影響，采用傳統(tǒng)方法獲取的振動信號與真實(shí)振動信號之間存在較大差異。

圖3：存在誤碼和真實(shí)情況下的振動信號

圖4為隨機(jī)加入的誤碼振動信號，不難看出，該隨機(jī)誤碼振動信號與真實(shí)振動信號在幅值上相當(dāng)，難以通過常規(guī)的濾波等手段消除其影響。

圖4：誤碼振動信號

圖5為采用動態(tài)規(guī)劃方法獲取的振動信號以及真實(shí)情況下的振動信號，可以看出，經(jīng)動態(tài)規(guī)劃獲得的振動信號與其真實(shí)信號相近。

圖5：動態(tài)規(guī)劃和真實(shí)情況下的振動信號

進(jìn)一步如圖6所示，動態(tài)規(guī)劃下獲得的振動信號與真實(shí)振動信號的相對誤差在2%-6%之間，最大不超過10%，精度在可以接受范圍內(nèi)，不影響數(shù)據(jù)的進(jìn)一步判讀和分析。

圖6：相對誤差

圖7為進(jìn)一步分析的結(jié)果，分別為動態(tài)規(guī)劃下獲得的振動信號與真實(shí)振動信號間的絕對誤差（ABE）、平均誤差（AME）以及均方誤差（MSE）。不難看出，絕對誤差幅值較小，最大不超過0.4，平均誤差為0.12，而均方誤差為0.03，從數(shù)據(jù)判讀和分析的角度，滿足飛行器飛行試驗(yàn)的相關(guān)要求，方法較為可靠。

圖7：絕對、平均和均方誤差

4 結(jié)論

誤碼率較高情況下，傳統(tǒng)多源遙測數(shù)據(jù)優(yōu)選方法難以獲得較為真實(shí)的結(jié)果數(shù)據(jù)。對先前方法進(jìn)行改進(jìn)，采用時(shí)間尺度對多源數(shù)據(jù)進(jìn)行多網(wǎng)格劃分，并抽象劃分的多源遙測數(shù)據(jù)節(jié)點(diǎn)，在滿足無后效性和最優(yōu)子結(jié)構(gòu)的前提下，提出基于動態(tài)規(guī)劃的多源遙測參數(shù)優(yōu)選模型。結(jié)合工程實(shí)際，對優(yōu)選目標(biāo)進(jìn)行了狀態(tài)設(shè)計(jì)和狀態(tài)轉(zhuǎn)移，進(jìn)一步完成了算法的設(shè)計(jì)和實(shí)現(xiàn)。利用實(shí)驗(yàn)數(shù)據(jù)，在附加隨機(jī)誤碼信息的情況下，對模型和算法進(jìn)行了驗(yàn)證。結(jié)果表明，誤差精度能夠滿足數(shù)據(jù)處理和分析的相關(guān)要求，基于動態(tài)規(guī)劃的多源遙測參數(shù)優(yōu)選思想是切實(shí)可行的，在多源遙測數(shù)據(jù)不同時(shí)混雜高誤碼信息的情況下，能夠?yàn)檫b測數(shù)據(jù)優(yōu)選工作提供切實(shí)可行的幫助。