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

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

(湖南師范大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長(zhǎng)沙 410081)

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

軟件眾包平臺(tái)通常采用在線競(jìng)爭(zhēng)機(jī)制挑選優(yōu)秀的眾包工人來承接任務(wù)。而工人工作能力的準(zhǔn)確度量是眾包任務(wù)分配前首先需考慮的關(guān)鍵因素，它直接影響到任務(wù)的最終完成質(zhì)量[2]?，F(xiàn)有研究尚缺乏對(duì)工人能力的全面分析，未綜合考慮眾包任務(wù)與工人能力的匹配程度對(duì)分配結(jié)果的影響[3]，現(xiàn)有的基于單一值的描述機(jī)制也無(wú)法客觀反映工人實(shí)際能力的不確定性。同時(shí)，現(xiàn)有研究主要采用基于匹配和基于規(guī)劃的任務(wù)分配模型，關(guān)注的是面向單個(gè)工人的一對(duì)一型和一對(duì)多型分配問題，尚未涉及面向眾包平臺(tái)的多對(duì)多型分配問題[3-4]。

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

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

1 相關(guān)工作

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

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

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

1.2 眾包任務(wù)的分配方法

眾包模型主要可分為兩類：①基于社會(huì)網(wǎng)絡(luò)的復(fù)雜任務(wù)群智協(xié)同眾包模型[4]。它不要求發(fā)包者自己分解一個(gè)復(fù)雜任務(wù)，而是由接收任務(wù)的工人通過組織其合作者來一起完成任務(wù)?？擅獬l(fā)包者的任務(wù)分解負(fù)擔(dān)，但增加了模型相關(guān)的計(jì)算量和對(duì)工人社會(huì)屬性深度挖掘的復(fù)雜性，實(shí)際應(yīng)用時(shí)仍有諸多問題需解決。②基于任務(wù)分解的復(fù)雜任務(wù)眾包模型[17]。它要求發(fā)包者具備良好的任務(wù)分解能力，也要求工人提交的結(jié)果具有良好的兼容性。綜合考慮可行性和時(shí)效性，實(shí)際眾包應(yīng)用平臺(tái)大多采用該模型。

基于任務(wù)分解的復(fù)雜任務(wù)眾包模型又可細(xì)分為兩類：①基于匹配的任務(wù)分配模型[3]。它使用二分圖匹配，根據(jù)任務(wù)與工人的時(shí)間、空間、狀態(tài)等特征，并結(jié)合工人的信譽(yù)值或可信度等，為每名工人分配一項(xiàng)任務(wù)，即一對(duì)一型任務(wù)分配。Mechanical Turk、豬八戒網(wǎng)等傳統(tǒng)眾包平臺(tái)以及滴滴出行、美團(tuán)眾包等空間眾包平臺(tái)均屬此類。②基于規(guī)劃的任務(wù)分配模型[3]。它類似于旅行商問題模型，研究眾包平臺(tái)如何為一個(gè)眾包工人分配合理的任務(wù)執(zhí)行順序和方案，本質(zhì)上是針對(duì)一對(duì)多型的任務(wù)分配問題，即為一個(gè)工人分配多個(gè)任務(wù)以達(dá)到最優(yōu)的工作組合?？紤]到工人的最晚工作時(shí)間約束，結(jié)合樹分解和深度優(yōu)先搜索方法[18]可獲得任務(wù)分配最優(yōu)方案。

隨著越來越多的任務(wù)被同時(shí)發(fā)布，眾包平臺(tái)可能存在大量具有相似特點(diǎn)和需求的相關(guān)任務(wù)。此時(shí)的任務(wù)分配問題呈現(xiàn)出“多對(duì)多”特征，即眾包平臺(tái)如何將多個(gè)相關(guān)任務(wù)分配給合適的多個(gè)工人，這是一個(gè)NP難問題。不同于傳統(tǒng)的一對(duì)一或一對(duì)多視角，它需要從眾包平臺(tái)整體的角度來考慮如何實(shí)現(xiàn)多個(gè)任務(wù)與工人間的組合優(yōu)化[3]，以幫助眾包平臺(tái)獲得全局最佳的任務(wù)完成質(zhì)量。

2 問題描述

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

1) 每個(gè)rj(0≤j

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

3) 同一項(xiàng)目中的不同任務(wù)的重要性不同。顯然，一些關(guān)鍵任務(wù)會(huì)相比非關(guān)鍵任務(wù)對(duì)于項(xiàng)目的完成具有更重要的影響。因此，在任務(wù)分配時(shí)應(yīng)為關(guān)鍵任務(wù)分配能力更強(qiáng)的優(yōu)秀工人。

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

