基于演化算法的軟件形式化開發(fā)部件選取方法

譚棉 馮夫健

摘要：形式化方法在軟件開發(fā)過程中一直扮演著重要角色。由于其建立在嚴(yán)格的數(shù)學(xué)基礎(chǔ)之上，因此開發(fā)成本較高。為了解決開發(fā)成本問題，將軟件開發(fā)整體分為形式化開發(fā)集合類和非形式化開發(fā)集合類。在此基礎(chǔ)上，開發(fā)部件采用二進(jìn)制串描述并構(gòu)建目標(biāo)函數(shù)模型，通過演化算法對模型進(jìn)行優(yōu)化求解，判定不同的部件開發(fā)集合類歸屬。選用（1+1）EA作為研究對象驗(yàn)證開發(fā)部件選取方法的可行性。采用遺傳算法、粒子群算法、二進(jìn)制差分演化算法進(jìn)行驗(yàn)證分析。結(jié)果表明，該分類方法可作為演化算法在軟件開發(fā)部件選取方面的一種理論工具。

關(guān)鍵詞：形式化方法；演化算法；目標(biāo)函數(shù)；集合類

DOI：10.11907/rjdk.181503

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2018）007-0064-03

Abstract：Formaldevelopmenthasplayedanimportantroleinsoftwaredevelopment，becauseitisbasedonrigorousmathematics，developmentcostsareoftenmoreexpensive.Inordertosolvethedevelopmentcostproblem，thispaperdividesthesoftwaredevelopmentintotwosetsoftheclass：formaldevelopmentcollectionclassandunformaldevelopmentcollectionclass.Onthisbasisbinarystringdescriptionisusedtodescribethedevelopmentcomponentsandconstructtheobjectivemodel.Themodelisoptimizedbytheevolutionaryalgorithmtodeterminetheownershipofdifferentdevelopmentcomponents.Inordertoverifythefeasibilityofthedevelopmentcomponentselection，weselect（1+1）EAastheresearchobject，andadoptsthegeneticalgorithm，particleswarmalgorithmandbinarydifferenceevolutionalgorithmtocarryoutexperimentalverificationanalysis.Theexperimentalresultsshowthattheproposedclassificationmethodcanbeusedastheoreticaltoolinselectionofsoftwaredevelopmentcomponents.

KeyWords：formalmethods；evolutionaryalgorithm；objectivefunction；collectionclasses

0引言

隨著軟件系統(tǒng)規(guī)模的不斷擴(kuò)大和復(fù)雜程度的增加，從20世紀(jì)60年代末開始，出現(xiàn)了大量可靠性不高、進(jìn)度延期和質(zhì)量缺陷等典型特征的軟件問題[1]。因此，開發(fā)正確、可靠的軟件迫在眉睫。形式化開發(fā)是解決此問題的有效方法，它建立在嚴(yán)格的數(shù)學(xué)基礎(chǔ)上，目標(biāo)是使系統(tǒng)具有較高的可信度和正確性，系統(tǒng)具有良好的結(jié)構(gòu)，使其易維護(hù)并能較好地滿足用戶需求[2]。

軟件工程中的形式化開發(fā)是具有精確數(shù)學(xué)語義的軟件系統(tǒng)開發(fā)方法，其以計算邏輯、代數(shù)理論和軟件結(jié)構(gòu)為基礎(chǔ)，有助于提高軟件系統(tǒng)質(zhì)量和可靠性。但是軟件的形式化開發(fā)方法從本質(zhì)上是一種較為嚴(yán)格、靈活性較差的方法，開發(fā)成本較高[3]?，F(xiàn)有的形式化開發(fā)方法主要解決較小規(guī)模問題，很難應(yīng)用到一些較大、較完整的軟件系統(tǒng)開發(fā)中。因此，許多軟件開發(fā)機(jī)構(gòu)對使用該方法仍持謹(jǐn)慎態(tài)度，對于怎樣使用或何時使用形式化開發(fā)方法依然存在較大爭議。

對于上述難點(diǎn)，一種方法是在軟件開發(fā)過程中部分引入形式化方法。鄭宇軍等[4-5]結(jié)合淺水波理論和水波優(yōu)化算法思想設(shè)計了一種離散水波優(yōu)化方法，實(shí)現(xiàn)軟件開發(fā)過程中對于形式化開發(fā)的關(guān)鍵部件選取問題[6]。Hamlet等[7]提出了一種基于部件的可靠度估算開發(fā)系統(tǒng)可靠度的新方法。Russo[8]針對選取重要軟件部件進(jìn)行形式化開發(fā)問題提出了一些指導(dǎo)性原則，主要包括手工開發(fā)易出錯部件、關(guān)鍵性安全部件、具有復(fù)雜控制邏輯的部件等。Xue[9]提出的形式化方法PAR則強(qiáng)調(diào)對軟件中的復(fù)雜算法進(jìn)行形式化開發(fā)，特別是對算法循環(huán)不變式進(jìn)行推導(dǎo)和驗(yàn)證。

利用隨機(jī)優(yōu)化算法求解軟件工程中的優(yōu)化問題已應(yīng)用在軟件開發(fā)的多個環(huán)節(jié)，比如軟件需求、模塊優(yōu)化、軟件測試等環(huán)節(jié)[10]。但到目前為止，演化算法在軟件形式化開發(fā)中的研究成果較少[11]。演化算法在求解優(yōu)化問題中的應(yīng)用越來越多，不同學(xué)科領(lǐng)域用此方法求解復(fù)雜的優(yōu)化問題[12]，如Nayak等[13]采用粒子群優(yōu)化算法實(shí)現(xiàn)數(shù)據(jù)流的自動測試，Lai等[14]通過演化算法實(shí)現(xiàn)對最小生成樹的性能分析。

本文針對形式化方法在軟件開發(fā)過程中的使用問題提出一種分類方法，將軟件開發(fā)整體定義為一個集合，通過演化算法對模型進(jìn)行優(yōu)化求解，判定不同部件集合類的歸屬，最終生成采用形式化開發(fā)的集合和采用非形式化方法開發(fā)的集合，以提高軟件開發(fā)的可靠性和準(zhǔn)確性。

1基于演化算法的形式化開發(fā)問題建模

對于軟件開發(fā)過程中各部件的開發(fā)方式歸屬問題，可將總的用于分類的部件定義為集合S，其中S中的元素為開發(fā)的各個部件且集合大小為n，將用于形式化開發(fā)的部件集合定義為F，對于采用傳統(tǒng)方式開發(fā)的部件集合定義為T。問題的解可用一個長度為n的二進(jìn)制串表示，其中，二進(jìn)制串的位置i的取值1表示采用形式化開發(fā)，0表示采用非形式化開發(fā)。