CN116307918B - 一种两段式差分优化驱动的基于类比的工作量度量方法 - Google Patents

Abstract

本发明涉及一种两段式差分优化驱动的基于类比的工作量度量方法，包括以下步骤：接收新项目；确定和新项目类似的历史项目；计算新项目和历史项目的特征差分；基于特征差分构建目标函数；使用BA算法对目标函数进行求解，得到最优参数；基于最优参数，对参与计算的每个历史项目的工作量进行加权得到新项目的工作量。与现有技术相比，本发明具有明确了特征差分和工作量差分之间的变化关系，使得计算得到的工作量准确性更高。

Description

一种两段式差分优化驱动的基于类比的工作量度量方法

技术领域

本发明涉及软件项目管理技术领域，尤其是涉及一种两段式差分优化驱动的基于类比的工作量度量方法。

背景技术

软件开发工作估计(Software Development Estimation，SDE)是软件开发过程中最重要的步骤之一，对软件项目的成功起着至关重要的作用。它不仅包括预测开发软件所需的工作量、时间和员工数量，而且还包括软件维护过程所需的工作量。近几十年来，人们提出了各种方法来估计SDE，可分为基于算法和基于非算法的工作量估计技术。应用最广泛的方法之一是Shepperd在1979年提出基于案例的推理(Case Based Reasoning，CBR)。尽管到目前为止已经介绍了许多SDE估计方法，但易用性和简单性使得CBR得到了广泛应用。CBR方法强调使用过去项目的知识，因此被称为是基于类比的估计(Analogy BasedEstimation，ABE)方法。

ABE方法的背景理论是具有相似特征的软件开发项目具有相似性的工作量。相似项目的数量是影响ABE方法中SDE准确性的一个因素，ABE方法中的工作量估算需要多个类似的软件开发项目，参与估计的项目个数值会影响工作量估计的准确性。不同的算法选取项目的策略有所不同，固定地选择K个最近邻项目和利用自适应规则灵活地确定K的大小是两种常见的方法。ABE方法中，对于一个新的软件开发项目，它与以前的项目的相似性是通过相似函数来度量的。相似函数被用来比较两个项目的特征和确定它们之间的相似程度，它在ABE方法中起着重要作用。由于所有原始特征(属性)在估计SDE时的重要性并不相同，因此在计算项目之间的相似性时不同特征可能具有不同的权重，可以利用特征选择和特征加权技术来优化不同特征对相似函数的影响。

目前常用的广告归因算法有首次归因，末次归因，平均归因，时间衰减归因四种。首次归因将每一次的转化收益都归功于转化链路上的第一个触点，该触点的贡献是100％，其余为0％。末次归因与首次归因相反，它认为转化只和转化链路上的最后一个触点有关，因此转化链路上的最后一个触点的贡献为100％，其余为0％。平均归因则是将转化的贡献平均分配到每个触点。时间衰减归因是根据距离转化时间点的时间间隔，将贡献按照时间递减的顺序分配到每个触点，距离转化时间点最远的触点贡献越小。

ABE算法首要工作就是寻找个合适的相似项目。研究人员提出了各种方法来指定这个数目：1)采用固定数目选择(即等)；2)基于聚类的动态选择。3)基于相似阈值的选择。然而，多数研究对所有新项目使用相同的值，但这样的做法并不一定会为每个单独的项目产生最佳的匹配；或是仅根据数据集的结构预测最佳值，没有考虑调整工作量的方法。为了更加精细化地为每个项目都寻找最佳的相似项目值，Azzeh等人使用蜜蜂算法提出了一种优化的基于类比的估计(Optimized Analogy Based Estimation，OABE)，该方法为每个项目同时搜索最优的值和每个特征差的权重因子。

基于历史项目的工作量调整新项目工作量的方法主要是研究相似函数，现有的研究中包含了大量的调整方法，使用最广泛的策略包括：Walkerden和Jeffery提出了基于尺寸外推的线性尺寸调整(Linear Size Adjustment，LSE)方法。Mendes等人提出了多线性特征外推法(Multiple Linear Feature Extrapolation，MLFE)来包含所有相关的尺寸特征。Jorgenson等人提出了回归均值(Regression Towards the Mean，RTM)来根据项目的生产力值调整项目。Chiu和Huang提出了一种基于遗传算法(Genetic Algorithm，GA)的调整，在最小化性能度量的基础上优化总结每个特征距离的系数。最近，Li等人提出使用神经网络(Neural Network，NN)来学习项目之间的差异，并将差异反映在最终的估计上。

