偏好匹配滿意度最大化的眾包任務(wù)分配*

郭嘉宇,付曉東,2,岳 昆,劉 驪,馮 勇,劉利軍

(1.昆明理工大學信息工程與自動化學院,云南 昆明 650500；2.昆明理工大學云南省計算機技術(shù)應(yīng)用重點實驗室,云南 昆明 650500；3.云南大學信息學院,云南 昆明 650504)

1 引言

近年來，互聯(lián)網(wǎng)技術(shù)和開放式創(chuàng)新的迅速發(fā)展促使眾包模式逐漸盛行。文獻[1]將眾包定義為一種公開的面向互聯(lián)網(wǎng)大眾的問題解決機制，它通過整合互聯(lián)網(wǎng)上未知的大眾來完成計算機難以單獨完成的任務(wù)。參與眾包活動的3個主體分別為：眾包發(fā)包者，通過眾包平臺發(fā)放眾包任務(wù)；眾包接包者(眾包工人)，由個體工人組成的問題解決群體；眾包平臺，連接眾包發(fā)包者和眾包工人的中間媒介，其中眾包發(fā)包者和眾包工人皆為眾包平臺用戶。眾包任務(wù)分配機制作為眾包平臺核心機制之一，其目的是在滿足特定限制條件的前提下，從候選參與者中選擇合適的一個或一組參與者來承擔任務(wù)的執(zhí)行[2]。

眾包質(zhì)量受多種因素影響，如任務(wù)難度、工人素質(zhì)和分配方法等，如何保障眾包完成質(zhì)量成為待解決的問題之一[3]。眾包發(fā)包者及工人的偏好與行為直接影響眾包完成質(zhì)量和雙方的滿意度，但現(xiàn)有的研究通常忽視了這一點。此外，在開放的網(wǎng)絡(luò)環(huán)境中，眾包發(fā)包者和眾包工人可進行溝通與交流，分配結(jié)果可能隨著分配雙方發(fā)現(xiàn)更好的合作對象而有所變更，出現(xiàn)無效分配。例如，眾包發(fā)包者在分配到不滿意的工人時，選擇取消訂單，從而產(chǎn)生了無效訂單，增加了眾包平臺分配次數(shù)；在翻譯通平臺中，工人根據(jù)自身偏好接受任務(wù)后，在任務(wù)執(zhí)行階段若出現(xiàn)分配雙方更加偏好的合作對象，發(fā)包者可能對當前翻譯工人的工作進行否定，而翻譯工人則可能放棄當前任務(wù)，出現(xiàn)無效的眾包訂單，打破了分配結(jié)果的穩(wěn)定性，給任務(wù)發(fā)包者及翻譯工人帶來了較差的眾包服務(wù)體驗。

為了解決上述問題，本文提出一種面向偏好匹配的眾包任務(wù)分配方法，該方法使用批處理模式動態(tài)地解決眾包任務(wù)分配問題。首先，在等分的時間間隔內(nèi)，獲取需分配的任務(wù)與工人并提取雙方的偏好序；然后，將偏好序信息轉(zhuǎn)換為分配雙方滿意度，在穩(wěn)定匹配規(guī)則下構(gòu)造滿意度最大化優(yōu)化模型；最后，使用貪心算法對模型求解，并更新未分配主體的偏好序信息，以便在下個時間間隔為其繼續(xù)分配，最終實現(xiàn)動態(tài)化眾包任務(wù)分配。此外，文中方法對無差別偏好進行關(guān)聯(lián)度計算，決策過程中選用關(guān)聯(lián)度較小的分配方案，減少無差別偏好對算法求解精度的影響，為無差別偏好的決策提供了新的思路。

2 相關(guān)工作

近年來國內(nèi)外學者圍繞眾包任務(wù)分配開展了大量研究，眾包完成質(zhì)量越來越受到人們的關(guān)注。根據(jù)現(xiàn)有研究對眾包過程各階段處理方式的差異，眾包任務(wù)分配方法主要包括任務(wù)分解分配法、基于迭代策略任務(wù)分配法、帶有社會結(jié)構(gòu)的任務(wù)分配法等。

在處理復雜眾包任務(wù)時，較為常見的方法是任務(wù)分解分配法。在這種方式中，復雜任務(wù)被分解成許多簡單的子任務(wù)，用工作流來約束它們之間的關(guān)系，每個工人獨立執(zhí)行簡單的子任務(wù)，然后再匯聚子任務(wù)的結(jié)果。文獻[4]在特定眾包場景下研究了基于MapReduce框架分解復雜眾包任務(wù)并整合工人答案完成初始任務(wù)的方法。文獻[5]將復雜的眾包任務(wù)分解為微任務(wù)并分配給多個眾包工人，獲得多個任務(wù)結(jié)果并選出最佳答案，從而提高了眾包任務(wù)完成質(zhì)量。文獻[6]提出了智能任務(wù)分解法，分解大規(guī)模眾包任務(wù)以最小的成本獲得所需的工人。在任務(wù)分解分配法中，不僅要求發(fā)包者具備良好的任務(wù)分解能力，而且對任務(wù)結(jié)果的匯聚算法要求較高。

