基于和聲搜索算法的軟件可靠性模型參數估計方法

周園園，錢 麗，李敬明

(1.安徽廣播電視大學省直分校 技術中心，安徽 合肥 230001；2.安徽新華學院 信息工程學院, 安徽 合肥 230088)

基于和聲搜索算法的軟件可靠性模型參數估計方法

周園園1，錢 麗2，李敬明2

(1.安徽廣播電視大學省直分校 技術中心，安徽 合肥 230001；2.安徽新華學院 信息工程學院, 安徽 合肥 230088)

針對軟件可靠性模型中參數估計不精確的問題，提出了一種基于和聲搜索算法的軟件可靠性模型參數估計方法.為了避免和聲搜索算法在求解參數時陷入局部最優解，對算法作了改進：在和聲記憶庫初始化時采用反向學習策略，提高了收斂速度；利用全局信息產生新解，提高了全局搜索能力.使用該方法對5組數據的兩個軟件可靠性模型的參數進行了估計，實驗結果表明，本算法應用于參數估計具有可行性和有效性，在精度和算法的收斂性上，明顯優于其他智能算法.

軟件可靠性模型；和聲搜索算法；參數估計

隨著軟件規模日益擴大，人們對軟件可靠性也越來越重視.軟件可靠性模型就是采用統計知識對軟件實際使用中收集的或軟件測試中的失效數據進行分析，找出規律，建立一個參數模型，然后在軟件可靠性數據的基礎上對模型中的未知參數進行估計，最后用此模型對軟件的可靠性進行定量估計或評價，從而開發出可靠的軟件[1]. 參數估計是軟件可靠性預測中最重要的一部分，參數估值結果的準確性決定了軟件產品的可靠性評估結果的準確性.但是目前的軟件可靠性模型大部分是非線性函數模型，其參數較難以估計.估計模型中參數的方法有很多，傳統的有極大似然法、最小二乘法和貝葉斯法. 目前較新的參數估計方法是采用智能優化算法. 馬敏書等利用遺傳算法求解可靠性模型中的參數[2]，但該方法結構較復雜，精確度很低；張克涵等利用粒子群算法求解可靠性模型的參數[3]，該方法計算的結果精確度較高，但搜索范圍大，收斂速度慢；鄭長友等利用蟻群算法求解可靠性模型的參數[4]，該算法雖收斂速度較快，但精確度有待提高.因此，需要尋求一種更好的算法. 和聲搜索(HarmonySearch，HS)算法是一種新的智能優化算法，該算法簡單通用，易于與其他算法混合，構造出具有更優性能的算法從而更好地解決函數優化問題.有關研究表明,在解決多維函數優化問題上HS算法比遺傳算法、模擬退火算法等具有更好的優化性能[5-8]. 因此，將該算法應用到軟件可靠性模型的參數估計中是可行的.

1 軟件可靠性模型

目前軟件可靠性模型有100多種，其中使用最多的是GO模型和MO模型，這兩個模型在預測的可靠性方面比較好.GO模型屬于指數軟件可靠性模型，MO模型屬于非齊次泊松過程模型，它們代表了大部分的軟件可靠性模型.本文研究的是GO模型和MO模型，它們的均值函數形式如下[9]：

GO模型：

μ(t)=a(1-e-bt)

(1)

MO模型：

μ(t)=ln(λ0θt+1)/θ

(2)

式中：μ(t)表示截止到t時刻檢測到錯誤數的期望值；t表示錯誤發現的時刻；a,b,λ0,θ為未知參數.

2 和聲搜索算法

2.1 標準和聲搜索算法(HS)

HS算法模擬音樂演奏家創作的過程，在創作過程中音樂家不斷地調整所奏樂器的音調，使整個演奏過程達到最佳狀態.HS算法中將樂器、樂器的音調、和聲、和聲效果評價與組合優化問題中的決策變量、決策變量的值、決策變量組成的解向量、目標函數的適應度值進行類比. 具體的算法步驟如下[8]：

(1)初始化算法參數

初始化算法參數包括：決策變量的個數N；和聲記憶庫的大小HMS;各個決策變量的取值范圍[Li,Ui];和聲記憶庫考慮概率HMCR;音調微調概率PAR;音調微調帶寬BW;算法的迭代次數NI.

(2)初始化和聲記憶庫HM

隨機生成HMS個和聲x1，x2，…，xHMS存入和聲記憶庫HM作為優化問題的初始解.

和聲記憶庫中的每個音調(即決策變量)按照式(3)產生：

(3)

式中，i=1,2,…,HMS；j=1,2,…,N；Li和Ui分別是j分量值域的下界和上界；

(3)產生一個新的和聲

首先，考慮和聲記憶庫或者隨機產生音調，公式如(4)式：

(4)

(5)

(4)更新和聲記憶庫HM

(5)檢查算法終止條件

重復步驟(3)和步驟(4)，直到創作( 迭代) 次數達到NI為止.