综上所述，基于类比的工作量度量方法因其卓越的预测性能在软件工程社区深受欢迎。这种方法背后的思想是在新项目到来的时候，通过最小化新项目和历史项目的误差来估计新项目的工作量。估计最小误差有两个重要步骤，第一步是确定和新项目最类似的项目，第二步是对新项目和历史项目的特征差分进行调整。然而，针对特征差分进行调整这一过程，现有研究并没有明确特征差分和工作量差分的关系，而是把二者假设为等量变化关系，导致对新项目工作量的度量准确度低。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种两段式差分优化驱动的基于类比的工作量度量方法。

本发明的目的可以通过以下技术方案来实现：

一种两段式差分优化驱动的基于类比的工作量度量方法，包括以下步骤：

接收新项目；

确定和新项目类似的历史项目；

计算新项目和历史项目的特征差分；

基于所述特征差分构建目标函数；

使用BA算法对目标函数进行求解，得到最优参数；

基于所述最优参数，对参与计算的每个历史项目的工作量进行加权得到新项目的工作量。

进一步地，所述特征差分指新项目的特征和历史项目的特征差值，即：

所述特征差分包括正特征差分和负特征差分。

进一步地，所述正特征差分和负特征差分和工作量的关系不一致，正特征差分与工作量差分的相关性更强；

定义特征差分与工作量差分的相关性为工作量弹性l，为称为调整因子，有：

式中，Δe⁺为工作量差分，即新项目工作量和历史项目工作量的差值，

进一步地，当采用直线拟合的情况下有： 为正调整因子，为负调整因子；项目中每个特征都有一组对应的

进一步地，所述目标函数的构建包括以下步骤：

构建特征权重矩阵为：

式中，为和新项目类似的历史项目个数，为特征权重，m表示每个项目的特征个数；中的每一行代表一个相似的历史项目中每个特征所对应的权重；

构建调整因子函数为：

式中，为正调整因子，为负调整因子，

基于所述特征权重矩阵和调整因子函数，构造每个项目的平均特征差分

通过构造出需要求解的目标函数

进一步地，所述特征权重需要满足：

进一步地，使用BA算法对目标函数进行求解包括以下步骤：

BA算法初始化个解，每个解的值在保证不重复的情况下随机生成，每个解的矩阵在满足约束条件的情况下也随机初始化；

从个解中选取个候选解进行邻域搜索，根据值进行评价后，对解进行升序排序，从小到大依次得到个最好的解；

针对这个解，每个解都进行个邻域解搜索，对于选出的剩余的个解则每个解都进行个邻域解搜索

没有被选中的个解则随机地在解空间内搜索；

重复上述步骤，直到满足最小值或最大迭代次数。

进一步地，所述的最优参数包括最优历史项目参与数、每个特征的正调整因子、每个特征的负调整因子及每个历史项目中各个特征的权重系数。

进一步地，所述对参与计算的每个历史项目的工作量进行加权得到新项目的工作量包括以下步骤：

基于所述最优参数，计算每个项目的最优平均特征差分；

针对每个项目，在历史项目工作量的基础上根据所述最优平均特征差分对新项目工作量进行估计，该估计用表示为：

对参与计算的每个历史项目的估计值进行聚合，得到新项目的工作量。

进一步地，所述对参与计算的每个历史项目的估计值进行聚合具体为按照相似度排序进行聚合，包括以下步骤：

根据每个项目的最优平均特征差分从小到大对个相似历史项目排序；

第项目的排序结果用标签表示，

根据下式得到最终计算的新项目工作量

与现有技术相比，本发明具有以下有益效果：

本申请在发现特征差分和工作量差分并不是等量变化的情况下提出了一种新的基于类比的工作量估计方法，分别定义正特征差分和负特征差分表征其与工作量变化呈现的不同函数关系，采取两段式对特征差分和工作量差分的线性关系进行描述。通过蜜蜂算法搜索得到线性系数、动态自适应相似项目个数和特征权重，与现有技术相比，本申请在四个公开的数据集上不同指标的实验结果对比表明本申请提出的算法具有一定的优越性，能够更加准确地度量新项目的工作量。

附图说明

图1为基于ABE方法的工作量评估流程图；

图2为本发明的算法流程图；

图3为平均特征差分和工作量差分在不同数据集上呈现的关系示意图；

