基于動(dòng)態(tài)閾值的時(shí)空眾包在線分配算法

余敦輝，袁 旭，張萬山，王晨旭

（1. 湖北大學(xué)計(jì)算機(jī)與信息工程學(xué)院，武漢430062； 2. 湖北省教育信息化工程技術(shù)中心，武漢430062）

（*通信作者電子郵箱904016107@qq.com）

0 引言

隨著共享經(jīng)濟(jì)模式的迅速發(fā)展，誕生了眾包［1-4］這種依賴群體智慧的分布式協(xié)同工作模式。例如Amazon Mechanical Turks（AMT）、CrowdFlower 等眾包平臺(tái)，通過互聯(lián)網(wǎng)將眾包任務(wù)分配給非特定工作群體，這種模式的迅速發(fā)展，使得眾包成為了工業(yè)界和學(xué)術(shù)界的研究熱點(diǎn)。尤其是近幾年，伴隨著移動(dòng)互聯(lián)網(wǎng)的迅速發(fā)展和移動(dòng)設(shè)備的普及，眾包模式不再局限于傳統(tǒng)眾包中的在線工作模式，逐漸衍生出時(shí)空眾包［5］這種蘊(yùn)含更多時(shí)空屬性的眾包模式，例如，滴滴打車、Uber、美團(tuán)外賣等時(shí)空眾包應(yīng)用的日益流行，為人們生活產(chǎn)生了很多便利。

在時(shí)空眾包的研究中，任務(wù)分配是其核心問題之一，而如何將帶有時(shí)間、位置屬性的任務(wù)分配給合適的工人，使得平臺(tái)效益最大化是時(shí)空眾包任務(wù)分配重要指標(biāo)之一。文獻(xiàn)［6-8］中分別研究了不同靜態(tài)場景下的時(shí)空眾包任務(wù)分配問題，但現(xiàn)實(shí)中眾包工人和任務(wù)多為動(dòng)態(tài)出現(xiàn)。而眾包任務(wù)動(dòng)態(tài)在線分配方面的研究大都聚焦于動(dòng)態(tài)在線匹配模型的構(gòu)造［9］，其難點(diǎn)在于工人和任務(wù)的出現(xiàn)時(shí)間和位置難以預(yù)料。文獻(xiàn)［10］研究了將搖臂賭博機(jī)（multi-armed bandit）機(jī)制與任務(wù)分配相結(jié)合，該方法融入了在線學(xué)習(xí)（online learning）領(lǐng)域的重要模型，但優(yōu)化目標(biāo)為任務(wù)分配數(shù)量，不能保證工人的效益。文獻(xiàn)［11］提出了實(shí)時(shí)的質(zhì)量預(yù)算方法，旨在保證高分配率的同時(shí)最大限度地提升分配質(zhì)量，但未考慮工人效率。文獻(xiàn)［12-14］綜合考慮了平臺(tái)與工人的利益，通過效用函數(shù)來表示單個(gè)工人完成任務(wù)所產(chǎn)生的效益，將優(yōu)化目標(biāo)定為所有工人完成任務(wù)后的分配總效用，其中文獻(xiàn)［12］將任務(wù)回報(bào)值與工人服務(wù)質(zhì)量的乘積作為效用，構(gòu)建自適應(yīng)閾值算法完成任務(wù)分配，不足是未考慮任務(wù)完成時(shí)間、地理位置和工人偏好等因素對(duì)任務(wù)分配的影響，且基于固定效用閾值完成任務(wù)篩選。文獻(xiàn)［13］提出基于動(dòng)態(tài)效用的閾值算法，以單位時(shí)間內(nèi)完成眾包任務(wù)所獲報(bào)酬為效用，但分配方法基于貪心思想，總效用還有很大的提升空間。文獻(xiàn)［14］提出基于時(shí)效均衡的在線閾值算法，以任務(wù)回報(bào)值與工人服務(wù)質(zhì)量的乘積作為效用，并在最大化總效用的同時(shí)預(yù)降低任務(wù)發(fā)布者等待時(shí)間，該算法不足是未考慮任務(wù)的時(shí)效性。

