信息物理融合系統建模的區間GMDH算法

任勝兵,黃 飛,劉 媛

(中南大學 軟件學院,長沙 410075)

1 引 言

信息物理融合系統[1](Cyber-Physical System,CPS)是集計算系統與物理系統于一體的下一代智能系統,通過嵌入式系統與網絡實現了兩者之間的實現深度融合與實時交互[2].未來CPS將廣泛應用于重要基礎設施的監測與控制、智能交通系統、智能高速公路、智能電網和智慧醫療等諸多領域.CPS自被美國國家委員會提出以來,受到了各國政府的廣泛關注,美國總統科學技術顧問委員會(NSF)把CPS列為關鍵的研究領域之一,并舉辦了一系列關于CPS的研討會.自2006年提出至今,CPS的發展得到了許多國家政府的大力支持和資助,成為學術界、科技界研究的重要方向.

由于離散的計算過程與連續的物理過程并存于CPS之中,兩者之間的融合特征很難能夠用單一的模型進行刻畫.且CPS具有的時空特性和動態非確定性,現有的建模語言也難以適應.因此,如何建立可靠的CPS模型成為研究和應用CPS的瓶頸.

本文在數據驅動建模方法的基礎上,將模型的參數估計問題看成是一個集合反演問題,結合區間分析思想,提出了區間GMDH(interval Group Method of Data Handling,iGMDH)算法.由于集合反演求解的SIVIA(Set Inverter via Interval Analysis,SIVIA)算法采用二分法對估計參數的先驗搜索域進行搜索,使得搜索的空間過大,算法的計算量成指數級增加,需要大量的時間和內存,甚至會使二分陷入死鎖.為此,本文提出的算法首先對SIVIA算法進行改進,通過引入收縮算子[3]使算法能夠在解集保持不變的情況下,對估計參數的區間進行壓縮,從而減少計算的時間復雜度和空間復雜度.其次,將GMDH算法的輸入及模型計算轉變成區間數和區間運算,以區間的形式實現數據的存儲和運算,并應用改進后的cSIVIA算法對模型參數進行估計,進一步計算求得區間估計的點估計,并依據外準則對產生的中間模型進行篩選,從而建立最終的系統模型.

2 相關工作

CPS建模是CPS系統研究的熱點.伯克利大學的Lee,Edward A通過總結現有的仿真控制建模方法提出了“信息系統物理化和物理系統信息化”的概念[4],來解決物理實體和信息實體的建模以及二者的交互問題.文獻[5]將CPS系統精化為計算實體和物理實體,并通過分析UML語言及simulink/RTW建模工具構建計算實體模型和物理實體模型的可行性提出了基于UML框架的兩種異質模型融合方法.文獻[6]利用AADL對CPS建模進行擴展,給出了一種新的建模語言CPSADL的編譯方法.并以月球車輛自主行走系統為例,說明了CPSADL的應用.文獻[7]通過深入分析諸如異構、分布式車載CPS軟件的特點,提出了一種車載CPS軟件的建模方法,以擴展混合自動機為形式化的建模工具,從服務提供的角度出發,分別將監控設備實體置主體作為設備服務.最后,以車輛速度控制系統為例說明了建模方法的有效性.文獻[8]通過對現有軟件體系結構進行擴展,提出了一種新的CPS體系結構模式,滿足了信息物理系統的建模需求,增加了對CPS的物理系統和信息系統之間交互的建模支持.并以鍋爐溫度控制系統為例,論證了CPS體系結構模式的應用.以上提出的CPS建模方法,在建立模型之前,建模者都需掌握其運行環境及所經狀態,以及每個狀態轉換所需的事件.而隨著CPS復雜度的增加,面臨環境的日益復雜,在構建系統框架或分析系統時這些方法都變得難以適應.

基于數據驅動的CPS建模是復雜CPS建模的另一類重要方法.通過使用經驗數據來對CPS運行過程中的主要屬性(自相似、非平穩性)進行描述,根據系統特征從數據中找出普遍規律并建立模型.文獻[9]提出了一種從數據出發建立CPS系統模型的方法,從獲取的離散數據中提取能夠反映系統屬性的特征值,運用GMDH算法[10,11]建立系統模型,實現了連續物理事件與離散計算系統的深度融合.GMDH算法是一種啟發式自組織的建模方法,它能夠根據輸入、輸出變量原始的信息構造出模型,并利用外準則選取最優模型,實現對研究系統內部結構的模擬.其在結構上具有的自組織、全局選優的特性,使其能夠有效地對復雜多變量系統進行辨識[12,13].然而,由于計算機字長有限導致的數據不精確性以及隨機噪聲引起的數據不確定性,使得計算機在處理程序時得到的浮點計算結果與理論計算之間存在著誤差,GMDH算法在進行模型參數估計的過程中,其計算產生的誤差,再次參與運算時將在原有的基礎上進一步產生誤差.尤其是在建立分層模型的過程中不斷擴大進而產生誤差累積的作用,最終可能得到無效結果.

