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

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

（1.江蘇科技大學(xué)電子信息學(xué)院 鎮(zhèn)江 212003）（2.上海船舶研究設(shè)計院 上海 201203）（3.江蘇科技大學(xué)計算機學(xué)院 鎮(zhèn)江 212003）

1 引言

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

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

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

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

2 基本概念

2.1 軟件可靠性及模型

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

軟件系統(tǒng)中累積失效數(shù)的估計函數(shù)形式如下：

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

2.2 狼群算法的基本原理

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

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

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

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

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

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

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

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

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

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

式中，S為步長因子。

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

3 研究方法

文獻［13］中使用粒子群算法進行了軟件可靠性模型參數(shù)的估計研究。此方法是構(gòu)造一種適應(yīng)值函數(shù)，將參數(shù)估計的問題轉(zhuǎn)變?yōu)楹瘮?shù)優(yōu)化問題。構(gòu)造的適應(yīng)值函數(shù)如下：

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

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

3.1 適應(yīng)值函數(shù)的構(gòu)造

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

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

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

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

3.2 問題解的剔除

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

3.3 先驗知識

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

4 算法仿真結(jié)果

4.1 參數(shù)估計

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

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

表1 狼群算法的估計結(jié)果

表2 文獻［7］的估計結(jié)果

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

表3 兩種算法誤差率對比

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

4.2 估計與預(yù)測

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

表4 狼群算法的估計結(jié)果

表5 文獻［7］方法的估計結(jié)果

表6 兩種算法誤差率對比

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

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

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

圖1 SYS1數(shù)據(jù)集后一半發(fā)生失效時刻

圖2 SS3數(shù)據(jù)集后一半發(fā)生失效時刻

圖3 CSR1數(shù)據(jù)集后一半發(fā)生失效時刻

圖4 CSR2數(shù)據(jù)集后一半發(fā)生失效時刻

5 結(jié)語

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