通過對(duì)上述閾值類算法的分析，不難發(fā)現(xiàn):1）通常只考慮了平臺(tái)的收益，工人的效益難以得到保障；2）大多采用的是隨機(jī)閾值，從而容易導(dǎo)致閾值過低起不到篩選作用，或閾值過高使得大部分工人或任務(wù)無法正常參與匹配；3）大多以效用為閾值，從而導(dǎo)致在非均勻分布數(shù)據(jù)上，對(duì)于高效工人與高回報(bào)任務(wù)聚集區(qū)域難以篩選，低效工人與低回報(bào)任務(wù)聚集區(qū)域難以匹配。

本文擴(kuò)展隨機(jī)閾值算法，設(shè)計(jì)了一種基于在線隨機(jī)森林的動(dòng)態(tài)閾值算法（Dynamic Threshold algorithm based on online Random Forest，DTRF），針對(duì)不同工人篩選出對(duì)應(yīng)“高回報(bào)率”任務(wù)，同時(shí)避免了非均勻數(shù)據(jù)導(dǎo)致的閾值效果驟減和隨機(jī)閾值導(dǎo)致的算法不穩(wěn)定，動(dòng)態(tài)地為工人分配理想的任務(wù)。在綜合考慮工人實(shí)時(shí)利益、平臺(tái)總效用、任務(wù)時(shí)效性的基礎(chǔ)上，對(duì)工人理想的任務(wù)回報(bào)率作預(yù)測，并以此作為任務(wù)分配的依據(jù)。

1 相關(guān)定義及問題分析

1.1 相關(guān)定義

定義1 時(shí)空眾包任務(wù)t。t由任務(wù)發(fā)起者在眾包平臺(tái)上發(fā)布，通常被定義為t=lt，rt，pt，dt，ft，ut。其中:lt為任務(wù)當(dāng)前的空間位置，rt為任務(wù)t能被工人所接受的半徑，pt為任務(wù)發(fā)布時(shí)間，dt為任務(wù)截止時(shí)間，ft為完成任務(wù)t所獲得的報(bào)酬，ut為任務(wù)目的地點(diǎn)。

定義2 時(shí)空眾包工人w。w是時(shí)間眾包任務(wù)的參與者，通常被定義為w=lw，rw，aw，ew，sw。其中:lw為工人w當(dāng)前的空間位置，rw是工人w能接受任務(wù)的范圍半徑，aw代表工人w抵達(dá)平臺(tái)的時(shí)間，sw為工人效率，表示工人w的歷史任務(wù)成功率。

定義3 任務(wù)回報(bào)率g。g指眾包工人w完成眾包任務(wù)t后單位時(shí)間的平均效益，定義為g(w，t)=ft（ct），ct為平臺(tái)預(yù)估工人w完成任務(wù)t所耗費(fèi)時(shí)長。

定義4 眾包分配效用U。U是指眾包工人在單位時(shí)間完成眾包任務(wù)所產(chǎn)生的效益，定義為U(w，t)=g(w，t)×sw。

1.2 問題分析

時(shí)間約束 只有工人任務(wù)同時(shí)在線且工人能在任務(wù)截止時(shí)間dt之前到達(dá)任務(wù)地點(diǎn)才能接受任務(wù)。

空間約束 任務(wù)分配t，w必須滿足任務(wù)t在以lw為中心，rw為半徑的范圍內(nèi)。

不變性約束 任務(wù)分配一旦給出，不可更改。

2 整體解決方案

為了解決MUTA 問題，首先，根據(jù)眾包平臺(tái)歷史分配數(shù)據(jù)中工人w的特征集合{Fw1，F(xiàn)w2，…，F(xiàn)wn}作為在線隨機(jī)森林樣本輸入，工人w歷史完成任務(wù)的任務(wù)回報(bào)率g作為樣本輸出，構(gòu)建出原始在線隨機(jī)森林（Online Random Forest）；其次，基于在線隨機(jī)森林對(duì)工人期望的任務(wù)回報(bào)率作預(yù)測，并將其預(yù)測值gexp作為工人篩選任務(wù)的初始閾值θIw；然后，在初始閾值的基礎(chǔ)上設(shè)計(jì)了一種動(dòng)態(tài)閾值算法，對(duì)初始閾值進(jìn)行動(dòng)態(tài)調(diào)整，以完成對(duì)工人的候選匹配集Cw的篩選；最后，基于KM（Kuhn-Munkres）算法從剩余的t，w匹配中獲取當(dāng)前時(shí)間窗的最大效用匹配集。每輪新的分配過程如下:

