基于狼群算法的軟件可靠性模型參數估計研究*

于苗苗 朱 兵 李 震 王東升 魏海峰

（1.江蘇科技大學電子信息學院 鎮江 212003）（2.上海船舶研究設計院 上海 201203）（3.江蘇科技大學計算機學院 鎮江 212003）

1 引言

軟件可靠性是評判軟件質量的重要特征之一，也是評價軟件質量的主要定量標準，具有重要的研究意義，因此越來越受到研究者的重視。迄今為止，研究者們已經發表了近百種軟件可靠性模型，比如G-O模型［1］、M-O模型［2］和J-M模型［3］等。然而這些模型基本上都是非線性函數模型，很難直接估計它們的參數，所以一種新的思路是將智能優化算法應用到模型參數的估計中。

群體智能算法在電力系統、航空航天、無線傳感網絡等領域得到了廣泛的研究與應用，但是在可靠性方面的研究相對較少。Harish Garg等［4］提出將PSO算法用于工業系統的可靠性分析中，通過PSO算法來優化系統中的關鍵參數，從而提高工業系統的性能及可靠性；Tarun Kumar Sharma等［5］提出將一種改進的ABC算法用于軟件可靠性增長模型的參數估計中，改進后的算法具有雙向搜索的能力，這使得算法的全局探索能力更強，性能更好，能更準確地預測模型的參數；Alaa Sheta［6］提出將粒子群算法用于軟件可靠性增長模型的問題中，通過PSO算法優化模型的參數，從而更好地通過模型來預測軟件失效數。WPA作為群體智能優化算法的一種，是由吳虎勝等學者系統地提出［7］。該算法具有較好的全局收斂性和較高的精度值，種群的多樣性較高。狼群算法也是一種典型的群體智能算法，目前對于狼群在一些領域的應用也是較多，比如圖像分割、無人機等［8～12］。

張克涵等［13］使用粒子群算法進行軟件可靠性模型參數的估計，存在的缺陷是算法搜索范圍大、收斂速度較慢，并且求解的精度不高；王正初等［14］提出了將粒子群算法用于求解復雜系統可靠性優化問題，并通過2個實例驗證了該算法的可行性和有效性。

鑒于狼群算法具有較好的全局尋優能力，收斂速度快。本文提出一種基于狼群算法（Wolf Pack Algorithm，WPA）的軟件可靠性模型參數估計的方法。

2 基本概念

2.1 軟件可靠性及模型

軟件可靠性，是在規定的條件下和時間內，軟件不引起系統發生失效的概率。IEEE計算機學會對軟件可靠性作出如下的定義［15］：1）在規定的條件下，在規定的時間內，軟件不引起系統失效的概率；2）在規定的時間周期內，在所述條件下，程序執行所要求的功能的能力。文章選擇軟件可靠模型中具有代表性的G-O模型作為研究對象，對其參數進行估計。

軟件系統中累積失效數的估計函數形式如下：

其中：m（t）代表到時刻t為止的累積失效數的期望函數；a代表測試結束后軟件期望被檢測出來的失效總數；b表示剩余失效被發現的概率，是一個比例常數，范圍為（0，1）。

2.2 狼群算法的基本原理

狼群算法意在模擬狼群的捕獵行為處理函數優化問題，將狼群分為三類：頭狼、探狼和猛狼。將狼群的整個捕獵活動抽象為3種智能行為（游走行為、召喚行為、圍攻行為）以及“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制。

1）頭狼生成準則：從待尋優空間中的某一初始獵物群開始，其中具有最佳適應度值的狼作為頭狼。

2）游走行為：選取除頭狼外最佳的S_num匹人工狼作為探狼執行游走行為S_num隨機取[(α+1)，n/α]之間的整數，n為狼群中人工狼群的總數，α為探狼比例因子。首先計算探狼i當前位置的獵物氣味濃度Yi，如果Y i

探狼i一直游走行為直至某一匹探狼所感知的氣味濃度Yi

其中，對于每一匹探狼的獵物搜索方式是存在差異的，即h的取值是不同的，在實際情況中取[hmin，hmax]之間的隨機整數。

