高麗萍,段普鴿,高 麗

1(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院,上海 200093)

2(復(fù)旦大學(xué) 上海數(shù)據(jù)科學(xué)重點實驗室,上海 200093)

3(上海理工大學(xué) 圖書館,上海 200093)

1 引 言

眾包[1]作為一個大眾人群積極參與其中的新型計算范式,已經(jīng)融入到我們生活的各個領(lǐng)域.近年來隨著互聯(lián)網(wǎng)行業(yè)的快速發(fā)展以及移動設(shè)備的激增,傳統(tǒng)的基于網(wǎng)絡(luò)的眾包正在轉(zhuǎn)向具有很大發(fā)展前景的空間眾包[2].任務(wù)分配[3]是空間眾包平臺面臨的首要挑戰(zhàn).在空間眾包中,工人需要親自前往目標(biāo)位置執(zhí)行任務(wù),因此,關(guān)于任務(wù)分配方法的很多研究都集中在最小化工人執(zhí)行任務(wù)的出行成本上.然而,這些研究在計算工人出行成本時都只單單考慮距離的遠(yuǎn)近.現(xiàn)實情況是,工人對想要執(zhí)行的任務(wù)地點的熟悉程度也很重要,這關(guān)乎到工人能否順利到達(dá)指定地點,及時完成任務(wù)以及是否有良好的出行體驗,目前很多研究工作沒有考慮這一點.本文在計算工人到達(dá)任務(wù)地點所要花費的代價時綜合考慮二者距離的長短以及工人對任務(wù)地點的熟知度兩方面因素.

工人對將要執(zhí)行的任務(wù)的偏好程度也被很多現(xiàn)有的任務(wù)分配方法忽略,然而除了出行成本,偏好也會影響工人在整個執(zhí)行任務(wù)過程中的體驗感.如果眾包平臺能投其所好,給工人分配到他比較想要執(zhí)行的任務(wù),工人就會有充足的動力,這樣也會增強任務(wù)被順利完成的可能性.另外,基于工人的意愿進(jìn)行任務(wù)分配時還要考慮工人的聲譽,聲譽越高,表明工人越有把握成功完成任務(wù).而且對于請求者來說,但凡是提交到眾包平臺上的任務(wù),都希望得到預(yù)期的結(jié)果,將任務(wù)分配給聲譽高的工人更能保證結(jié)果質(zhì)量.因此在設(shè)計任務(wù)分配方案時引入聲譽值既考慮到了工人執(zhí)行任務(wù)的積極性,又保障了請求者的利益.

綜上,本文提出一個以用戶體驗為導(dǎo)向的空間任務(wù)分配問題并建立最大化任務(wù)被成功完成的可能性分配(MPA)模型.MPA模型考慮了工人的出行成本,工人對任務(wù)的偏好度以及工人執(zhí)行任務(wù)累積的聲譽值3方面因素,基于此模型產(chǎn)生的任務(wù)分配方案對工人和請求者都是有利的.對于工人來說,MPA模型充分考慮了其在執(zhí)行任務(wù)時會考量的因素,選擇積極性高的工人執(zhí)行相關(guān)任務(wù),這樣也能保證任務(wù)完成的質(zhì)量和效率.從長遠(yuǎn)來看,能吸引更多的人參與到空間眾包任務(wù)的執(zhí)行中來.對于請求者來說,MPA任務(wù)分配模型能夠盡可能使其獲得期望的結(jié)果.總之,本文的目標(biāo)是讓眾包系統(tǒng)的所有利益相關(guān)者,即工作人員、請求者和平臺都被兼顧到.本文還提出改進(jìn)的模擬退火算法,即MPS-SA算法智能搜索最佳分配方案以最大化全局概率分?jǐn)?shù).最后,在真實數(shù)據(jù)集和仿真數(shù)據(jù)集上通過與其他算法的比較驗證了MPS-SA算法的有效性.

2 相關(guān)工作

近年來,關(guān)于空間眾包任務(wù)分配的研究有很多.Tong[4]等人首次提出空間眾包的全局在線微任務(wù)分配問題(GOMA),其中,任務(wù)和工人可以隨機(jī)地動態(tài)出現(xiàn).Zhao[5]等人提出基于工人時間偏好的空間眾包任物分配系統(tǒng),設(shè)計了偏好感知的個體任務(wù)分配算法,隨后又提出將每個任務(wù)分配給一組工人的策略優(yōu)化了原來的框架.