1）將工人w的特征集{Fw1，F(xiàn)w2，…，F(xiàn)wn}輸入在線隨機(jī)森林，通過在線隨機(jī)森林回歸模型為待分配工人w預(yù)測一個(gè)期望的任務(wù)回報(bào)率gexp，并以此為工人w篩選任務(wù)的初始閾值θIw；

2）根據(jù)工人w的已等待時(shí)間WT將初始閾值θIw調(diào)整為θw；

3）通過范圍查詢算法，將處于待分配工人w接受任務(wù)的范圍半徑rw內(nèi)，且工人w能在任務(wù)截止時(shí)間dt之前抵達(dá)的任務(wù)加入工人w候選匹配集Cw；

4）將工人w候選匹配集Cw中匹配任務(wù)回報(bào)率g(w，t)低于預(yù)閾值θw的任務(wù)剔除；

5）在綜合考慮任務(wù)截止時(shí)間dt以及任務(wù)回報(bào)率g(w，t)的基礎(chǔ)上，用KM 算法進(jìn)行當(dāng)前最大總效用匹配，進(jìn)而完成對(duì)工人w的任務(wù)分配。

3 基于動(dòng)態(tài)閾值算法的任務(wù)篩選

3.1 基本思想

閾值算法（Threshold Algorithm）中閾值對(duì)象的選取是影響分配總效用的關(guān)鍵因素，其策略的核心在于舍棄部分低效用匹配來規(guī)避最差的情況。因?yàn)槿蝿?wù)和工人在任務(wù)范圍半徑rw內(nèi)出現(xiàn)的動(dòng)態(tài)性，若不基于工人任務(wù)回報(bào)率來設(shè)置閾值，則有可能出現(xiàn)某個(gè)回報(bào)率低的任務(wù)在當(dāng)前時(shí)間窗被分配，從而使得該工人無法接受下一個(gè)時(shí)間窗所出現(xiàn)的回報(bào)率更高的任務(wù)，最終導(dǎo)致工人效用的損失。為此，本文基于工人的任務(wù)回報(bào)率來對(duì)工人能接受任務(wù)范圍半徑內(nèi)的任務(wù)進(jìn)行篩選，舍棄回報(bào)率相對(duì)較低的任務(wù)。

閾值大小的設(shè)置對(duì)任務(wù)分配效用至關(guān)重要，過高會(huì)導(dǎo)致工人接不到任務(wù)，過低則無法起到篩選作用。為此，本文綜合考慮任務(wù)與工人自身的效率、周圍其他工人的效率以及周圍任務(wù)的分布狀況等因素，完成對(duì)工人預(yù)期任務(wù)回報(bào)率的預(yù)測，最終基于預(yù)期的任務(wù)回報(bào)率實(shí)現(xiàn)閾值的動(dòng)態(tài)設(shè)置。

考慮到對(duì)任務(wù)回報(bào)率的預(yù)測在現(xiàn)實(shí)場景中會(huì)出現(xiàn):1）容易產(chǎn)生異常數(shù)據(jù)，例如，突發(fā)意外狀況導(dǎo)致的額外損失；2）實(shí)時(shí)的天氣、道路狀況對(duì)回報(bào)率造成很大影響。由于隨機(jī)森林訓(xùn)練速度快、預(yù)測準(zhǔn)確率高、不需要過多的參數(shù)優(yōu)化、能夠動(dòng)態(tài)地進(jìn)行調(diào)整等特點(diǎn)，因此選用在線隨機(jī)森林作為本文預(yù)測方法。

3.2 在線隨機(jī)森林構(gòu)建

文獻(xiàn)［15］中研究表明，集成回歸（Integrated Regression）比單回歸器具有更好的泛化性能。在線隨機(jī)森林就是由多個(gè)回歸樹h(x，θk)組成的集成學(xué)習(xí)算法，隨著回歸樹數(shù)量的增加，隨機(jī)森林泛化誤差會(huì)收斂到極限。在線隨機(jī)森林構(gòu)建過程分如下3步:

1）工人情境特征選取。工人情境特征作為回歸模型的輸入，對(duì)回歸樹構(gòu)建至關(guān)重要。本文選取對(duì)工人完成任務(wù)回報(bào)率產(chǎn)生影響的幾個(gè)主要因素作為工人情境特征，如工人當(dāng)前所在時(shí)間I、地點(diǎn)P、天氣WE、工人效率sw、周圍工人密度ρw、周圍任務(wù)密度ρt、周圍任務(wù)平均回報(bào)tˉ。

