随着软件系统规模的不断扩大和复杂程度的日益加大, 从20世纪60年代末期开始, 出现了以大量软件项目进度延期、预算超支和质量缺陷为典型特征的软件危机, 至今仍频繁发生。国外在对超过5万个项目进行统计后发现, 有18%的项目未完成或取消, 53%的项目超支或质量明显低于预算, 在美国, 超过90%的大型项目没有进行系统的估算。国内超过75%的软件项目实际工作量超出预期, 而最大偏差超过100%, 超过80%的项目在甲乙方签订合同前没有进行系统估算。
在现代软件项目管理过程中, 软件估算是一项极具有挑战性的工作, 在众多的软件项目管理活动中, 占据着十分重要的地位。软件估算的准确程度对后续的开发计划和进度控制有决定性的影响, 甚至影响到软件项目的成败。在软件开发过程中不同的专家, 不同的项目, 不同的技术人员估算结果不尽相同。而在项目开始的早期阶段, 是进行准确可信估算的重要时期。传统的估算技术模型, 比如说“传统的线性回归模型和形式技术”, 其处理定性指标能力不足, 只能使用类比法或者专家经验法, 参照以前的数据进行估算;与此同时, 这些模型还不能处理当确切数据未知而一般常识已知的情况。
目前在软件估算方面已经研究了很多的方法, 比如说, COCOMO等数学方式的软件估算模型, 需要利用历史数据对其中的因子参数进行校正调整;基于类比的估算是对新项目和历史项目进行比较, 以此找出和新项目特征最匹配的历史项目, 进而对新项目进行估算。在已有的研究中, 遗传算法和模糊决策树算法都有运用在软件估算中的研究, 但两者的结合较少。
决策树技术是一种以实例为基础的归纳学习算法, 其所形成的决策树形象易于理解, 而且把模糊逻辑技术对不精确、不确定信息的处理能力融合于其中对其进行优化, 形成模糊决策树, 再利用遗传算法的优化, 从而进一步得出最好的结果数据, 把遗传算法和模糊决策树法结合的算法应用于软件过程, 引历史数据进行归纳学习, 可高效地形成能够反映软件开发本质的决策树, 进而对新的软件项目进行估算, 最后可产生解释性更强的估算结果。
决策树的典型算法中, C4.5算法排名第一, C4.5算法是机器学习算法中的一种分类决策树算法, 其核心算法是ID3算法, 决策树示意图如图1所示。
ID3算法是一种著名的决策树算法, 该算法是以信息论为基础, 以信息熵和信息增益度为衡量标准, 以自顶向下递归划分训练样本的方式来构造决策树。在构造决策树过程中, 每个节点上判定属性的选择标准是最大信息增益。
模糊决策数树是模糊逻辑和决策树算法相结合的产物, 基于ID3算法的模糊决策树是模糊逻辑和ID3算法相结合的产物。模糊逻辑是源于模糊集合论的一种近似推理型的多值逻辑, 是基于模糊集合理论上对经典逻辑的延伸。对于模糊决策树的使用, 同经典决策树一样, 分为两个步骤:第一步使用历史数据对模糊决策树算法进行训练, 产生能够描述特定数据集内在规律的本地化模糊决策树;第二步使用上步所形成的模糊决策树对新样本的目标属性进行预测。遗传算法的基本思想是从初始种群出发, 采用优胜劣汰、适者生存的自然法则选择个体, 并通过杂交、变异来产生新一代种群, 如此逐代进化, 直到满足目标为止[1]。
基于决策树的软件项目估算方法首先需要根据已有的基准数据建立决策树。软件项目估算决策树的叶节点是目标项目的预测属性, 中间节点是软件项目估算活动中可以收集的项目属性。软件项目属性通常包括开发周期、开发团队规模、开发团队的能力成熟度水平、业务类型、应用类型、基础设施平台、开发工作量等[2]。
基于遗传算法的模糊决策树的软件估算研究大体上可分为以下几个步骤:
1) 数据预处理。
收集整理历史项目数据, 由于实际项目中缺失数据和噪音数据的存在, 需要我们在处理数据时补充和剔除, 同一个数据集中标致方法有多种, 在建模前需要对这些不同的表达方式进行一致化, 得到统一、清晰的数据表示。历史数据经过模糊化处理后作为模糊决策树的输入数据。
2) 构建决策树模型。
使用ID3算法的模糊决策树算法构建模糊决策树, 然后用遗传算法优化模糊决策树的α、β两个参数 (这两个参数的选择目前需要经验, 也是我们后续研究的方向) , 构建软件估算模型后为我们新项目估算提供依据。
3) 新项目估算。
估算新项目的过程, 就是决策推理和去模糊化的过程。在这个过程中我们要处理好叶节点, 还应考虑估算结果如果表示。
4) 改进与评估。
基于遗传算法的模糊决策树的软件估算研究其目的是提高软件可靠性, 对于软件的可靠性评价主要采用定量评价方法, 即选择合适的可靠性度量因子 (可靠性参数) , 然后分析可靠性数据而得到参数具体值, 最后进行评价, 我们可以使用平均相对误差来进行评价。
按照以上步骤, 我们将以目前正准备开发的实习实训管理系统为实例, 建立估算模型, 形成评价体系, 提高软件可靠性。
摘要:本文以软件估算为核心, 运用模糊决策树和遗传算法, 设计估算步骤, 建立评估模型, 利用历史数据对其中的因子参数进行校正调整, 基于ID3算法的模糊决策树, 确定遗传算法优化模糊决策树的α、β两个参数, 进而对新项目进行估算, 对提高软件可靠性提供了有效方法, 值得参考。
关键词:模糊决策树,遗传算法,软件估算
参考文献
[1] 张朝杰.一种基于模糊决策树的软件工作量估算方法[D].国防科学技术大学, 2010.
[2] 阎魏.基于决策树的软件工作量估算方法[J].计算机工程与科学, 2009 (08) .
[3] 王健, 刘尔烈, 骆刚.工程项目管理中工期—成本—质量综合均衡优化[J].系统工程学报, 2004 (02) .