基于改進(jìn)模擬退火算法的軟件可靠性模型參數(shù)估計(jì)方法

溫曉玲，孫智孝，姜夢岑，艾笑天

(航空工業(yè)沈陽飛機(jī)設(shè)計(jì)研究所，遼寧 沈陽 110035)

軟件可靠性可定義為在規(guī)定使用環(huán)境、規(guī)定時(shí)間下，不發(fā)生失效的概率[1]，已成為最關(guān)鍵的軟件質(zhì)量屬性之一。作為度量軟件可靠性的重要途徑，從20世紀(jì)70年代起，學(xué)術(shù)界提出許多與時(shí)間相關(guān)的軟件可靠性評估模型，用于軟件可靠性評估和預(yù)測工作[2]。

目前，現(xiàn)有軟件可靠性增長評估模型的參數(shù)估計(jì)多采用最大似然估計(jì)(Maximum Likelihood Estimation,MLE)方法[3]。但是MLE方法在很多非線性求解情況下很難得到最優(yōu)的精確解，導(dǎo)致軟件可靠性模型精度和質(zhì)量受到較大約束。因此，許多學(xué)者開始對模型參數(shù)估計(jì)方法展開研究，以提升模型參數(shù)估計(jì)效率和精度[4-6]。其中，文獻(xiàn)[4]采用遺傳算法進(jìn)行可靠性模型參數(shù)求解，但是該方法結(jié)構(gòu)較為復(fù)雜且精確度較低。文獻(xiàn)[5]采用和聲搜索(Harmony Search,HS)算法進(jìn)行可靠性模型參數(shù)求解，該方法更適用于高維復(fù)雜非線性方程求解算法的優(yōu)化問題，應(yīng)用于軟件可靠性模型(屬于一般非線性方程)的參數(shù)求解時(shí)，其搜索范圍過大且收斂速度慢。文獻(xiàn)[6]應(yīng)用蟻群(Ant Colony Algorithm,AC)算法進(jìn)行可靠性模型參數(shù)求解，具有解的全局性好、收斂速度快等優(yōu)點(diǎn)。文獻(xiàn)[7]應(yīng)用狼群算法進(jìn)行可靠性模型參數(shù)求解，在算法執(zhí)行過程中需要加入先驗(yàn)知識來提高求解的精確度和優(yōu)化參數(shù)搜索方向，即其依賴于先驗(yàn)知識獲取的可信性。

近年來，模擬退火算法作為一種通用的隨機(jī)搜索算法，已經(jīng)被廣泛地應(yīng)用于各個(gè)領(lǐng)域的非線性求解問題[8-10]。與其他非線性求解算法相比，其具有適用于較大的搜索空間、快速收斂于一個(gè)可接受的優(yōu)秀解、比窮舉法更有效、不需要額外的先驗(yàn)知識等優(yōu)點(diǎn)。因此，模擬退火算法已經(jīng)被應(yīng)用在基于支持向量機(jī)的軟件可靠性模型參數(shù)選擇問題中[11-12]。

本質(zhì)上，軟件可靠性模型參數(shù)求解也是一個(gè)局部搜索最優(yōu)化問題，因此，本文考慮應(yīng)用模擬退火算法開展軟件可靠性模型參數(shù)估計(jì)研究。首先，基于模擬退火算法，提出相應(yīng)的參數(shù)求解過程；然后，針對模型參數(shù)求解最優(yōu)化問題，提出一種改進(jìn)的模擬退火(Modified Simulated Annealing)算法，即結(jié)合軟件可靠性模型特征，確定相應(yīng)的懲罰函數(shù)，以提升算法收斂精度。在此基礎(chǔ)上，提出一種基于改進(jìn)模擬退火算法的軟件可靠性模型參數(shù)估計(jì)方法(簡稱為MSAE法)；最后，將MSAE法與MLE法、HS法和AC法應(yīng)用于3組經(jīng)典的軟件可靠性模型和4種典型失效數(shù)據(jù)集中，開展工程實(shí)例研究。通過實(shí)例比較分析，驗(yàn)證了MSAE法在求解收斂進(jìn)度和模型擬合性能改進(jìn)方面的有效性。

1 基于模擬退火算法的參數(shù)求解過程

模擬退火算法借鑒了固體退火原理，即從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率變化特性，在目標(biāo)可能的解集空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解。因此，本文基于模擬退火算法，提出以下的模型參數(shù)求解過程。