3.5 算法分析

在DTKT算法中，假設(shè)工人集合W中工人數(shù)量為n，任務(wù)集合T中任務(wù)數(shù)量為m，k-d樹建樹的時(shí)間復(fù)雜度和空間復(fù)雜度分別O(mlogm)和O(m)，查找單個(gè)工人w有效范圍內(nèi)的任務(wù)集Cw的時(shí)間復(fù)雜度和空間復(fù)雜度分別為O(m1/2)和O(1)，對(duì)工人進(jìn)行任務(wù)篩選的時(shí)間復(fù)雜度和空間復(fù)雜度分別為O(k)（k為Cw中任務(wù)的個(gè)數(shù)，一般遠(yuǎn)小于m）和O(1)。因此，DTKT算法的時(shí)間復(fù)雜度和空間復(fù)雜度分別為O(mlogm+nm1/2)和O(m)。

3.6 運(yùn)行實(shí)例

如圖2 所示，當(dāng)搜索以工人w1為圓心、2.5 為半徑的范圍內(nèi)所有任務(wù)時(shí):1）由于x方向上的方差大于y方向上的方差，所以用x方向上中間點(diǎn)t4來分割平面，然后按照規(guī)則遞歸分割，生成如圖3所示樹結(jié)構(gòu)；2）從根節(jié)點(diǎn)t4開始搜索，在x方向上t1比t5距w1更近，因此搜索到t1，此時(shí)搜索路徑為t4→t1；3）在y方向上t3比t6距w1更近，因此搜索到t3，此時(shí)搜索路徑為t4→t1→t3，由于t3為葉子節(jié)點(diǎn)，并且在w1范圍內(nèi)，因此將t3加入結(jié)果集，此時(shí)結(jié)果集為{t3}；4）從t3開始回溯到t1，由于t1在w1范圍內(nèi)，因此將t1加入結(jié)果集，結(jié)果集為{t1，t3}；5）搜索t1的右孩子節(jié)點(diǎn)t6，發(fā)現(xiàn)t6不在w1范圍內(nèi)，且t6為葉子節(jié)點(diǎn)，此時(shí)搜索路徑為t4→t1；6）從t1回溯到t4，發(fā)現(xiàn)t4不在w1范圍內(nèi)且t4的分割線x= 7 不與w1所在圓相交，回溯到根節(jié)點(diǎn)，算法結(jié)束，返回結(jié)果集{t1，t3}。

圖3 任務(wù)k-d樹對(duì)應(yīng)的二叉樹圖Fig. 3 Binary graph corresponding to task k-d tree

4 基于KM算法的任務(wù)分配

通過閾值算法對(duì)工人候選任務(wù)集篩選避免了大量較差效用的匹配，但為了進(jìn)一步優(yōu)化全局總效用，還需要求解出當(dāng)前最優(yōu)的匹配，KM（Kuhn-Munkres）算法是帶權(quán)二分圖的最優(yōu)匹配算法，通過將工人-任務(wù)的匹配轉(zhuǎn)換為帶權(quán)二分圖求出當(dāng)前時(shí)間窗的最優(yōu)匹配。

4.1 基于任務(wù)結(jié)束時(shí)間和任務(wù)回報(bào)率的匹配度計(jì)算

除了任務(wù)回報(bào)率和工人效率之外，任務(wù)結(jié)束時(shí)間也是影響整體效用的一個(gè)關(guān)鍵因素，例如當(dāng)工人w周圍的任務(wù)t1比任務(wù)t2回報(bào)率略高，而t1剩余有效時(shí)長遠(yuǎn)遠(yuǎn)高于t2時(shí)，如果優(yōu)先分配t1，很可能導(dǎo)致t2超時(shí)而損失，最終導(dǎo)致分配總效用降低。因此，為了均衡任務(wù)回報(bào)率和任務(wù)有效時(shí)期限對(duì)工人收益的影響，本文定義工人、任務(wù)匹配的匹配度v為:

其中，RTt為任務(wù)剩余有效時(shí)間，RTt∈[0，+ ∞)，任務(wù)t剩余時(shí)間越短則擁有越高的權(quán)值。

4.2 基于KM算法的在線最優(yōu)匹配