區間分析[14]是R.E.Moore等人為了研究計算機浮點數運算所產生的誤差問題,于上世紀60年代初提出的.區間分析能夠以區間的形式實現數據的存儲與運算,從而避免浮點運算所產生的誤差,保證了計算結果的可靠性.另外,還可以把某些不確定性表述為區間,并直接包含在區間算法之中,可以很好地表示其可行集.因此,區間分析被認為是系統參數估計的一個有力工具.

SIVIA算法作為區間分析在非線性系統參數估計中的經典算法,能夠在給定精度內求出參數值的全部全局最優解,并能給出包含最優解且滿足要求的任意小區間.文獻[15]根據先驗知識,實驗數據和模型的附屬要求將數據與相應模型輸出之間的誤差包含在已知的可行域中,并描述出了貝葉斯最優置信域.文獻[16]提出了一種基于區間分析的有界誤差估計方法來識別定向井有桿抽油系統的粘滯阻尼系數和庫侖摩擦系數,與傳統的估計方法相比,該方法不僅具有全局性且不需要初始化,還能夠避免由于測量輸出數據的轉換而產生的數量誤差.文獻[17]通過將非線性邊界誤差估計問題看做一種反演集合,提出了一種根據機器人車載傳感器、環境傳感器以及其他機器人的實時數據估計移動機器人位置的方法,解決了大型協作環境中移動機器人的定位問題.然而,SIVIA算法在采用二分法對先驗搜索域進行搜索時,使得算法需要大量的時間和內存,甚至會使二分陷入死鎖.因此,本文提出的算法首先對其進行了改進.

3 基于區間分析的iGMDH算法

GMDH算法通常采用最小二乘估計對建立的模型進行參數估計.但由于觀測誤差、模型的結構誤差以及隨機噪聲等不確定因素的存在,容易造成輸入數據不精確、難以確定的問題.為了解決這個問題,本文通過引入區間分析的算法,將GMDH算法的輸入轉變成區間數,基于區間進行運算,建立了具有區間參數的CPS系統模型,其具體的建模流程如圖1所示.

圖1 區間GMDH算法的建模流程Fig.1 Modeling process of interval GMDH algorithm

其中x1,x2,…,x5為系統5個可能的輸入變量,對輸入變量兩兩組合之后,運用SIVIA算法進行區間估計得到待估參數的估計集,生成第一層的中間模型u1,u2,…,u10.計算出所得估計集的中心,作為參數估計的點估計.并根據算法的外準則篩選出第二層的輸入變量,重復上述步驟,依次產成第二層的中間模型z1,z2,…,z6,在外準則達到最優時,停止建模并得到最優模型y.

由于SIVIA算法在進行參數估計的過程中,采用二分對先驗搜索域(priori search set)進行遞歸地搜索,這會使算法的計算量成指數級增加,從而耗費大量的時間和內存,甚至會使二分陷入死鎖.為此,本文的算法中首先對其進行了改進,通過引入收縮算子,在解集保持不變的情況下對估計參數的搜索域進行壓縮,從而減少計算的時間復雜度和空間復雜度(子塊pavings中box的數量),提高算法的速度和效率.

3.1 SIVIA算法及其改進

3.1.1 SIVIA算法

(1)

公式(1)中的y(xi)表示輸入xi的觀測值,ym(p,xi)為輸入xi的理論輸出.由式子可以看出隨著樣本容量的增多,S包含的范圍將逐步縮小,參數集S的長度也就越小,當樣本容量足夠多時,待估參數的可行值越接近系統模型的真實參數.由于f是多參數非線性函數時,式(1)表示的S不能準確的計算出來,所以通過f的反函數f-1轉化為式(2)的集合反演問題來進行求解.

S=f-1(Y)∩P

(2)

(3)

3.1.2 改進的SIVIA算法cSIVIA

圖2 改進的SIVIA算法cSIVIA
Fig.2 Improved SIVIA algorithm cSIVIA

3.2 iGMDH算法