① 依據(jù)當(dāng)前解算結(jié)果，生成一個(gè)位于有效解集空間的新解算結(jié)果。本過程主要是對當(dāng)前解算結(jié)果進(jìn)行內(nèi)容或結(jié)構(gòu)上的變化，例如對解算結(jié)果的內(nèi)容或結(jié)構(gòu)進(jìn)行交換或倒置，從而產(chǎn)生一個(gè)位于有效解集空間的新解算結(jié)果。這個(gè)新的解算結(jié)果由當(dāng)前解算結(jié)果的結(jié)構(gòu)與取值方式來決定，從而對冷卻進(jìn)度表的選取或生成產(chǎn)生影響。

② 計(jì)算當(dāng)前解算結(jié)果與新解算結(jié)果所對應(yīng)的目標(biāo)函數(shù)之間的差值。本過程針對當(dāng)前解算結(jié)果和新解算結(jié)果，分別計(jì)算對應(yīng)的目標(biāo)函數(shù)值。進(jìn)而按照某種特定方法(例如增量計(jì)算等)，計(jì)算兩者對應(yīng)目標(biāo)函數(shù)之間的差值。

③ 判斷新解是否被接受,判斷的依據(jù)是一個(gè)接受準(zhǔn)則。本過程依據(jù)某種接受準(zhǔn)則，對新解算結(jié)果與當(dāng)前解算結(jié)果的目標(biāo)函數(shù)差值進(jìn)行分析，判斷其是否可被接受。較為經(jīng)典的接受準(zhǔn)則是Metropolis準(zhǔn)則，若“目標(biāo)函數(shù)差值”的導(dǎo)數(shù)值Δt′<0，則接受新解算結(jié)果作為當(dāng)前的解算結(jié)果，否則以概率exp(-Δt′/T)接受新解算結(jié)果作為當(dāng)前的解算結(jié)果。

④ 若確定新解算結(jié)果被接受，則用新解算結(jié)果替代當(dāng)前解算結(jié)果。若依據(jù)Metropolis準(zhǔn)則，以較高置信度的概率判定新解算結(jié)果被接受，則將當(dāng)前解算結(jié)果替換為新解算結(jié)果?？蓪?dāng)前解算結(jié)果中對應(yīng)的結(jié)構(gòu)或內(nèi)容替換為新解算結(jié)果。同時(shí)，對相應(yīng)的目標(biāo)函數(shù)進(jìn)行完善。若當(dāng)前新解算結(jié)果被接受，則意味著完成一次迭代，可以在新解算結(jié)果基礎(chǔ)上開展新的分析；若當(dāng)前新解算結(jié)果不被接受，則還需要在當(dāng)前解算結(jié)果基礎(chǔ)上開展新的分析。

2 基于改進(jìn)模擬退火算法的軟件可靠性模型參數(shù)估計(jì)

首先，在模擬退火算法基礎(chǔ)上，結(jié)合軟件可靠性模型參數(shù)的物理含義，提出改進(jìn)的模擬退化算法，進(jìn)而提出基于改進(jìn)模擬退火算法的軟件可靠性模型參數(shù)估計(jì)方法。

2.1 結(jié)合模型求解特征的改進(jìn)模擬退火算法

考慮到軟件可靠性模型各個(gè)參數(shù)的物理含義(例如，GO模型的參數(shù)a>0,b<1等)，引入禁忌搜索，即不符合實(shí)際意義的參數(shù)，考慮給其評價(jià)函數(shù)(反映模型對失效數(shù)據(jù)的擬合性能，均方差函數(shù)MSE()即是一種典型的評價(jià)函數(shù))一個(gè)非常大的懲罰函數(shù)P，即

(1)

式中：x1,x2，…，xm為模型參數(shù)變量；m為參數(shù)維數(shù)。此時(shí)，可以得到擴(kuò)展評價(jià)函數(shù)為

S(x1,x2，…，xm)=λ1·MSE(x1,x2，…，xm)+λ2·P(x1,x2，…，xm)

(2)

式中:λ1為原始評價(jià)函數(shù)(即MSE函數(shù))的權(quán)重系數(shù);λ2為懲罰函數(shù)(即P函數(shù))的權(quán)重系數(shù)。λ1、λ2有如下關(guān)系：

λ1+λ2=1,λ1>>λ2

(3)

通?？梢匀。?/p>

(4)

2.2 基于改進(jìn)模擬退火算法的模型參數(shù)估計(jì)算法

基于上述改進(jìn)退火算法，提出新的軟件可靠性模型參數(shù)估計(jì)算法。MSAE法流程如圖1所示。

圖1 MSAE算法流程圖

依據(jù)圖1，給出MSAE法如下。

① Input()://失效數(shù)據(jù)讀入