2.2 改進的和聲搜索算法

針對標準HS算法在后期收斂速度較慢和容易陷入局部最優解的問題，本文對標準HS算法做了如下兩點改進：

(1)和聲記憶庫初始化的改進

反向學習策略已經被證明能產生高質量的初始解[10]，提高算法的收斂速度，而且已經被成功地應用到其他智能算法的解空間的初始化中.

為了提高初始解的質量，本算法不再按照標準的HS算法采用均勻分布的策略，而是采用均勻分布與反向學習相結合的策略對和聲記憶庫初始化. 和聲記憶庫中一半的解按照均勻分布策略產生如式(3)，剩余的一半解采用反向學習策略產生如式(6).

(6)

式中，k=HMS/2+1,…,HMS.

(2)新解產生的改進

為了提高算法的全局搜索能力，避免算法陷入局部最優解，在產生新解的步驟中，保留當前和聲記憶庫中的最優解，對標準HS算法中的式(5)做了改進，若新解來自于和聲記憶庫，有一半的概率是來自最優解，新解不再按照式(5)產生，而是按照式(7)產生：

(7)

式中，i=1,2,…,n；k=1,2,…,HMS,即將當前和聲記憶庫中最優解的第j維變量賦值給新解的第j維變量.

改進的HS算法流程與標準HS算法流程相同.

3 基于和聲搜索算法的軟件可靠性模型參數估計方法

3.1 算法流程

對兩個模型中參數估計就是如何確定式(1)中a和b的值，式(2)中λ0和θ的值，使得每個模型的均值函數曲線更接近于實測數據曲線.

目標函數的構造是利用HS算法估計軟件可靠性模型參數的關鍵，它是最優解的評價標準，借鑒文獻[3]，本文采用式(8)作為目標函數，即

(8)

式中:T表示測試終止時間；m(t)表示累計到t時刻實際測試出來的軟件失效數;μ(t)表示模型的均值函數;J表示模型估計的軟件失效數與實際測試出的軟件失效數之間的歐氏距離，其大小可以表示模型預測的精確度，J值越小，參數估計越準確，模型越精確.

利用HS算法估計參數時，首先預估每個式子中的未知參數的個數即HS算法中變量的個數，式(1)和(2)變量個數都是2；然后給出未知參數取值范圍即HS算法中變量的值域；最后將文獻[11]的實際數據集作為m(t)的數據，使用HS算法求解軟件可靠性模型的均值函數的未知參數.具體算法流程如圖1所示.

圖1 算法流程圖

3.2 仿真實驗

采用Matlab2013使用改進后的HS算法，對Musa數據集[11]中的SYS1、SYS2、CSR1、CSR2、SS3 5組數據進行實驗. 實驗中HS算法中參數設置為HMS=5,HMCR=0.95，PARmin= 0.01，PARmax=0.99，BWmin=0.000 001，BWmax=(Ui-Li)/20，NI=50 000. 算法獨立運行20次，取目標函數J的最小值所對應的參數.參數估計的精確度根據目標函數評價，目標函數值J越小，說明參數估計的精確度越高.

表1和表2給出了用5組數據估計兩個可靠性模型參數的實驗結果.結果表明了HS搜索算法應用于參數估計的可行性. 表3給出了粒子群(PSO)算法、蟻群算法和本文的HS算法參數擬合的結果.圖2～圖8則給出了兩種模型分別擬合5組數據的曲線.

表1 G-O模型參數估計結果

數據集模型參數估計值ab適應值JSYS1124．4664670．00005168．58356SYS294．1493390．00001911．8704995CSR1352．5592470．000077341．669559CSR2114．2036060．00006882．012696SS3455．0524430．000018144．179677

表2 M-O模型參數估計結果

數據集模型參數估計值λ0θ適應值JSYS10．010340．02270331．60092SYS20．002230．02010810．16799CSR10．0469470．009278406．2147CSR20．0119130．0253373．07945SS30．0085140．003068154．4498

表3 PSO、蟻群算法和HS算法參數擬合的結果

數據集G-O模型M-O模型PSO[3]蟻群算法[4]HS算法PSO[3]蟻群算法[4]HS算法SYS196．6076．2968．585034．0833．3231．6010SYS237．2230．9312．039930．0624．9710．1681CSR1354．10356．68341．6739420．68406．99406．2147CSR2421．8382．9982．012875．6175．3373．0795SS31270．31149．96144．3090276．40159．41154．4500

3.3 結果分析

(1)與PSO算法、蟻群算法的比較

由表1～表3和圖2～圖6可見, 本文提出的軟件可靠性模型參數估計方法效果比較好，沒有擬合不出來的情況，說明該算法對不同軟件可靠性模型的適應性也比較好.從表3中可以看出，本文的方法得出的精度明顯比PSO和蟻群算法的精度高.

圖2 SYS1數據的擬合結果

圖3 SYS2數據的擬合結果

圖4 CRS1數據的擬合結果

