馬 華,陳躍鵬,黃卓軒,唐文勝,婁小平
(湖南師范大學(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ì)量。
眾包工人能力度量的傳統(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ì)。
眾包模型主要可分為兩類:①基于社會(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ì)量。
假定軟件眾包平臺(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ì)量。 定義1區(qū)間數(shù)。設(shè)bL、bH是兩個(gè)實(shí)數(shù),如果B=[bL,bH],0≤bL≤bH≤1,則稱B為一個(gè)區(qū)間數(shù)。bL和bH分別稱為區(qū)間的下限和上限。 (1) (2) (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 在實(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) 基于能力指標(biāo)的權(quán)重向量,最終可獲得各個(gè)ai完成rj的綜合勝任度,計(jì)算方法如式(6)所示。 (6) Qi, j表示工人ai對(duì)于任務(wù)rj的綜合勝任能力,該值越大,說明此工人對(duì)于該項(xiàng)任務(wù)的勝任力越強(qiáng),則將來可以獲得更高的任務(wù)完成質(zhì)量。 借鑒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≤i 3) 工作組性能ρ:所有被分配了任務(wù)的工人形成一個(gè)工作組G。ρ表示G中所有工人的能力值總和。ρ越大,表示所有任務(wù)的完成質(zhì)量越高。對(duì)于一組軟件眾包任務(wù),需要最大化發(fā)揮工人的能力,以確保所有任務(wù)的ρ最高。 因此,一個(gè)任務(wù)并不一定被分配給一個(gè)勝任力最強(qiáng)的工人。 2) 任務(wù)的工人數(shù)量需求向量L:Lj表示任務(wù)rj需要的最少工人數(shù)量。 如果Lj≥1,表示任務(wù)rj需要多個(gè)工人協(xié)作來完成此項(xiàng)眾包任務(wù)。 為提高任務(wù)分配的效率和成功率,在任務(wù)分配時(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è)可以獲得最大工作組性能ρ的候選工人集合。 以上眾包任務(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)解。 借鑒基于角色協(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á)式 假定當(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。 為驗(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次取平均值。 運(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,能夠具有較理想的處理性能。 實(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ì)比 以窮舉法獲得的最優(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)解的概率越低。 本實(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ì)比 總體來看,本文方法的整體表現(xiàn)明顯優(yōu)于其他方法,在一定規(guī)模的眾包任務(wù)分配求解時(shí),能保證良好的執(zhí)行效率,并始終能夠確保用戶獲得最優(yōu)解?;诒疚姆椒梢蕴岣哕浖姲娜蝿?wù)完成質(zhì)量,降低項(xiàng)目的開發(fā)風(fēng)險(xiǎn)。 針對(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)行深入探討。3 基于模糊區(qū)間數(shù)的眾包工人能力度量
3.1 基本定義
3.2 基于歷史評(píng)價(jià)的工人能力模糊度量計(jì)算
3.3 任務(wù)需求期望導(dǎo)向的工人能力匹配度計(jì)算
3.4 工人能力評(píng)價(jià)指標(biāo)權(quán)重的模糊層次分析
3.5 基于能力模糊度量的工人綜合勝任度計(jì)算
4 基于角色協(xié)同的眾包任務(wù)分配模型
4.1 基本模型
4.2 約束定義
4.3 目標(biāo)函數(shù)
5 眾包任務(wù)分配問題的求解
5.1 求解過程
5.2 基于CPLEX的求解方法
6 案例分析
7 實(shí)驗(yàn)分析
7.1 數(shù)據(jù)預(yù)處理時(shí)間分析
7.2 執(zhí)行耗時(shí)分析
7.3 命中最優(yōu)解的概率分析
7.4 求解精度分析
7.5 評(píng)價(jià)
8 結(jié)論