周園園，錢 麗，李敬明

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

基于和聲搜索算法的軟件可靠性模型參數(shù)估計(jì)方法

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

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

針對(duì)軟件可靠性模型中參數(shù)估計(jì)不精確的問題，提出了一種基于和聲搜索算法的軟件可靠性模型參數(shù)估計(jì)方法.為了避免和聲搜索算法在求解參數(shù)時(shí)陷入局部最優(yōu)解，對(duì)算法作了改進(jìn)：在和聲記憶庫初始化時(shí)采用反向?qū)W習(xí)策略，提高了收斂速度；利用全局信息產(chǎn)生新解，提高了全局搜索能力.使用該方法對(duì)5組數(shù)據(jù)的兩個(gè)軟件可靠性模型的參數(shù)進(jìn)行了估計(jì)，實(shí)驗(yàn)結(jié)果表明，本算法應(yīng)用于參數(shù)估計(jì)具有可行性和有效性，在精度和算法的收斂性上，明顯優(yōu)于其他智能算法.

軟件可靠性模型；和聲搜索算法；參數(shù)估計(jì)

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

1 軟件可靠性模型

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

GO模型：

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

(1)

MO模型：

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

(2)

式中：μ(t)表示截止到t時(shí)刻檢測(cè)到錯(cuò)誤數(shù)的期望值；t表示錯(cuò)誤發(fā)現(xiàn)的時(shí)刻；a,b,λ0,θ為未知參數(shù).

2 和聲搜索算法

2.1 標(biāo)準(zhǔn)和聲搜索算法(HS)

HS算法模擬音樂演奏家創(chuàng)作的過程，在創(chuàng)作過程中音樂家不斷地調(diào)整所奏樂器的音調(diào)，使整個(gè)演奏過程達(dá)到最佳狀態(tài).HS算法中將樂器、樂器的音調(diào)、和聲、和聲效果評(píng)價(jià)與組合優(yōu)化問題中的決策變量、決策變量的值、決策變量組成的解向量、目標(biāo)函數(shù)的適應(yīng)度值進(jìn)行類比. 具體的算法步驟如下[8]：

(1)初始化算法參數(shù)

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

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

隨機(jī)生成HMS個(gè)和聲x1，x2，…，xHMS存入和聲記憶庫HM作為優(yōu)化問題的初始解.

和聲記憶庫中的每個(gè)音調(diào)(即決策變量)按照式(3)產(chǎn)生：

(3)

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

(3)產(chǎn)生一個(gè)新的和聲

首先，考慮和聲記憶庫或者隨機(jī)產(chǎn)生音調(diào)，公式如(4)式：

(4)

(5)

(4)更新和聲記憶庫HM

(5)檢查算法終止條件

重復(fù)步驟(3)和步驟(4)，直到創(chuàng)作( 迭代) 次數(shù)達(dá)到NI為止.

2.2 改進(jìn)的和聲搜索算法

針對(duì)標(biāo)準(zhǔn)HS算法在后期收斂速度較慢和容易陷入局部最優(yōu)解的問題，本文對(duì)標(biāo)準(zhǔn)HS算法做了如下兩點(diǎn)改進(jìn)：

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

反向?qū)W習(xí)策略已經(jīng)被證明能產(chǎn)生高質(zhì)量的初始解[10]，提高算法的收斂速度，而且已經(jīng)被成功地應(yīng)用到其他智能算法的解空間的初始化中.

為了提高初始解的質(zhì)量，本算法不再按照標(biāo)準(zhǔn)的HS算法采用均勻分布的策略，而是采用均勻分布與反向?qū)W習(xí)相結(jié)合的策略對(duì)和聲記憶庫初始化. 和聲記憶庫中一半的解按照均勻分布策略產(chǎn)生如式(3)，剩余的一半解采用反向?qū)W習(xí)策略產(chǎn)生如式(6).

(6)

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

(2)新解產(chǎn)生的改進(jìn)

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

(7)

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

改進(jìn)的HS算法流程與標(biāo)準(zhǔn)HS算法流程相同.

3 基于和聲搜索算法的軟件可靠性模型參數(shù)估計(jì)方法

3.1 算法流程

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

目標(biāo)函數(shù)的構(gòu)造是利用HS算法估計(jì)軟件可靠性模型參數(shù)的關(guān)鍵，它是最優(yōu)解的評(píng)價(jià)標(biāo)準(zhǔn)，借鑒文獻(xiàn)[3]，本文采用式(8)作為目標(biāo)函數(shù)，即

(8)

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

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

圖1 算法流程圖

3.2 仿真實(shí)驗(yàn)

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

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

表1 G-O模型參數(shù)估計(jì)結(jié)果

數(shù)據(jù)集模型參數(shù)估計(jì)值ab適應(yīng)值JSYS1124．4664670．00005168．58356SYS294．1493390．00001911．8704995CSR1352．5592470．000077341．669559CSR2114．2036060．00006882．012696SS3455．0524430．000018144．179677

表2 M-O模型參數(shù)估計(jì)結(jié)果

數(shù)據(jù)集模型參數(shù)估計(jì)值λ0θ適應(yīng)值JSYS10．010340．02270331．60092SYS20．002230．02010810．16799CSR10．0469470．009278406．2147CSR20．0119130．0253373．07945SS30．0085140．003068154．4498

表3 PSO、蟻群算法和HS算法參數(shù)擬合的結(jié)果

數(shù)據(jù)集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 結(jié)果分析

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

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

圖2 SYS1數(shù)據(jù)的擬合結(jié)果

圖3 SYS2數(shù)據(jù)的擬合結(jié)果

圖4 CRS1數(shù)據(jù)的擬合結(jié)果

圖5 CRS2數(shù)據(jù)的擬合結(jié)果

圖6 SS3數(shù)據(jù)的擬合結(jié)果

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

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

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

4 結(jié)束語

針對(duì)估計(jì)軟件可靠性模型中的參數(shù)不精確問題，提出一種改進(jìn)的和聲搜索算法用于估計(jì)軟件可靠性模型參數(shù).該算法采用反向?qū)W習(xí)策略初始化和聲記憶庫，并利用當(dāng)前和聲記憶庫的最優(yōu)解產(chǎn)生新解來改進(jìn)算法. 使用該方法分別估計(jì)了Musa數(shù)據(jù)集中的5組數(shù)據(jù)的兩種軟件可靠性模型，通過實(shí)驗(yàn)驗(yàn)證了和聲搜索算法在參數(shù)估計(jì)應(yīng)用中的可行性和有效性.通過與其他智能算法比較可知，該算法參數(shù)估計(jì)的精度高、收斂速度快，能適應(yīng)不同的模型.

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

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

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

[4] 鄭長友, 劉曉明, 黃松. 基于蟻群算法的軟件可靠性模型參數(shù)估計(jì)方法[J]. 計(jì)算機(jī)應(yīng)用, 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ìn)展[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2011, 20(7): 244-248.

[9] HOANG P. 系統(tǒng)軟件可靠性[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

安徽省教育廳自然科學(xué)基金重點(diǎn)項(xiàng)目(KJ2014A100,KJ2016A308)

周園園, 女,yuanyzhou@qq.com

1672-6197(2017)02-0044-05

TP301.6

A