一般來說,空間眾包平臺在進(jìn)行任務(wù)分配時,要實現(xiàn)一定的優(yōu)化目標(biāo),如最大化分配任務(wù)的總數(shù)或最小化平臺的招募成本.Liu[6]等人提出了兩個雙目標(biāo)優(yōu)化問題—FPMT問題(工人少,任務(wù)多)和MPFT(工人多,任務(wù)少)問題.FPMT問題的目標(biāo)是最大化完成任務(wù)的數(shù)量和最小化工人的總行駛距離,而MPFT問題的目標(biāo)是最小化平臺的總支付報酬和最小化工人的總行駛距離.Zhang[7]等人使用工人置信度來表示成功完成所分配任務(wù)的可靠性,提出了招聘預(yù)算約束下的最大化可靠性分配問題(MRA)和任務(wù)可靠性要求下的最小化成本分配問題(MCA)并分別構(gòu)建優(yōu)化函數(shù).

由于空間眾包的特性,工人與任務(wù)之間的距離成為任務(wù)分配的重要度量指標(biāo).gMission[8]平臺是一個典型的空間眾包平臺,其主要工作是獲得用戶的位置信息然后據(jù)此推薦任務(wù).在推薦任務(wù)時平臺只考慮距離的遠(yuǎn)近,也就是說,任務(wù)常常被推薦給離它最近的工人.在文獻(xiàn)[9]中,首次關(guān)注空間眾包任務(wù)分配率并提出任務(wù)包分配的問題.其中,分配是基于工人和任務(wù)之間的一定范圍的距離度量,這里的距離使用的是歐幾里得距離.文獻(xiàn)[10]認(rèn)為在三維空間中使用歐幾里得距離度量方法不夠精確,為了提高距離的精確度,Jaya[10]等人提出用半正矢公式測量工人到任務(wù)的距離.文獻(xiàn)[11] 注意到在某些場合,工人對將要前往的任務(wù)地點是否熟悉成為及時正確完成空間任務(wù)的關(guān)鍵,因此將最大化位置熟悉度作為優(yōu)化目標(biāo).

目前對以數(shù)據(jù)質(zhì)量為主要目標(biāo)的參與者選擇方法的研究還不夠深入[12].在優(yōu)化分配方案時考慮工人完成任務(wù)的結(jié)果情況是很有必要的.由于請求者的預(yù)算有限,又想獲得期望的結(jié)果,因此目前很多研究都希望在控制成本和達(dá)到請求者的預(yù)期結(jié)果之間達(dá)到一個平衡[13].解決這個問題一種比較有效的方法是聲譽感知計算[14].在文獻(xiàn)[13]中,工人執(zhí)行一項任務(wù)的結(jié)果預(yù)期質(zhì)量由工人的聲譽和他與該任務(wù)地點之間的距離共同決定的,其中工人的信譽還決定了他在每項任務(wù)中能得到多少報酬.Wang[15]等人也認(rèn)為工人完成某項任務(wù)的質(zhì)量受到二者的物理距離和工人的信譽影響,并分別定義了物理位置影響系數(shù)和工人的可信度影響系數(shù).

可以發(fā)現(xiàn),目前現(xiàn)有的關(guān)于空間眾包任務(wù)分配的研究大都只把工人的出行距離作為出行成本的單一衡量因素,甚至直接用工人總的行駛路程來表示眾包平臺的招募成本,并且工人對任務(wù)的偏好和聲譽這兩個因素也沒有被充分利用.本文在計算工人的出行成本時,引入了工人對任務(wù)地點的熟知度.不僅如此,本文構(gòu)建的任務(wù)分配模型還結(jié)合了工人的偏好和聲譽,同時兼顧了請求者和工人的利益.

3 相關(guān)定義和MPA模型建立

在本節(jié)中,首先介紹了一些相關(guān)定義,然后引出本文的任務(wù)分配問題,即MPA模型的建立.

3.1 相關(guān)定義

定義1.工人

