周 僑， 方 明

(西安石油大學 計算機學院， 西安 710065)

0 引 言

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

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

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

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

Fig.1Multi-Agentcrowdsourcingmanagementplatformstructure

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

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

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

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

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

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

(1)

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

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

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

(2)

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

(3)

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

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

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

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ù)中通過的數(shù)量；numberm指的是眾包方u完成難度系數(shù)中等的任務(wù)總次數(shù)；amountm是完成的中等任務(wù)中通過的數(shù)量；numbere指的是眾包方u完成簡單任務(wù)的總次數(shù)；amounte是完成的簡單任務(wù)中通過的數(shù)量。

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

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

(5)

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

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

2.2 新眾包方問題的解決

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

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

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

3 實驗方案及分析

3.1 實驗方案

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

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

Tab.1Thetimeandinitialexperiencevalueofthecrowd-sourcingpartytocompletethetask

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

3.2 實驗結(jié)果分析

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

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

圖2 隨機分配算法中眾包方負載

圖3 本文算法中眾包方負載

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

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

Fig.4Thecrowdsourcingpartyobtainsthetaskratiointherandomallocationalgorithm

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

Fig.5Thecrowdsourcingpartyobtainsthetaskratiointhealgorithmofthispaper

4 結(jié)束語

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