支持工人能力模糊度量和角色協同的軟件眾包任務分配*

馬 華，陳躍鵬，黃卓軒，唐文勝，婁小平

(湖南師范大學 信息科學與工程學院, 湖南 長沙 410081)

近年來，以開源眾包、任務中國、亞馬遜Mechanical Turk和TopCoder等為代表的軟件眾包平臺發展迅速。依托它們，傳統的封閉式、高成本、低效率的軟件開發過程逐漸呈現出開放式、高性價比、高效率的團體間多人協作的新范式[1]。隨著大量眾包任務被不斷發布，越來越多的軟件技術人員以眾包工人的角色加入軟件眾包的協同開發過程。綜合考慮工人的歷史表現和任務的屬性特征以準確度量眾包工人的綜合能力，實現眾包任務和工人間多對多模式下的分配優化，對于確保眾包平臺獲得最佳的整體任務完成質量，具有重要的理論價值和現實意義。

軟件眾包平臺通常采用在線競爭機制挑選優秀的眾包工人來承接任務。而工人工作能力的準確度量是眾包任務分配前首先需考慮的關鍵因素，它直接影響到任務的最終完成質量[2]。現有研究尚缺乏對工人能力的全面分析，未綜合考慮眾包任務與工人能力的匹配程度對分配結果的影響[3]，現有的基于單一值的描述機制也無法客觀反映工人實際能力的不確定性。同時，現有研究主要采用基于匹配和基于規劃的任務分配模型，關注的是面向單個工人的一對一型和一對多型分配問題，尚未涉及面向眾包平臺的多對多型分配問題[3-4]。

多對多型分配問題從軟件眾包平臺的角度考慮如何將一組相關任務分配給具有協作關系的工人，以獲得最佳的全局任務完成質量。由此，多對多型任務分配本質上可視為一個典型的基于角色協同[5](role-based collaboration，RBC)問題。作為RBC的核心模型，E-CARGO[6-7]使用一組核心概念建立組角色分配相關的數學模型，之前基于E-CARGO的任務分配優化研究[8]可為解決多對多型眾包任務分配提供重要的求解范式。

基于此，本文提出支持工人能力模糊度量和角色協同的軟件眾包任務分配方法。該方法通過結合工人的歷史表現和任務的需求期望，采用模糊區間數[9]評估工人的多屬性能力匹配度，以模糊層次分析法計算工人的綜合勝任能力，并引入RBC理論和E-CARGO模型對多對多型任務分配問題進行系統的形式化建模和約束分析，給出了一種有效的問題求解方法，以確保獲得最優的整體任務完成質量。

1 相關工作

1.1 眾包工人能力的綜合度量

眾包工人能力度量的傳統策略包括基于黃金標準數據的策略[10]、多階段動態眾包質量評估策略[11]、基于熵的眾包質量評估策略[12]和基于投票的一次性策略[13]等。并且，基于歷史數據對工人進行信譽評估，有助于全面了解工人的綜合能力。芮蘭蘭等[14]引入懲罰激勵因子來處罰惡意工人和激勵理性工人提高任務完成質量。借鑒滴滴出行軟件中司機服務的星級評價，冉家敏等[15]將空間眾包中工人的歷史等級評價轉化為服務質量評價，綜合當前評價和歷史評價來計算工人得分。針對眾包全景拼接系統特點，李沁雅等[16]通過量化街景圖像對全景地圖構建的貢獻度來確定圖像質量，以此評估工人能力，并將其與工人酬勞相結合來激勵參與者。

現有研究主要使用單一的確定值描述工人的能力。但是，軟件技術人員在實施不同項目時，可能受到物質或精神激勵、情緒、知識儲備和技術成熟度等諸多影響，工作表現并不穩定。從而，在度量工人的綜合能力時，不能忽視其具有的不確定性本質。

1.2 眾包任務的分配方法

