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

譚棉 馮夫健

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

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

DOI：10.11907/rjdk.181503

中圖分類號：TP301

文獻標識碼：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ī)模的不斷擴大和復雜程度的增加，從20世紀60年代末開始，出現(xiàn)了大量可靠性不高、進度延期和質量缺陷等典型特征的軟件問題[1]。因此，開發(fā)正確、可靠的軟件迫在眉睫。形式化開發(fā)是解決此問題的有效方法，它建立在嚴格的數(shù)學基礎上，目標是使系統(tǒng)具有較高的可信度和正確性，系統(tǒng)具有良好的結構，使其易維護并能較好地滿足用戶需求[2]。

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

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

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

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

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

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