軟件失效時序數(shù)據(jù)的灰色擬合及多步預(yù)測算法

摘要： 關(guān)鍵詞： 中圖分類號： 文獻標(biāo)志碼： A文章編號： 2095-2163

Abstract： For the reliability model of the software system， its main function is to accurately predict the occurrence of a subsequent software failure time. The paper studies grey fitting problem of the software failure time series data， and proposes the corresponding multistep prediction algorithm. First of all， based on the condition of a fitting accuracy， apply grey theory GM （1， 1） model for the software failure time series data to establish the corresponding piecewise fitting model； then， use the orthogonal polynomial function to estimate fitting residual error at the end of the sequence， and utilize the estimate result for correcting and compensating grey prediction model at the end of the sequence； in the end， apply the combined forecasting model based on compensation to realize multistep projections for the occurrence of software failure time. The experiment verifies the correctness and effectiveness of the algorithm.

0引言

在軟件可靠性的分析與建模過程中，其首要任務(wù)就是建立一個精確易用的預(yù)測模型，以便對軟件系統(tǒng)的各種可靠狀況做出精確的預(yù)測。根據(jù)預(yù)測目標(biāo)的不同，軟件可靠性的預(yù)測模型通?？梢苑譃閮煞N：靜態(tài)模型和動態(tài)模型。其中，靜態(tài)模型主要是利用軟件系統(tǒng)的各種復(fù)雜性參數(shù)來預(yù)測該軟件所隱藏的缺陷總數(shù)；而動態(tài)模型則是基于軟件測試過程中所獲得的失效時序數(shù)據(jù)，借助數(shù)理統(tǒng)計的方法來預(yù)測下一次軟件失效的發(fā)生時間[1-3]。由于軟件失效時序數(shù)據(jù)較為容易獲取，故動態(tài)模型在實際應(yīng)用中得到了更為廣泛的應(yīng)用。

目前，軟件可靠性的動態(tài)模型按其使用的建模方法劃分，又可分為統(tǒng)計分析方法和時序數(shù)據(jù)辨識方法兩大類[4-5]。其中，統(tǒng)計分析方法是在假設(shè)某些條件成立的情況下，應(yīng)用特定的函數(shù)分布來描述軟件失效時間的發(fā)生過程。以基于非齊次泊松過程（non-homogeneous poisson process， NHPP）的預(yù)測方法為例，由于該類方法具有預(yù)測精度高且結(jié)構(gòu)簡單的優(yōu)點，故其成為軟件可靠性的經(jīng)典統(tǒng)計分析方法[6-8]。相對地，時序數(shù)據(jù)辨識方法則無需指定任何先決條件的假設(shè)，而是利用軟件失效時序數(shù)據(jù)的前后相依關(guān)系，直接將時序數(shù)據(jù)辨識方法應(yīng)用于建模研究中。例如，馬颯颯等通過對軟件失效時序數(shù)據(jù)設(shè)計提出多尺度分解，并對分解后所得到的不同數(shù)據(jù)成分進行單獨的建模，進而得到了一種適應(yīng)性較好的軟件可靠性預(yù)測模型[9]；賈治宇等基于非平穩(wěn)時序數(shù)據(jù)辨識方法，運用自回歸積分滑動平均模型 （auto-regressive integrated moving average model， ARIMA）對軟件失效時序數(shù)據(jù)進行建模，從而得到了一種簡捷易用的軟件可靠性預(yù)測模型[10]。此外，由于時序數(shù)據(jù)辨識方法在建模過程中能較好地關(guān)注了數(shù)據(jù)的動態(tài)特性，故在辨識精度上較統(tǒng)計分析方法更具有優(yōu)勢。

在實際應(yīng)用中，用戶往往需要預(yù)測下一次、甚至后續(xù)多次的軟件失效的發(fā)生時間，即需要進行多步預(yù)測。據(jù)此，本文擬基于分段的灰色預(yù)測模型，設(shè)計實現(xiàn)一種具有誤差補償機制的軟件失效序列的多步預(yù)測算法，并在軟件可靠性評測領(lǐng)域的公開數(shù)據(jù)集中驗證算法的正確性和有效性。

1問題描述