對于迭代策略任務(wù)分配法，文獻[7]提出一種數(shù)據(jù)分析系統(tǒng)，在任務(wù)執(zhí)行的過程中，通過評估完成質(zhì)量來判斷是否提前終止任務(wù)，以保證結(jié)果質(zhì)量。文獻[8]提出基于社會網(wǎng)絡(luò)分解復雜眾包任務(wù)的批量分配方法，將復雜任務(wù)中相似的子任務(wù)集成到一個批量中，分配給相同的工人。文獻[9]提出階段式動態(tài)眾包質(zhì)量控制策略，在任務(wù)執(zhí)行過程中設(shè)置檢測點，如果發(fā)現(xiàn)工人提交的結(jié)果質(zhì)量低下，則招募新工人代替舊工人。迭代策略分配在一定程度上保證了眾包任務(wù)完成質(zhì)量，然而在分配過程中未考慮任務(wù)及工人偏好。

對于帶有社會結(jié)構(gòu)的任務(wù)分配法，文獻[10]分別提出完全集中和完全分散的社會網(wǎng)絡(luò)任務(wù)分配方法，結(jié)合了社會網(wǎng)絡(luò)和物理網(wǎng)絡(luò)的影響，顯著減少了執(zhí)行任務(wù)的通信時間。文獻[11]研究了社交網(wǎng)絡(luò)中復雜眾包任務(wù)的團隊形成問題，利用工人之間的熟悉度，提高工人協(xié)作能力。文獻[12]研究了一種基于情景感知的眾包任務(wù)分配方法，復雜的任務(wù)可以通過分配給可靠工人及其社會網(wǎng)絡(luò)中感知的工人自主協(xié)調(diào)來完成。

此外，任務(wù)分配算法的典型目標包括任務(wù)分配質(zhì)量最大化[13]、系統(tǒng)成本與開銷最小化[14]等。文獻[15]以貪心算法作為基礎(chǔ)算法，提出了一種基于兩階段框架模型的微任務(wù)分配算法，在確保算法高效執(zhí)行的同時提高任務(wù)分配效用。文獻[16]提出了一種多任務(wù)分配框架，為每個工人分配一組適當?shù)娜蝿?wù)，從而使整個系統(tǒng)的效用最大化。文獻[17]將異構(gòu)任務(wù)分配問題抽象為動態(tài)背包問題，并提出了一種改進的算法，該算法隨機選擇了工人到達的順序，目標是在預算固定的約束條件下最大化分配任務(wù)的數(shù)量。

上述研究在分配初始化階段采取了不同的處理策略和目標，以提高眾包任務(wù)完成質(zhì)量，然而在分配實現(xiàn)階段并未在穩(wěn)定規(guī)則下考慮眾包分配主體雙方的偏好及滿意度，無法保證分配結(jié)果的穩(wěn)定性?？紤]到以上的不足，本文以偏好理論與穩(wěn)定思想作為基礎(chǔ)，結(jié)合眾包特性提出偏好匹配滿意度最大化分配模型，以眾包任務(wù)與工人的偏好作為輸入，求解模型以獲取分配方案。最后，通過實驗來驗證該方法的合理性及有效性。

3 問題描述

為了更好地闡述偏好匹配滿意度最大化的眾包任務(wù)分配問題，本文先對相關(guān)概念進行描述。

定義1集合Φ={s1,s2,…,sk，…sl}表示整個分配時間段，sk表示將Φ進行等分后的時間間隔。

為了解決動態(tài)任務(wù)分配問題，本文采用批處理模式，按照sk等分后的時間間隔分批次獲取相應(yīng)的眾包任務(wù)與工人。

定義2集合T={t1,t2,…,tm}為眾包任務(wù)集合，ti(1≤i≤m)表示眾包任務(wù)集合T中第i個任務(wù)；集合W={w1,w2,…,wn}為眾包工人集合，wj(1≤j≤n)表示眾包工人集合W中第j個工人。其中，眾包任務(wù)與工人作為分配機制的參與主體，統(tǒng)稱為分配主體，m表示眾包任務(wù)數(shù)量，n表示眾包工人數(shù)量。

定義3眾包任務(wù)ti對眾包工人的偏好序定義為ri=wπ(1)?wπ(2)?…?wπ(pi)，ri(j)表示工人wj在任務(wù)ti偏好序列中的位序，ri(j)越小則偏好程度越高，整體任務(wù)的偏好集合為R={ri|i=1,2,…,m}；眾包工人wj對眾包任務(wù)的偏好序定義為uj=tλ(1)?tλ(2)?…?tλ(qj)，uj(i)表示任務(wù)ti在眾包工人wj偏好序列中的位序，uj(i)越小則偏好程度越高，整體工人的偏好集合為U={uj|j=1,2,…,n}。

