譚棉 馮夫健

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

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

DOI：10.11907/rjdk.181503

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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年代末開(kāi)始，出現(xiàn)了大量可靠性不高、進(jìn)度延期和質(zhì)量缺陷等典型特征的軟件問(wèn)題[1]。因此，開(kāi)發(fā)正確、可靠的軟件迫在眉睫。形式化開(kāi)發(fā)是解決此問(wèn)題的有效方法，它建立在嚴(yán)格的數(shù)學(xué)基礎(chǔ)上，目標(biāo)是使系統(tǒng)具有較高的可信度和正確性，系統(tǒng)具有良好的結(jié)構(gòu)，使其易維護(hù)并能較好地滿足用戶需求[2]。

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

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

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

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

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

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