眾包模型主要可分為兩類：①基于社會網絡的復雜任務群智協同眾包模型[4]。它不要求發包者自己分解一個復雜任務，而是由接收任務的工人通過組織其合作者來一起完成任務。可免除發包者的任務分解負擔，但增加了模型相關的計算量和對工人社會屬性深度挖掘的復雜性，實際應用時仍有諸多問題需解決。②基于任務分解的復雜任務眾包模型[17]。它要求發包者具備良好的任務分解能力，也要求工人提交的結果具有良好的兼容性。綜合考慮可行性和時效性，實際眾包應用平臺大多采用該模型。

基于任務分解的復雜任務眾包模型又可細分為兩類：①基于匹配的任務分配模型[3]。它使用二分圖匹配，根據任務與工人的時間、空間、狀態等特征，并結合工人的信譽值或可信度等，為每名工人分配一項任務，即一對一型任務分配。Mechanical Turk、豬八戒網等傳統眾包平臺以及滴滴出行、美團眾包等空間眾包平臺均屬此類。②基于規劃的任務分配模型[3]。它類似于旅行商問題模型，研究眾包平臺如何為一個眾包工人分配合理的任務執行順序和方案，本質上是針對一對多型的任務分配問題，即為一個工人分配多個任務以達到最優的工作組合。考慮到工人的最晚工作時間約束，結合樹分解和深度優先搜索方法[18]可獲得任務分配最優方案。

隨著越來越多的任務被同時發布，眾包平臺可能存在大量具有相似特點和需求的相關任務。此時的任務分配問題呈現出“多對多”特征，即眾包平臺如何將多個相關任務分配給合適的多個工人，這是一個NP難問題。不同于傳統的一對一或一對多視角，它需要從眾包平臺整體的角度來考慮如何實現多個任務與工人間的組合優化[3]，以幫助眾包平臺獲得全局最佳的任務完成質量。

2 問題描述

假定軟件眾包平臺中某一版塊新發布了一個軟件開發項目，分解該項目后得到n個待分配任務，以R={r0,r1,…,rn-1}表示任務集(task set)，假設在報酬激勵下有m個候選工人申請參加該項目，以A={a0,a1,…,am-1}表示工人組(worker group)。則該多對多型軟件眾包任務分配問題的特點包括：

1) 每個rj(0≤j

2) 不失一般性，假定每個ai(0≤i

3) 同一項目中的不同任務的重要性不同。顯然，一些關鍵任務會相比非關鍵任務對于項目的完成具有更重要的影響。因此，在任務分配時應為關鍵任務分配能力更強的優秀工人。

4) 考慮到現實世界中眾包工人與任務之間可能存在的各種沖突因素，例如完成任務的時間沖突、合作習慣的沖突以及地理位置的沖突等[1]，導致某些工人無法在一起高效地合作開展工作，即工人之間可能存在協作沖突，這些工人不能被分配參與同一任務或項目。

5) 結合眾包平臺上的歷史數據，從技能水平、任務完成效率、任務完成質量、平臺活躍程度4個指標對ai的能力進行綜合評價。其中，技能水平反映工人的軟件設計、開發、測試等方面的專業能力熟練程度；任務完成效率體現工人完成任務的時效性；任務完成質量體現工人最終提交的成果的優劣程度；平臺活躍程度反映工人的社交和協作意愿。以上每項指標可由多個子指標來進一步刻畫。例如，工人技能水平可從崗位(如前端工程師、開發工程師)、應用類型(如移動應用、微信應用)、開發語言(如Java、HTML5)等方面進行精細度量。通常而言，參與任務的工人的綜合能力越強，該任務的最終完成質量越高。

6)為確保獲得理想的眾包任務完成質量并控制好項目成本開支，發包者可分別對參與rj的ai的各個能力指標設定需求期望(或偏好)[19]。需求期望體現了任務對工人能力的閾值要求。例如，一個工人曾獨立完成過高難度的任務，但其平臺活躍度和任務完成效率偏低，則該工人并不適合參加對協作性、實時性要求較高的任務。現實中，工人的綜合能力越強，通常其雇傭成本也越高，因此，有必要遵循“工人能力夠用即可”原則來挑選工人，通過合理設定各個任務的需求期望，以兼顧項目的整體經費開支。