定義3中，wπ(1)?wπ(2)表示任務(wù)ti認為工人wπ(1)優(yōu)于工人wπ(2)，π(pi)表示工人序列號，pi表示任務(wù)ti的偏好序列長度，pi

定義4在眾包任務(wù)ti的偏好序ri中，若?wa,wb，滿足ri(a)=ri(b)，則稱眾包任務(wù)ti的偏好序中存在無差別偏好，表示任務(wù)ti對工人wa,wb的偏好程度相同。其中，無差別偏好在眾包任務(wù)分配過程中表現(xiàn)為任務(wù)(工人)認為多個工人(任務(wù))之間沒有區(qū)別，本文使用tie表示偏好序列中存在無差別偏好關(guān)系。當分配主體的偏好序列中出現(xiàn)無差別偏好時，分配決策過程影響分配結(jié)果。

定義5集合TW={〈ti,wj〉|ti∈T,wj∈W}表示任務(wù)分配集合，TW中的眾包任務(wù)-工人分配關(guān)系界定為關(guān)系M，二元組〈ti,wj〉為眾包任務(wù)-工人分配對，也記為(ti)M(wj)或者(wj)M(ti)，表示眾包任務(wù)ti分配給了工人wj。集合[ti]M={j|wj∈W,(ti)M(wj)}表示與任務(wù)ti存在分配關(guān)系的工人序列號集合，集合[wj]M={i|ti∈T,(ti)M(wj)}表示與工人wj存在分配關(guān)系的任務(wù)序列號集合。其中，在眾包任務(wù)-工人分配關(guān)系M中，若|[ti]M|=0表示任務(wù)ti未分配；若|[wj]M|=0則表示工人wj未分配。

因此，眾包任務(wù)分配問題可表達為：給定時間片段Φ={s1,s2,s3,…}，在每個時間段sk內(nèi)，獲取需分配的眾包任務(wù)集合T與眾包工人集合W，設(shè)置任務(wù)分配目標函數(shù)，并根據(jù)目標函數(shù)求解分配方案TW，使得TW中目標函數(shù)值最大化。

4 基于偏好匹配的眾包任務(wù)分配

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，眾包用戶的上下文信息越來越容易采集，如眾包用戶的時間、位置和情緒等。通過這些上下文信息，能夠有效地將真實情景信息融入到偏好提取過程中。結(jié)合眾包環(huán)境和偏好提取的相關(guān)研究[18,19]，可能影響眾包任務(wù)偏好的上下文因素包括：工人類型標簽、工人信譽和工人歷史行為等；可能影響眾包工人偏好的上下文因素包括：任務(wù)類型標簽、任務(wù)難度、任務(wù)酬勞和任務(wù)執(zhí)行時間等。本文使用文獻[20]中基于上下文信息的用戶偏好提取方法，在不同的眾包場景下，根據(jù)歷史評分等信息確定分配主體偏好與上下文維度的相關(guān)性，然后根據(jù)任務(wù)申請情況進行雙方評分預測，最終經(jīng)過排序獲得眾包任務(wù)與工人的偏好序。

4.1 分配雙方的滿意度獲取

分配雙方主體給出的偏好序信息在一定程度上反映了雙方主體間的相互滿意程度，然而在實際應(yīng)用中偏好序值的增加(減小)與滿意程度的降低(增加)之間不一定呈線性關(guān)系[21]。為了更好地描述眾包任務(wù)(工人)對分配工人(任務(wù))的滿意程度，將雙方滿意度定義如下：

定義6設(shè)αij為任務(wù)ti對工人wj的滿意度，βij為工人wj對任務(wù)ti的滿意度，滿意度αij與βij可分別表示為：

(1)

(2)

其中，ci為任務(wù)ti所需的工人人數(shù)，bj為工人wj可接受的任務(wù)數(shù)量。l(x)與g(x)具有多種表達方式，反映了分配主體在實際問題中不同的偏好類型，本文使用序列偏好，位序值越高則主體滿意度越小。因此，設(shè)定l(x)與g(x)為單調(diào)遞減函數(shù)，0≤l(x),g(x)≤1，在模型中給定：

(3)

(4)

則滿意度轉(zhuǎn)化為：

(5)

(6)

其中，pi表示任務(wù)ti的偏好序列長度，qj表示工人wj的偏好序列長度。當任務(wù)(工人)不在工人(任務(wù))的偏好序列中，則當前工人(任務(wù))對該任務(wù)(工人)滿意程度為0。當前時間段中所有任務(wù)對眾包工人的滿意度用矩陣SatT=[αij]m×n表示，當前時間段中所有眾包工人對眾包任務(wù)的滿意度用矩陣SatW=[βij]n×m表示。

4.2 穩(wěn)定匹配

