软件估算的两大目标是进度与成本, 而这两大目标永远不会是一门精确的科学, 人员、技术、环境、策略等等对软件最终成本与开发所需工作量都有严重影响。估算有风险, 越来越多的人在研究软件估算的方法。现在世界上比较流行的软件估算方法有:“模糊逻辑”法, 功能点法, 标准构件法, 修改法, 基于代码行 (LOC) 的估算方法, 基于功能点 (FP) 的估算方法, 基于过程的估算方法, 基于COCOMO模型的估算方法, 基于软件方程式的估算方法。各种方法各有优缺点, 为使软件估算更精确, 提高软件可靠性, 本文将通过某项目实例使用遗传算法和模糊决策树结合的方法进行软件估算。遗传算法优化的模糊决策树软件工作量估算模型是基于遗传算法优化的模糊决策树算法, 输入的数据为原始化数据。
遗传算法 (Genetic Algorithm, GA) , 是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型, 它是由美国Michigan大学的J.Holland教授于1975年首先提出的。遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表, 把问题的解用染色体代表 (在计算机里用二进制码表示) , 从而得到一个由具有不同染色体的个体组成的群体.这个群体在问题特定的环境里生存竞争, 适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征, 并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境, 不断进化, 最后收敛到一族最适应环境的类似个体, 即得到问题最优的解。
随机给出两个参数的初始值, 它们的范围分别是0、1。用遗传算法每一代优化得到的参数都进行启发式算法的诱导, 即选择、交叉、变异;循环执行上述步骤, 直到评价函数达到要求。当循环一定代数以后, 模糊决策树的分类准确率和叶子总数达到满意结果且较稳定。
在构建模型中本文采用10-折交叉验证 (10-fold crossvalidation) , 它用来测试算法准确性。是常用的测试方法。将数据集分成十份, 轮流将其中9份作为训练数据, 1份作为测试数据, 进行试验。每次试验都会得出相应的正确率 (或差错率) 。10次结果的正确率 (或差错率) 的平均值作为对算法精度的估计, 一般还需要进行多次10折交叉验证 (例如10次10折交叉验证) , 再求其均值, 作为对算法准确性的估计。之所以选择将数据集分为10份, 是因为通过利用大量数据集、使用不同学习技术进行的大量试验, 表明10折是获得最好误差估计的恰当选择。
软件开发是一项非常复杂的工程, 不仅包含需求分析、设计 (概要设计、详细设计) 、编码、测试、实施维护等完整的过程, 还涉及到开发工具、开发人员技术水平、项目范围、项目沟通等众多因素。这里我以Desharnais数据集为基础数据, 开展软件估算工作。Desharnais数据集最初由Desharnais在1989年使用, 来自一个加拿大软件公司。它是在软件工作量估算领域中最著名的公开数据集之一。把数据集划分为样本数大致相等的子集, 10个项目属性分别是实际工作量、项目进度、开发人员技术水平、项目管理经验、业务、调整前功能点数、调整因子、调整后功能点数、开发环境、完成年份、系统数据模型的实体数。软件项目的进度和属性实际工作量一样, 因此不予考虑。在这10个属性中, 属性开发环境为类别属性, 其它的属性为数值属性。
软件开发语言环境, 有三种开发语言环境 (开发语言环境1, 开发语言环境2, 开发语言环境3) 模糊化后, 模糊变量开发有三个模糊集, 分别是开发环境1、开发环境2、开发环境3, 在模糊化中可使用对类别属性的处理方法进行模糊化处理。假设样本的属性a是类别型属性, 该属性有n个类别值, 分别为n1, n2, n3, …, ni, 则属性a的模糊化后, 可得到i个模糊集合, 其隶属函数为:
即, 对于类别型属性, 每一类就是一个模糊集合, 某模糊集合的隶属函数是分段二值函数, 当属性值是该类时, 隶属函数为1, 当属性值不是该类时, 隶属度值为0。例如, 某项目的开发语言环境为1, 则其在三个语言值语言1、语言2和语言3上的隶属度分别为1、0、0。
开发人员对设备的熟悉程度和项目管理经验两个属性是根据工作经验来确定的, 在实际生活中, 我们用新手、有一定经验、经验丰富等语言来说明人们对工作的熟练程度, 我们可以用工作年限来进行处理。这样的话, 属性开发人员技术水平和属性项目管理经验的模糊化就是要解决工作年数与相应语言值之间的映射关系。使用三角隶属函数对这两个属性进行模糊化, 工作年限最小为0。
下面对以上属性进行模糊化处理。当子集实际工作量为测试样本、其余子集样本为训练集时, 模糊化处理过程如表1。
采用半开口式对于属性系统数据模型的实体数 (31, 149.3, 267.7) 三个模糊集合的隶属函数参数见表2。根据由此产生的隶属函数对训练集合和测试集进行模糊化。其它几个属性相同的方法进行模糊化。
按照以上的方法, 在其它子集作为验证集时, 先确定模糊集合和相应的隶属函数, 然后对样本数据进行模糊化处理, 为构建模糊决策树、验证模型性能做好数据准备。
摘要：本文将通过某项目实例使用遗传算法和模糊决策树结合的方法进行软件估算。遗传算法优化的模糊决策树软件工作量估算模型是基于遗传算法优化的模糊决策树算法, 输入的数据为原始化数据。使用Desharnais数据集, 采用10-折交叉验证, 对离散和连续型的样本数据使用函数求值。
关键词：模糊决策树,遗传算法优化,10-fold,cross-validation软件估算
参考文献
[1] 张朝杰.一种基于模糊决策树的软件工作量估算方法[D].国防科学技术大学, 2010.
[2] Steve Mc Connell.软件估算黑匣子揭秘[M].电子工业出版社, 2007.
[3] 阎魏.基于决策树的软件工作量估算方法[J].计算机工程与科学, 2009 (08) .
[4] 冯楠, 李敏强, 寇纪淞, 等.一种基于模糊决策树的软件成本估计模型[J].计算机工程与应用, 2007, 43 (026) :21-23.
[5] Sharma Vishal, Verma Harsh Kumar.Optimized Fuzzy Logic Based Framework for Effort Estimation in Software Development[J].International Journal of Computer Science Issues, 2010, 7 (2) :30-38.