綜上，多對多型軟件眾包任務分配問題，就是在滿足給定約束的前提下，基于工人的多指標能力評估和任務需求期望分析，建立n個任務和m個候選者之間的映射關系，為各個待分配任務尋找綜合能力盡可能優秀的候選工人，并確保為所有任務挑選出來的工人的全局綜合勝任度最高，從而爭取整個項目獲得最優的完成質量。

3 基于模糊區間數的眾包工人能力度量

3.1 基本定義

定義1區間數。設bL、bH是兩個實數，如果B=[bL,bH]，0≤bL≤bH≤1，則稱B為一個區間數。bL和bH分別稱為區間的下限和上限。

3.2 基于歷史評價的工人能力模糊度量計算

(1)

(2)

3.3 任務需求期望導向的工人能力匹配度計算

(3)

由式(3)可計算工人與每個任務在各個評價指標的可能度，并最終得到工人與任務兩兩之間關于評價指標匹配度的模糊決策矩陣P，Pi,j,k表示第i(0≤i

3.4 工人能力評價指標權重的模糊層次分析

在實時型或協作頻繁型應用等場景下，發包者對工人的各個能力指標的需求存在差異性。模糊層次分析(fuzzy analytic hierarchy process，FAHP)既可減少主觀設定權重的偏差，又可避免計算量大且精度不高的問題，適用于解決多指標綜合問題[22]。令模糊判斷矩陣B=[bi, j]n×n，滿足0≤bi, j≤1，n是工人能力指標個數。bi, j是第i個能力指標與第j個能力指標的重要性之比。采用由0.1、0.3、0.5、0.7、0.9構成的五級互補標度[21]確定bi， j。

矩陣B滿足bi， j+bj， i=1，bi， i=0.5，B為模糊互補判斷矩陣。當滿足bi， j=bi， k-bj， k+0.5時，B為模糊一致性矩陣。令bi為模糊互補矩陣中第i行之和，按式(4)[23]將B轉換為模糊一致性矩陣。

zi， j=(bi-bj)/[2(n-1)]+0.5

(4)

僅Z=[zi， j]n×n是模糊一致性矩陣，n=4。計算Z中每行的和，并進行標準化處理，按式(5)獲得工人能力指標的權重向量W=[w1,w2,…,w4]。

(5)

3.5 基于能力模糊度量的工人綜合勝任度計算

基于能力指標的權重向量，最終可獲得各個ai完成rj的綜合勝任度，計算方法如式(6)所示。

(6)

Qi, j表示工人ai對于任務rj的綜合勝任能力，該值越大，說明此工人對于該項任務的勝任力越強，則將來可以獲得更高的任務完成質量。

4 基于角色協同的眾包任務分配模型

4.1 基本模型

借鑒E-CARGO模型[6-8]，多對多型軟件眾包任務分配問題可抽象為：∑::=〈E,C,O,R,A,G〉。 其中：E表示一個涉及多個工人和多個任務的問題環境environment；C是E中抽象概念的類(class)集合；O是與C相關的具體對象(object)集合；R是待分配的任務集合，它對應RBC中的role；A是候選的工人集合，它對應RBC中的agent；G是工作組(group)，即由任務分配算法建立的工人團隊。 令m=|A|表示候選工人的數量，n=|R|表示待分配的眾包任務的數量。 模型中的關鍵組件包括：

1) 工人綜合能力評估矩陣Q：它表示工人ai對于待分配任務rj的勝任程度。 工人的綜合能力可通過工人的技能水平、歷史任務完成效率和完成質量、平臺活躍程度等因素[1]來衡量，Q的計算方法如式(7)所示。

