软件众包工人能力动态度量算法

余敦辉，王 意，张万山

(1.湖北大学 计算机与信息工程学院，武汉 430062； 2.湖北省教育信息化工程技术中心，武汉 430062)(*通信作者电子邮箱wangyi365@foxmail.com)

0 引言

随着互联网技术的快速发展，软件众包[1]应用不断增长，大量的软件众包开发平台(例如Topcoder、Kaggle等)被使用，这些平台大多采用在线竞争机制寻找优秀工人完成软件众包开发任务[2]。毋庸置疑，软件众包工人能力度量是任务合理分配的一个关键因素，但现有的很多平台对工人能力度量研究不够深入，缺乏对工人已完成任务的类型、任务复杂度、任务质量、研发时间、工人擅长技能的综合考虑。对此，科学度量软件众包工人的能力，是众包平台亟待的一项具有价值和挑战意义的工作。

当前，学术界对于软件众包工人能力的度量也展开了积极的研究，文献[3]提出一种面向众包的基于信誉值的激励机制，完成众包工人信誉值的度量，实现对众包工人的工作能力的衡量，但对任务完成质量考虑不足；文献[4]提出一种基于活跃度的众包工作者信誉模型，从众包工人活跃度和历史信誉值的角度计算基于活跃度的工人信誉值，以衡量工人的工作能力，但缺乏对任务复杂度和工人完成任务时间的考虑；文献[5]基于任务的客观难度，实现工人完成任务的能力评估，但缺乏对任务类型、任务开发时效的考虑；文献[6]提出一种基于用户可靠性的众包系统任务分配机制，利用完成不同类型任务的可靠性不同，实现工人能力的度量，但并未考虑任务复杂度对工人能力度量值的影响；文献[7]提出基于滑动任务窗的众包质量评估算法，引入专业准确率的概念，对众包工人能力进行度量，但任务类型、任务复杂度对工人能力度量也有实际影响；文献[8]提出一种考虑技能提升的软件众包开发者推荐算法，使用负指数学习曲线模型预测开发人员技能变化，但并未考虑工人静态属性也会对能力度量结果产生一定影响；文献[9]提出一种自适应的软件众包任务-工人匹配算法，借助可扩展的元模型来描述工人技能水平，但缺乏对任务技能权重的考虑；文献[10]提出一种用于预测众包工人绩效的能力需求方法，使用贝叶斯网络模拟不同状态的工人能力，虽然考虑了工人各方面能力，但缺乏对任务本身特性的考虑；文献[11]提出基于模糊层次分析法的社交编程网站开发者度量方法，通过构建开发者度量模型对开发者能力具体量化，但欠缺对工人开发能力的变化的考虑；文献[12]提出跨软件社区的开发人员能力自动建模方法，借助对社区问答(Community Question and Answer, CQA)站点和开源软件(Open Source Software, OSS)社区中的异构信息挖掘，实现开发者的编程能力的建模和评估，但忽略了工人对于不同类型的开发任务其能力度量值不同所产生的影响。由于任务类型、任务复杂度、任务完成质量、工人擅长技能等众多因素都会影响工人能力高低的判断，上述研究没有综合考虑多方面因素，因此评估得到的工人能力高低往往不准确。

为了解决上述问题，本文提出了一种软件众包工人能力动态度量算法(Ability Dynamic Measurement algorithm, ADM)，该算法综合考虑了工人的静态技能属性、已完成任务的类型、任务复杂度、任务质量、任务开发时效、任务技能覆盖率、时间因子等影响工人开发能力度量的多方面因素，并将这些影响因素进行了量化；并且ADM能适用于所有代码行数10万行以下的中小规模软件众包开发任务，与所使用的软件开发语言及任务性质无关。

1 软件众包工人能力动态度量算法模型

1.1 问题描述

ADM算法研究的是基于工人历史完成的所有软件众包任务预测工人对于待分配任务的开发能力。针对该算法提出如下相关概念定义：

