基于演化算法的软件形式化开发部件选取方法

谭棉 冯夫健

摘要：形式化方法在软件开发过程中一直扮演着重要角色。由于其建立在严格的数学基础之上，因此开发成本较高。为了解决开发成本问题，将软件开发整体分为形式化开发集合类和非形式化开发集合类。在此基础上，开发部件采用二进制串描述并构建目标函数模型，通过演化算法对模型进行优化求解，判定不同的部件开发集合类归属。选用（1+1）EA作为研究对象验证开发部件选取方法的可行性。采用遗传算法、粒子群算法、二进制差分演化算法进行验证分析。结果表明，该分类方法可作为演化算法在软件开发部件选取方面的一种理论工具。

关键词：形式化方法；演化算法；目标函数；集合类

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引言

随着软件系统规模的不断扩大和复杂程度的增加，从20世纪60年代末开始，出现了大量可靠性不高、进度延期和质量缺陷等典型特征的软件问题[1]。因此，开发正确、可靠的软件迫在眉睫。形式化开发是解决此问题的有效方法，它建立在严格的数学基础上，目标是使系统具有较高的可信度和正确性，系统具有良好的结构，使其易维护并能较好地满足用户需求[2]。

软件工程中的形式化开发是具有精确数学语义的软件系统开发方法，其以计算逻辑、代数理论和软件结构为基础，有助于提高软件系统质量和可靠性。但是软件的形式化开发方法从本质上是一种较为严格、灵活性较差的方法，开发成本较高[3]。现有的形式化开发方法主要解决较小规模问题，很难应用到一些较大、较完整的软件系统开发中。因此，许多软件开发机构对使用该方法仍持謹慎态度，对于怎样使用或何时使用形式化开发方法依然存在较大争议。

对于上述难点，一种方法是在软件开发过程中部分引入形式化方法。郑宇军等[4-5]结合浅水波理论和水波优化算法思想设计了一种离散水波优化方法，实现软件开发过程中对于形式化开发的关键部件选取问题[6]。Hamlet等[7]提出了一种基于部件的可靠度估算开发系统可靠度的新方法。Russo[8]针对选取重要软件部件进行形式化开发问题提出了一些指导性原则，主要包括手工开发易出错部件、关键性安全部件、具有复杂控制逻辑的部件等。Xue[9]提出的形式化方法PAR则强调对软件中的复杂算法进行形式化开发，特别是对算法循环不变式进行推导和验证。

利用随机优化算法求解软件工程中的优化问题已应用在软件开发的多个环节，比如软件需求、模块优化、软件测试等环节[10]。但到目前为止，演化算法在软件形式化开发中的研究成果较少[11]。演化算法在求解优化问题中的应用越来越多，不同学科领域用此方法求解复杂的优化问题[12]，如Nayak等[13]采用粒子群优化算法实现数据流的自动测试，Lai等[14]通过演化算法实现对最小生成树的性能分析。

本文针对形式化方法在软件开发过程中的使用问题提出一种分类方法，将软件开发整体定义为一个集合，通过演化算法对模型进行优化求解，判定不同部件集合类的归属，最终生成采用形式化开发的集合和采用非形式化方法开发的集合，以提高软件开发的可靠性和准确性。

1基于演化算法的形式化开发问题建模

对于软件开发过程中各部件的开发方式归属问题，可将总的用于分类的部件定义为集合S，其中S中的元素为开发的各个部件且集合大小为n，将用于形式化开发的部件集合定义为F，对于采用传统方式开发的部件集合定义为T。问题的解可用一个长度为n的二进制串表示，其中，二进制串的位置i的取值1表示采用形式化开发，0表示采用非形式化开发。