3）召喚行為：頭狼發起嚎叫進行召喚行為，通知周圍M_num匹猛狼迅速向頭狼靠攏，其中M_num=n-S_num-1；猛狼聽到嚎叫，都以相對較長的奔襲步長快速地向頭狼的位置逼近（此時的步長稱為奔襲步長st ep b）。則猛狼j經歷第k+1次迭代次數時，在第d維空間中的位置為

在奔襲的過程中，如果猛狼j感知到的氣味濃度Y jY lea d，則猛狼j繼續進行奔襲行為，當與頭狼s之間的距離d js小于判定距離dnear時，轉為圍攻行為。判定距離d ne ar通過估算得到：

其中：D為待尋優變量空間的維數；maxd和mind是待尋優的第d維空間的最大值和最小值。w為距離判定因子，其不同取值將影響算法的收斂速度，當w增大時，會加速算法收斂，但是如果w過大，就會使得人工狼很難進入圍攻行為，缺乏對獵物的精細搜索。

4）圍攻行為：狼群根據式（5）進行圍攻行為。對于第k代狼群，設獵物在第i維空間中的位置為，可用如下公式表示狼群的圍攻行為

式中，λ為［-1，1］間分布的隨機數；為人工狼i在第d維空間中采取圍攻行為時的攻擊步長。

式中，S為步長因子。

5）“強者生存”的狼群更新機制。剔除目標函數值最差的R匹人工狼，并且同時隨機產生R匹新的人工狼。R的取值為之間的隨機整數，β是群體更新比例因子。

3 研究方法

文獻［13］中使用粒子群算法進行了軟件可靠性模型參數的估計研究。此方法是構造一種適應值函數，將參數估計的問題轉變為函數優化問題。構造的適應值函數如下：

式（7）中：J表示實際測出的軟件失效數與通過模型估計出的軟件失效數之間的歐式距離，m（t）表示在測試時間段［0，t）中實際發現的累積失效數；m（t）代表在測試時間段［0，t）中用模型估計出來的累積失效數；t表示失效發生時刻；T表示終止測試的時間。

本文使用軟件可靠性模型參數的極大似然估計公式來構造新的適應值函數，并且在算法執行過程中先剔除掉那些明顯錯誤的解，再根據先驗知識朝著更準確解的方向搜索。

3.1 適應值函數的構造

文章使用極大似然法對G-O模型進行估計，a、b的結果計算公式如下所示：

上式中：n表示已知的失效數；t i為第i個失效發生的時刻；i=1，2，3，…n。

文章根據G-O模型參數a、b的極大似然估計公式構造一種新的適應值函數，具體做法是將式（8）中的第一項代入到第二項中并進行數學變換，構造成一個只與參數b相關的式子，如下所示：

f即為新的適應值函數，公式中除了b以外其余的參數均為已知，f越小說明參數b估計的效果越好。通過WPA算法迭代搜索，當達到算法停止準則后輸出最優的參數b，然后再代入參數a的極大似然估計公式中求出對應的最優的參數a。

3.2 問題解的剔除

在實現G-O模型的算法中，由于參數b是（0，1）范圍內的隨機數，在算法的迭代搜索過程中可能會出現一些問題解。為了得到較好的值，需要將實驗中的問題解剔除。通過多次的實驗運行可以發現，參數b的精度必須保持在1e-5內，因為當參數b的精度達到1e-6或者更高時，就會出現問題解。因此在程序中，對參數b加入限制條件，從而達到剔除問題解，使算法在較好解的范圍內繼續搜索的目的。

3.3 先驗知識

根據式（8）可知參數a和b是反向的關系：b大則a小，b小則a大。如果根據第一次運行得到的結果b求出的累積失效數a大于已知失效數，希望a的值變小，那么由先驗知識可知參數b的值就要偏大，繼續運行程序找出較大的b；如果根據第一次運行得到的結果b求出的參數a小于已知失效數，希望a的值變大，那么由先驗知識可知參數b的值就要偏小，繼續運行程序找出較小的b。由此，作為下一輪算法的迭代的開始，可以求出更加準確的參數。