定义1 软件众包任务。设某工人历史完成的任务的集合为T={T1,T2,…,Tm}，其中，T1,T2,…,Tm表示按照完成时间先后顺序排列的m个任务。对于某个历史任务Tp∈T，用四元组Tp={D,com,qua,eft}来描述，其中:D表示任务描述信息，包含任务开发目标、应用领域、技能要求、开发期限等；com表示任务复杂度；qua表示任务完成质量；eft表示任务开发时效。用TN表示一个待分配的软件众包任务。

用ski表示工人对于待分配任务的静态技能覆盖率，ski′表示工人对于待分配任务的任务技能覆盖率。软件众包任务的开发技能包括开发语言、开发框架、专业技术、开发类型等。任务技能本身具有技能权重。

1.2 基于静态技能覆盖率的能力初始值计算

对于新加入众包平台的工人，还没有历史完成任务记录，此时，在评估众包工人对于待分配任务的开发能力时，则根据工人在平台上注册的信息，计算工人对于待分配任务的能力初始值。

抽取众包工人在平台上注册的信息F，包含擅长的开发技能、项目经验。擅长的开发技能和项目经验分别对应的权重为w1和w2，满足条件：①w1+w2=1；②w1>w2(认为工人填写的擅长的开发技能比项目经验中包含的技能权重大)。

将skiN中的技能si与F0中的所有技能依次进行比对，如果si与fv比对成功(si在F0中存在即为比对成功)，此时令wh=ws,i及wh′=wf,v，每比对成功一次h加1，h=1,2,…,q，q表示比对成功的个数，由此得到工人对于待分配任务TN的静态技能覆盖率为：

(1)

将ski作为工人U对于待分配任务的初始能力值A0，即A0=ski。

1.3 基于单个历史完成任务的开发能力计算

众包工人的开发能力决定其所胜任的任务难度，影响任务的最终完成质量，同时也影响任务的开发时效。

1.3.1 任务复杂度计算

工人完成的任务难度越大，则工人能力越强。软件众包任务的难度用任务复杂度表示，基于众包工人完成任务后提交的代码进行分析，采用类的方法复杂度(Method Complexity of per Class, MCC)进行度量，参照文献[13-15]所述软件复杂度计算方法计算而来。

设工人完成的任务Tp包含的类的集合为C={c1,c2,…,cx}，x表示类的个数，类ci(i=1,2,…,x)包含的方法的集合为Mi={mi,1,mi,2,…,mi,y}，y表示方法的个数，方法mi, j(j=1,2,…,y)对应的复杂度为mcci, j，复杂度mcci, j采用McCabe度量方法计算，计算式为：

mcci,j=N(mi, j)+1

其中N(mi,j)表示方法mi, j中包含的判定节点数。

参考开源的Eclipse插件Metris工具所给出的判定节点的范围，将判定节点确定为：if、for、while、do、case、catch、&&、||、:?(三目运算符)。由此得到任务Tp的类的方法复杂度为：

(2)

将其归一化，得到任务Tp的复杂度为：

(3)

图1 任务复杂度计算函数曲线Fig.1 Calculation function curve of task complexity

1.3.2 任务完成质量计算

工人完成的软件众包任务获得的评价越高，则任务完成质量越高。任务完成质量越高，则工人能力越强。任务完成质量高低可以由任务发布方对工人提交的任务结果的评价和用户使用软件后反馈的评价作为度量依据。

任务发布方对工人提交的任务结果的评价采用多数表决(Majority Voting, MV)机制进行打分，是站在软件功能、性能的角度进行的评价。设对任务Tp的质量评价为e1，e1∈[0,1]，e1值越大，说明工人完成任务Tp的质量越高，反之则说明质量越低。

由于已将软件项目分解为多个开发模块任务，用户对包含任务Tp的软件的评价即为用户对任务Tp的评价，是站在用户体验的角度进行的评价。设参与任务Tp评价的用户数为num，用户i对任务Tp评价为pi，pi∈[0,1],则用户对任务Tp的平均评分为：

(4)

由此得到任务Tp的完成质量为：

qua=μ·e1+(1-μ)·e2

(5)

