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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

通常可以取：

(4)

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

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

圖1 MSAE算法流程圖

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

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

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

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

② Init()://初始化

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

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

{

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

{

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

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

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

{

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

}

else

{

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

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

{

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

}

}

}

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

}

④ 重復上述步驟，直至t=tend

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

3 實例分析

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

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

采用不同方法對GO、MO、S型這3個模型的參數(shù)進行估計，并計算每個模型對失效數(shù)據(jù)集的擬合值(均方差值(MSE))。依據(jù)模型對失效數(shù)據(jù)的擬合程度，來驗證本文提出的MSAE法的有效性和可行性。具體計算結(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ù)進行對比分析，具體如下。

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

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

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

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

在本文中，大樣本數(shù)據(jù)集是指Sys5和Sys6(即失效數(shù)據(jù)量≥60個數(shù)據(jù))。在大樣本數(shù)據(jù)集Sys5和Sys6上，MLE法在MO模型中存在參數(shù)求解不收斂的情況，即無法獲得合理的參數(shù)估計值。而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法；同時，基于MSAE的模型擬合性能要優(yōu)于MLE法、HS法和AC法。

通過圖2～圖5進一步闡述了基于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)化問題，提出一種改進模擬退火算法，即結(jié)合軟件可靠性模型特征，確定相應的懲罰函數(shù)。依據(jù)改進模擬退火算法，提出了一種新的軟件可靠性模型參數(shù)估計方法(MSAE法)。最后，在4組數(shù)據(jù)集上，將MSAE法與MLE法、HS法和AC法應用于GO、MO和S型這3種經(jīng)典軟件可靠性模型，開展工程實例研究，實例驗證結(jié)果表明：

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

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

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

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