5) 結(jié)合眾包平臺(tái)上的歷史數(shù)據(jù)，從技能水平、任務(wù)完成效率、任務(wù)完成質(zhì)量、平臺(tái)活躍程度4個(gè)指標(biāo)對(duì)ai的能力進(jìn)行綜合評(píng)價(jià)。其中，技能水平反映工人的軟件設(shè)計(jì)、開發(fā)、測(cè)試等方面的專業(yè)能力熟練程度；任務(wù)完成效率體現(xiàn)工人完成任務(wù)的時(shí)效性；任務(wù)完成質(zhì)量體現(xiàn)工人最終提交的成果的優(yōu)劣程度；平臺(tái)活躍程度反映工人的社交和協(xié)作意愿。以上每項(xiàng)指標(biāo)可由多個(gè)子指標(biāo)來進(jìn)一步刻畫。例如，工人技能水平可從崗位(如前端工程師、開發(fā)工程師)、應(yīng)用類型(如移動(dòng)應(yīng)用、微信應(yīng)用)、開發(fā)語(yǔ)言(如Java、HTML5)等方面進(jìn)行精細(xì)度量。通常而言，參與任務(wù)的工人的綜合能力越強(qiáng)，該任務(wù)的最終完成質(zhì)量越高。

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

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

3 基于模糊區(qū)間數(shù)的眾包工人能力度量

3.1 基本定義

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

3.2 基于歷史評(píng)價(jià)的工人能力模糊度量計(jì)算

(1)

(2)

3.3 任務(wù)需求期望導(dǎo)向的工人能力匹配度計(jì)算

(3)

由式(3)可計(jì)算工人與每個(gè)任務(wù)在各個(gè)評(píng)價(jià)指標(biāo)的可能度，并最終得到工人與任務(wù)兩兩之間關(guān)于評(píng)價(jià)指標(biāo)匹配度的模糊決策矩陣P，Pi,j,k表示第i(0≤i

3.4 工人能力評(píng)價(jià)指標(biāo)權(quán)重的模糊層次分析

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

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

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

(4)

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

(5)

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

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

(6)

Qi, j表示工人ai對(duì)于任務(wù)rj的綜合勝任能力，該值越大，說明此工人對(duì)于該項(xiàng)任務(wù)的勝任力越強(qiáng)，則將來可以獲得更高的任務(wù)完成質(zhì)量。

4 基于角色協(xié)同的眾包任務(wù)分配模型

4.1 基本模型

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

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

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

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

4.2 約束定義

2) 任務(wù)的工人數(shù)量需求向量L：Lj表示任務(wù)rj需要的最少工人數(shù)量。 如果Lj≥1，表示任務(wù)rj需要多個(gè)工人協(xié)作來完成此項(xiàng)眾包任務(wù)。

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

4.3 目標(biāo)函數(shù)

基于以上定義，可以得到基于角色協(xié)同的眾包任務(wù)分配問題的目標(biāo)函數(shù)：

(7)

它應(yīng)該滿足以下條件：

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

(8)

(9)

(10)

(11)

(12)

(13)

(14)

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

5 眾包任務(wù)分配問題的求解

5.1 求解過程

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

Step1：從眾包平臺(tái)獲取工人能力評(píng)價(jià)的相關(guān)原始數(shù)據(jù)、發(fā)包者對(duì)工人的能力期望D、任務(wù)的下限向量L以及沖突矩陣CA和CR等。

Step2：將工人能力評(píng)價(jià)的原始數(shù)據(jù)按3.2節(jié)介紹的方法轉(zhuǎn)換為區(qū)間數(shù)U。

Step3：比較工人能力與待分配任務(wù)的需求期望區(qū)間數(shù)，按3.3節(jié)的公式計(jì)算工人與任務(wù)間關(guān)于評(píng)價(jià)指標(biāo)匹配度的三維模糊決策矩陣P。

Step4：基于3.4節(jié)的介紹，使用FAHP方法計(jì)算工人能力指標(biāo)的權(quán)重向量W。

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

Step6：根據(jù)給定的Q、CA和CR，對(duì)目標(biāo)函數(shù)求解，得到ρ的最大值和任務(wù)分配矩陣T。

Step7：如果T可用，則T為最終的分配方案；否則無(wú)解，此時(shí)眾包平臺(tái)通知任務(wù)發(fā)包者對(duì)任務(wù)要求進(jìn)行調(diào)整，直至獲得可行的最優(yōu)解。

5.2 基于CPLEX的求解方法

借鑒基于角色協(xié)同的任務(wù)分配研究[7-8]，采用IBM CPLEX優(yōu)化包求解，實(shí)現(xiàn)步驟如下：

Step1：確定與CPLEX接口的核心數(shù)據(jù)結(jié)構(gòu)。CPLEX需要目標(biāo)函數(shù)系數(shù)、約束系數(shù)、右側(cè)約束值以及上下限等輸入?yún)?shù)。使用Q、L和T定義CPLEX中的線性規(guī)劃問題，Q是目標(biāo)函數(shù)系數(shù)，T是變量，Qi, j∈[0,1]，Ti, j∈{0,1}。

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

Step4：調(diào)用CPLEX的cplex.solve()方法，根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式來計(jì)算最大化的ρ值。

算法1 添加約束表達(dá)式

6 案例分析