軟件失效時序數(shù)據(jù)是指軟件系統(tǒng)在規(guī)定的環(huán)境中其各次無失效運行的持續(xù)時間，以數(shù)學(xué)的形式進行描述，有：Y=Yt， t∈N+（1）其中，Yt為一隨機變量，用于記錄軟件的各次無失效運行的持續(xù)時間，t為正整數(shù)。

基于一定的樣本數(shù)量n，便可以通過最小二乘或極大似然等方法估算出式（3）中的各有關(guān)待定參數(shù)，在此基礎(chǔ)上，令t=n+1，n+2，…，并代入式（3）和式（2）進行計算，便可以預(yù)測出該軟件系統(tǒng)的下一次及后續(xù)多次的無失效運行的持續(xù)時間。然而，隨著預(yù)測步數(shù)的增加，上述預(yù)測模型的預(yù)測結(jié)果將嚴重地偏離真實值，究其原因有：式（3）中的各有關(guān)待定參數(shù)雖然能使已有樣本的擬合誤差為最小值，但過多的外延預(yù)測造成了預(yù)測精度無法保證；另一方面，隨機噪聲項的估計值從第二步開始也引用了部分的預(yù)測值，此時，固有的誤差累積效應(yīng)也加劇了整體預(yù)測性能迅速變差。

2灰色分段擬合及多步預(yù)測算法的設(shè)計

針對上述問題，本文擬設(shè)計一種具有誤差補償機制的軟件失效時序數(shù)據(jù)的多步預(yù)測算法。算法的主要思想是，基于灰色理論的GM（1，1）模型為軟件失效時序數(shù)據(jù)Yt建立合適的分段擬合模型，并對末段子序列的擬合誤差施行正交多項式函數(shù)的預(yù)測和補償，在此基礎(chǔ)上，對軟件失效發(fā)生時間進行多步預(yù)測。

2.1基于GM（1，1）模型的時序數(shù)據(jù)的分段擬合endprint

2.2基于正交多項式的擬合誤差的補償

如前所述，基于GM（1，1）模型將可以把軟件失效時序數(shù)據(jù)劃分為數(shù)段子序列，易知，對后續(xù)的軟件失效發(fā)生時間的預(yù)測應(yīng)在末段子序列中設(shè)計展開。為進一步提高預(yù)測精度，這里將應(yīng)用正交多項式函數(shù)來估算末段子序列其GM（1，1）模型的擬合殘差，在此基礎(chǔ)上，對原GM（1，1）模型進行補償，進而構(gòu)建具有誤差補償機制的組合預(yù)測模型。

若軟件失效時序數(shù)據(jù)被劃分為m段子序列，令末段子序列（設(shè)該子序列的長度為v）其GM（1，1）模型的擬合殘差序列為em，則有：emt=ymt-y^mt t=1， 2， …， v（12）由于在高次多項式的曲線擬合過程中，往往會遇到病態(tài)方程組的求解問題，據(jù)此，這里將基于正交多項式對上述的殘差序列emt進行擬合。

2.3算法的設(shè)計

研究至此， 可設(shè)計得到如下的軟件失效時序數(shù)據(jù)的多步預(yù)測算法。算法的步驟內(nèi)容表述如下。

算法名稱：軟件失效時序數(shù)據(jù)的多步預(yù)測算法

輸入：長度為n的時序數(shù)據(jù)Yt，平均絕對百分誤差MAPE的閾值ε，各分段子序列的最小樣本長度Δ，預(yù)測步數(shù)step；

輸出：軟件失效序列的各step步的預(yù)測值。

步驟1從Yt的最左端選取Δ個右鄰樣本數(shù)據(jù)構(gòu)成Ysubt子序列，p=Δ；

步驟2利用式（6）對Ysubt進行一次累加生成處理得到y(tǒng)（1）subt，將y（1）subt代入式（9）求出待估參數(shù)a，b，將a，b代入式（5）得到y(tǒng)^（1）subt，利用式（10）對y^（1）subt進行一次逆累加生成處理得到y(tǒng)^subt；

步驟3利用式（11）計算y^subt的平均絕對百分誤差MAPE，若MAPE≤ε成立，轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟5；

步驟4P=P+1，若P≤n，向Ysubt中添加一個右鄰樣本數(shù)據(jù)，轉(zhuǎn)步驟2；否則，轉(zhuǎn)步驟6；