2) 任務分配矩陣T：Ti, j∈{0,1}(0≤i0是Ti, j=1的充分條件，否則無解，即能力值為0的工人不應被分配任務。

3) 工作組性能ρ：所有被分配了任務的工人形成一個工作組G。ρ表示G中所有工人的能力值總和。ρ越大，表示所有任務的完成質量越高。對于一組軟件眾包任務，需要最大化發揮工人的能力，以確保所有任務的ρ最高。 因此，一個任務并不一定被分配給一個勝任力最強的工人。

4.2 約束定義

2) 任務的工人數量需求向量L：Lj表示任務rj需要的最少工人數量。 如果Lj≥1，表示任務rj需要多個工人協作來完成此項眾包任務。

為提高任務分配的效率和成功率，在任務分配時需要避開以上可能存在沖突的分配組合。

4.3 目標函數

基于以上定義，可以得到基于角色協同的眾包任務分配問題的目標函數：

(7)

它應該滿足以下條件：

Ti, j∈{0,1} 0≤i

(8)

(9)

(10)

(11)

(12)

(13)

(14)

其中：約束(8)表示工人是否被分配；約束(9)表示每個任務被分配的工人數量滿足該任務所要求的人數限制；約束(10)表示工人只能承接一項任務；約束(11)和約束(12)表示存在沖突的兩個工人不能被分配在同一個任務或同一個項目中；約束(13)和約束(14)表示一個工人與其他工人或任務間只存在有沖突與無沖突的兩種狀態。求解基于角色協同的眾包任務分配問題就是要建立一個可以獲得最大工作組性能ρ的候選工人集合。

5 眾包任務分配問題的求解

5.1 求解過程

以上眾包任務分配問題的求解過程如下：

Step1：從眾包平臺獲取工人能力評價的相關原始數據、發包者對工人的能力期望D、任務的下限向量L以及沖突矩陣CA和CR等。

Step2：將工人能力評價的原始數據按3.2節介紹的方法轉換為區間數U。

Step3：比較工人能力與待分配任務的需求期望區間數，按3.3節的公式計算工人與任務間關于評價指標匹配度的三維模糊決策矩陣P。

Step4：基于3.4節的介紹，使用FAHP方法計算工人能力指標的權重向量W。

Step5：使用3.5節的式(6)和W計算得到各個ai完成rj的綜合勝任度，從而獲得候選工人的綜合能力值矩陣Q。

Step6：根據給定的Q、CA和CR，對目標函數求解，得到ρ的最大值和任務分配矩陣T。

Step7：如果T可用，則T為最終的分配方案；否則無解，此時眾包平臺通知任務發包者對任務要求進行調整，直至獲得可行的最優解。

5.2 基于CPLEX的求解方法

借鑒基于角色協同的任務分配研究[7-8]，采用IBM CPLEX優化包求解，實現步驟如下：

Step1：確定與CPLEX接口的核心數據結構。CPLEX需要目標函數系數、約束系數、右側約束值以及上下限等輸入參數。使用Q、L和T定義CPLEX中的線性規劃問題，Q是目標函數系數，T是變量，Qi, j∈[0,1]，Ti, j∈{0,1}。

Step3：設定目標函數和約束表達式。眾包任務分配問題的目標函數由矩陣Q和T的一維數組形式和L的線性表達式組成。首先，將Q和T變換成一維陣列：Xi×n+j=Ti, j和Vi×n+j=Qi, j。然后，添加優化目標，調用以下方法：IloIntVar[]X=cplex.intVarArray(m*n, 0, 1);cplex.addMaximize(cplex.scalProd(X,V))。最后，迭代添加約束表達式，以Java代碼為例，具體實現方法見算法1。

Step4：調用CPLEX的cplex.solve()方法，根據目標函數和約束條件表達式來計算最大化的ρ值。

算法1 添加約束表達式

6 案例分析