穩(wěn)定匹配最早應(yīng)用在婚姻匹配中，其概念是由Gale等[22]提出的。Mcvitie等[23]系統(tǒng)地定義了穩(wěn)定匹配，其核心思想是實現(xiàn)一種穩(wěn)定狀態(tài)，在這種狀態(tài)下的分配主體相比于其他可更換對象，都更中意于當前的分配對象。

在開放的網(wǎng)絡(luò)環(huán)境中，眾包用戶可以自主地進行交流與溝通，具有穩(wěn)定性的分配方案可以確保分配雙方之間維系穩(wěn)定的合作關(guān)系。無效分配出現(xiàn)在因產(chǎn)生不穩(wěn)定分配對，導致合作關(guān)系破裂的分配方案中。若分配結(jié)果是不穩(wěn)定的，則存在2個(未)分配的主體，對彼此的偏好程度均優(yōu)于當前分配對象，有著放棄當前分配對象而相互合作的“動機”，進而出現(xiàn)無效分配。為了避免以上情況的出現(xiàn)，本文引入穩(wěn)定匹配的概念，在穩(wěn)定匹配的約束條件下獲取滿意度最大化分配方案，即使分配主體想變更分配結(jié)果也不會存在比當前分配對象更滿意的選項，出于對自身利益的考慮，從而放棄變更“動機”。本文給出以下穩(wěn)定匹配定義：

定義7對于眾包分配方案TW，若分配對〈ti,wj〉滿足以下情況之一，稱分配對〈ti,wj〉為不穩(wěn)定分配對，包含不穩(wěn)定分配對的任務(wù)分配方案為不穩(wěn)定分配方案。

(1)?ti,tb∈T,?wj,wa∈W,〈ti,wa〉∈TW,〈tb,wj〉∈TW，滿足ri(j)

(2)?ti∈T,?wj,wa∈W,〈ti,wa〉∈TW,|[wj]M|=0，滿足ri(j)

(3)?ti,tb∈T,?wj∈W,〈tb,wj〉∈TW,|[ti]M|=0或0<|[ti]M|

(4)?ti∈T,?wj∈W,|[ti]M|=0,|[wj]M|=0，滿足i∈T(j)且j∈W(i)。

其中，(1)表示任務(wù)ti,tb分別分配給工人wa,wj，任務(wù)ti相比于現(xiàn)有分配對象wa更偏好工人wj，且工人wj相比于現(xiàn)有分配對象tb更偏好于ti；(2)表示任務(wù)ti分配給工人wa，工人wj未分配，任務(wù)ti和工人wj相互偏好程度更高但未分配；(3)表示工人wj分配給任務(wù)tb，任務(wù)ti未分配或者仍有工人需求，任務(wù)ti和工人wj相互偏好程度更高但未相互分配；(4)表示任務(wù)ti和工人wj未相互分配，但有相互分配的意愿。

為了獲取分配結(jié)果中不穩(wěn)定分配對的數(shù)量，本文使用反饋算法計算分配主體雙方放棄當前分配對象的“動機”數(shù)量。反饋算法模擬眾包用戶交互過程，向當前分配方案中任務(wù)更偏好但未相互分配的工人發(fā)出邀請，工人選擇拒絕邀請或者更換分配對象，變更數(shù)量越多意味著無效的分配結(jié)果越多。反饋算法如算法1所示。

算法1反饋算法

輸入：眾包任務(wù)集合T,眾包工人集合W。

輸出：不穩(wěn)定分配數(shù)量UM。

Step1UM=0;

Step2FOReach taskti∈TDO

Step2.1TP=W(ti);

Step2.2FOReach workerwj∈TP

Step2.2.1WP=T(wj);

Step2.2.2IFti∈WPANDri(j)

Step2.2.2.1UM++;

Step2.2.3ELSETHEN

Step2.2.3.1CONTINUE

Step2.2.4ENDIF

Step2.3ENDFOR

Step3ENDFOR

Step4RETURNUM。

該算法在任務(wù)分配完成后，根據(jù)眾包任務(wù)數(shù)量會執(zhí)行m次，算法結(jié)合定義7查找當前任務(wù)更偏好的工人，并判斷是否存在不穩(wěn)定分配對。算法的終止條件為分配方案中最后一個任務(wù)處理結(jié)束，算法在有限的迭代次數(shù)后收斂，且迭代次數(shù)為多項式時間O(mn)。

4.3 基于偏好匹配的眾包任務(wù)分配模型

給定m個眾包任務(wù)和n個眾包工人以及雙方主體的偏好序，根據(jù)4.1節(jié)中滿意度計算方式獲取眾包任務(wù)-工人滿意度和任務(wù)-工人滿意度。基于偏好匹配的眾包任務(wù)分配方法在穩(wěn)定匹配的規(guī)則下，尋找滿意度最大化分配方案TW。該模型的目標函數(shù)為：

(7)

其中，αij為任務(wù)ti對工人wj的滿意度。在模型中，xij為決策變量，表示任務(wù)ti是否分配給工人wj，1代表分配，0代表不分配。結(jié)合眾包環(huán)境，該模型滿足以下基本約束條件：