用W={w1,w2,…,wm}表示一組工人,單個工人wi={lwi,repi,σi,num},其中l(wèi)wi表示工人wi的位置,repi代表工人wi的聲譽,σi是工人wi可接受的任務(wù)的最遠(yuǎn)距離,num表示工人wi可接受任務(wù)的最大數(shù)量.

定義2.空間任務(wù)

用T={t1,t2,…,tn}表示一組空間任務(wù),單個任務(wù)tj={ltj,etj},其中l(wèi)tj表示任務(wù)tj所在的位置,etj是tj的過期時間.

空間眾包服務(wù)器會定期組織可用的工人,給其分配有效的任務(wù).在本文中,一個任務(wù)分配周期內(nèi)有m個工人,n個任務(wù),一個任務(wù)最多由一個工人完成,而一個工人可以完成多個任務(wù).我們假定每個工人有相同的最大任務(wù)負(fù)載量num,這是由空間眾包服務(wù)器基于調(diào)查評估的[11].我們還假設(shè)任務(wù)可以在過期之前被完成.

定義3.位置熟悉度

每個工人wi對每個任務(wù)tj所在位置的熟悉度定義如下:

(1)

定義4.工人的出行成本

本文用經(jīng)緯度坐標(biāo)表示工人和任務(wù)的位置信息.用dist(wi,tj)表示工人wi當(dāng)前位置和任務(wù)tj所在位置之間的物理距離,首先,將角度轉(zhuǎn)化成弧度,用到下面的公式:

(2)

則工人wi的經(jīng)緯度坐標(biāo)locwi(dlatwi,dlngwi)和任務(wù)tj的經(jīng)緯度坐標(biāo)loctj(dlattj,dlngtj)分別轉(zhuǎn)化成locwi(rlatwi,rlngwi)和loctj(rlattj,rlngtj).然后,二者之間的距離公式如下:

dist(wi,tj)=

(3)

其中,x=rlatwi-rlattj,y=rlngwi-rlngtj,R是地球半徑.

距離越近,對任務(wù)所在地越熟悉,工人越能快速順暢到達(dá),所花費的代價也就越小.因此,本文用一個分?jǐn)?shù)來表示工人執(zhí)行某一任務(wù)的出行成本,如下面公式所示,Tcostij是工人wi執(zhí)行任務(wù)tj的出行成本.

(4)

定義5.工人對任務(wù)的偏好

由于需要移動到特定地點才能完成空間任務(wù),因此工人可能想在前往一些目的地的途中執(zhí)行任務(wù),例如下班回家的路上,或者是偏愛那些距離自己當(dāng)前位置沒那么遠(yuǎn)的任務(wù)地點.我們用prefij表示工人wi對任務(wù)tj的偏好:

prefij=1-max[0,min[logσi(dist(wi,tj)),1]]

(5)

由上述公式可知,工人對位于距離閾值之外的任務(wù)的偏好度是0,也就是說,工人只可能接受在自己一定距離范圍內(nèi)的任務(wù).

3.2 MPA模型建立

聲譽代表了工人成功完成所分配任務(wù)的可靠性.聲譽值越高,工人成功完成任務(wù)的把握就越大.一個工人的聲譽值可以從他執(zhí)行任務(wù)的歷史數(shù)據(jù)中推斷出來.本文旨在研究以用戶體驗為導(dǎo)向的空間眾包任務(wù)分配問題,影響用戶體驗的3個因素分別是工人到達(dá)任務(wù)地點的出行成本,工人對任務(wù)的偏好以及工人的聲譽.可以發(fā)現(xiàn),這3個因素不僅決定了工人執(zhí)行空間任務(wù)的體驗感,實際上還關(guān)系到工人成功完成所分配任務(wù)的可能性.因此本文研究的以用戶體驗為導(dǎo)向的任務(wù)分配問題可以量化為計算工人成功完成任務(wù)的概率分?jǐn)?shù).把工人wi成功完成任務(wù)tj的可能性得分記作Probij,計算公式如下:

(6)

然后,建立如下全局目標(biāo)函數(shù):

(7)

約束為:

(8)

(9)

其中,xij是一個二進(jìn)制變量,表示任務(wù)tj是否分配給工人wi.,每個任務(wù)只能分配給一個工人,并且分配給工人的任務(wù)數(shù)量不能超過他的負(fù)載.

