軟件失效時序數據的灰色擬合及多步預測算法

摘要： 關鍵詞： 中圖分類號： 文獻標志碼： 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引言

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

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

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

1問題描述

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

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

2灰色分段擬合及多步預測算法的設計

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

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

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

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

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

2.3算法的設計

研究至此， 可設計得到如下的軟件失效時序數據的多步預測算法。算法的步驟內容表述如下。

算法名稱：軟件失效時序數據的多步預測算法

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

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

步驟1從Yt的最左端選取Δ個右鄰樣本數據構成Ysubt子序列，p=Δ；

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

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

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

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

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

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

3實驗及結果分析

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

3.1實驗過程與方法

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

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

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

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

4結束語

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

參考文獻：

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

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

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

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

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

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

[7] 何焱，張來順，劉偉，等. 一種基于離散時間的NHPP軟件可靠性增長模型[J]. 計算機應用研究，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] 馬颯颯，王光平，趙守偉. 基于時間序列的軟件可靠性預測模型研究[J]. 計算機工程與設計，2007，28（11）：2520-2523.

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

[11]何書元. 應用時間序列分析[M]. 北京： 北京大學出版社，2003.

[12]黃雄波. 多周期時序數據的傅氏級數擬合算法[J]. 計算機系統應用，2015，24（7）：142-148.

[13]黃雄波. 基于自相關函數的非平穩時序數據的辨識改進[J]. 微型機與應用，2016，35（13）：10-14，18.

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

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

[16]鄭咸義，姚仰新，雷秀仁，等. 應用數值分析[M].廣州： 華南理工大學出版社，2008.

[17]李慶揚，關治，白峰彬.數值計算原理[M]. 北京： 清華大學出版社，2005.endprint