基于多Agent的眾包任務(wù)分配算法的研究

周 僑， 方 明

(西安石油大學(xué) 計(jì)算機(jī)學(xué)院， 西安 710065)

0 引 言

眾包平臺(tái)的任務(wù)分配機(jī)制對(duì)眾包任務(wù)完成質(zhì)量有很大影響，不合理的任務(wù)分配機(jī)制通常會(huì)帶來(lái)不理想的任務(wù)完成質(zhì)量。因此任務(wù)分配給合適的眾包方，是眾包分配機(jī)制的重要組成部分。現(xiàn)有的一些分配機(jī)制主要是通過(guò)綜合考慮任務(wù)參與者的工作負(fù)載，對(duì)不同類型任務(wù)的完成質(zhì)量等因素。采用基于任務(wù)參與者負(fù)載平衡和經(jīng)驗(yàn)值的任務(wù)分配策略[1]；或者從待分配任務(wù)和任務(wù)候選人的狀態(tài)屬性出發(fā)，采用基于模糊集與TOPSIS的任務(wù)分配方法來(lái)解決任務(wù)的自動(dòng)優(yōu)選問(wèn)題[2]；還有一些根據(jù)任務(wù)基線權(quán)重值以及眾包方的技能等級(jí)等因素，采用DTA算法來(lái)解決在線任務(wù)分配問(wèn)題[3]。這些研究在一定范圍和程度上較好地解決了眾包任務(wù)的合理分配問(wèn)題，但尚缺少結(jié)合眾包方的興趣，眾包任務(wù)的難易程度以及新眾包方無(wú)歷史行為數(shù)據(jù)而無(wú)法分配任務(wù)的問(wèn)題，也未充分考慮到眾包任務(wù)分配中，外界環(huán)境的不確定性，眾包方的能力的動(dòng)態(tài)性的問(wèn)題。本文結(jié)合多Agent技術(shù)，將傳統(tǒng)被動(dòng)的眾包方變?yōu)橹鲃?dòng)競(jìng)爭(zhēng)任務(wù)的智能體(Agent)，將眾包平臺(tái)的各組成部分構(gòu)造成Agent，以多Agent協(xié)作組織和工作方式實(shí)現(xiàn)相應(yīng)的眾包任務(wù)分配處理模式，以此來(lái)縮短任務(wù)執(zhí)行時(shí)間，提高任務(wù)的運(yùn)行效率。

1 多Agent眾包任務(wù)分配平臺(tái)的總體結(jié)構(gòu)

眾包是一種特殊的新興的大眾網(wǎng)絡(luò)聚集方式，是指一個(gè)公司或機(jī)構(gòu)把過(guò)去由員工或者承包商完成的工作任務(wù)，以自由自愿的形式外包給非特定的大眾網(wǎng)絡(luò)或虛擬社區(qū)的做法[4]。Agent技術(shù)是一種處于一定環(huán)境下包裝的計(jì)算機(jī)系統(tǒng)，為實(shí)現(xiàn)設(shè)計(jì)目的，能在該環(huán)境下靈活、自主的活動(dòng)。多Agent把許多個(gè)體組織起來(lái)，可以彌補(bǔ)個(gè)體工作能力的限制。傳統(tǒng)的眾包平臺(tái)由發(fā)包方、眾包引擎以及眾包方組成，眾包任務(wù)分配與相應(yīng)的基本過(guò)程為任務(wù)申請(qǐng)、任務(wù)初始化、任務(wù)執(zhí)行和任務(wù)完成，眾包任務(wù)分配和傳統(tǒng)任務(wù)的分配有很大不同。首先，眾包方的能力及興趣是未知，發(fā)包方希望把任務(wù)分配給技能相對(duì)高的眾包方，但傳統(tǒng)的任務(wù)是隨機(jī)分配的；其次，眾包方的工作時(shí)間比較隨意，而且眾包方有可能會(huì)同時(shí)接受很多任務(wù)，而眾包方接受大量時(shí)間沖突的任務(wù)會(huì)導(dǎo)致任務(wù)不能在規(guī)定時(shí)間完成；最后，隨機(jī)分配可能導(dǎo)致低技能任務(wù)分給高能力的眾包方而導(dǎo)致低的利用率，高技能任務(wù)分配給低能力眾包方使得任務(wù)無(wú)法完成或任務(wù)質(zhì)量達(dá)不到要求。同時(shí)，傳統(tǒng)的眾包平臺(tái)一般將眾包中的任務(wù)，以及眾包方看作為處于被動(dòng)等待的實(shí)體，是缺乏智能的實(shí)體對(duì)象，不具備主動(dòng)根據(jù)所處環(huán)境和所要解決的問(wèn)題來(lái)調(diào)整自身知識(shí)結(jié)構(gòu)解決問(wèn)題的能力。為此，本文提出一種基于多Agent的眾包任務(wù)分配算法來(lái)提升任務(wù)質(zhì)量的結(jié)果。在該平臺(tái)中，為改變以往眾包的被動(dòng)性，采用多Agent技術(shù)將眾包平臺(tái)的各組成部分構(gòu)造成Agent。該平臺(tái)的體系結(jié)構(gòu)如圖1所示。