(1)工人wj所分配的任務(wù)總量小于自身可接受量。

(8)

其中，bj為工人wj可接受的任務(wù)數(shù)量(在當前眾包環(huán)境下，為了保證任務(wù)完成質(zhì)量，模型設(shè)定每位工人在一次分配中僅可接受一項任務(wù)，即bj=1)。

(2)任務(wù)分配完整性約束，任務(wù)一旦在當前時間段內(nèi)分配，則需滿足任務(wù)ti所需要的工人數(shù)。

(9)

其中，ci為任務(wù)ti所需要的工人數(shù)量，決策變量yi代表任務(wù)ti是否分配，1代表分配，0代表不分配。協(xié)作型眾包任務(wù)需要多人合作完成工作，當工人數(shù)量不夠時需要等待工人加入，直到滿足任務(wù)所需工人數(shù)量方可開展工作。該約束保證了協(xié)作型任務(wù)分配的完整性，避免占用工人申請額度，減少工人資源的浪費。若任務(wù)無需合作完成，則該約束條件可省略。

(3)穩(wěn)定性約束，若工人wj分配給任務(wù)ti，則滿足已分配給任務(wù)ti的工人數(shù)量未達到該任務(wù)需求且任務(wù)ti對這些工人的偏好程度均高于wj。

j=1,2,…,n;i∈T(j)

(10)

j=1,2,…,n;i∈T(j)

(11)

(4)若任務(wù)ti對工人wj無偏好，即工人wj不在任務(wù)ti偏好序列中，則任務(wù)ti與工人wj不能進行分配。

(12)

(5)若工人wj對任務(wù)ti無偏好，即任務(wù)ti不在工人wj偏好序列中，則任務(wù)ti與工人wj不能進行分配。

(13)

結(jié)合眾包環(huán)境，在約束條件的共同作用下，該模型在單次分配過程中可保證任務(wù)分配的完整性，因此選取定義7中(1)、(2)作為本文模型的非穩(wěn)定匹配約束。以上約束條件可根據(jù)眾包類型和應(yīng)用環(huán)境進行調(diào)整使用。

4.4 基于偏好匹配的眾包任務(wù)分配算法

在眾包任務(wù)分配過程中，為了在出現(xiàn)tie的情況下對分配對象進行選擇，本文借鑒PageRank[24]算法思想，在滿意度相同的情況下選擇對其他待分配主體影響較小的選項。以下給出關(guān)聯(lián)度相關(guān)定義：

定義8設(shè)CN(vi)為分配個體vi的關(guān)聯(lián)度，表示個體vi在分配時對其他主體分配結(jié)果的影響程度，CN的計算如式(4)所示：

(14)

其中，V(vi)表示所有對vi存在偏好的對象集合，P(vj)表示主體vj的偏好序列長度，N表示分配雙方總體個數(shù)，θ為阻尼參數(shù)，一般取0.85。

在眾包任務(wù)分配過程中，相關(guān)度具有以下特性：(1)如果一個工人(任務(wù))出現(xiàn)在很多任務(wù)(工人)偏好序列中，表明該工人(任務(wù))較為受歡迎，關(guān)聯(lián)度會相對較高；(2)如果一個同等滿意度且關(guān)聯(lián)度值很高的工人(任務(wù))被分配，那么對其他任務(wù)(工人)的分配結(jié)果會產(chǎn)生影響，關(guān)聯(lián)度越高影響程度越大。

基于以上分析，在tie中選取分配主體時，使用關(guān)聯(lián)度較小的節(jié)點，可減少對向下拓展節(jié)點的影響程度。根據(jù)當前眾包任務(wù)與工人的偏好序信息建立偏好網(wǎng)絡(luò)，把待分配的眾包任務(wù)與工人看作獨立節(jié)點，若任務(wù)ti對工人wj擁有偏好，則節(jié)點ti指向節(jié)點wj，稱為邊(ti,wj)。節(jié)點具有相同的初始關(guān)聯(lián)度值，經(jīng)過多次迭代獲取最終關(guān)聯(lián)度值。算法的時間復雜度為O((m+n)2t(ε))，其中(m+n)是眾包用戶數(shù)量，t(ε)是迭代次數(shù)，這個迭代次數(shù)與收斂的閾值ε有關(guān)。在眾包任務(wù)與工人數(shù)量較多的情況下，迭代的次數(shù)與總偏好個數(shù)接近線性比[24]。

隨著眾包用戶的增多，眾包任務(wù)分配問題的規(guī)模逐漸增大，貪心算法是把一個復雜問題分解為一系列較為簡單的局部最優(yōu)選擇問題，每一步選擇都是對當前解的一個擴展，直到獲得問題的完整解。算法遍歷長度為m的任務(wù)列表，每次選擇一個未分配任務(wù)進行分配，遍歷該任務(wù)的偏好序列，將最大滿意度的工人在穩(wěn)定性規(guī)則下分配給該任務(wù)，執(zhí)行m次迭代后將返回的結(jié)果作為眾包任務(wù)分配的結(jié)果。