N;//為軟件失效數(shù)據(jù)量

M(t);//為軟件失效間隔時(shí)間

② Init()://初始化

設(shè)置iterator，即鄰域內(nèi)的解數(shù)量;

③ while(t>tend)//t為退火過程中的溫度

{

for(j=1;j<=iterator;j++)

{

隨機(jī)生成U(t)鄰域內(nèi)的解U′(t)=U(t)+G(t);//G(x)為鄰域選擇函數(shù)

計(jì)算error=S(U′(t))-S(U(t));//S為評價(jià)函數(shù)

if(error<0)//新生成的解比較優(yōu)

{

U(t)=U′(t);//完全接受為新解

}

else

{

Check=rand();//隨機(jī)產(chǎn)生一個(gè)在[0,1]之內(nèi)的數(shù)值

if(Check>exp(-error/t))

{

U(t)=U′(t);//也接受為最新解

}

}

}

t=F(t);//溫度逐漸下降,對于不同溫度采用不同的下降函數(shù)F(可根據(jù)模型參數(shù)特點(diǎn)，選擇一個(gè)減函數(shù)作為下降函數(shù)F)

}

④ 重復(fù)上述步驟，直至t=tend

⑤ 輸出最終的最優(yōu)解U(t)

3 實(shí)例分析

驗(yàn)證試驗(yàn)采用了Sys3[12](19個(gè)數(shù)據(jù))、Sys4[13](20個(gè)數(shù)據(jù))、Sys5[1](60個(gè)數(shù)據(jù))和Sys6[1](200個(gè)數(shù)據(jù))共4組公開的經(jīng)典失效數(shù)據(jù)集。這4組經(jīng)典失效數(shù)據(jù)集分別來自O(shè)hba[13]、Wood[14]、Lyu[1]等學(xué)者收集的經(jīng)典軟件可靠性失效數(shù)據(jù)(具體數(shù)據(jù)內(nèi)容可參見相應(yīng)文獻(xiàn))，常用于軟件可靠性模型擬合性能的比較和分析。借助拉普拉斯法，這4組數(shù)據(jù)的可靠性趨勢均為“增長”，所適用的軟件可靠性模型包括GO、MO、S型等增長評估模型[11]。

為驗(yàn)證所提出的方法的有效性，將本文提出的MSAE法和MLE法、HS法、AC法分別應(yīng)用于GO、MO和S型這3個(gè)經(jīng)典軟件可靠性增長評估模型[14]。需要說明的是，蟻群算法與狼群算法均屬于群體智能算法，相比較而言，蟻群算法更成熟且具有典型性，而狼群算法嚴(yán)重依賴于先驗(yàn)知識的可信性，所以本文選擇蟻群算法作為群體智能算法代表參與實(shí)例分析驗(yàn)證。

采用不同方法對GO、MO、S型這3個(gè)模型的參數(shù)進(jìn)行估計(jì)，并計(jì)算每個(gè)模型對失效數(shù)據(jù)集的擬合值(均方差值(MSE))。依據(jù)模型對失效數(shù)據(jù)的擬合程度，來驗(yàn)證本文提出的MSAE法的有效性和可行性。具體計(jì)算結(jié)果如表1～表4所示。

表1 模型在4組數(shù)據(jù)集上的擬合結(jié)果(基于MSAE法)

表2 模型在4組數(shù)集據(jù)上的擬合結(jié)果(基于MLE法)

表3 模型在4組數(shù)據(jù)集上的擬合結(jié)果(基于HS法)

表4 模型在4組數(shù)據(jù)集上的擬合結(jié)果(基于AC法)

依據(jù)表1～表4中的數(shù)據(jù)進(jìn)行對比分析，具體如下。

(1)針對小樣本數(shù)據(jù)集Sys3和Sys4的對比分析。

在本文中，小樣本數(shù)據(jù)集是指Sys3和Sys4(即失效數(shù)據(jù)量≤30個(gè)數(shù)據(jù))。針對小樣本數(shù)據(jù)集Sys3和Sys4，MSAE法、MLE法、HS法和AC法對模型參數(shù)求解的收斂情況基本一致，均能給出較為合理的參數(shù)估計(jì)值。此外，根據(jù)這4種方法計(jì)算出的失效數(shù)據(jù)的擬合值(MSE值)相差不大，即4種方法在3個(gè)模型中對小樣本數(shù)據(jù)的擬合性能相差不大。例如，針對Sys3，基于MSAE法的GO模型的擬合值為139.815，而基于MLE法、HS法和AC法的GO模型的擬合值則分別為139.82、139.83、140.098。