4 算法仿真結果

4.1 參數估計

本文使用實際工業項目中得到的5組軟件失效間隔時間數據集SYS1、SS3、CSR1、CSR2、CSR3，數據下載地址為http：//www.cse.cuhk.edu.hk/lyu/book/reliability/data.html［13］。文章將文獻［13］中的參數估計方法與本文提出的基于狼群算法的軟件可靠性模型參數估計方法的實驗結果進行了對比。

WPA算法各參數設置如下：人工狼的總數n=50，距離判定因子w=100，最大游走限制次數Tmax=30，探狼比例因子α=4，更新比例因子β=10，步長因子S=1000；，適應值精度要求k≤1e（-5），每個狼群的位置即GO模型的參數b，b是初始化為（0，1）之間的隨機數。算法初始運行20次，按照第3章節中的原則取最好的結果作為初始值。實驗結果的對比見表1和表2所示。

表1 狼群算法的估計結果

表2 文獻［7］的估計結果

使用本文的算法和文獻中的算法的執行結果與實際結果的誤差率對比如表3所示。

表3 兩種算法誤差率對比

已知SYS1、SS3、CSR1、CSR2、CSR3這5組數據集實際的累積失效數n分別為136、278、397、129、104。由表1、表2和表3可以看出用本文提出的狼群算法估計所得的累積失效數a相較于文獻［13］而言，估計出的準確度是更高的，與實際結果n的誤差均在2%內，而文獻［7］估計出的誤差率較大，由此有力地說明了文章提出的方法具有更好的準確性。

4.2 估計與預測

在這一小節中，我們主要的研究內容是將參數估計和模型預測結合起來，針對兩種方法，分別用5組數據集的前一半失效來估計GO模型的參數，然后將估計出來的參數代入到GO模型的函數表達式中，對后一半失效的發生時刻進行預測。算法初始運行20次，按照第3章節中的原則取最好的結果作為初始值，參數估計的結果如表4、表5所示。

表4 狼群算法的估計結果

表5 文獻［7］方法的估計結果

表6 兩種算法誤差率對比

觀察表4、表5和表6，可以發現在只用數據集的前一半數據做參數估計時，本文方法估計出的結果與實際值的誤差依舊是很小的，但是使用文獻［13］方法估計出的結果與實際值之間的誤差比較大。這說明在實際的工業項目中，在只有少部分失效數據的情況下，用本文提出的方法可以更加合理的進行估計與預測。

將表4和表5中的參數分別帶回到公式（1）中，根據公式分別對5組數據集后一半失效的發生時刻進行預測，并將得到的預測結果曲線與實際曲線作對比，如圖1～5所示。

從圖1～5觀察可以發現，使用本文提出的狼群算法預測的曲線與實際曲線相比，盡管有一定的誤差，但大致上走勢是一致的；并且曲線是呈指數分布，曲線的斜率不斷變大，表明軟件失效發生的時間間隔不斷增大，說明軟件的可靠性逐漸在得到改善，這是符合實際軟件測試中可靠性隨著失效的發現及修改而得到提高的情況。由此可知，根據本文提出的狼群算法用一半失效數據做模型參數估計，再通過模型來預測后面失效發生的時刻在實際中是比較可行的并且是較為準確的。

圖1 SYS1數據集后一半發生失效時刻

圖2 SS3數據集后一半發生失效時刻

圖3 CSR1數據集后一半發生失效時刻

圖4 CSR2數據集后一半發生失效時刻

5 結語

軟件可靠性模型參數估計的效果會直接影響模型預測的準確性，所以具有重要的研究意義。文章提出了一種基于WPA的軟件可靠性模型參數估計方法，利用極大似然估計方法構造了新的適應值函數，在算法運行過程中增加了問題解的剔除，同時優化了參數的搜索方向。最終的實驗數據和結果比對表明，文章提出的方法可以很好地提高軟件可靠性模型參數估計和預測的準確性。