圖1 多Agent眾包管理平臺(tái)結(jié)構(gòu)圖

Fig.1Multi-Agentcrowdsourcingmanagementplatformstructure

其中，發(fā)包方根據(jù)階段與任務(wù)的不同，進(jìn)行任務(wù)設(shè)計(jì)、任務(wù)分解、任務(wù)發(fā)布和質(zhì)量檢測(cè)等。通過(guò)任務(wù)設(shè)計(jì)Agent對(duì)相關(guān)任務(wù)進(jìn)行設(shè)計(jì)，并用任務(wù)分解Agent按照不同的需求將任務(wù)分解成各個(gè)子任務(wù)，子任務(wù)描述Agent對(duì)每個(gè)子任務(wù)的內(nèi)容、難度以及酬勞對(duì)任務(wù)進(jìn)行描述。任務(wù)發(fā)布Agent發(fā)布任務(wù)并統(tǒng)計(jì)參與競(jìng)選任務(wù)的眾包方，任務(wù)分配Agent根據(jù)能力將任務(wù)分配給合適的眾包方。在任務(wù)時(shí)間截止后，結(jié)果接收Agent收集任務(wù)，并通過(guò)質(zhì)量檢測(cè)Agent對(duì)眾包方提交的任務(wù)進(jìn)行質(zhì)量評(píng)估。

眾包方根據(jù)眾包方接口Agent發(fā)現(xiàn)發(fā)包方在眾包平臺(tái)發(fā)包的任務(wù)，由任務(wù)推薦Agent根據(jù)眾包方以往任務(wù)的歷史記錄給其推薦任務(wù)，眾包方通過(guò)競(jìng)選任務(wù)Agent參選自己感興趣的任務(wù)，并在獲得任務(wù)的前提下，通過(guò)任務(wù)執(zhí)行Agent完成任務(wù)，任務(wù)提交Agent將任務(wù)提交至眾包平臺(tái)供發(fā)包方接收任務(wù)。

2 基于Agent的眾包任務(wù)分配算法

2.1 基于Agent的眾包任務(wù)分配相關(guān)函數(shù)和概念

根據(jù)基于Agent的眾包任務(wù)分配算法的思路，需要給出相關(guān)參數(shù)的概念定義和公式函數(shù)。

定義1眾包方興趣指數(shù)。眾包方u對(duì)某類型任務(wù)t的興趣指數(shù)用Interest(u，t)表示，其計(jì)算公式為：

(1)

其中，number指的是眾包方u完成全部任務(wù)的總次數(shù)，number(t)指眾包方u完成此類型任務(wù)的次數(shù)。

興趣可以提高人們的積極性，促使人們積極、愉快地完成該類型任務(wù)，對(duì)完成任務(wù)起到了積極的作用。Interest(u，t)的指數(shù)越大，說(shuō)明眾包方對(duì)此類型任務(wù)更有興趣，獲得此類型任務(wù)的概率越大。

定義2眾包方的負(fù)載。用loadt表示眾包方接收t類型任務(wù)的負(fù)載，用其歷史記錄中完成該類型任務(wù)的平均時(shí)長(zhǎng)決定，其中l(wèi)表示眾包方當(dāng)前任務(wù)集合中的任務(wù)數(shù)量，load表示眾包方當(dāng)前剩余的每個(gè)任務(wù)的負(fù)載，眾包方u的負(fù)載任務(wù)量用load(u)來(lái)表示，其計(jì)算公式為：

(2)

用Z-score標(biāo)準(zhǔn)化方法對(duì)任務(wù)總負(fù)載進(jìn)行歸一化處理，歸一化在0-1之間，以方便數(shù)據(jù)的處理，則眾包方的負(fù)載為：

(3)

其中，x表示眾包方集合中樣本數(shù)據(jù)的均值，y表示所有樣本數(shù)據(jù)的標(biāo)準(zhǔn)差。

由定義2可知，load(u)越小，表明該眾包方的負(fù)載越小，越容易被分配到新任務(wù)。