步驟5保存分界點P并清空Ysubt， p=p+Δ，若P≤n，以P為起點選取Δ個右鄰樣本數(shù)據(jù)構(gòu)成新的Ysubt子序列，轉(zhuǎn)步驟2；否則，轉(zhuǎn)步驟6；

步驟6以新近的P值為分界點，輸出末段軟件失效子序列ymt，基于式（15）～（16）的正交多項式迭代法計算ymt的殘差序列emt的估計值，并得到e^mt；

步驟7用補償后的組合預(yù)測模型（ymt+e^mt）輸出step個后續(xù)的軟件失效的發(fā)生時間，算法結(jié)束。

3實驗及結(jié)果分析

為了驗證本文算法的正確性及有效性，這里將選取國際知名軟件可靠性工程學(xué)者 Lyu發(fā)布的失效數(shù)據(jù)集SYS2.DAT為基礎(chǔ)來參與研發(fā)相關(guān)的多步預(yù)測實驗。實驗在PC機上設(shè)計發(fā)生，其硬件配置為：Intel 酷睿i5 4570四核CPU、Kingmax DDR3 16 GB RAM、Western Digital 500 G Hard Disk；操作系統(tǒng)與開發(fā)環(huán)境為，Microsoft Windows 10、Microsoft Visual Studio 2010集成開發(fā)環(huán)境中的C++。在實驗過程中，著重圍繞現(xiàn)有算法與本文算法在多步預(yù)測時的辨識誤差和計算開銷等性能指標(biāo)，并對相關(guān)結(jié)果提供了詳盡的討論與分析。

3.1實驗過程與方法

失效數(shù)據(jù)集SYS2.DAT中共有86個樣本序列，在實驗過程中，取失效數(shù)據(jù)集的前80個序列進行建模，并用建模所得的預(yù)測模型對后續(xù)的六個序列進行預(yù)測。實驗中需要進行對比的算法有：文獻[9]算法、文獻[10]算法及本文算法。

從圖1的擬合誤差曲線可知，在對已知樣本序列的建模過程中，文獻[9]算法的擬合精度是最高的，本文算法次之，而文獻[10]算法則位列第三，上述各種算法的平均絕對百分誤差MAPE均在10%以內(nèi)，故都屬于高精度擬合。而從圖2的多步預(yù)測誤差曲線易知，上述各種算法對第一步的預(yù)測精度是基本相同的，但從預(yù)測的第二步起，文獻[9]和文獻[10]算法的預(yù)測精度均出現(xiàn)了明顯的振蕩，且振蕩現(xiàn)象隨著預(yù)測步數(shù)的增加而加劇，當(dāng)中，又以文獻[10]算法的振蕩現(xiàn)象更為顯著；與之形成對比的是，本文算法其多步預(yù)測的誤差曲線僅在零值上做非常微弱（MAPE≤9.46%）的波動。事實上，文獻[9]和文獻[10]算法在建模過程中，各自得到的預(yù)測模型只保證了在已知樣本序列范圍內(nèi)其擬合誤差是最小的，但沒有對外延預(yù)測進行任何的處理；而本文算法首先基于某一精度的條件下，通過灰色GM（1，1）模型對已有樣本序列進行分段擬合，目的就是避免預(yù)測模型出現(xiàn)數(shù)據(jù)飽和的情況，在此基礎(chǔ)上，引入正交多項式對末段GM（1，1）模型的擬合誤差進行估計和補償，這樣，補償后的預(yù)測模型對外延預(yù)測的誤差趨勢便能及時加以修正，從而使得本文算法的多步預(yù)測能力具有一定的魯棒性。

算法類型計算耗時/ms建立預(yù)測模型的耗時多步預(yù)測的平均耗時本文算法188.745.98文獻[9]算法367.569.32文獻[10]算法102.333.15在實驗過程中，文獻[9]算法的建模流程是最為復(fù)雜的，該算法首先是引用小波方法對已有序列來進行多尺度分解，然后分別用AR模型和RBF神經(jīng)網(wǎng)絡(luò)對分解出的各種數(shù)據(jù)進行參數(shù)估計，所以其計算耗時遠多于參加對比試驗的其他兩種算法。對于本文算法而言，其計算用時則主要是消耗在灰色子序列的劃分過程中，（1-AGO）、矩陣求逆及（1-IAGO）等運算過程占用了本文算法較多的計算時間。相對地，文獻[10]算法在經(jīng)過若干次差分運算后，直接對近似的平穩(wěn)時序數(shù)據(jù)進行自回歸滑動平均模型（auto-regressive moving average model， ARMA） 的參數(shù)估計，故其花費的計算耗時是最小的。此外，表2中的多步預(yù)測的平均耗時是指，進行1～6步預(yù)測時所花費計算時間的平均值，根據(jù)各種算法所得的預(yù)測模型其復(fù)雜程度的不同，這里，多步預(yù)測的平均耗時與建立預(yù)測模型的耗時有著正比例的關(guān)系。endprint