綜上,本文從用戶體驗出發(fā),把最大化任務(wù)被成功完成的可能性分配問題轉(zhuǎn)化為求最佳全局概率分?jǐn)?shù)問題.

4 MPA模型實現(xiàn)

在一個分配周期內(nèi),首先計算m個工人分別針對不同的任務(wù)得到的概率分?jǐn)?shù).如果工人之前沒去過將要前往的任務(wù)地點,那么出行成本就直接等于二者之間的物理距離.因為通過公式(1),可以發(fā)現(xiàn)時間間隔要達(dá)到10145.728小時,熟悉度才為1.注意,每個工人都有一個可接受任務(wù)的距離范圍σ,也就是說當(dāng)任務(wù)所在地距離工人當(dāng)前位置超過σ時,工人對該任務(wù)的偏好為0.計算概率分?jǐn)?shù)的方法如算法1所示.

算法1.計算概率分?jǐn)?shù)

輸入：Wloc←worker GPS location

Tloc←worker GPS location

Wrep←worker Reputation

Distance thresholdσ

Time intervalWt

輸出：Prob[W][T]

1. for workerwiinWlocdo

2. for tasktjinTlocdo

3.x=rlatwi-rlattj,y=rlngwi-rlngtj

4. Calculatedist(wi,tj) according to formula 3

5. fortijinWtdo

8.prefij=1-max[0,min[logσi(dist(wi,tj)),1]]

9. forwiinWdo

10. fortjinTdo

Prob[i][j]=(prefij×Wrepi)/Tcostij

本文最后的目標(biāo)是找到使全局概率分?jǐn)?shù)最大的任務(wù)分配方案,由于任務(wù)分配需要滿足一定的約束,這使問題變得困難起來,在這里我們采用一種基于模擬退火算法(Simulated Annealing,SA)的啟發(fā)式算法.SA借鑒固體的退火原理,在尋找給定函數(shù)的全局最優(yōu)值方面具有一定的優(yōu)勢[18].SA在某一溫度下的每次迭代中,都會產(chǎn)生一個新的解,然后通過評估目標(biāo)函數(shù)將新解與當(dāng)前解進(jìn)行比較.SA接受更好的解作為當(dāng)前解,并按Metropolis準(zhǔn)則[19]來接受一個比當(dāng)前解要差的解,這樣可以避免陷入局部最優(yōu),繼續(xù)搜索更多可能的解從而得到全局最優(yōu)解.SA的算法流程如圖1所示.

圖1 SA算法流程圖

可以看出,擾動產(chǎn)生新解的策略對于算法能否快速實現(xiàn)全局收斂非常重要.尤其是當(dāng)解空間很大時,就要盡可能擴(kuò)大搜索范圍從而防止算法陷入局部最優(yōu).傳統(tǒng)的模擬退火算法在解決本文這類問題時,通常只采用簡單隨機(jī)交換的方式產(chǎn)生新的解,由于本文的MPA問題搜索空間較大,這種產(chǎn)生新解的方法不能有效地達(dá)到預(yù)期的結(jié)果.為了盡快取得全局最優(yōu)值,本文設(shè)計的MPS-SA在產(chǎn)生新的分配結(jié)果時不僅考慮到隨機(jī)性,還考慮到搜索的方向性,主要采用以下3種方式:

a)在當(dāng)前的分配結(jié)果中任意挑選兩個工人,然后隨機(jī)交換分配給他們的任務(wù),如果其中一個工人沒有被分配任務(wù),那么將另一個工人的任務(wù)直接轉(zhuǎn)移給他.

b)在當(dāng)前的分配結(jié)果中,任意挑選一個任務(wù)tj,然后隨機(jī)分配給工人wi,如果工人wi已經(jīng)達(dá)到他的最大負(fù)載量,不能再接受新的任務(wù),那么就用tj替換掉wi目前執(zhí)行的概率分?jǐn)?shù)最小的任務(wù),同時將替換掉的任務(wù)分配給原來執(zhí)行tj的工人.

