0 概述

随着互联网的快速发展, 众包服务已引起各领域的广泛关注。相对传统外包模式, 众包模式^[1-2]的发展为任务发布者和任务请求者提供了极大的便利。随着众包模式的发展, 越来越多的用户选择采用众包模式发布软件任务, 这使得对于众包软件这一课题的研究更加有意义。然而, 由于众包平台的发包方和工人具有不确定性, 因此如何有效准确地将多样性任务分配给能力参差不齐的工人是亟待解决的问题^[3]。

在此背景下, 国内外众多学者在该领域展开研究。文献[4]根据历史完成情况和当前完成情况对工人进行综合评定, 提高任务分配精度。文献[5]根据工人性格对工人能力进行度量, 但对于任务属性考虑不足。文献[6]从基本信息、能力、资源和描述4个维度建立任务模型, 并基于SIMFT算法向工人推荐任务。该方法虽然考虑到了任务模型对于完成质量的影响, 但并未深入考虑任务复杂度等影响因子。文献[7]基于多元线性回归得出影响任务质量的潜在因素, 但该方法得出的“任务名称每增加一个英文单词, 参与率降低1.491”结论的普适性有待商榷。文献[8]得出众包任务的质量很大程度上受到任务难度影响的结论, 但未考虑任务完成后可能需要维护以及用户对各任务重视程度不一致等问题, 可能出现用户不满意导致返工的情况。

鉴于现有研究仍存在对模块质量、模块重要度考虑不足以及工人能力利用不充分的问题, 本文提出一种基于核心度排序的软件众包模块分配算法。该算法综合考虑模块复杂度、模块质量、模块重要度, 为软件模块挑选出最合适的工人。

1 问题模型

本文研究的软件众包任务均为基于竞标模式的复杂任务, 相关定义及问题描述具体如下:

定义1 (模块)  模块是指已经过众包平台架构师分解的软件任务, 其定义为一个四元组, M={D_m, S_m, U_m, C_m}, 其中, D_m表示模块的复杂度, S_m表示模块的质量, U_m表示模块的重要度, C_m表示模块的核心度。

定义2(软件模块网络)  软件模块网络定义为一个有向网络G_d=(V_d, E_d), 其中, 结点v_d(v_d∈V_d)代表软件项目中的模块, 如果2个模块之间存在依赖关系, 则构成有向边e_ij(e_ij∈E_d)。

2 模块复杂度计算

模块复杂度的度量对于提升模块质量、缩短开发周期具有重要作用, 本文描述的模块复杂度主要包括结构复杂度和技术复杂度^[9-11]。

结构复杂度可根据软件模块网络计算得到, 用来衡量软件项目中各模块之间的依赖关系, 依赖关系越多, 结构复杂度越高。本文主要考虑以下4种依赖情况^[12]:

1) 实现, 假设v₁类实现了v₂接口, 则存在有向边e₁₂=<v₁, v₂>, 边的权值用w₁表示。

2) 泛化, 假设v₃类继承了v₄类的功能, 则存在有向边e₃₄=<v₃, v₄>, 边的权值用w₂表示。

3) 依赖, 假设v₅类的变化会引起v₆类的变化, 则存在有向边e₅₆=<v₅, v₆>, 边的权值用w₃表示。

4) 关联, 假设v₇类和v₈类之间有一定的联系, 该关系使得一个类知道另一个类的属性和方法, 则存在有向边e₇₈=<v₇, v₈>, 边的权值用w₄表示。

考虑到上述4种关系在实际开发中依赖程度不同, 因此本文约定w₁+w₂+w₃+w₄=1。假设某个软件项目中共有m个模块, 对于模块i而言其结构复杂度f_i为:

$ {f_i} = {{\rm{e}}^{{{\left( { - \sum {{w_1}} + \sum {{w_2}} + \sum {{w_3}} + \sum {{w_4}} } \right)}^{ - 1}}}} $

(1)