假定當(dāng)前環(huán)境下需要9名工人完成5個(gè)任務(wù)，用R={r0,r1, …,r4}表示任務(wù)集，假設(shè)有12名工人參加競(jìng)標(biāo)，用A={a0,a1, …,a11}表示候選工人集。用U={u0,u1,u2,u3}表示工人綜合能力的評(píng)價(jià)指標(biāo)集，u0代表技能水平、u1代表任務(wù)完成效率、u2代表任務(wù)完成質(zhì)量、u3代表平臺(tái)活躍程度。在計(jì)算各工人的綜合能力后，采用基于角色協(xié)同的任務(wù)分配方法來最優(yōu)化分配任務(wù)。假定由FAHP方法計(jì)算得到的權(quán)重值為W=[0.15,0.25,0.50,0.10]。從眾包平臺(tái)獲取工人的原始評(píng)價(jià)數(shù)據(jù)，轉(zhuǎn)換為區(qū)間數(shù)值，如表1所示。

表1 候選工人的能力評(píng)價(jià)

發(fā)包者為任務(wù)設(shè)定的需求期望如表2所示。

表2 各個(gè)任務(wù)對(duì)工人能力的需求期望

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

表3 第1個(gè)工人的匹配度P0, j, k

現(xiàn)實(shí)中可能存在多種沖突，假定工人與任務(wù)間的沖突約束CR如下所示：

接下來，利用CPLEX優(yōu)化包求解，設(shè)L=[2,1,3,2,1]，得到最優(yōu)解：

根據(jù)以上結(jié)果，可得到每個(gè)待分配任務(wù)對(duì)應(yīng)的眾包工人組合，如表5所示。

表5 任務(wù)分配結(jié)果

綜上可知，通過評(píng)估候選工人的綜合能力，建立基于角色協(xié)同的任務(wù)分配模型，求解后獲得多對(duì)多型任務(wù)分配方案的目標(biāo)函數(shù)最大值為2.569。

7 實(shí)驗(yàn)分析

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

7.1 數(shù)據(jù)預(yù)處理時(shí)間分析

運(yùn)用所提方法進(jìn)行任務(wù)協(xié)同分配前，需搜集眾包平臺(tái)上工人能力的原始評(píng)價(jià)數(shù)據(jù)并將它們轉(zhuǎn)換為區(qū)間數(shù)，再與任務(wù)需求期望區(qū)間數(shù)進(jìn)行可能度計(jì)算，繼而通過權(quán)重合成后獲得工人的綜合能力評(píng)估矩陣Q。實(shí)驗(yàn)分析以上數(shù)據(jù)預(yù)處理過程的時(shí)間消耗?？紤]到現(xiàn)實(shí)中能力指標(biāo)值很低的工人較少可能競(jìng)爭(zhēng)到眾包任務(wù)，設(shè)定工人能力和任務(wù)需求期望的隨機(jī)范圍為[0.3,1.0]，設(shè)定n=?m/3」或n=?m/4」、沖突概率為0.1，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 數(shù)據(jù)預(yù)處理時(shí)間分析Fig.1 Analysis of data preprocess time

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

7.2 執(zhí)行耗時(shí)分析

實(shí)驗(yàn)設(shè)定n=?m/3」、沖突概率為0.1。考慮到每個(gè)Lj>1的任務(wù)可等價(jià)為L(zhǎng)j=1的多個(gè)相同任務(wù)，統(tǒng)一設(shè)定Lj=1,j∈{1,2,…,n}。每個(gè)步驟中初始化Q、CA、CR，對(duì)比本文方法與貪心方法、窮舉方法的執(zhí)行時(shí)間，結(jié)果如表6所示。

表6 n=?m/3」時(shí)執(zhí)行耗時(shí)分析

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

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

表7 執(zhí)行耗時(shí)對(duì)比

7.3 命中最優(yōu)解的概率分析

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

圖2 命中最優(yōu)解的概率Fig.2 Hit probability of optimal solution

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

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

7.4 求解精度分析

本實(shí)驗(yàn)以窮舉法的結(jié)果為基準(zhǔn)，對(duì)比本文方法與貪心方法的求解精度。實(shí)驗(yàn)設(shè)定任務(wù)數(shù)為5，沖突概率為0.1，工人數(shù)量以步長(zhǎng)5在[10，60]范圍內(nèi)變動(dòng)。求解精度值的計(jì)算公式為：

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

(15)

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

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

圖3 精度對(duì)比Fig.3 Comparison of accuracy

表9 精度對(duì)比

7.5 評(píng)價(jià)

總體來看，本文方法的整體表現(xiàn)明顯優(yōu)于其他方法，在一定規(guī)模的眾包任務(wù)分配求解時(shí)，能保證良好的執(zhí)行效率，并始終能夠確保用戶獲得最優(yōu)解?；诒疚姆椒梢蕴岣哕浖姲娜蝿?wù)完成質(zhì)量，降低項(xiàng)目的開發(fā)風(fēng)險(xiǎn)。

8 結(jié)論

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