其中:μ表示质量评价系数，由于任务发布方相对于用户更能准确评价任务完成质量，因此所占比重大，所以设置μ∈(0.5,1)。在实际应用中，取μ=0.7较为合理。

1.3.3 任务开发时效计算

对于任务Tp，在任务发布方给定的开发期限内，工人实际开发时间越短，则开发时效越高。开发时效越高，则工人能力越强。设任务开发期限为t1，工人实际完成时间为t2(以天为单位计算)，基于任务开发期限和工人实际完成时间，引入反正切归一化函数[4]并修正，得到任务开发时效为：

(6)

任务开发时效计算函数曲线如图2所示(此时假设t1=15)。从图2可以看出，当t2=t1时，任务开发时效eft=0.5；当t2值接近t1时，eft变化速率增大；当t2值远离t1时，eft变化速率减小。

图2 任务开发时效计算函数曲线Fig.2 Calculation function curve of task development time efficiency

1.3.4 开发能力综合计算

基于众包工人U历史完成的单个任务Tp，由任务复杂度com、任务完成质量qua、任务开发时效eft，得到工人完成任务Tp的开发能力度量公式为：

(7)

其中φ表示能力度量系数，由于任务完成质量相对于任务开发时效更能体现工人开发能力，因此所占比重大，所以设置φ∈(0.5,1)。实验结果表明，当φ=0.7时效果最佳。

工人近期完成的软件众包任务更能真实地反映工人当前开发能力，假如工人一段时间内没有任务完成记录，则认为该工人开发能力会有所下降。因此，引入时间因子t，t表示工人历史完成的任务Tp距离当前时间的时间间隔(以月为单位计算,不满一个月按0计算)。定义工人完成任务Tp的开发能力随时间衰减的函数为：

(8)

计算开发能力随时间衰减只针对工人最后完成的单个历史任务，并且满足条件Ap>0，即t<1/λ。其中λ表示能力衰减系数，λ∈(0,0.1)，以此激励工人持续完成软件众包开发任务。实验结果表明，当λ=0.03时效果最佳。

1.4 基于所有历史完成任务的能力度量值动态更新

基于工人历史完成的所有任务的集合T，得到工人开发能力动态更新公式为：

(9)

其中：p=0表示该工人历史完成任务集合T为∅；ε表示能力更新系数，由于工人所有历史任务完成情况相对于当前任务完成情况更能体现工人开发能力，因此所占比重大，所以设置ε∈(0.5,1)。实验结果表明，当ε=0.8时效果最佳。

1.5 基于历史任务技能覆盖率的开发能力计算

当工人历史完成的所有任务对于待分配任务TN的技能覆盖率越高，则工人更擅长完成任务TN，此时，认为工人对于任务TN的开发能力也越高。

1.5.1 历史任务技能覆盖率计算

对于工人历史完成的所有任务的集合T，从每个任务的任务描述D中提取出相关的开发技能，得到每个任务包含的技能集合，以及每个技能对应的技能权重。对所有历史任务包含的技能进行分类，相同的技能分为一类，由不同类的技能组成新的技能集合。将相同类中所有技能对应的技能权重相加求和，将求得的和除以m(m表示集合T中任务的个数)得到该类技能对应的新的技能权重。新的技能集合以及新的技能权重描述如下。

与1.2节中计算静态技能覆盖率方法相同，将待分配任务TN的技能集合skiN中的技能与历史任务技能集合skiT中的所有技能依次进行比对，计算得到工人对于待分配任务TN的任务技能覆盖率为ski′。

1.5.2 开发能力最终计算

基于历史任务技能覆盖率ski′，得到工人对于待分配任务TN的开发能力为：

(10)

综上可知，工人想要提升能力度量值并且获得待分配任务，则需要持续高质量、高时效的完成复杂度较高的且擅长技能相似的开发任务，从而对众包工人产生激励作用。

2 ADM算法

2.1 ADM算法具体实现

ADM算法的输入为某众包工人U、该工人历史完成的所有软件众包任务集合T和待分配任务TN，计算出众包工人U对于待分配任务TN的动态开发能力AT,N，并将AT,N作为输出返回给众包平台。

