軟件眾包工人能力動態度量算法

余敦輝，王 意，張萬山

(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)，實現了工人能力的度量和動態更新，以激勵工人持續高質量、高時效地完成軟件眾包任務。該算法主要解決了已有研究中存在的工人能力考慮不足而導致分配給工人的任務完成質量低下的問題。仿真實驗結果驗證了所提算法的合理性與有效性，為后續研究基于工人的能力度量值進行多任務-多工人分配提供了理論依據。