假定當前環境下需要9名工人完成5個任務，用R={r0,r1, …,r4}表示任務集，假設有12名工人參加競標，用A={a0,a1, …,a11}表示候選工人集。用U={u0,u1,u2,u3}表示工人綜合能力的評價指標集，u0代表技能水平、u1代表任務完成效率、u2代表任務完成質量、u3代表平臺活躍程度。在計算各工人的綜合能力后，采用基于角色協同的任務分配方法來最優化分配任務。假定由FAHP方法計算得到的權重值為W=[0.15,0.25,0.50,0.10]。從眾包平臺獲取工人的原始評價數據，轉換為區間數值，如表1所示。

表1 候選工人的能力評價

發包者為任務設定的需求期望如表2所示。

表2 各個任務對工人能力的需求期望

由式(3)計算工人能力與任務需求的匹配度模糊決策矩陣。第1個工人的匹配度模糊決策子矩陣數據示例如表3所示。再使用權重W加權求和，獲取的如表4所示的工人綜合勝任度矩陣Q。

表3 第1個工人的匹配度P0, j, k

現實中可能存在多種沖突，假定工人與任務間的沖突約束CR如下所示：

接下來，利用CPLEX優化包求解，設L=[2,1,3,2,1]，得到最優解：

根據以上結果，可得到每個待分配任務對應的眾包工人組合，如表5所示。

表5 任務分配結果

綜上可知，通過評估候選工人的綜合能力，建立基于角色協同的任務分配模型，求解后獲得多對多型任務分配方案的目標函數最大值為2.569。

7 實驗分析

為驗證所提方法，采用仿真數據進行實驗分析。使用64位Windows 10、Eclipse、Java語言。CPU為Intel Core i5-9600K、4.30 GHz，內存為16 GB DDR 4、3 200 MHz，IBM CPLEX Optimization Studio 版本12.7。借鑒任務分配問題常用的實驗設定[6, 8]，取n=?m/3」或n=?m/4」，m從10變化到60、步長為5，執行50次取平均值。

7.1 數據預處理時間分析

運用所提方法進行任務協同分配前，需搜集眾包平臺上工人能力的原始評價數據并將它們轉換為區間數，再與任務需求期望區間數進行可能度計算，繼而通過權重合成后獲得工人的綜合能力評估矩陣Q。實驗分析以上數據預處理過程的時間消耗。考慮到現實中能力指標值很低的工人較少可能競爭到眾包任務，設定工人能力和任務需求期望的隨機范圍為[0.3,1.0]，設定n=?m/3」或n=?m/4」、沖突概率為0.1，實驗結果如圖1所示。

圖1 數據預處理時間分析Fig.1 Analysis of data preprocess time

由圖1可知，隨著工人數量和任務數量的不斷增多，數據預處理所消耗的時間逐漸增加，呈現近似于線性增長的趨勢。在任務數為20、候選工人數為60的最大數據規模下，多對多型軟件眾包任務分配問題的數據預處理時間低于0.07 ms，能夠具有較理想的處理性能。

7.2 執行耗時分析

實驗設定n=?m/3」、沖突概率為0.1。考慮到每個Lj>1的任務可等價為Lj=1的多個相同任務，統一設定Lj=1,j∈{1,2,…,n}。每個步驟中初始化Q、CA、CR，對比本文方法與貪心方法、窮舉方法的執行時間，結果如表6所示。

表6 n=?m/3」時執行耗時分析

表6中，N/A表示在30 min無法獲得最優解。由表5、表6可知，隨著工人數量的增加，3種方法的耗時隨之明顯增加，尤其是窮舉方法的執行耗時呈指數增長。在n=?m/3」的實驗中，當工人數小于等于35、任務數小于等于11時，貪心算法的執行性能明顯優于本文方法；但是，隨著問題規模的增大，當工人數大于等于40、任務數大于等于13以后，在某些特殊的隨機數據情況下，貪心方法的執行時間可能急劇增加，在30 min內無法獲得優化解。針對m=40、n=13的情況下進行了深入分析，在多個特殊的隨機數據樣例(原始數據發布于百度云)下貪心方法與本文方法的耗時對比如表7所示。由表7可知，在問題復雜度較大(即工人數和任務數具有一定規模)時，貪心方法在不同數據樣例情況下的執行時間具有不確定性，其原因是，在一些特殊沖突矩陣CA和工人綜合能力評估矩陣Q場景下，貪心方法在尋找優化解過程中為了避免沖突情況要進行回溯，而隨機生成的沖突矩陣可能導致回溯過于頻繁，從而使整體執行時間急劇增加。