ADM算法的具体执行过程如算法1所示。

算法1 能力动态度量算法ADM。

输入 众包工人U，工人历史完成的所有软件众包任务集合T，待分配任务TN。

输出 工人动态开发能力度量值AT,N。

基于静态技能覆盖率ski计算工人初始能力值A0；

ifT≠∅；

将T中的任务按照完成的时间先后顺序进行排序;

for (每个任务Tp∈T)

通过McCabe度量方法计算任务复杂度com；

综合任务发布者和用户的打分计算任务完成质量qua；

通过任务开发期限和工人实际开发时间计算任务开发时效

eft；

基于时间因子t，计算工人完成任务Tp随时间衰减的开发能

力Ap；

基于工人历史完成的所有任务，按照任务完成的时间先后顺

end for；

通过任务技能权重计算历史任务技能覆盖率ski′；

基于ski′计算工人对于待分配任务TN的开发能力AT,N；

end if；

returnAT,N。

根据上述算法，计算出工人对于待分配任务的开发能力，众包平台可以基于工人开发能力合理分配任务。

2.2 算法复杂度分析

ADM算法复杂度主要由两部分构成:1)基于静态技能覆盖率计算中，时间复杂度主要由技能归类和技能比对时产生，由工人注册信息包含的技能个数n1与待分配任务包含的技能个数n2决定，为O(n1·n2)。2)基于历史任务技能覆盖率计算中，时间复杂度主要由技能归类和技能比对时产生，由所有历史任务包含的技能个数n3与待分配任务包含的技能个数n2决定，为O(n2·n3)。由此得到ADM算法复杂度的量级为O((n1+n3)·n2)。

3 实验结果与分析

为了验证本文所提出的ADM算法的合理性与有效性，从开源中国众包平台上抓取了1 000个众包工人、6 000个历史完成的软件众包开发任务和500个待分配任务，将其作为实验数据集。抓取的任务包括移动应用、H5应用、微信应用、企业应用、Web应用、工具应用、桌面应用、嵌入式应用、游戏开发等类型。对抓取的数据进行预处理后，任务信息包括开发技能及对应的技能权重、开发期限、工人实际开发时间(天)、完成任务时距离当前时间间隔(月)、任务发布方和用户对任务质量的评分，工人信息包括擅长的开发技能及对应的技能熟练程度、多个项目经验。

3.1 相关参数的确定

基于数据集中选取的1 000个众包工人，将每个工人历史完成的软件众包任务按照任务完成时间先后顺序排序。

对于每个工人历史完成的每个任务：①计算任务完成质量qua，将qua作为工人完成此任务的实际开发能力值，记为A′；②计算工人在此任务之前完成的所有任务对于此任务的预测能力值，记为A；③计算预测能力值与实际开发能力值之间的吻合度，记为fg=1-|(A-A′)/A′|。对于每个工人历史完成所有任务，计算吻合度平均值。进行如下验证实验:

1)能力衰减系数λ与吻合度平均值之间的关系。

在λ分别取值为0.01,0.02,…,0.09时，计算得到系数λ与吻合度平均值之间的关系,结果如图3(a)所示。

2)能力更新系数ε与吻合度平均值之间的关系。

在ε分别取值为0.55,0.60,…,0.95时，计算得到系数ε与吻合度平均值之间的关系如图3(b)所示。

3)能力度量系数φ与吻合度平均值之间的关系。

在φ分别取值为0.55,0.60,…,0.95时，计算得到系数φ与吻合度平均值之间的关系如图3(c)所示。

由图3(a)可知，当能力衰减系数λ=0.03时，工人预测能力值与实际开发能力值之间的吻合度平均值最高，达到87.2%；由图3(b)可知，当能力更新系数ε=0.8时，吻合度

平均值最高，达到88.6%；由图3(c)可知，当能力度量系数φ=0.7时，吻合度平均值最高，达到86.8%。

3.2 合理性验证

为验证众包工人每次完成任务后能力度量值变化情况，首先计算工人完成单个任务的能力值,然后计算工人完成此任务后动态更新的能力值，得到工人能力度量值动态更新过程如图4所示。