考虑到实际开发中可能存在模块结构较简单, 但技术实现困难的情况, 为更好地度量模块的技术复杂度, 本文采用专家打分的方式对模块技术复杂度进行打分(满分为10分), 假设共有h名专家进行打分, 对于模块i而言其技术复杂度为:

$ {g_i} = \frac{1}{{10h}}\sum\limits_{j = 1}^h {scor{e_j}} $

(2)

其中, score_j表示第j个专家给出的分数。

模块复杂度D为:

$ D = \delta {f_i} + \left( {1 - \delta } \right){g_i} $

(3)

其中, δ为常数, 具体数值由众包平台指定。

3 模块质量计算

考虑到模块的完成质量与工人的能力具有很强的关联性, 但未进行开发之前, 待开发模块的质量未知, 因此需要借助已有的相似模块进行估测。本节给出基于余弦相似度算法的模块相似度度量方法、已完成模块的质量计算方法以及待开发模块的质量估测方法。

3.1 基于余弦相似度算法的模块相似度度量

余弦相似度是利用空间向量夹角的余弦来衡量对象间的差异, 余弦值越接近1, 表明夹角越接近0, 2个向量越相似^[13-15]。假设历史模块集合DB是一个三元组, DB=(P, A, R), 其中, P表示模块集, P={P₁, P₂, …, P_e}, A表示模块的属性集合, A={A₁, A₂, …, A_g}, R表示模块P的属性A的取值, 即R_ab={P_a(A_b)}表示第a个模块的第b个属性的取值。

模块p、q的余弦相似度计算如下:

$ sim\left( {p,q} \right) = \frac{{\sum\limits_{i = 1}^n {\left( {{R_{pi}} \times {R_{qi}}} \right)} }}{{\sqrt {\sum\limits_{i = 1}^n {{{\left( {{R_{pi}}} \right)}^2}} } \times \sqrt {\sum\limits_{i = 1}^n {{{\left( {{R_{qi}}} \right)}^2}} } }} $

(4)

其中, 属性R_pi取值如下:

$ {R_{pi}} = \left\{ \begin{array}{l} 1,文本型,存在该属性\\ 0,文本型,不存在该属性\\ \frac{{{R_{pi}}}}{{{R_{pi}} + {R_{qi}}}},数值型 \end{array} \right. $

(5)

模块属性取值如表 1所示。p₀、p₁属性取值如表 2所示。p₀、p₂属性取值如表 3所示。

p₀、p₁的余弦相似度计算如下:

$ sim\left( {{p_0},{p_1}} \right) = \frac{{1 + 0.47 \times 0.53 + 0.52 \times 0.48}}{{\sqrt {{1^2} + {{0.47}^2} + {{0.52}^2}} \times \sqrt {{1^2} + {{0.53}^2} + {{0.48}^2}} }} = 0.998 $

p₀、p₂的余弦相似度计算如下:

$ \begin{array}{l} sim\left( {{p_0},{p_2}} \right) = \frac{{0 + 0 + 0.51 \times 0.49 + 0.55 \times 0.45}}{{\sqrt {{1^2} + 0 + {{0.51}^2} + {{0.55}^2}} \times \sqrt {0 + {1^2} + {{0.49}^2} + {{0.45}^2}} }} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0.332 \end{array} $

经计算易知, p₀与p₁最相似。考虑到不同属性的影响程度不同, 在实际使用中, 众包平台也可根据具体情况为不同属性赋予不同的权值。

3.2 已完成模块的质量计算

由于任务完成质量差导致某些模块经常需要维护且用户满意度较低, 因此模块维护频率、维护时长、用户评分可以有效反映模块质量, 假设F_m为第k个模块的维护频率, T_m为第k个模块的维护时长, Z_k为用户对第k个模块的评分(满分为10分), 假设平台已完成m个模块, 用S_k表示第k个模块的完成质量。

$ {S_k} = a\frac{{\min \left( {{F_m}} \right)}}{{{F_k}}} + b\frac{{\min \left( {{T_m}} \right)}}{{{T_k}}} + c\frac{{{Z_k}}}{{\max \left( {{Z_m}} \right)}} $

(6)

其中, a、b、c为权值, 并且满足a+b+c=1, 0<a, b, c<1, 该权值由众包平台根据实际情况指定。

3.3 待开发模块的质量计算

在计算待开发模块质量时, 首先计算待开发模块与已开发模块的相似度, 选出相似度最高的前K个模块, 待开发模块A的质量计算如下:

$ {S_A} = {{\rm{e}}^{{{\left( { - \sum\limits_{i = 1}^K {{S_{ki}}} } \right)}^{ - 1}}}} $

(7)

4 模块重要度计算

若要缩短软件周期, 则需缩短位于关键路径上的模块开发周期, 因此应该尽可能为关键路径上的模块分配能力更高的工人^[16]。

本文假设已经构建待开发项目的AOE网, 假设关键路径上的结点集合key={k₁, k₂, …, k_m}, 其中每一个结点代表一个模块。根据文献[17]方法, 容易计算得到关键路径, 假设计算得到n条关键路径, 获得相应的结点集合key₁, key₂, …, key_n, 则位于关键路径上的结点集合最终为:

$ KEY = \bigcup\limits_{i = 1}^n {ke{y_i}} $

(8)

对KEY中的结点按照开发的先后排序得到集合KEY′, 假设KEY′内有V个结点, 对于第t个结点对应模块的重要度U_t计算如下:

$ U_{t}=L \times t+L_{0} $

(9)

其中, L<0, L₀为初始值。

假设集合UKEY表示非关键路径上的结点, 则有:UKEY=KEY, 对于UKEY中的结点T, 其对应模块的重要度U_T计算如下:

$ U_{T}=w+L_{0} $

(10)

其中, w为常数, L₀与w均由众包平台指定, 该值可根据项目的紧急程度、发包方对平台的重要程度等因素确定。

5 基于核心度排序的软件众包任务分配 5.1 模块核心度计算

鉴于模块复杂度考虑不足时可能会将简单模块分配给高级工人导致工人能力利用不充分, 模块质量考虑不足时可能将质量要求较高的模块分配给初级工人造成任务完成质量低, 模块重要度考虑不足时可能会将位于关键路径上的模块分配给初级工人造成软件开发延期。为此, 本文提出核心度的概念, 模块核心度是模块复杂度、模块质量、模块重要度的综合体现, 用以表示模块的主要特性, 模块核心度C_v具体计算如下:

$ {C_v} = \alpha \times {{\rm{e}}^{{{\left( { - \sum\limits_{v = 1}^m {{D_v}} } \right)}^{ - 1}}}} + \beta \times {{\rm{e}}^{ - \sum\limits_{v = 1}^m {{S_v}} }} + \gamma \times {{\rm{e}}^{{{\left( { - \sum\limits_{v = 1}^m {{U_v}} } \right)}^{ - 1}}}} $

(11)

其中, α、β、γ为权值并且满足α+β+γ=1, 0<α, β, γ<1, D_v表示第v个模块的复杂度, S_v表示第v个模块的质量, U_v表示第v个模块的重要度。

5.2 软件众包任务分配算法

本节提出基于核心度排序的软件众包任务分配算法(CMA), 先计算模块的核心度, 将得到的模块核心度从大到小排序, 再按照文献[18]方法进行工人打分并按照从高到低的顺序进行排序。鉴于本文研究重点是模块核心度, 为方便描述, 忽略了模块之间所需工人技能的差异。

在进行工人任务匹配时, 本文采取文献[19]方法, 即按照模块核心度从大到小依次分配时, 每次从工人集合中选出能力最强的工人对其进行任务匹配。这样分配可以保证核心度最高的模块由技能最高的工人完成, 在一定程度上可提升团队开发效率, 缩短开发时间。CMA算法具体描述如下:

输入   待开发模块集合WM、工人集合W、模块个数N

输出   工人-任务匹配集合L

1.计算各模块的结构复杂度;

2.计算各模块的技术复杂度;

3.计算各模块的复杂度;

4.找出与待开发模块相似的k个历史模块;

5.计算待开发模块的质量;

6.计算各模块的重要度;

7.计算各模块的核心度得到核心度集合core;

8.将core内的元素从大到小排序;

9.采用负指数模型对工人进行打分, 得到工人分数集合score;

10.将score按从大到小排序;

11.for i←|core|

12.L[i].core=core[i];

13.L[i].score=score[i];

14.end for

15.return L;

6 实验结果与分析

鉴于软件众包领域缺乏基准数据集, 本文爬取程序员客栈和威客众包平台的3 764条数据, 从这些数据中获取了软件的维护情况、用户对软件的评分、模块重要度, 参考文献[11, 18]的研究, 增加了模块复杂度及工人技能评分2个指标, 并根据SCM模型和工作者质量评估模型对指标值进行生成。实验在具有2.9 GHz Inter(R)Core(TM) i7-7500U处理器和12 GB内存的机器上运行, 操作系统为Windows10, 编程语言为Matlab。

6.1 算法对比

将本文提出的基于核心度排序的软件众包任务分配算法分别与以下算法进行对比:

1) 复杂度优先算法(CFA)^[7], 即在每次分配时将复杂度最大的模块分配给能力最高的工人。

