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

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

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

1 引言

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

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

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

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

2 基本概念

2.1 軟件可靠性及模型

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

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

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

2.2 狼群算法的基本原理

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

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

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

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

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

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

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

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

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

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

式中，S為步長(zhǎng)因子。

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

3 研究方法

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

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

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

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

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

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

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

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

3.2 問(wèn)題解的剔除

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

3.3 先驗(yàn)知識(shí)

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

4 算法仿真結(jié)果

4.1 參數(shù)估計(jì)

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

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

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

表2 文獻(xiàn)［7］的估計(jì)結(jié)果

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

表3 兩種算法誤差率對(duì)比

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

4.2 估計(jì)與預(yù)測(cè)

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

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

表5 文獻(xiàn)［7］方法的估計(jì)結(jié)果

表6 兩種算法誤差率對(duì)比

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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