由此可知，針對小樣本失效數(shù)據(jù)集(Sys3和Sys4)，這4種參數(shù)估計(jì)方法對模型參數(shù)求解的收斂情況基本一致，均能給出較為合理的參數(shù)估計(jì)值，同時(shí)基于MSAE法、MLE法、HS法和AC法的可靠性模型擬合性能相差不大。

(2)針對大樣本數(shù)據(jù)集Sys5和Sys6的對比分析。

在本文中，大樣本數(shù)據(jù)集是指Sys5和Sys6(即失效數(shù)據(jù)量≥60個(gè)數(shù)據(jù))。在大樣本數(shù)據(jù)集Sys5和Sys6上，MLE法在MO模型中存在參數(shù)求解不收斂的情況，即無法獲得合理的參數(shù)估計(jì)值。而MSAE法則明顯改善了在某些失效數(shù)據(jù)上MLE法參數(shù)求解不易于收斂的問題。此外，基于MSAE法的軟件可靠性模型擬合值比MLE法、HS法和AC法要小。例如，針對Sys5，基于MSAE法的GO模型擬合值為5.1227，而基于MLE法、HS法和AC法的GO模型擬合值分別為70.12、10.8331和8.1186；針對Sys6，基于MSAE法的GO模型擬合值為2.0651，而基于MLE法、HS法和AC法的GO模型擬合值分別為102.57、8.6519和9.1743。

由此可知，針對大樣本失效數(shù)據(jù)集(Sys5和Sys6)，基于MSAE法的軟件可靠性模型參數(shù)求解收斂效果要優(yōu)于MLE法；同時(shí)，基于MSAE的模型擬合性能要優(yōu)于MLE法、HS法和AC法。

通過圖2～圖5進(jìn)一步闡述了基于MSAE法的GO模型和MO模型對數(shù)據(jù)集Sys5和Sys6的擬合效果。

從圖2～圖5可以看出，基于MSAE法的GO模型和MO模型對Sys5和Sys6的擬合效果也非常良好，即模型曲線與原始數(shù)據(jù)非常接近。

圖2 GO模型對Sys5的擬合(基于MSAE法)

圖3 MO模型對Sys5的擬合(基于MSAE法)

圖4 GO模型對Sys6的擬合(基于MSAE法)

圖5 MO模型對Sys6的擬合(基于MSAE法)

依據(jù)上述分析可知，MSAE法相比于傳統(tǒng)的MLE法，可以有效提升軟件可靠性模型的擬合性能，即MSAE法具有可行性和有效性。

4 結(jié)論

本文在模擬退火算法基礎(chǔ)上，結(jié)合軟件可靠性模型求解的最優(yōu)化問題，提出一種改進(jìn)模擬退火算法，即結(jié)合軟件可靠性模型特征，確定相應(yīng)的懲罰函數(shù)。依據(jù)改進(jìn)模擬退火算法，提出了一種新的軟件可靠性模型參數(shù)估計(jì)方法(MSAE法)。最后，在4組數(shù)據(jù)集上，將MSAE法與MLE法、HS法和AC法應(yīng)用于GO、MO和S型這3種經(jīng)典軟件可靠性模型，開展工程實(shí)例研究，實(shí)例驗(yàn)證結(jié)果表明：

① 在指定的小樣本數(shù)據(jù)集Sys3和Sys4上(即失效數(shù)據(jù)量≤30個(gè)數(shù)據(jù))，MSAE法與MLE法、HS法和AC法的參數(shù)求解收斂效果基本一致。且基于MSAE法、MLE法、HS法和AC法的軟件可靠性模型對失效數(shù)據(jù)的擬合性能相差不大。

② 在指定的大樣本數(shù)據(jù)集Sys5和Sys6上(即失效數(shù)據(jù)量≥60個(gè)數(shù)據(jù))，MSAE法可有效改善基于MLE法模型參數(shù)求解不易于收斂的問題。同時(shí)，基于MSAE法的軟件可靠性模型對失效數(shù)據(jù)的擬合性能優(yōu)于MLE法、HS法和AC法。

③ 基于實(shí)例分析結(jié)果可以得出初步的結(jié)論，即MSAE法、HS法和AC法在指定的小樣本和大樣本數(shù)據(jù)集上都較為適用，而MLE法則更適用于小樣本數(shù)據(jù)集(即失效數(shù)據(jù)量≤30個(gè)數(shù)據(jù))。

在未來的工作中，還需要在更多的失效數(shù)據(jù)集上比較分析MSAE法、MLE法、HS法和AC法的擬合性能，進(jìn)一步判定這幾種典型算法的適用性范圍。