為了選取當(dāng)前時(shí)間窗滿足閾值條件的最優(yōu)分配，首先將待分配工人集W和任務(wù)集T分別視為二分圖的兩個(gè)點(diǎn)集，待分配工人wi與候選任務(wù)tj的匹配度V(i，j)看作二分圖的邊的權(quán)重。然后，通過KM 算法尋找二分圖的最優(yōu)匹配，進(jìn)而完成當(dāng)前時(shí)間窗最優(yōu)匹配?；谠诰€隨機(jī)森林的動(dòng)態(tài)閾值算法（Dynamic Threshold algorithm based on online Random Forest，DTRF）的整體算法描述如下所示。

算法2 基于在線隨機(jī)森林的動(dòng)態(tài)閾值算法（DTRF）。

4.3 算法舉例

假設(shè)當(dāng)前待分配工人集合W={w1，w2，w3，w4，w5}和任務(wù)集合T={t1，t2，t3，t4}中工人與任務(wù)的信息如表1 所示，工人和任務(wù)相對(duì)位置如圖4所示。按照DTRF執(zhí)行步驟:

在對(duì)學(xué)生進(jìn)行分層強(qiáng)化訓(xùn)練的過程中，雖然大部分學(xué)生都能夠向好的方面發(fā)展，但是依舊有一小部分學(xué)生成績進(jìn)步不是很明顯，這些現(xiàn)象還有待于日后更好的解決，也就是說從根本上改變一小部分學(xué)生的不良學(xué)習(xí)習(xí)慣和主觀態(tài)度還是需要一定時(shí)間的，比如有的同學(xué)沉迷于網(wǎng)絡(luò)、小說、游戲等，這就不僅需要老師，而且要家庭和社會(huì)各方面有利的配合。

1）據(jù)工人有效范圍半徑獲得工人候選任務(wù)匹配集為:Cw1={(w1，t3)，(w1，t4)}、Cw2={(w2，t4)，(w2，t5)}、Cw3={(w3，t3)}、Cw4={(w4，t1)，(w4，t2)，(w4，t5)}、Cw5={(w5，t1)}。

2）首先根據(jù)在線隨機(jī)森林預(yù)獲取每個(gè)工人期望的任務(wù)回報(bào)率，設(shè)得到工人初始閾值θIw1=13.5、θIw2=15.3、θIw3=12.8、θIw4=14.7、θIw5=16.3，然后根據(jù)工人已等待時(shí)間進(jìn)行閾值調(diào)整，計(jì)算得:θw1=10.6、θw2=11.8、θw3=10.0、θw4=11.5、θw5=13.4。

3）通過g(w，t)函數(shù)得到:g(w1，t3)= 11.2 ＞θw1、g(w1，t4)=11.6 ＞θw1、g(w2，t4)= 10.3 ＜θw2、g(w2，t5)= 12.7 ＞θw2、g(w3，t3)=10.7 ＞θw3、g(w4，t1)= 12.1 ＞θw4、g(w4，t2)= 13.6 ＞θw4、g(w4，t5)=11.4 ＜θw4、g(w5，t1)= 12.6 ＜θw5，通過動(dòng)態(tài)閾值篩 選 后 工 人 候 選 匹 配 集 為:Cw1={(w1，t3)，(w1，t4)}、Cw2={(w2，t5)}、Cw3={(w3，t3)}、Cw4={(w4，t1)，(w4，t2)}。

4）計(jì)算Cw中工人與任務(wù)的匹配系數(shù)為:V(w1，t3)= 8.89、V(w1，t4)= 7.74、V(w2，t5)= 9.52、V(w3，t3)=8.49、V(w4，t1)=10.32、V(w4，t2)= 10.20。

5） 通過KM 算法得到當(dāng)前最優(yōu)匹配為:M={(w1，t4)，(w2，t5)，(w3，t3)，(w4，t1)}，匹 配 總 效 用 為11.6×0.8+12.7×0.7+ 10.7×0.75+ 12.1×0.65即34.06。

表1 DTRF舉例Tab. 1 Examples of DTRF

圖4 任務(wù)和工人位置示意圖Fig. 4 Schematic diagram of task and worker locations

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

5.1 實(shí)驗(yàn)準(zhǔn)備