在UBB(unknow-but-bounded)[18]假設下,iGMDH算法在對系統模型進行參數估計時,只需知道待估參數取值的范圍,不需要其他人為的假設,這在一定程度上避免了人的主觀因素對參數估計結果的影響.與GMDH算法相比,iGMDH算法能夠將GMDH算法的輸入及模型計算轉變成區間數和區間運算,并把系統模型的參數估計看成是集合反演問題,應用cSIVIA算法求得待估參數近似但可靠的估計集,從而很好地解決浮點運算所產生的誤差及誤差累積問題.經過進一步計算,還可以得到待估參數的點估計.并且,即使在只有少量輸入數據的情況下也可以進行參數的估計,且隨著數據量的增多,提供的信息越豐富,估計的精度也就越高.

若系統有m個輸入x1,x2,…,xm,y為該系統的輸出.則給定一組輸入值就必有一y值與之對應.假定有N組x的值及對應的輸出y,則iGMDH算法建立系統模型的流程如圖3所示.圖3為iGMDH算法的偽代碼,算法第1步首先對數據集進行了處理,通過提取反映系統本質的特征屬性m,確定系統輸入變量—輸出變量的樣本集合N,并將其分為訓練集Nt和測試集Nc,其中,Nt≥Nc且Nt∪Nc=N,Nt∩Nc=φ.其次,通過2～3步構造K-G多項式,如公式(4)所示.

(4)

(5)

重復進行上述步驟,依次產生第二層、第三層的中間模型,如果新一層的Rmin不再減小時,則建模停止,并得到系統的最終模型(最優復雜度模型).

圖3 iGMDH算法
Fig.3 iGMDH algorithm

4 實驗結果與分析

4.1 實驗數據

實驗選用文獻[9]中的數據集,該數據集由加州大學歐文分校(UCI)在實際運行環境下測得,表1給出了數據集的一些相關屬性.表1所述的數據集中有在各種特征條件下汽車的自動規約值、風險等級和與指定的其他汽車相比其歸一化的損耗值.在開始測試各數據之前會根據汽車的價格為每一種類型初始化分配一個安全等級,如果該汽車測試得出其安全性能降低(升高),則相應的增大(減小)其對應的風險等級,+3便是汽車的安全性能最低,-3表示其安全系數最高.實際上,原始數據集包含26個屬性,但由于其中的10條對進行分析的對象(安全系數)的影響系數較低,因此可以忽略不計,直接剔除.在實驗的過程中,將風險等級設為輸出變量,其他15個屬性作為輸入變量來構建系統的連續模型.本文進行的所有實驗都是在對數據進行歸一化處理后進行的.

4.2 參數估計性能實驗

實驗對以汽車的“歸一化損耗”為輸出變量,“輪距”和“車速”為輸入變量建立的模型分別運用cSIVIA算法和SIVIA算法對模型的參數進行了估計.本實驗中,實際觀測數據與模型輸出間的誤差E為[-1.0,1.0],先驗搜索域為[-10,10]×[-10,10]×[-10,10]×[-10,10]×[-10,10]×[-10,10],容差參數ε0為0.01,不動點fp為0.001.實驗主要對兩種算法的計算時間和計算過程中子塊pavings產生的盒子數量進行了對比.從表2中看出本文提出的cSIVIA算法在時間和產生的盒子數量上要少于SIVIA算法.

表1 實驗數據集的屬性
Table 1 Properties of experimental data sets

symbolingNormalized-lossesWheel-baselengthwidthheight-3,-2,-1,0,1,2,3From 65 to 256From 86.6 to 120.9From 141.1to 208.1From 60.3 to 72.3From 47.8to 72.3Curb-weightEngine-sizeborestrokeCompression-ratiohorsepowerFrom 1488 to 4066From 61 to 326From 2.54 to 3.94From 2.07to 4.17From 7 to 23From 48 to 288Peak-rpmCity-mpgHighway-mpgpriceFrom 4150 to 6600From 13 to 49From 16 to 54From 5118to 45400

表2 兩種算法的比較
Table 2 Comparison of two algorithms

算法 計算時間產生的盒子數(boxes)SIVIA136S212381cSIVIA105S168175

4.3 CPS建模實驗

圖4 模型參數的估計結果Fig.4 Estimation results of model parameters

y=[-0.030218,-0.027986]+[0.696037,0.7098921]u1

(6)

u1=[-0.065031,-0.064567]+[0.3891221,0.3902663]x1

(7)

u2=[-0.501329,-0.479862]+[-0.682412,-0.647312]x2

(8)

4.4 建模誤差實驗