對比結果可知，沖突約束下多對多型軟件眾包任務分配問題求解時，即使在工人數為60、任務數為20的最復雜情況下，本文基于CPLEX的求解方法僅耗時66.9 ms，始終能獲得令人滿意的執行性能。

表7 執行耗時對比

7.3 命中最優解的概率分析

以窮舉法獲得的最優解為基準，在不同沖突概率情況下測試本文方法命中最優解的概率。實驗設定n=?m/3」、Lj=1，j∈{1,2,…,n}，沖突概率分別設置為0.1～0.4。結果如圖2和表8所示。

圖2 命中最優解的概率Fig.2 Hit probability of optimal solution

表8 n=?m/3」情況下的精度分析

由圖2可知，隨著問題規模的增加，命中最優解的概率逐漸下降，當問題規模達到一定程度后，命中率將急劇下降。n=?m/3」的實驗中，沖突概率大于等于0.2時，m大于等于40以后獲得最優解的概率就明顯不理想了。實驗表明，在固定n/m比值的情況下，工人人數越多、沖突概率越大，則命中最優解的概率越低。

7.4 求解精度分析

本實驗以窮舉法的結果為基準，對比本文方法與貪心方法的求解精度。實驗設定任務數為5，沖突概率為0.1，工人數量以步長5在[10，60]范圍內變動。求解精度值的計算公式為：

F=1-(ρ*-ρ)/ρ*

(15)

式中，ρ*是窮舉法獲得的最優的工作組性能值，ρ是其他方法獲得的工作組性能值。

實驗結果如圖3和表9所示。由圖3可知，本文方法在較大問題規模情況下均能準確獲得最優解，求解精度始終為1。而貪心方法雖然執行性能較高，但無法保證始終獲得最優解，尤其在問題規模偏小時，其準確率明顯不理想。圖3中，當候選工人增多時，貪心方法的精度得以明顯提高。

圖3 精度對比Fig.3 Comparison of accuracy

表9 精度對比

7.5 評價

總體來看，本文方法的整體表現明顯優于其他方法，在一定規模的眾包任務分配求解時，能保證良好的執行效率，并始終能夠確保用戶獲得最優解。基于本文方法可以提高軟件眾包的任務完成質量，降低項目的開發風險。

8 結論

針對工人能力的不確定性和任務屬性的多樣性，提出一種眾包工人綜合勝任能力的模糊度量方法。它結合工人的歷史記錄和任務的需求期望，以模糊區間數表征眾包工人的歷史表現，從技能水平、任務完成效率、任務完成質量和平臺活躍程度4個指標評價工人的綜合能力，計算多屬性模糊能力匹配度，應用模糊層次分析法獲得工人的綜合勝任能力。引入RBC理論和E-CARGO模型，將涉及任務集與工人組的多對多任務分配問題形式化建模為基于角色協同的組合優化問題，該模型以工人綜合勝任能力為基礎，綜合考慮任務的權重約束、工人數量需求約束、工人與任務間的沖突約束等，以提高任務分配的效率和成功率，并給出了一種基于CPLEX的問題求解方法。通過案例和實驗分析了所提方法的可行性和有效性，所提方法可為軟件眾包應用提供重要的理論參考和決策基礎。未來研究中，將對工人綜合能力的動態度量和動態任務分配、包含同步任務的工人多角色協同分配等進行深入探討。