為驗(yàn)證本文算法的有效性，實(shí)驗(yàn)數(shù)據(jù)從聚數(shù)力網(wǎng)站（http://dataju.cn）上下載并整理得到。數(shù)據(jù)處理時(shí)選取范圍為相對(duì)位置300×300 的工人和任務(wù)數(shù)據(jù)共60 000 條。將匹配數(shù)據(jù)分成10 份進(jìn)行交叉驗(yàn)證，每份取5 000 條匹配數(shù)據(jù)作為模型的訓(xùn)練集，1 000條匹配數(shù)據(jù)作為驗(yàn)證集。分別從任務(wù)分配成功率、分配總效用、工人平均收益和運(yùn)行時(shí)間4 個(gè)方面比較了貪心算法、隨機(jī)閾值算法、自適應(yīng)閾值算法和DTRF。本文實(shí)驗(yàn)在具有2.4 GHz Inter Core i5 處理器和8 GB 內(nèi)存的機(jī)器上運(yùn)行，操作系統(tǒng)為Windows 10，編程語言為C++。實(shí)驗(yàn)數(shù)據(jù)如表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)參數(shù)Tab. 2 Experimental data parameters

5.2 分配總效用實(shí)驗(yàn)結(jié)果分析

本文的優(yōu)化目標(biāo)為任務(wù)分配的總效用，在這組實(shí)驗(yàn)中，通過改變工人數(shù)量、任務(wù)數(shù)量、工人接受范圍半徑以及任務(wù)等待時(shí)間四種條件，分別比較了四種算法在不同情況下對(duì)分配總效用的影響，如圖5 所示，實(shí)驗(yàn)表明，在分配總效用方面，DTRF穩(wěn)定且大多數(shù)情況下優(yōu)于其他三種算法，貪心算法最為穩(wěn)定，但總效用一直低于其他算法。當(dāng)工人數(shù)量增加時(shí)，總效用上升趨勢都很明顯；當(dāng)任務(wù)數(shù)量增加時(shí)，DTRF 和貪心算法的總效用呈線性上升，隨機(jī)閾值算法和自適應(yīng)閾值算法雖有波動(dòng)但也都上升較大；當(dāng)工人接受任務(wù)范圍的半徑rw增加時(shí)，總效用增加一段之后基本穩(wěn)定不變；當(dāng)任務(wù)等待時(shí)間WT增加時(shí)，總效用只有少量提升。

圖5 四種算法在分配總效用方面的實(shí)驗(yàn)結(jié)果Fig. 5 Experimental results of four algorithms in total allocation utility

5.3 任務(wù)分配成功率實(shí)驗(yàn)結(jié)果分析

5.4 工人平均收益結(jié)果分析

眾包工人的平均收益也是影響眾包平臺(tái)穩(wěn)定的一個(gè)重要因素，由于本文以工人期望的任務(wù)回報(bào)率為閾值，所以在優(yōu)化分配總效用兼顧到了工人的收益，這組實(shí)驗(yàn)對(duì)比了不同情況下四種算法對(duì)工人平均收益的影響，如圖7 所示。實(shí)驗(yàn)表明，DTRF在工人平均收益方面優(yōu)于其他三種算法，但偶爾會(huì)有低于其他算法的情況。當(dāng)工人數(shù)量增加時(shí)，由于工人間競爭加劇，工人平均收益都下降較快，但隨著工人遠(yuǎn)遠(yuǎn)超過任務(wù)，降低趨勢趨于平緩；當(dāng)任務(wù)數(shù)量增加時(shí)，工人平均收益剛開始上升較快，但當(dāng)任務(wù)遠(yuǎn)遠(yuǎn)多于工人時(shí)平均收益基本穩(wěn)定；當(dāng)工人接受任務(wù)范圍的半徑rw增加時(shí)，工人平均收益基本穩(wěn)定不變；當(dāng)任務(wù)等待時(shí)間WT增加時(shí)，工人平均收益有一定增長，但很快保持穩(wěn)定。

圖6 四種算法在任務(wù)分配成功率方面的實(shí)驗(yàn)結(jié)果Fig. 6 Experimental results of four algorithms in task allocation

圖7 四種算法在工人平均收益方面的實(shí)驗(yàn)結(jié)果Fig. 7 Experimental results of four algorithms on average worker income

5.5 運(yùn)行時(shí)間分析