為了驗證iGMDH算法的優越性,本文做了兩組對比實驗,一組是不含隨機噪聲的實驗,另一組是向實驗數據集中加入隨機噪聲的實驗,分別用兩組實驗來說明在數據不精確性和數據不確定性的情況下,運用GMDH算法和iGMDH算法建模時的具體對比狀況.

4.4.1 不含隨機噪聲的情況

本文選用平均相對誤差作為模型誤差來評估參數估值偏離真值的程度,圖5和圖6分別為iGMDH算法與GMDH算法建立模型的最小均方根值及模型誤差結果對比圖.由圖5和圖6可知,iGMDH算法建模產生的最小均方根值與模型誤差均比GMDH算法的小,兩種算法的誤差及最小均方根值的變化趨勢都呈現出先減小而后增大的趨勢.這是由于在建立前兩層模型時誤差產生的累積作用較小,而算法本身具有的收斂性,能夠在誤差達到最小的情況下,選出系統的最優模型.但在建立的分層模型中,即使模型誤差再小也具有一定的誤差累積作用,并且隨著模型層數的增多,所產生誤差的累積作用就會越大,從而影響模型的精確度.而iGMDH算法則不存在這個問題,它能夠將取值不精確的浮點數存儲為區間,基于區間進行計算.因此,應用其建立的模型要比GMDH算法所建的模型更加精確、可靠.

圖5 最小均方根值比較Fig.5 Comparison of the minimum RMS

圖6 模型誤差的比較Fig.6 Comparison of model errors

4.4.2 含有隨機噪聲的情況

我們向實驗數據集中加入均值為0,標準差為0.1的正態隨機噪聲.實驗將不含隨機噪聲的實測數據求得的歸一化損耗值作為“真實值”.將含有隨機噪聲的實測數據求得的歸一化損耗值作為“實測值”,這樣做能夠保證參數估計的所有誤差僅來源于樣本數據及參數估計的方法本身,以便于研究隨機噪聲對模型參數估計結果的影響.表3為在實驗數據不含隨機噪聲和含有隨機噪聲的情況下,iGMDH算法與文獻[12]中GMDH算法選擇相同變量建立模型的參數估計結果.由表3可以看出在有隨機噪聲干擾的情況下,GMDH算法參數估計結果明顯偏離了參數的真實值,而iGMDH算法無論是在有噪聲干擾的情況下還是無噪聲干擾的情況下,都能穩健地得到可靠的逼近真實值的解集.進一步計算求得區間參數的點估計,通過計算模型的相對誤差來評估參數估計值偏離其真值的程度,即參數的估計精度.求得iGMDH的平均相對誤差為1.56363%,GMDH算法的為3.40609%,由此可以得出,iGMDH算法估計精度、抗噪性均優于GMDH算法.

表3 實驗數據有噪聲、無噪聲情況下兩種算法參數估計結果對比
Table 3 Comparison of parameters estimation results between two algorithms with or without noise in experimental data

無隨機噪聲有隨機噪聲區間GMDHGMDH 區間GMDHGMDH A [-0.030218,-0.027986]-0.0288 [-0.035607,-0.025419]-0.0145 B [0.696037,0.7098921]0.7052 [0.679346,0.72314715]0.8164 C[0.260018,0.275146]0.2738 [0.2589316,0.289710]-0.0221 D [-1.613138,-1.496873]-1.5375 [-1.654271,-1.4867359]-0.6956 E [1.279510,1.2925138]1.2859 [1.27698465,1.3109412]0.9670 F[0.317692,0.335104]0.3248 [0.3068923,0.3449271]0.3078

5 結 語

為了解決CPS系統建模過程中由于數據不精確性以及隨機噪聲引起的數據不確定性產生的誤差及誤差累積問題,本文將GMDH算法用區間分析的算法加以改進,首先通過引入收縮算子,對估計參數的搜索域進行壓縮,改進了SIVIA算法,提出了cSIVIA算法.其次,將GMDH算法的輸入和計算轉變為區間數和區間計算,利用cSIVIA算法進行模型的參數估計,從而提出新的算法—iGMDH算法,建立了具有區間參數的模型.實驗結果表明本文提出的iGMDH算法能夠使估計得到的區間參數直接包含在計算之中,在有無噪聲干擾的情況下都能夠得到待估參數近似但可靠的估計集.與GMDH算法相比,算法的精確度高、抗噪性強,有效地解決了建模過程中存在的誤差及誤差累積問題,為我們更加準確地估計和評價所得結果提供了新的依據.此外,該算法在樣本容量較少的情況下也能夠求得模型參數的近似估計,這對于CPS系統的研究與應用具有重要意義.