c)在當(dāng)前的分配結(jié)果中,將未形成分配的工人-任務(wù)對應(yīng)的概率分?jǐn)?shù)按從大到小的順序排列,然后依次對已分配的任務(wù)進(jìn)行重新分配,重新分配的原則是:在這里,假設(shè)未形成分配的工人-任務(wù)對應(yīng)的概率分?jǐn)?shù)為pij(表示工人wi如果執(zhí)行tj,成功的概率分?jǐn)?shù)為pij),其中任務(wù)tj已經(jīng)被分配給了工人wm,而工人wm完成tj的成功可能性分?jǐn)?shù)小于pij,那么就將tj重新分配給工人wi.注意,分配給工人wi的任務(wù)數(shù)量不能超過他的最大承受數(shù)量num.如果超過,不再重新分配,繼續(xù)查看下一個稍小的概率分?jǐn)?shù).

算法2描述了MPS-SA的過程.在某一溫度下的每次迭代中,采用上文提到的3種方法產(chǎn)生新解.第7～第11行表示當(dāng)新的任務(wù)分配方案優(yōu)于當(dāng)前的任務(wù)分配方案時,那么就直接將當(dāng)前的任務(wù)分配方案更新為新的任務(wù)分配方案,否則,以一定的概率接受新方案為當(dāng)前的任務(wù)分配方案.在一開始,把當(dāng)前溫度設(shè)為最高溫度.第8行根據(jù)公式(10)更新當(dāng)前溫度,其中ρ是一個常數(shù),表示溫度下降的速率.每一溫度下的所有迭代結(jié)束后,將當(dāng)前溫度Temp與最小的溫度Tmin進(jìn)行比較,當(dāng)Temp

Temp=ρ×Tmax

(10)

算法2.MPS-SA

輸入：Prob[W][T],the maximum temperatureTmax,the minimum temperatureTmin,the rate of temperature declineρ,the iteration timesiter

輸出：∑Prob,Set of worker-task pairs

1. Generate the initial task assignment result randomly;

2.Temp=Tmax

3. whileTemp>Tmindo

4. forj=1 toiterdo

5.NewSolution= GenerateNewSolution()

Calculate ∑Probnew

7. if ∑Probnew>∑Probcur

8.CurrentSolution=NewSolution;

9. else Calculate the probabilityp

10. ifp>rand(0,1)

11.CurrentSolution=NewSolution;

12. renew the current temperatureTempby Eq.(10);

5 實驗分析

在本節(jié)中,我們在真實數(shù)據(jù)集及仿真數(shù)據(jù)集上評估了本文提出的MPS-SA算法的性能.首先介紹了數(shù)據(jù)集和一些實驗設(shè)置.然后從不同方面對提出的解決MPA問題的算法進(jìn)行實驗分析,給出了不同參數(shù)設(shè)置下的實驗結(jié)果,包括不同的任務(wù)數(shù),工人數(shù)以及工人的最大任務(wù)負(fù)載量等.

5.1 實驗數(shù)據(jù)集

數(shù)據(jù)集來自文獻(xiàn)[20],其中包含了會員信息數(shù)據(jù)和項目任務(wù)數(shù)據(jù),將每個會員都視為一個可用的工人.工人信息數(shù)據(jù)和任務(wù)數(shù)據(jù)都包含了位置信息,也就是經(jīng)緯度坐標(biāo).對于之前去過的任務(wù)地點,工人距離上一次前往的時間間隔在[8,2400]小時內(nèi)隨機(jī)生成.另外,為了便于后面的計算,本文的位置熟悉度直接用百分點表示.同樣,為了計算方便,用下面的公式標(biāo)準(zhǔn)化工人的聲譽值,使其在1～100的范圍內(nèi).

(11)

由于工人只對地點在自己一定距離范圍的任務(wù)感興趣,本文將距離閾值設(shè)置為20千米.此外,工人最多能執(zhí)行的任務(wù)數(shù)量對實驗結(jié)果也有影響,在這里將工人的最大任務(wù)負(fù)載量設(shè)置為3個.本文進(jìn)行50次實驗,然后取平均概率分?jǐn)?shù)值(該值量化了工人成功完成任務(wù)的可能性,結(jié)合本節(jié)實際數(shù)據(jù),越大越好)作為最后的實驗結(jié)果.實驗運行在一臺擁有Intel Core i5-10210U 處理器,8GB RAM的聯(lián)想筆記本電腦上.操作系統(tǒng)是windows 10,編程語言是Java.