2) 质量优先算法(QFA), 即在每次分配时将质量最差的模块分配给能力最高的工人。

3) 重要度优先算法(KFA), 即在每次分配时将重要度最大的模块分配给能力最高的工人。

为满足分配需求, 本文按照模块数与工人3:4的比例进行分配, 每次实验从数据集中随机抽取特定数量的模块进行实验, 每个实验重复10次, 实验结果取平均值, 部分参数(或常数)设定如下:δ=0.5, L₀=1, w=-0.5, t=0.05。

为比较不同算法的优劣, 本文提出适配值的概念, 具体如下:

$ r = \frac{1}{{\sum\limits_{i = 1}^N {\left( {\left( {{x_i} - {y_i}} \right) - \overline {\left( {{x_i} - {y_i}} \right)} } \right)} }} $

(12)

其中, N表示模块数, x_i表示第i个工人得分, y_i表示指标数值, 该指标可以是模块复杂度、模块质量、模块重要度, $\overline{\left(x_{i}-y_{i}\right)}$表示一组实验中x_i与y_i差值的平均值。

由图 1~图 6可以看出, 本文算法与CFA算法相比质量适配值至少提升33.9, 重要度适配值至少提升57.2;与QFA算法相比复杂度适配值至少提升27.7, 重要度适配值至少提升57.9;与KFA算法相比复杂度适配值至少提升29.9, 质量适配值至少提升27.8。

6.2 参数取值讨论

对于式(6)、式(11)中的参数, 综合考虑每个影响因子在实际开发中的影响效果及其约束条件, 本文将a、b、c、α、β、γ的取值范围限定于[0.2, 0.5]内, 讨论参数权值组合对适配值的影响。根据图 7、图 8并结合a+b+c=1、α+β+γ=1可知, 当α=0.3、β=0.5、γ=0.2、a=0.3、b=0.3、c=0.4时适配置最大, 任务分配效益最高。

7 结束语

本文针对当前软件众包任务分配中模块核心度考虑不足的问题, 提出基于核心度排序的众包软件模块分配算法。实验结果表明, 该算法可有效提升众包工人能力利用率, 众包模块开发质量, 并缩短开发周期。由于本文重点研究了任务属性对任务质量的影响, 对于工人和任务的匹配考虑比较单一, 因此下一步可在此基础上考虑工人间的合作关系及工人对不同技能的熟练程度等, 更好实现众包工人与任务的匹配。