图4为正负特征差分和工作量在不同数据集上呈现的关系示意。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

基于ABE的工作量度量方法的流程如图1所示。基于类比的工作量度量方法因其卓越的预测性能在软件工程社区深受欢迎。这种方法背后的思想是在新项目到来的时候，通过最小化新项目和历史项目的误差来估计新项目的工作量。估计最小误差有两个重要步骤，第一步是确定和新项目最类似的项目，第二步是对新项目和历史项目的特征差分进行调整。

本申请提出了一种两段式差分优化算法用来调整特征差分，主要的灵感来源于以下两点：本实施例发现特征差分增量和工作量差分增量并不是等额增加，它们存在倍数关系；此外，正负特征差分增量对于工作量差分增量的影响是不同的，正的特征差分增量对工作量差分增量的影响明显强于负的特征差分增量。

基于以上两点发现，本申请采用蜜蜂算法寻找每个特征的正负差分增量的最优调整因子。所提出的算法在四个公开的数据集上的实验结果普遍优于用来对比的其它优秀算法。

本申请提出的算法流程如图2所示。首先计算新项目和个历史项目的特征差分，随后特征差分被用于目标函数的构建。目标函数构建完成后，使用BA算法进行求解。BA算法迭代完成即可求得最优的历史项目参与数每个特征的正负特征差分拟合系数及每个历史项目每个特征的权重系数。

在上述最优参数已知的情况下，本实施例对参与计算的每个历史项目的工作量进行加权得到新项目的工作量。

具体的，本申请主要包括以下步骤：

步骤一：特征差分和工作量差分计算；

特征差分是指新项目的特征和历史项目的特征差值，即工作量差分是指新项目的工作量和历史项目的工作量差值，即

特征差分和工作量差分一直以来被假设是等量变化的，即但是，本实施例在四个公开的工作量度量数据集Albrecht、Cocomo81、Kemerer和Maxwell上的实验发现这个假设似乎并不成立。

每个数据集都包含了多个项目特征，为了能够研究特征差分和工作量差分的关系，本实施例计算了每个项目的平均特征差分。平均特征差分定义为：

其中m表示数据集每个项目的特征个数。由于每个数据集的数据量都非常有限，因此在每个数据集上本实施例计算了任意两个项目的和Δe，平均特征差分和工作量差分依次在数据集Albrecht、Cocomo81、Kemerer和Maxwell上的关系如图3所示：

图中虚线是实线通过拟合得到，从图可以看出因此并不能简单地假设特征的变化量就等于工作量的变化量。

特征差分和工作量差分并非等量的变化关系，因此发掘它们之间的内在关系，对工作量评估任务非常重要，图4呈现了本实施例通过两段式拟合得到的特征差分和工作量的关系。本实施例采用两段式拟合是因为本申请假设正负特征差分和工作量差分的关系用下面的分段线性函数就可以很好地描述：

图4中的实线是本实施例通过分段线性拟合得到的拟合效果，在Albrecht、Cocomo81、Kemerer和Maxwell上的拟合分别是：0.93、0.44、0.68、0.77，而采用拟合的分别是：0.90、0.44、0.61、0.76。这可以说明本实施例对两者之间分段线性关系的假设是合理的。由图4可知，正的特征差分和负的特征差分确实和工作量的关系不一致。而且可以明显地观察到，正特征差分和工作量差分呈现出比负特征差分更快的变化速率。事实上出现这种现象其实也符合本实施例的认知，这是因为在增加一个特征强度的情况下通常比等量地减少该特征强度要对工作量带来的影响更加剧烈。本实施例把这种现象定义为工作量弹性l，为称为调整因子，因此有：

当采用直线拟合的情况下有：

参数和是后续本实施例算法中需要求解的未知参数，该参数为与特征相关的参数，而与具体的项目无关，因此每个特征都有自己的一组本实施例需要做的就是假设它们的两段式线性关系，具体求解方法是把它们作为蜜蜂算法的位置参数进行搜索优化。

步骤二：目标函数构建；

本实施例首先搜索最佳的相似项目个数和特征权重特征权重矩阵的结构如下所示：

中的每一行代表一个相似的项目每个特征所对应的权重，特征权重需要满足：

如前文所述公式(1)所述，本实施例为每个特征安排了一个两段式的调整函数每个函数包含两个调整因子和两个调整因子都需要满足：因此，对于所有的调整函数表示如下：

基于上述的特征权重和调整因子函数，本实施例首先构造每个项目的平均特征差分