定義3眾包方的能力。用Ablity(u)表示眾包方u的能力，Ablityd(u)表示眾包方u完成難度系數(shù)高的任務(wù)的能力，Ablitym(u)表示眾包方u完成難度系數(shù)中等的任務(wù)的能力，Ablitye(u)表示眾包方u完成簡(jiǎn)單任務(wù)的能力。眾包任務(wù)在發(fā)布時(shí)用難度系數(shù)[1，0)來(lái)表示任務(wù)的難度，將難度系數(shù)[1，0.7)之間的歸類為高難度任務(wù)，系數(shù)在[0.7，0.3)范圍內(nèi)的劃分到中等難度的范圍內(nèi)，系數(shù)在[0.3，0)之間的認(rèn)為是簡(jiǎn)單的任務(wù)。則眾包方u的各能力計(jì)算公式分別為：

Ablity(u)=λ1×Ablityd(u)+λ2×Ablitym(u)+

λ3×Ablitye(u)

(4)

其中，λ1+λ2+λ3=1；number表示眾包方u完成全部任務(wù)的總次數(shù)；numberd指的是眾包方u完成難度系數(shù)高的任務(wù)的總次數(shù)；amountd是完成高等任務(wù)中通過(guò)的數(shù)量；numberm指的是眾包方u完成難度系數(shù)中等的任務(wù)總次數(shù)；amountm是完成的中等任務(wù)中通過(guò)的數(shù)量；numbere指的是眾包方u完成簡(jiǎn)單任務(wù)的總次數(shù)；amounte是完成的簡(jiǎn)單任務(wù)中通過(guò)的數(shù)量。

定義4眾包方的綜合實(shí)力。用Capacity(u)表示眾包方u的綜合實(shí)力，其計(jì)算公式為：

Capacity(u)=λ4×Intersert(u,t)+λ5×(1-load(u))+λ6×Ablity(u)

(5)

其中，λ4+λ5+λ6=1

由定義4可知，給難度高的任務(wù)賦予大的權(quán)重值，簡(jiǎn)單的任務(wù)給予小的權(quán)重值，則Ablity(u)的值越大，表明該眾包方u的能力越強(qiáng)，獲得新任務(wù)的概率越大。

2.2 新眾包方問(wèn)題的解決

任務(wù)分配算法需要根據(jù)眾包方的歷史行為數(shù)據(jù)來(lái)預(yù)測(cè)眾包方未來(lái)的行為和興趣，因此大量的眾包方歷史行為數(shù)據(jù)就是系統(tǒng)為眾包方分配任務(wù)的重要組成部分和先決條件。但是，任務(wù)分配系統(tǒng)沒(méi)有新眾包方的歷史行為數(shù)據(jù)，所以如何在沒(méi)有眾包方行為數(shù)據(jù)的情況下判斷眾包方是否有能力完成高質(zhì)量的眾包任務(wù)，這就是任務(wù)分配問(wèn)題中的新眾包方問(wèn)題。對(duì)于新眾包方問(wèn)題，可以在眾包方注冊(cè)賬號(hào)的時(shí)候，填寫(xiě)眾包方個(gè)人簡(jiǎn)歷，簡(jiǎn)歷信息具體包括眾包方的姓名、年齡、學(xué)歷、興趣工作、目前工作內(nèi)容等相關(guān)信息。系統(tǒng)可以根據(jù)眾包方的工作內(nèi)容以及學(xué)歷，興趣等條件來(lái)判斷眾包方是否有能力完成眾包任務(wù)，并把一些相對(duì)簡(jiǎn)單的，較次要的任務(wù)分配給這些新眾包方，從而解決新眾包方問(wèn)題。

2.3 基于Agent的眾包任務(wù)分配算法

結(jié)合上述策略，當(dāng)發(fā)包方在眾包平臺(tái)上發(fā)布任務(wù)之后，眾包方的任務(wù)推薦Agent根據(jù)自身的負(fù)載能力以及個(gè)人興趣等因素決定是否接受此類任務(wù)，當(dāng)確定可以接受此類任務(wù)后，競(jìng)選任務(wù)Agent將響應(yīng)此任務(wù)的競(jìng)選。當(dāng)任務(wù)分配Agent統(tǒng)計(jì)所有參與任務(wù)的眾包方后，綜合考慮眾包方的任務(wù)負(fù)載，對(duì)不同難度、不同類型任務(wù)的完成質(zhì)量及其興趣等因素，把任務(wù)分配給能力最高，以及對(duì)此類任務(wù)感興趣的眾包方，并且對(duì)入選的眾包方，將難度系數(shù)高的任務(wù)分配給技能高的眾包方，簡(jiǎn)單的任務(wù)分配給技能相對(duì)低的眾包方，使得綜合能力高的眾包方的能力得到充分利用，也防止綜合能力低的眾包方分配到無(wú)法完成的任務(wù)。其中如果有新眾包方存在，則將部分簡(jiǎn)單任務(wù)預(yù)留給有相關(guān)工作經(jīng)驗(yàn)、興趣度高的新眾包方。

3 實(shí)驗(yàn)方案及分析