由图4可知，当工人完成单个任务的能力值高于前一次动态更新的能力值时，工人的能力值增加，反之能力值下降;并且随着完成任务个数的增加，工人的能力值也在缓慢地增加或减少，不会因为一次、两次较好或者较差地完成开发任务而对工人能力度量值有较大影响。

随着工人完成任务数量的增加，历史任务包含的开发技能会增多，历史任务技能覆盖率就会增加，工人熟悉的技能增多，任务完成质量会提高、开发时效会加快，能力度量值会增大，工人能力增强，可能会请求难度更高的任务。但工人有时完成任务情况不好，能力度量值也会有所波动。

3.3 有效性验证

将ADM与文献[6]中的用户可靠性度量算法(User Reliability Measurement algorithm, URM)进行对比实验。URM根据用户完成任务的质量评价更新用户可靠性，计算式为：

1)历史任务时间周期对算法效果的影响。

设定时间因子t=0，计算1 000个众包工人能力吻合度平均值，在每轮计算中依次使时间因子t增加1,得到时间因子t与能力吻合度之间的关系如图5所示。

由图5可知，URM随着时间因子t的增加，能力吻合度会逐渐降低，根据URM计算的工人能力预测值只考虑任务完成质量，将工人之前完成任务的情况用于衡量工人完成下一个任务的预测能力值，而实际上工人完成的任务距离当前时间越远，工人实际开发能力值会有所下降，完成下一个任务的质量可能会降低，因此能力预测值与实际开发能力值之间的误差会增大，吻合度会降低。

图5 时间因子t与能力吻合度之间的关系Fig. 5 Relationship between time factor t and coincidence degree of ability

ADM随着时间因子t的增加，能力吻合度基本保持在85%附近，因为在能力度量过程中考虑了时间因子t对工人能力度量值的影响，能力预测值与实际开发能力值之间的误差会比较小，因此能力吻合度并不受时间因子t的影响。当t≥1/λ时，工人能力不再衰减，所以ADM在时间周期1/λ内有效。

2)历史任务数量对算法效果的影响。

计算工人每完成一个任务对于下一个任务的预测能力值。得到历史任务数量与能力吻合度之间的关系如图6所示。

图6 历史任务数量与能力吻合度之间的关系Fig. 6 Relationship between number of historical tasks and coincidence degree of ability

由图6可知，URM随着历史完成任务数量的增加，能力吻合度快速上升，逐渐趋于稳定，保持在82%附近。ADM随着历史完成任务数量的增加，能力吻合度起初会逐渐缓慢地增加，最高达到90.5%，然后保持在89%附近。

在URM中，考虑了任务类型和任务完成质量，在ADM中，考虑了任务技能和任务完成质量等多因素。随着历史任务数量的增加，两种算法工人完成任务会更熟练，任务完成质量会提高，计算的预测能力值会更符合实际能力值，因此吻合度会上升。

历史任务数量对ADM效果的影响比较小，因为每个工人对于待分配任务的预测能力值都是基于历史任务完成情况以及技能覆盖率来计算的。在历史任务数量不足的情况下，同样能较准确地计算出不同工人对于同一个待分配任务的预测能力值，能有效地将不同工人的开发能力区别开来，因此，众包平台可以基于工人开发能力合理分配任务。

4 结语

本文针对软件众包平台中的工人能力度量算法进行研究，综合考虑了工人静态技能属性、任务类型、任务复杂度、任务质量、任务开发时效、任务技能覆盖率等影响工人开发能力度量的多方面因素，并将这些影响因素进行了量化，从而提出了一种软件众包工人能力动态度量算法(ADM)，实现了工人能力的度量和动态更新，以激励工人持续高质量、高时效地完成软件众包任务。该算法主要解决了已有研究中存在的工人能力考虑不足而导致分配给工人的任务完成质量低下的问题。仿真实验结果验证了所提算法的合理性与有效性，为后续研究基于工人的能力度量值进行多任务-多工人分配提供了理论依据。