5.2 實驗結(jié)果

圖2表明了在不同任務(wù)數(shù)量下本文使用的MPS-SA算法和其他算法在性能方面的比較,工人的數(shù)量固定在80,其中每個工人最多執(zhí)行3個任務(wù).由圖2可以看出,隨著任務(wù)數(shù)量的不斷增加,任務(wù)能被成功完成的可能性分?jǐn)?shù)整體呈上升趨勢,這是因為所求的概率分?jǐn)?shù)是全局性的.圖2清楚地表明本文使用的MPS-SA算法能得到更大的概率分?jǐn)?shù),這說明我們提出的方法具有一定的搜索最優(yōu)解的優(yōu)勢.

圖2 任務(wù)數(shù)量對概率分?jǐn)?shù)的影響

不同算法在不同工人數(shù)量下的性能對比如圖3所示.其中,任務(wù)的數(shù)量固定在140,每個工人最多執(zhí)行3個任務(wù).從圖3可以看出,對于SA和本文提出的MPS-SA來說,一開始工人數(shù)量的變化對概率分?jǐn)?shù)的影響并不是很大,后面隨著平臺上可用的工人越來越多,目標(biāo)函數(shù)值才增加的較明顯.這是因為當(dāng)工人的規(guī)模比較大時,可選的工人范圍就大,這樣選中更加合適的工人的可能性就越高.除此之外,可以看出本文提出的MPS-SA算法相較于傳統(tǒng)的SA算法和貪婪算法在最大化目標(biāo)函數(shù)上仍然是具有優(yōu)勢的.

圖3 工人數(shù)量對概率分?jǐn)?shù)的影響

圖4顯示了在工人最多接受的任務(wù)數(shù)量不同的情況下,概率分?jǐn)?shù)的變化.其中,工人數(shù)固定在80,任務(wù)數(shù)固定在140,每個工人的最大任務(wù)負(fù)載量分別設(shè)置為2,3,4,5,6.圖4說明總的概率分?jǐn)?shù)受工人最多能執(zhí)行的任務(wù)數(shù)量影響并不是很大.隨著工人可承受的任務(wù)數(shù)量增多,在搜索概率分?jǐn)?shù)較高的工人來執(zhí)行任務(wù)的過程中就不會那么受限,因此用MPA-SA算法求解的最優(yōu)值在逐步增大.

圖4 工人最多執(zhí)行的任務(wù)數(shù)量對概率分?jǐn)?shù)的影響

圖5顯示了在本文提出的算法下,任務(wù)能被成功完成的概率分?jǐn)?shù)隨不同工人,不同任務(wù)數(shù)量的變化情況.從圖5可以得知,在任務(wù)數(shù)量固定的情況下,全局最優(yōu)值隨工人數(shù)量的增加緩慢增大.當(dāng)工人數(shù)量相同的時候,任務(wù)數(shù)量越多,概率分?jǐn)?shù)就越大.

圖5 工人數(shù)量、任務(wù)數(shù)量對概率分?jǐn)?shù)的影響

6 結(jié)束語

本文構(gòu)建了一個最大化任務(wù)成功完成的可能性分配(MPA)模型.為了解決MPA模型中的最大化概率分?jǐn)?shù)問題,本文提出一種有效的基于模擬退火的啟發(fā)式算法(MPS-SA).MPS-SA算法在每次迭代過程中都致力于找到更優(yōu)的解而不是盲目地搜尋,這樣能盡快得到使概率分?jǐn)?shù)最大的任務(wù)分配結(jié)果.最后在真實數(shù)據(jù)集上進(jìn)行實驗,結(jié)果表明MPS-SA算法在實現(xiàn)優(yōu)化分配上具有一定的競爭力.當(dāng)然,本文還有一些方面需要完善,比如在計算出行成本時,可以根據(jù)工人的需求給距離和位置熟知度設(shè)置相應(yīng)的權(quán)重.未來,我們還計劃考慮空間眾包平臺的成本預(yù)算,另一個可以探究的方向是工人及任務(wù)位置數(shù)據(jù)的動態(tài)性.