通过本实施例构造出整个问题需要求解的目标函数

BA算法用于求解上述最小化目标函数。通过对所采用的数据集进行灵敏度分析，本实施例确定了BA算法初始化需要设置的参数，并且为每个参数确定了合适的值。表1给出了本研究使用的BA参数及其缩写和初值。下面本实施例简要描述BA为每个新项目寻找最佳值、权重以及调整因子的过程。

表1BA算法主要参数及其初始值设置

BA算法初始化了个解，每个解的值在保证不重复的情况下随机生成，每个解的矩阵在满足约束条件的情况下也随机初始化。解迭代过程诸如前述BA算法所述：首先从个解里面选出个候选解进行邻域搜索，然后根据值评价后，对解进行升序排序，依次从小到大依次得到个最好的解，针对这个解，每个解都进行个邻域解搜索，对于选出的剩余的个解则每个解都进行个邻域解搜索没有被选中的个解则自己随机地在解空间内搜索。上述这样安排的目的是，大量的解都在有前景的解的附近搜索，重复这些步骤，直到满足停止标准(最小MR)或最大迭代次数。

步骤三：工作量计算；

上述最优化目标函数完成迭代后，目标函数里面未知参数都获得了最优值，这时本实施例就可以根据这些最优值计算每个项目的最优的平均特征差分估计本申请的方法是在的基础上根据特征差分的浮动对进行估计，每个相似项目都有一个对的估计，该估计用表示如下：

可能大于也可能小于这取决于平均特征差分

有了每个相似项目对的估计，接下来就是如何合理地对每个项目的估计值进行聚合。工作量聚合步骤通常有较多的方法，比如均值聚合，中位数聚合，百分比聚合，最大和最小值聚合等等。通过比较几种聚合方法，本实施例发现按照相似度排序进行聚合的方法有比较好的优势。因此本实施例采用了相似度排序聚合的方法，该方法具体过程如下：首先，根据从小到大对个相似项目排序；然后第项目的排序结果用标签表示，最后根据下式合成最终的工作量

该估计方法的含义是根据个项目的相似情况进行加权，越相似的项目的权重越大。

至此，本实施例估算工作量的所有过程都介绍完毕，从特征差分计算，到目标函数构建和求解，再到工作量的聚合，本实施例分三个部分对本申请方法的计算过程进行了详细的叙述。需要注意的是，本实施例的度量方法是数据集依赖的方法，因为每个数据集的特征数量和项目个数都不一致，因此在实际应用本申请方法之前应该根据经验首先选择一个可用的数据集，度量新项目的然后再根据本申请叙述的计算过程度量新项目的工作量。

步骤四：评价指标；

工作量度量方法评估的标准是实际工作量和预测工作量之间的误差是否足够小。常用的工作量度量方法评价指标有相对幅度误差(Magnitude Relative Error，MRE)、平均幅度误差(Mean Magnitude Relative Error，MMRE)、中值幅度误差(MedianMagnitude Relative Error，MdMRE)、预测性能(Prediction Performance，PP)。下面分别给出它们各自的计算公式：

MRE计算的是估计值相对于真实值偏离的百分比，它的计算方法如下：

MMRE是用所设计的方法估计个新项目之后对估计结果的MRE取平均：

MdMRE与MMRE的计算方法类似，它是对个新项目的MRE取中值：

PP是指多次预测后，统计MRE不超过25％的项目个数的百分比：

需要说明的是，MMRE虽然被认为是偏向于低估或高估的指标，但本实施例在这里还是使用了这个指标，因为它的确被广泛用于工作量评价预测领域。

步骤五：实验结果评估；

本实施例选择了五个经典的ABE方法：LSE、MLFE、RTM、GA、NN、OABE与本申请方法进行比较。本申请方法中最佳值的值是动态选择的，不需要预先设置最佳值。相比之下，其他算法必须找到几乎适合自身模型的最佳值，因此本实施例对每个模型应用了从1到5的不同设置在各个数据集进行尝试，本实施例平衡了各个数据的差异，为其它方法选择了平均性能最好的值。

为了保证实验结果的稳定性和公平性，本实施例的实验的方法是在每个数据集上按照80％：20％的比例随机地将数据集划分为训练集和测试集，测试集每一个项目都去训练集执行本申请的工作量评价算法，并记录MMRE、MdMRE、PP三个评价指标。每个数据集上述过程重复100次，然后将这100次的所有测试集合的平均值作为最终的实验结果。