算法2穩(wěn)定條件下貪心算法

輸入：眾包任務(wù)集合T，眾包任務(wù)偏好集合R，眾包工人集合W，眾包工人偏好集合U。

輸出：分配方案TW與最大滿意度MaxSat。

Step1MaxSat=0;

Step2FOReach taskti∈TDO

Step2.1Temp= 當前任務(wù)ti偏好序列中滿足模型約束條件的工人個數(shù);

Step2.2IFTemp>=ciTHEN

Step2.2.1W′=任務(wù)ti偏好序列中前ci個滿足條件的工人集合;/*若出現(xiàn)tie則選取CN值較小的工人*/

Step2.2.2FOReach workerw′∈W′do

Step2.2.2.1MaxSat=MaxSat+sat(ti→w′);

Step2.2.2.2TW←(ti,w′);

Step2.2.3ENDFOR

Step2.3ELSETHEN

Step2.3.1CONTINUE

Step2.4ENDIF

Step3ENDFOR

Step4RETURNTWANDMaxSat。

貪心算法首先遍歷眾包任務(wù)，根據(jù)眾包任務(wù)個數(shù)會執(zhí)行m次。然后，根據(jù)約束條件篩選工人數(shù)量的時間復雜度為O(mn2)，采用堆選擇工人的時間復雜度為O(nlogn)。綜上所述，本文貪心算法總的時間復雜度為O((mn)2)，能夠在多項式時間內(nèi)計算出穩(wěn)定條件下滿意度最大化的分配方案。

5 實驗與結(jié)果分析

為了驗證基于偏好匹配的眾包任務(wù)分配方法的有效性和相應(yīng)算法的性能，本文設(shè)計實現(xiàn)了相關(guān)實驗并對實驗結(jié)果進行分析。實驗環(huán)境為Intel Core i7 3.6 GHz CPU，8 GB RAM，64 位Windows 10專業(yè)版操作系統(tǒng)的PC，開發(fā)平臺為PyCharm Community Edition 2019.3.1，開發(fā)語言為Python 3.6，編譯器為Anaconda 3。

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

由于在眾包環(huán)境中，工人不可能申請所有任務(wù)，任務(wù)屬性也不可能適合所有工人，故偏好可能為不完全偏好。因此，本文通過隨機截取分配主體的完全偏好序列來獲取不完全偏好，對數(shù)據(jù)集進行預處理，刪除任務(wù)偏好序列中對該任務(wù)無偏好的工人，以及工人偏好序列中對該工人無偏好的任務(wù)，在非完整偏好情況下縮短偏好序列長度，并隨機生成協(xié)作型眾包任務(wù)所需工人數(shù)量，模擬真實眾包任務(wù)分配環(huán)境。

5.2 有效性驗證

實驗的目的是對本文方法進行有效性驗證，分配方法的評價標準是分配結(jié)果的準確性和穩(wěn)定性。任務(wù)分配準確性是指當前任務(wù)分配的工人符合任務(wù)需求的程度。由于模型目標值為當前分配任務(wù)的滿意度總和，為了體現(xiàn)已分配任務(wù)準確度，實驗使用滿意度總和與當前已分配任務(wù)數(shù)量的比值作為分配準確度值。分配準確度SQ的計算公式如式(15)所示：

(15)

其中,S表示當前分配方案滿意度總和，AT表示當前已分配工人的數(shù)量。

為了驗證方法合理性及有效性，實驗將本文模型使用的穩(wěn)定匹配規(guī)則下滿意度最大化策略(簡稱MA)與滿意度最大化策略(簡稱SA)、任務(wù)數(shù)量最大化策略(簡稱TA)[17]的分配結(jié)果進行對比。其中，MA策略不僅考慮任務(wù)及工人的偏好，而且還保證了分配結(jié)果的穩(wěn)定性。SA策略考慮任務(wù)單方偏好，在未引入穩(wěn)定匹配思想的情況下以任務(wù)滿意度最大化為目標進行分配。TA策略[17]是眾包分配中較為常用的分配策略，在不考慮任務(wù)與工人的雙邊偏好情況下，追求任務(wù)數(shù)量的最大化目標。

5.2.1 穩(wěn)定性驗證

首先，實驗使用Mallows模型生成眾包任務(wù)及工人的完全偏好，對偏好集進行預處理并隨機選取10～100個任務(wù)(對應(yīng)20～200個工人)，在保證任務(wù)與工人的比例值不變的情況下，采用貪心算法進行30次實驗并取平均值。使用反饋算法對分配結(jié)果進行處理，記錄實驗結(jié)果的不穩(wěn)定分配數(shù)量，3種分配策略的實驗結(jié)果如圖1所示。

Figure 1 Results comparison of three strategies圖1 3種策略實驗結(jié)果對比