3.1 實(shí)驗(yàn)方案

隨機(jī)分配算法將所有的眾包方視為無(wú)差異的，該算法將任務(wù)以輪轉(zhuǎn)的方式分配給眾包方。本實(shí)驗(yàn)使用隨機(jī)分配算法作為實(shí)驗(yàn)的比較對(duì)象，運(yùn)用本文算法與隨機(jī)分配算法實(shí)驗(yàn)進(jìn)行仿真，選取3種類別(T，i=1，2，3)的100個(gè)任務(wù)及3個(gè)眾包方(U，i=1，2，3)作為實(shí)驗(yàn)對(duì)象，對(duì)實(shí)驗(yàn)進(jìn)行仿真及分析。眾包方完成各類任務(wù)所需的時(shí)間以及經(jīng)驗(yàn)值見(jiàn)表1。

表1眾包方完成任務(wù)的時(shí)間和初始經(jīng)驗(yàn)值

Tab.1Thetimeandinitialexperiencevalueofthecrowd-sourcingpartytocompletethetask

T/uU1時(shí)間經(jīng)驗(yàn)值U2時(shí)間經(jīng)驗(yàn)值U3時(shí)間經(jīng)驗(yàn)值T14.410.42.20.83.210.6T25.500.86.20.64.20.9T315.50.512.30.711.20.8

3.2 實(shí)驗(yàn)結(jié)果分析

在本實(shí)驗(yàn)中，從以下方面將該算法與隨機(jī)任務(wù)分配算法進(jìn)行對(duì)比，眾包方的負(fù)載情況、眾包方所獲得的3種類別任務(wù)數(shù)量比例。眾包方總的負(fù)載情況如圖2，圖3所示。

從圖2可以看出，使用隨機(jī)分配算法負(fù)載分布不均衡，由于眾包方U1執(zhí)行每個(gè)任務(wù)的時(shí)間比較長(zhǎng)，導(dǎo)致負(fù)載的增長(zhǎng)速度上升很快；而如圖3中所示，利用該算法，3個(gè)眾包方的負(fù)載在任務(wù)增加的情況下基本保持一致，達(dá)到了眾包方負(fù)載均衡的目的。

圖2 隨機(jī)分配算法中眾包方負(fù)載

圖3 本文算法中眾包方負(fù)載

眾包方所獲得各種類任務(wù)比例如圖4、圖5所示。使用隨機(jī)分配算法時(shí)眾包任務(wù)是以輪轉(zhuǎn)的方式分配給眾包方的，所以每名眾包方分配得到的各類任務(wù)數(shù)量比例基本相同。而在本算法中，根據(jù)眾包方完成此類任務(wù)的經(jīng)驗(yàn)值來(lái)分配任務(wù)。所以眾包方的經(jīng)驗(yàn)值越高，所分配得到的此類任務(wù)數(shù)目越多。

圖4 隨機(jī)分配算法中眾包方獲得任務(wù)比例

Fig.4Thecrowdsourcingpartyobtainsthetaskratiointherandomallocationalgorithm

圖5 本文算法中眾包方獲得任務(wù)比例

Fig.5Thecrowdsourcingpartyobtainsthetaskratiointhealgorithmofthispaper

4 結(jié)束語(yǔ)

本文基于眾包理論和方法，結(jié)合Agent技術(shù)，提出一個(gè)基于多Agent的眾包任務(wù)分配算法。以Agent技術(shù)的自治性、反應(yīng)性、社會(huì)性和能動(dòng)性特點(diǎn)為目標(biāo)[5]，通過(guò)任務(wù)分配Agent分配任務(wù)，把任務(wù)分配給能力最高，以及對(duì)此類任務(wù)感興趣的眾包方，并且對(duì)入選的眾包方，將難度系數(shù)高的任務(wù)分配給技能高的眾包方，簡(jiǎn)單的任務(wù)分配給技能相對(duì)低的眾包方，保證眾包任務(wù)合理的分配，可通過(guò)眾包方的個(gè)人簡(jiǎn)歷來(lái)解決新眾包方的問(wèn)題，保證眾包任務(wù)高效、準(zhǔn)時(shí)地完成，來(lái)提高企業(yè)復(fù)雜任務(wù)工作的效率。由于本文基于個(gè)人意愿進(jìn)行任務(wù)分配，無(wú)法保證眾包平臺(tái)中每個(gè)眾包方都能看到眾包任務(wù)，這樣無(wú)法保證高能力眾包方能參與到任務(wù)競(jìng)選中，下一步的工作任務(wù)將采用任務(wù)主動(dòng)推送和任務(wù)分配相結(jié)合的方式來(lái)完善任務(wù)分配算法，將任務(wù)主動(dòng)推送給高能力的眾包方。