綜上所述，本文算法在花費少量的額外計算耗時后，即已獲得了良好的多步預(yù)測能力，據(jù)此可證，本文算法是正確和有效的。

4結(jié)束語

對于某一預(yù)測模型而言，多步預(yù)測的魯棒性能表征了該模型是否具有良好的外延預(yù)測能力。本次研究提出了一種改進的魯棒多步預(yù)測算法，改進算法的有效性在權(quán)威的軟件失效數(shù)據(jù)集中得到了驗證。后續(xù)面臨的主要工作有，提升現(xiàn)有的灰色系統(tǒng)GM（1，1）模型的擬合精度，同時，也需要探討更為高效的矩陣快速求逆方法，以便進一步提升算法的預(yù)測精度和計算效能。

參考文獻：

[1] 徐仁佐，謝曼，鄭人杰. 軟件可靠性模型及應(yīng)用[M]. 北京：清華大學(xué)出版社，1994.

[2] 趙靖. 軟件可靠性模型及應(yīng)用[M]. 哈爾濱： 哈爾濱工程大學(xué)出版社，2007.

[3] 郭平. 軟件可靠性工程中的計算智能方法[M]. 北京： 科學(xué)出版社，2012.

[4] 樓俊鋼，江建慧，帥春燕，等. 軟件可靠性模型研究進展[J]. 計算機科學(xué)，2010，37（9）：13-19，27.

[5] 耿技，聶鵬，秦志光. 軟件可靠性模型現(xiàn)狀與研究[J]. 電子科技大學(xué)學(xué)報，2013，42（4）：565-570.

[6] 張寧紅. NHPP類軟件可靠性增長模型的統(tǒng)一及其性能分析[J]. 系統(tǒng)工程與電子技術(shù)，1999，21（8）：74-77.

[7] 何焱，張來順，劉偉，等. 一種基于離散時間的NHPP軟件可靠性增長模型[J]. 計算機應(yīng)用研究，2011，28（7）：2569-2572.

[8]ZHANG Jie，LU Yang， YANG Shu， et al. NHPPbased software reliability model considering testing effort and multivariate fault detection rate[J]. Journal of Systems Engineering and Electronics， 2016，27（1）： 260-270.

[9] 馬颯颯，王光平，趙守偉. 基于時間序列的軟件可靠性預(yù)測模型研究[J]. 計算機工程與設(shè)計，2007，28（11）：2520-2523.

[10]賈治宇，康銳. 軟件可靠性預(yù)測的ARIMA方法研究[J]. 計算機工程與應(yīng)用，2008，44（35）：17-19.

[11]何書元. 應(yīng)用時間序列分析[M]. 北京： 北京大學(xué)出版社，2003.

[12]黃雄波. 多周期時序數(shù)據(jù)的傅氏級數(shù)擬合算法[J]. 計算機系統(tǒng)應(yīng)用，2015，24（7）：142-148.

[13]黃雄波. 基于自相關(guān)函數(shù)的非平穩(wěn)時序數(shù)據(jù)的辨識改進[J]. 微型機與應(yīng)用，2016，35（13）：10-14，18.

[14]劉思峰，楊英杰. 灰色系統(tǒng)研究進展（2004-2014）[J]. 南京航空航天大學(xué)學(xué)報，2015，47（1）：1-18.

[15]黨耀國，王俊杰，康文芳. 灰色預(yù)測技術(shù)研究進展綜述[J]. 上海電機學(xué)院學(xué)報，2015，18（1）：1-7，18.

[16]鄭咸義，姚仰新，雷秀仁，等. 應(yīng)用數(shù)值分析[M].廣州： 華南理工大學(xué)出版社，2008.

[17]李慶揚，關(guān)治，白峰彬.數(shù)值計算原理[M]. 北京： 清華大學(xué)出版社，2005.endprint