由于數(shù)據(jù)模擬真實眾包環(huán)境，數(shù)據(jù)集具有一定的隨機性。實驗結(jié)果顯示，隨著任務(wù)與工人數(shù)量的增多，分配的準確度SQ值逐漸減小，不穩(wěn)定分配對的數(shù)量逐漸增多。在圖1a中MA策略和SA策略均使用偏好，2種分配策略的SQ值均優(yōu)于TA策略的，實驗表明眾包任務(wù)分配引入偏好匹配有利于提高分配方案的滿意度和準確性。由圖1b可知，MA策略的不穩(wěn)定分配對數(shù)量最少，MA策略使用穩(wěn)定規(guī)則有效減少了不穩(wěn)定分配的數(shù)量。綜合來看，相較其他2種分配策略，MA策略的分配準確性和穩(wěn)定性較高。因此，分配過程中使用偏好和穩(wěn)定性規(guī)則可以提高分配方案準確度，減少不穩(wěn)定分配數(shù)量，在任務(wù)與工人達到滿意的狀態(tài)下提高任務(wù)完成質(zhì)量。

5.2.2 準確性分析

在眾包環(huán)境中，隨著眾包用戶的增多，存在較多工人申請同一個任務(wù)的情況。為了驗證本文模型分配結(jié)果準確度與用戶比例之間的關(guān)系，實驗使用Mallows模型分別生成20個任務(wù)與20～100個工人的雙邊完全偏好，采用貪心算法進行30次實驗并取平均值。記錄相關(guān)實驗得SQ值如圖2所示。

Figure 2 SQ values of MA strategyunder different number of workers圖2 不同工人數(shù)量下MA策略的SQ值

實驗結(jié)果顯示，隨著工人數(shù)量的增加，任務(wù)可選擇的工人數(shù)量增多，分配方案的SQ值越高，即分配結(jié)果的準確度越高，并逐漸趨向于1。由此可見，本文模型在任務(wù)與工人比例差值較大時仍可保證分配結(jié)果的準確性。

在眾包環(huán)境中，任務(wù)的偏好長度對分配結(jié)果的滿意度及準確度有影響。為了驗證本文方法分配結(jié)果的準確度與任務(wù)偏好序列長度的關(guān)系，實驗使用Mallows模型生成10個任務(wù)和10個工人的雙邊完全偏好，對任務(wù)偏好序列進行截取，截取長度分別為1，2，3，4，5，6，7，8，9，10。使用貪心算法分別進行30次實驗并記錄分配結(jié)果的任務(wù)滿意度S與分配準確度SQ值，實驗結(jié)果如圖3所示。

Figure 3 Satisfaction values and SQ values of MA strategyunder different tasks preference lengths圖3 不同任務(wù)偏好長度下MA策略的滿意度值與SQ值

實驗結(jié)果顯示，在任務(wù)偏好長度為1時，任務(wù)和工人的可供分配對象較少，只能對工人所需數(shù)為1的任務(wù)進行分配。任務(wù)分配到的工人在當前情況下最符合其需求。隨著任務(wù)給予偏好數(shù)量的增多，任務(wù)和工人互相選擇的意愿增多，任務(wù)的總體滿意度會隨著任務(wù)偏好長度的增大而增加。分配方案的準確度隨著任務(wù)偏好長度的增大在小幅度降低后有所上升，并達到平穩(wěn)狀態(tài)。實驗結(jié)果表明，即使任務(wù)和工人為了自身利益申請多個分配對象，本文方法也能保證任務(wù)分配的準確度，從而保障眾包任務(wù)完成質(zhì)量。

5.2.3 關(guān)聯(lián)度分析

為了驗證關(guān)聯(lián)度特性，實驗使用Mallows模型生成10個任務(wù)與10個工人的雙邊完全偏好序列。分別選取一個任務(wù)和工人，對選取任務(wù)與工人的偏好序列進行截取，截取長度分別為1，2，3，4，5，6，7，8，9，10。根據(jù)文獻[25]相關(guān)研究，設(shè)置計算CN的最大迭代次數(shù)為100，阻尼系數(shù)θ取0.85，收斂閾值ε為0.000 01。實驗記錄選取任務(wù)(工人)的CN值，實驗結(jié)果如圖4所示。

Figure 4 CN values under different preference lengths圖4 不同偏好長度下的CN值

實驗結(jié)果顯示，隨著選取任務(wù)的偏好長度增大，任務(wù)CN值不斷增長。在眾包環(huán)境中，眾包任務(wù)偏好序列越長，代表著可分配工人越多，與偏好序列長度較短的任務(wù)相比，該任務(wù)的分配結(jié)果影響的工人數(shù)目更多。與此同時，在其他條件不變的情況下，隨著選取工人的偏好長度增大，工人的CN值不斷增長。因此，當偏好序列中出現(xiàn)差別偏好時，選取CN值較低的分配主體可以減少對其他分配對象的影響程度。此外，當工人為了自身利益同時申請較多任務(wù)時，從tie中選用CN值較低的工人，在一定程度上保證了偏好的真實性。