综上所述，本申请首先研究了特征差分和工作量差分的关系，实验结果表明特征差分和工作量差分并非现有技术中潜在假设的等量变化关系，即并且本实施例发现正负特征差分变化对工作量差分变化的影响并不一致，正特征差分对工作量差分的影响明显大于负特征差分，即这种现象也完全符合本实施例的认知，因为项目增加单位强度肯定要比减少单位强度对工作量的影响更加显著。据此，本申请提出了两段式拟合方法，对正负特征差分和工作量差分的变化关系分别进行拟合，这样能够更加精确地预估工作量。综上，本申请的贡献在于以下三点：

1)发现了特征差分和工作量差分并非等量变化关系。

2)正特征差分对工作量的影响明显强于负特征差分，并将这个特性考虑到了工作量度量之中。

3)在公开的数据集上进行了算法验证，实验结果表明本申请算法具有较好的性能。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。

Claims (7)

1.一种两段式差分优化驱动的基于类比的工作量度量方法，其特征在于，包括以下步骤：

接收新项目；

确定和新项目类似的历史项目；

计算新项目和历史项目的特征差分；

基于所述特征差分构建目标函数；

使用BA算法对目标函数进行求解，得到最优参数；

基于所述最优参数，对参与计算的每个历史项目的工作量进行加权得到新项目的工作量；

所述特征差分指新项目的特征和历史项目的特征差值，即：

所述特征差分包括正特征差分和负特征差分；

所述目标函数的构建包括以下步骤：

构建特征权重矩阵为：

式中，为和新项目类似的历史项目个数，为特征权重，表示每个项目的特征个数；中的每一行代表一个相似的历史项目中每个特征所对应的权重；

构建调整因子函数为：

式中，为正调整因子，为负调整因子，

；

基于所述特征权重矩阵和调整因子函数，构造每个项目的平均特征差分：

通过构造出需要求解的目标函数：

使用BA算法对目标函数进行求解包括以下步骤：

BA算法初始化个解，每个解的值在保证不重复的情况下随机生成，每个解的矩阵在满足约束条件的情况下也随机初始化；

从个解中选取个候选解进行邻域搜索，根据值进行评价后，对解进行升序排序，从小到大依次得到个最好的解；

针对这个解，每个解都进行个邻域解搜索，对于选出的剩余的个解则每个解都进行个邻域解搜索，其中；

没有被选中的个解则随机地在解空间内搜索；

重复上述步骤，直到满足最小值或最大迭代次数。

2.根据权利要求1所述的一种两段式差分优化驱动的基于类比的工作量度量方法，其特征在于，所述正特征差分和负特征差分和工作量的关系不一致，正特征差分与工作量差分的相关性更强；

定义特征差分与工作量差分的相关性为工作量弹性，为称为调整因子，有：

式中，为工作量差分，即新项目工作量和历史项目工作量的差值，

。

3.根据权利要求2所述的一种两段式差分优化驱动的基于类比的工作量度量方法，其特征在于，当采用直线拟合的情况下有：，，为正调整因子，为负调整因子；项目中每个特征都有一组对应的（）。

4.根据权利要求1所述的一种两段式差分优化驱动的基于类比的工作量度量方法，其特征在于，所述特征权重需要满足：

。

5.根据权利要求1所述的一种两段式差分优化驱动的基于类比的工作量度量方法，其特征在于，所述的最优参数包括最优历史项目参与数、每个特征的正调整因子、每个特征的负调整因子及每个历史项目中各个特征的权重系数。

6.根据权利要求2所述的一种两段式差分优化驱动的基于类比的工作量度量方法，其特征在于，所述对参与计算的每个历史项目的工作量进行加权得到新项目的工作量包括以下步骤：

基于所述最优参数，计算每个项目的最优平均特征差分；

针对每个项目，在历史项目工作量的基础上根据所述最优平均特征差分对新项目工作量进行估计，该估计用表示为：

对参与计算的每个历史项目的估计值进行聚合，得到新项目的工作量。

7.根据权利要求6所述的一种两段式差分优化驱动的基于类比的工作量度量方法，其特征在于，所述对参与计算的每个历史项目的估计值进行聚合具体为按照相似度排序进行聚合，包括以下步骤：

根据每个项目的最优平均特征差分从小到大对个相似历史项目排序；

第项目的排序结果用标签表示，

；

根据下式得到最终计算的新项目工作量：

。