在眾包工作中，由于眾包工人和任務(wù)都是動(dòng)態(tài)出現(xiàn)，每當(dāng)出現(xiàn)新工人或新任務(wù)時(shí)分配算法都會(huì)運(yùn)行一次，所以分配算法的運(yùn)行時(shí)間對(duì)分配效率產(chǎn)生了很大影響，若運(yùn)行時(shí)間過長會(huì)大大降低平臺(tái)的效益，這組實(shí)驗(yàn)通過對(duì)比不同情況下四種算法的運(yùn)行時(shí)間來驗(yàn)證算法的合理性。如圖8所示，DTRF 會(huì)在初始構(gòu)建時(shí)耗費(fèi)一定時(shí)間，但之后的運(yùn)行時(shí)間僅比隨機(jī)閾值算法和自適應(yīng)閾值算法略高，所以DTRF 在運(yùn)行時(shí)間上的劣勢不大，貪心算法的運(yùn)行時(shí)間比其他算法要低很多。當(dāng)工人數(shù)量增加時(shí)，四種算法的運(yùn)行時(shí)間都上升很快；當(dāng)任務(wù)數(shù)量增加時(shí)，DTRF 和貪心算法的運(yùn)行時(shí)間呈線性上升；當(dāng)工人接受任務(wù)范圍的半徑rw增加時(shí)，運(yùn)行時(shí)間基本保持不變；當(dāng)任務(wù)等待時(shí)間WT增加時(shí)，運(yùn)行時(shí)間有一定波動(dòng)但變化不大。

5.6 實(shí)驗(yàn)總結(jié)

通過以上實(shí)驗(yàn)不難發(fā)現(xiàn):

1）在分配總效用方面，DTRF始終略高于隨機(jī)閾值算法和自適應(yīng)閾值算法，且比貪心算法要高很多。

2）在任務(wù)分配成功率方面，DTRF與自適應(yīng)閾值算法差距不大，但始終高于隨機(jī)閾值算法和貪心算法，且在工人數(shù)量、任務(wù)數(shù)量、任務(wù)范圍半徑和任務(wù)等待時(shí)間變動(dòng)時(shí)，DTRF最為穩(wěn)定。

3）在工人平均收益方面，DTRF 展現(xiàn)出了較大的優(yōu)勢，雖然在收益狀況好時(shí)與隨機(jī)閾值算法和自適應(yīng)閾值算法差距不大，但其他三種算法在工人數(shù)量、任務(wù)數(shù)量、任務(wù)范圍半徑和任務(wù)等待時(shí)間變化較大時(shí)，工人平均收益出現(xiàn)了比較大的波動(dòng)，而DTRF沒有出現(xiàn)收益驟減的情況。

4）在運(yùn)行時(shí)間方面，雖然DTRF 運(yùn)行時(shí)間比其他算法都要長，但是大部分時(shí)間耗費(fèi)在預(yù)處理數(shù)據(jù)上面，而運(yùn)行過程中只是略高于其他算法，并且DTRF 可以通過分布式處理的方式加快運(yùn)行。

綜上所述，與其他三種算法相比，DTRF 能夠在耗費(fèi)少量時(shí)間代價(jià)的情況下，獲取一定程度上的分配總效用、任務(wù)分配成功率以及工人平均收益三個(gè)方面的增長，所以DTRF 具有較好的實(shí)際應(yīng)用價(jià)值。

6 結(jié)語

本文研究了時(shí)空眾包環(huán)境下動(dòng)態(tài)在線任務(wù)分配問題，通過借鑒在線學(xué)習(xí)的思想以及機(jī)器學(xué)習(xí)的方法，對(duì)工人任務(wù)回報(bào)率的期望值作預(yù)測，在優(yōu)化平臺(tái)總效用的基礎(chǔ)上保障工人的利益。通過與貪心算法、隨機(jī)閾值算法和自適應(yīng)閾值算法的對(duì)比實(shí)驗(yàn)，驗(yàn)證了該算法能夠有效地提升平臺(tái)總效用、工人的平均收益以及任務(wù)分配率，且能夠很好地適應(yīng)現(xiàn)實(shí)場景下工人和任務(wù)的動(dòng)態(tài)出現(xiàn)。在未來的時(shí)空眾包研究中，可以探索以下兩個(gè)方面:1）研究工人的目的地點(diǎn)對(duì)未來分配的影響，將每個(gè)場景劃分為舊場景變化和新增場景；2）在現(xiàn)有閾值的基礎(chǔ)上考慮工人的路徑規(guī)劃，對(duì)工人的旅行消耗進(jìn)行優(yōu)化。

圖8 四種算法在運(yùn)行時(shí)間方面的實(shí)驗(yàn)結(jié)果Fig. 8 Experimental results on running time of four algorithms