圖5 CRS2數據的擬合結果

圖6 SS3數據的擬合結果

(2)與其他HS方法的比較

圖7給出了HS、IHS和IGHS 3種算法以SYS1數據集為測試數據求解GO模型優化的收斂曲線(限于篇幅，未給出其他模型優化收斂曲線)，比較了3種算法的收斂速度，橫坐標表示迭代次數，每迭代1 000次保留一次最優值，縱坐標取最優值的以2為底的對數表示.從圖7可以看出，改進算法的初始解的質量較高，在前3 000次迭代曲線相差不大，表明3種算法都能較快收斂，在8 000次時本文算法已趨于收斂，12 000次后HS和IHS算法才趨于收斂，這表明本文算法的收斂速度比HS，IHS的更快，其中IHS收斂速度是最慢的，這表明僅僅按照線性的調整參數未必能改善HS的性能.

圖7 3種HS算法的收斂曲線

4 結束語

針對估計軟件可靠性模型中的參數不精確問題，提出一種改進的和聲搜索算法用于估計軟件可靠性模型參數.該算法采用反向學習策略初始化和聲記憶庫，并利用當前和聲記憶庫的最優解產生新解來改進算法. 使用該方法分別估計了Musa數據集中的5組數據的兩種軟件可靠性模型，通過實驗驗證了和聲搜索算法在參數估計應用中的可行性和有效性.通過與其他智能算法比較可知，該算法參數估計的精度高、收斂速度快，能適應不同的模型.

[1]陸民演. 軟件可靠性工程[M]. 北京: 國防工程出版社, 2011.

[2] 馬敏書, 張仲義, 呂永波. 利用遺傳算法進行軟件可靠性增長模型參數估計[J]. 中國安全科學學報, 2004, 14(7): 9-12.

[3] 張克涵, 李愛國, 宋保維. 基于 PSO 的軟件可靠性模型參數估計方法[J]. 計算機工程與應用, 2008, 44(11): 47-49.

[4] 鄭長友, 劉曉明, 黃松. 基于蟻群算法的軟件可靠性模型參數估計方法[J]. 計算機應用, 2012, 32(04): 1 147-1 151.

[5] TUO S H, ZHANG J Y. A harmony search algorithm for high dimensional multimodal optimization problems[J]. Digital Signal Processing, 2015, 46 : 151-163 .

[6] EHSAN V, SAEED T, SHAHRAM M. An intelligent global harmony search approach to continuous optimization problems[J]. Applied Mathematics and Computation, 2014, 232 : 670-684.

[7] ASHRAFI S M, DARIANE A B. Performance evaluation of an improved harmony search algorithm for numerical optimization: Melody Search (MS)[J]. Engineering Applications of Artificial Intelligence, 2013, 26(4): 1 301-1 321.

[8] 雍龍泉.和聲搜索算法研究進展[J]. 計算機系統應用, 2011, 20(7): 244-248.

[9] HOANG P. 系統軟件可靠性[M].李璐煒,譯.北京:國防工程出版社,2014:203-205.

[10] WANG H, WU Z, RAHNAMAYAN S, et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181(20): 4 699-4 714.

[11] LYU M R.Handbook of software reliability engineering[M/OL].New York:IEEE.Computer Society Press,1996[2016-05-13]. http://www.cse.cuhk.edu.hk/～lyu/book/reliability/data.htm.

(編輯：郝秀清)

Estimatingparametersofsoftwarereliabilitymodelbyharmonysearchalgorithm

ZHOUYuan-yuan1,QIANLi2,LIJing-ming2

(1.TechnologyCenter,AnhuiShengzhiRadioandTVUniversity,Hefei230001,China;2.SchoolofInformationEngineering,AnhuiXinhuaUniversity,Hefei230088,China)

Astotheproblemofinaccurateestimationoftheparametersofsoftwarereliabilitymodel,amethodofestimatingparametersofsoftwarereliabilitymodelbasedontheharmonysearchalgorithmisproposedinthispaper.Inordertoavoidtheharmonysearchalgorithmforsolvingtheparametersintoalocaloptimalsolution,twoimprovementsaremade.Firstly,theopposition-basedlearningisusedtoinitializedharmonymemorytoimprovethespeedofconvergence.Secondly,globalinformationisusedtogeneratethenewtoimprovetheglobalsearchability.Theparametersoftwosoftwarereliabilitymodelsofsevendatasetswereestimatedbytheproposedmethod.Theexperimentalresultsshowthatthealgorithmisfeasibilityandeffectivenessinparameterestimationandissuperiortoothermeta-heuristicalgorithmsintheconvergenceandaccuracy.

softwarereliabilitymodel;harmonysearchalgorithm;parameterestimation

2016-05-18

安徽省教育廳自然科學基金重點項目(KJ2014A100,KJ2016A308)

周園園, 女,yuanyzhou@qq.com

1672-6197(2017)02-0044-05

TP301.6

A