5.3 性能測試

窮舉法在小規(guī)模數(shù)據(jù)集上可求解模型的精確解，針對大規(guī)模問題其局限性較為明顯。遺傳算法[26]在穩(wěn)定匹配決策方面存在應(yīng)用研究，其優(yōu)點在于具有良好的全局搜索能力，并且利用其內(nèi)在并行性可以方便地進行分布式計算，加快求解速度。因此，為了測試本文貪心算法的求解精度和效率，在小規(guī)模數(shù)據(jù)集上對比窮舉法、貪心算法和遺傳算法[26]求解結(jié)果的滿意度值與運行時間。實驗使用Mallows模型，生成5～25個任務(wù)與10～50個工人的雙邊完全偏好，對數(shù)據(jù)集進行相應(yīng)處理，分別使用窮舉法、貪心算法和遺傳算法在小規(guī)模數(shù)據(jù)集上對模型求解，實驗結(jié)果對比如圖5、表1和表2所示。

Figure 5 Results comparison of different algorithms圖5 不同算法的結(jié)果對比

Table 1 Ratio of satisfactions between greedy algorithm and exhaustive algorithm

Table 2 Ratio of satisfactions between greedy algorithm and genetic algorithm

圖5a實驗結(jié)果顯示，當分配主體(包含任務(wù)與工人)數(shù)量超過60時，窮舉法的運行時間顯著增長，由于窮舉法的運行時間是指數(shù)級增加，因此窮舉法并不適合在大規(guī)模數(shù)據(jù)集上求解模型。從表1中可看出，本文貪心算法求解的滿意度與窮舉法求解的滿意度比值在0.863～1.000，說明本文算法在數(shù)據(jù)量較小的情況下能獲得相對最優(yōu)解。從表2中可看出,使用本文貪心算法求解的滿意度與遺傳算法求解結(jié)果的比值在0.919～1.000，因此在較大數(shù)據(jù)集上，本文使用遺傳算法求解結(jié)果作為對比。此外，實驗表明，遺傳算法雖然在小規(guī)模數(shù)據(jù)集上有較好的收斂性，但貪心算法在效率上表現(xiàn)更好，更適用于眾包任務(wù)分配場景。

為了測試本文算法處理較大規(guī)模數(shù)據(jù)集的性能，實驗使用Mallows模型生成眾包任務(wù)及工人的完全偏好，對偏好集進行預處理并計算滿意度矩陣。隨機選取50～250個任務(wù)(對應(yīng)100～500個工人)，在保證任務(wù)與工人的比例值不變的情況下求解本文模型，采用貪心算法與遺傳算法進行30次實驗并取平均值，實驗結(jié)果如圖6和表3所示。

Figure 6 Results comparison between genetic algorithm and greedy algorithm圖6 遺傳算法與貪心算法的求解結(jié)果對比

Table 3 Ratio of satisfactions between genetic algorithm and greedy algorithm

如圖6a實驗結(jié)果顯示，隨著分配主體(包含任務(wù)與工人)數(shù)量的增加，貪心算法和遺傳算法的求解時間不斷增長。當分配主體數(shù)量超過300時，遺傳算法運行時間大幅度增加，貪心算法的運行時間緩慢增加。貪心算法和遺傳算法求解任務(wù)滿意度比值非常接近，在0.927～0.946。在較大規(guī)模數(shù)據(jù)集上，相比于遺傳算法，貪心算法可快速求解模型且求解時間差距較大，貪心算法的效率更高。此外，如圖6b所示，隨著眾包分配主體的增加，不穩(wěn)定分配數(shù)量逐漸增多，貪心算法所得分配方案相比遺傳算法的分配方案，不穩(wěn)定匹配數(shù)量更少。實驗表明，本文貪心算法在任務(wù)與工人數(shù)量較多時仍然適用，較遺傳算法效率更高且不穩(wěn)定分配數(shù)量更少，因此更適用于眾包任務(wù)分配場景。

6 結(jié)束語

在眾包任務(wù)分配場景中，分配結(jié)果的準確性與穩(wěn)定性對于提升眾包完成質(zhì)量非常重要。然而，目前相關(guān)研究并未綜合考慮眾包分配主體的偏好與分配方案的穩(wěn)定性。為此，本文討論了基于偏好匹配的眾包任務(wù)分配方法，該方法將分配主體的偏好序轉(zhuǎn)換為滿意度，然后借鑒穩(wěn)定匹配思想將眾包任務(wù)分配問題建模為在穩(wěn)定匹配規(guī)則下求解滿意度最大化分配方案的最優(yōu)化問題。本文使用貪心算法對該問題進行求解，得到眾包任務(wù)分配方案，并通過實驗驗證了該方法的有效性。本文方法在分配過程中使用了偏好序，但未能全面考慮影響偏好真實性的因素，下一步工作將結(jié)合眾包場景對該問題進行探討。