陳寶童，王麗清，蔣曉敏，姚寒冰

1.云南大學(xué) 信息學(xué)院，昆明 650091

2.云南廣播電視臺，昆明 650500

群智協(xié)同計算[1]旨在充分挖掘網(wǎng)絡(luò)群智資源，實現(xiàn)群體智能[2]的最大化利用來解決計算機(jī)單獨難以完成的復(fù)雜任務(wù)[3]。任務(wù)分配作為群智協(xié)同計算的核心環(huán)節(jié)之一，不僅直接關(guān)系著群智任務(wù)的結(jié)果質(zhì)量、完成效率，而且影響著協(xié)同工作者的參與體驗。

由于群智任務(wù)與網(wǎng)絡(luò)協(xié)同工作者的復(fù)雜性與不確定性，任務(wù)分配機(jī)制大多存在適用范圍窄、匹配準(zhǔn)確度不高、分配效率低等問題。究其原因，主要有三類：

第一，不同的任務(wù)因其屬性與約束不同，故對工作者與任務(wù)分配算法的要求也有差異，這使得特定的任務(wù)分配機(jī)制往往只能適用于特定的一類或幾類相似的任務(wù)。

第二，不同的網(wǎng)絡(luò)協(xié)同工作者，其工作能力、專業(yè)領(lǐng)域、性格等屬性特征各不相同，且隨著時間和經(jīng)驗的變化帶來特征的動態(tài)變化，而任務(wù)分配要實現(xiàn)最佳匹配，不僅需要考慮最初的“冷啟動”問題，還需要對工作者屬性特征變化完成動態(tài)感知。

第三，大數(shù)據(jù)背景下，群智任務(wù)與協(xié)同工作者的數(shù)量急劇上升，群智協(xié)同任務(wù)分配機(jī)制的效率與準(zhǔn)確性也將受到更大的挑戰(zhàn)。

因此，設(shè)計一個合理、高效的群智協(xié)同任務(wù)分配機(jī)制，不僅能夠保證任務(wù)與工作者之間的精準(zhǔn)匹配，保證任務(wù)分配成功率，而且能夠在給定約束下提高任務(wù)的結(jié)果質(zhì)量和完成效率。

為了解和掌握目前群智協(xié)同任務(wù)分配研究領(lǐng)域的進(jìn)展，本文基于任務(wù)分配的通用框架，分別從工作者模型、任務(wù)模型，任務(wù)和工作者匹配算法三個方面，對群智協(xié)同任務(wù)分配的國內(nèi)外研究進(jìn)展進(jìn)行了研究和分析，總結(jié)了研究現(xiàn)存的主要問題，提出了未來可能的研究趨勢和研究熱點，為該領(lǐng)域的相關(guān)研究提供參考。

1 任務(wù)分配方式及其通用框架

1.1 任務(wù)分配方式

目前，主流群智協(xié)同任務(wù)分配機(jī)制可分為“推”和“拉”兩種方式：前者由于工作者體驗差、任務(wù)分配不均勻等缺點已很少被研究，本文主要研究“推”式分配，主要根據(jù)工作者和任務(wù)的不同需求，實現(xiàn)雙方的個性化篩選，進(jìn)而完成二者的合理匹配，其優(yōu)點總結(jié)如下：

第一，降低了工作者選擇任務(wù)的難度[4]。雖然任務(wù)搜索功能可提供多種過濾條件的組合，但隨著任務(wù)數(shù)量的增長，工作者在搜索上消耗的時間增多，甚至與在完成任務(wù)上花費(fèi)的時間幾乎相當(dāng)[5]。而“推”式分配可以更快、更準(zhǔn)確地讓工作者找到適合的任務(wù)，降低了時間成本。

第二，能夠提高任務(wù)分配的準(zhǔn)確性與任務(wù)結(jié)果質(zhì)量。根據(jù)工作者的特征屬性完成工作者的篩選，使不同需求的任務(wù)，可以盡可能匹配到最符合其要求的工作者，同時也間接保證了任務(wù)的順利完成，并得到更高質(zhì)量的結(jié)果。

但“推”式分配也存在算法構(gòu)建復(fù)雜等需要投入更多研究和技術(shù)的問題。表1給出了兩種方式的對比情況。

表1 兩種任務(wù)分配方式對比Table 1 Comparison of two types of task allocation methods

1.2 任務(wù)分配通用研究框架

根據(jù)任務(wù)分配的總體流程，總結(jié)提出一個任務(wù)分配通用框架，如圖1所示。該框架主要包含3個部分：任務(wù)模型、工作者模型、分配算法。首先對任務(wù)的內(nèi)容和描述信息進(jìn)行分析，從中抽取出重要的任務(wù)約束和屬性，建立任務(wù)模型；然后根據(jù)任務(wù)對工作者屬性的具體要求，完成工作者屬性的精確感知，并建立工作者模型；最后，基于特定場景，設(shè)計分配算法完成工作者與任務(wù)間的合理匹配，進(jìn)而實現(xiàn)任務(wù)的準(zhǔn)確分配。以下分別從任務(wù)模型、工作者模型和分配算法三方面分析和總結(jié)國內(nèi)外相關(guān)研究進(jìn)展。

圖1 任務(wù)分配框架Fig.1 Framework of task allocaton

2 群智協(xié)同任務(wù)分配國內(nèi)外研究現(xiàn)狀

2.1 任務(wù)模型

2.1.1 任務(wù)屬性

（1）任務(wù)類別

不同類別的任務(wù)對工作者專業(yè)能力的要求不同。例如，翻譯類任務(wù)往往要求工作者具有較高的語言能力水平，而開發(fā)類任務(wù)則更關(guān)注工作者的開發(fā)能力。因此，正確描述任務(wù)類別對工作者屬性的篩選具有指導(dǎo)作用。

（2）任務(wù)粒度

按照任務(wù)粒度的大小可將群智任務(wù)分為宏觀任務(wù)（macro-task）與微觀任務(wù)（micro-task）[6]。微觀任務(wù)是一些計算機(jī)難以完成而人類能夠輕易解決的簡單任務(wù)，這類任務(wù)不需要工作者具有較強(qiáng)能力，往往幾秒就能得到結(jié)果。與此相反，宏觀任務(wù)指的是一些較為復(fù)雜或?qū)I(yè)性較強(qiáng)的任務(wù)，需要工作者具有一定的專業(yè)知識和能力水平，并且需要一定的時間才能得到結(jié)果。

（3）任務(wù)領(lǐng)域

與前兩種屬性不同，任務(wù)的領(lǐng)域?qū)傩允菑娜蝿?wù)的具體內(nèi)容中抽取出來的特性，能夠反映出任務(wù)的主題信息。根據(jù)任務(wù)所屬領(lǐng)域來篩選工作者，能夠提高任務(wù)分配的針對性，從而提升任務(wù)完成的效率和質(zhì)量。例如，對于根據(jù)影視片段識別出電影名的群智任務(wù)，將這類主題為“影視”的任務(wù)分配給興趣愛好為看電影或者所學(xué)專業(yè)為影視編輯的工作者，能夠更快地得到更為準(zhǔn)確的結(jié)果。

2.1.2 任務(wù)約束

（1）成本

大部分群智任務(wù)在提交給可靠的工作者完成任務(wù)后，需要支付一定報酬。此外，欺詐性工作者或者信譽(yù)較低的工作者所提交的虛假或低質(zhì)量結(jié)果，在一定程度上也影響了任務(wù)的成本。如何在給定任務(wù)成本的約束下，得到較好的結(jié)果質(zhì)量，是任務(wù)模型構(gòu)建中的關(guān)鍵環(huán)節(jié)。

（2）工期

任務(wù)工期即整個任務(wù)完成的時間。不同的任務(wù)按照其工期的長短可歸為不同的緊急程度。對于工期較長的任務(wù)，對工人活躍程度的要求不高，而對于工期較短的任務(wù)，需要優(yōu)先將其分配給活躍度高、能力強(qiáng)、負(fù)載量低的工作者，以保證任務(wù)能夠按時完成。

（3）質(zhì)量

任務(wù)完成的結(jié)果質(zhì)量是任務(wù)最基本的要求。任務(wù)分配的關(guān)鍵環(huán)節(jié)都將最終影響結(jié)果的質(zhì)量，包括任務(wù)模型、工作者模型定義的準(zhǔn)確性和任務(wù)分配的機(jī)制。

2.2 工作者模型

工作者建模的工作主要包括：第一，如何根據(jù)任務(wù)需求完成對工作者屬性的選擇與定義；第二，如何正確地感知工作者的屬性。

2.2.1 工作者的主要屬性

（1）能力水平

工人的能力水平是任務(wù)分配中要考慮的關(guān)鍵因素之一[7]，尤其是對于一些難度較大或技能性較高的任務(wù)。文獻(xiàn)[8]針對泰語眾包翻譯任務(wù)，利用工作者的語言證書等級、歷史翻譯結(jié)果質(zhì)量等信息對其專業(yè)語言能力進(jìn)行評價，按照專業(yè)語言能力篩選出符合要求的工作者，不但保證了任務(wù)的順利完成還得到了高質(zhì)量的翻譯結(jié)果。但是僅僅針對某一特定類型的任務(wù)來確定工作者的能力評價方案，往往也只能適用于這一類任務(wù)。當(dāng)面臨新型任務(wù)時，該方法就無法使用。如何設(shè)計一個廣泛適用的工作者能力評價模型仍是一個研究難點。

此外，如何準(zhǔn)確定義工作者的能力也是一個值得研究的工作。在文獻(xiàn)[9]中，作者將工作者的能力表現(xiàn)為他的專業(yè)水平，并結(jié)合黃金標(biāo)準(zhǔn)數(shù)據(jù)法[10]和期望最大化評估算法（Expectation Maximization algorithm，EM）[11]將其應(yīng)用到了眾包任務(wù)質(zhì)量評價研究中。文獻(xiàn)[12]在此基礎(chǔ)上加入了性格能力的概念，希望從工作者的性格特征中提取出有價值的信息對其能力進(jìn)行多角度補(bǔ)充，但對于獲取工作者的準(zhǔn)確性格特征，在實現(xiàn)上較為困難。文獻(xiàn)[13-14]基于“具有高認(rèn)知能力的工作者可以帶來更好的工作績效”[15]的理念，將工作者的認(rèn)知能力也定義為工作者能力的一部分。目前較為理想的研究來自文獻(xiàn)[16]，其首次將工作者的能力水平與勝任力理論[17]聯(lián)系起來，提出了一個融合工作者知識（Knowledge）、技能（Skill）、能力（Ability）和其他特征（Others）的勝任力KSAO模型，較為全面地定義了工作者的能力水平。

（2）信譽(yù)值

由于工作者存在最大化個人利益的自私性[18]，因此，準(zhǔn)確評估工作者的信譽(yù)值極為必要，同時也是一個極具挑戰(zhàn)性的問題。信譽(yù)的準(zhǔn)確評估，直接影響著群智任務(wù)的完成質(zhì)量和任務(wù)發(fā)布者的切身利益。因此，如何設(shè)計一個工作者信譽(yù)評估機(jī)制以篩選出惡意工作者具有重要意義。

最簡單的方式是對完成的任務(wù)情況進(jìn)行工作者互評分，評分過低的即判定為信譽(yù)缺失工作者[19]。但工作者的表現(xiàn)受多種因素影響，并非一定是信譽(yù)問題，而且利用其他工作者進(jìn)行評分在帶來多余開銷的同時，也容易對評估對象造成誤判。平均信譽(yù)模型，針對工作者提交的每一個結(jié)果，分別計算它與平均值的差距，按照差距值的大小來評估工作者的信譽(yù)[20]，但某些時候正確結(jié)果有可能是少部分工作者提交的。在移動眾包感知中[21-22]，Huang等人利用Gompertz函數(shù)[23]計算工作者每一段時間內(nèi)向服務(wù)器發(fā)送的數(shù)據(jù)質(zhì)量，利用數(shù)據(jù)質(zhì)量的評分來評估工作者的信譽(yù)度[24]，提升了評估效果。

（3）興趣愛好

興趣愛好一直是推薦系統(tǒng)中廣泛考慮的用戶屬性之一[25-27]。為了將任務(wù)分配給對其感興趣的工作者，Ambati等人專門構(gòu)建了工作者的興趣偏好模型[28-29]。但興趣愛好只是工作者屬性中的一個因素，工作者的能力、可靠性等屬性對任務(wù)分配的影響也不能忽視。與此相比，文獻(xiàn)[30-31]采取的方式在興趣因素之外，結(jié)合了其他屬性共同完成對工作者的建模與篩選。

針對工作者不同屬性之間的聯(lián)系和相互影響，文獻(xiàn)[32]首次提出了工作者的興趣能夠正面或負(fù)面地影響工作者任務(wù)完成態(tài)度的問題，如圖2所展示的一種情景：對于一個令工作者A和B感興趣的任務(wù)，盡管B的能力不是很強(qiáng)，但是仍然能夠較為準(zhǔn)確地完成該任務(wù)；而對于工作者C，雖然能夠勝任這一項任務(wù)，但是由于他并不喜歡這個任務(wù)，那么他完成的結(jié)果質(zhì)量可能比不擅長此任務(wù)的B還差。為此，文獻(xiàn)[33-34]提出了主題興趣度的概念，將工作者的興趣度按照任務(wù)主題的不同而分開描述，這樣既能精細(xì)地描述工作者的興趣，又很好地解決了上述問題。

圖2 興趣有時會對工作者能力造成負(fù)面影響Fig.2 Inter ests sometimes negatively affect the ability of workers

在任務(wù)分配中考慮工作者的興趣愛好，一方面能夠提升工作者的積極性和工作體驗，另一方面也有助于提高群智任務(wù)的結(jié)果質(zhì)量。

（4）其他屬性

工作者的其他屬性主要包括活躍度、負(fù)載量、所在位置等。

工作者的活躍度反映了參與任務(wù)活動的頻次，是工作者積極性的體現(xiàn)。文獻(xiàn)[35]通過歸一化正切函數(shù)從工作者近30天內(nèi)參與眾包活動的天數(shù)計算出該工作者的活躍因子，綜合其信譽(yù)值來對工作者進(jìn)行綜合評價。為了保證軟件眾包任務(wù)的開發(fā)質(zhì)量，文獻(xiàn)[36]按照工作者的活躍時間對其進(jìn)行分組，然后按照小組分配軟件開發(fā)任務(wù)，保證了工作者能夠在完成任務(wù)的過程中相互交流。文獻(xiàn)[37]通過對任務(wù)的緊急程度按照等級進(jìn)行劃分，并根據(jù)工作者某一時間段內(nèi)完成任務(wù)的數(shù)量來表示其活躍度，優(yōu)先將等級高的任務(wù)分配給比較活躍的工作者。

與文獻(xiàn)[37]不同的是，文獻(xiàn)[38]從另一個角度考慮了緊急任務(wù)的分配問題，它認(rèn)為如果工作者當(dāng)前已經(jīng)接受但尚未完成的任務(wù)數(shù)量過多，則難以保證新任務(wù)的完成。因此，將工作者當(dāng)前剩余未完成的任務(wù)數(shù)量和完成這類任務(wù)需要的時間進(jìn)行運(yùn)算，得到工作者當(dāng)前的負(fù)載量屬性，若該工作者負(fù)載量較大，則不考慮將緊急任務(wù)分配給他。

除此之外，在涉及到空間的任務(wù)時，工作者的位置屬性也非常重要，文獻(xiàn)[39]通過工作者當(dāng)前的位置與空間任務(wù)的具體位置計算得到工作者的距離，將任務(wù)優(yōu)先分配給距離其位置最近的工作者，從而減小了任務(wù)完成的時間消耗。為了在完成移動群智感知[40]任務(wù)的同時盡可能地減少工作者的數(shù)量，文獻(xiàn)[41-42]通過建立工作者的移動模型來預(yù)測工作者的位置信息，然后通過預(yù)測的結(jié)果選取較少的工作者來完成任務(wù)，從而節(jié)約了成本。

2.2.2 工作者屬性的感知策略

工作者的異質(zhì)性與不確定性使得對工作者屬性的精確感知成為困難。通過對當(dāng)前相關(guān)研究進(jìn)展的分析，感知主要可分為隱式感知與顯式感知兩類。

（1）顯式感知

顯式感知主要是從工作者的注冊信息、簡介（如擅長領(lǐng)域、專業(yè)技能、興趣愛好）、問卷反饋等顯式信息中獲取屬性信息。這種方式簡單，但也存在著不可避免的缺點。一方面，出于隱私保護(hù)等原因，工作者可能并不愿意提供相關(guān)信息或者給出虛假的信息，導(dǎo)致感知結(jié)果不夠準(zhǔn)確。另一方面，由于工作者的屬性會隨著時間、環(huán)境的變化而改變，顯式信息感知難以獲取因此帶來的動態(tài)變化。

（2）隱式感知

隱式感知通過工作者的隱含交互信息來推測其屬性特征，一定程度彌補(bǔ)了顯式感知的不足。

文獻(xiàn)[43-44]將工作者完成的歷史任務(wù)按照不同類別進(jìn)行結(jié)果評價，從而推測出工作者能力與興趣。文獻(xiàn)[45]提出一個平均信譽(yù)模型，通過對工作者歷史完成任務(wù)的結(jié)果質(zhì)量取平均值作為信譽(yù)度，并按照閾值完成了高信譽(yù)工作者的篩選。文獻(xiàn)[46]認(rèn)為僅僅依靠工作者的歷史任務(wù)信息來推測其屬性并不全面，在此基礎(chǔ)上提出了結(jié)合工作者歷史搜索記錄的隱式感知方法。但對于一些尚未完成過任務(wù)的工作者來說，該方法就不再適用。對此，文獻(xiàn)[47-48]基于工作者社交網(wǎng)絡(luò)的屬性感知方法，從工作者的社交平臺或社交信息中挖掘有價值的屬性特征，為工作者“冷啟動”提供了一個解決思路，但存在牽涉到工作者隱私和數(shù)據(jù)獲取的實現(xiàn)問題。文獻(xiàn)[17，49]通過將一些帶有標(biāo)準(zhǔn)答案的任務(wù)隨機(jī)分配給工作者，根據(jù)完成的情況來測驗其能力、興趣等屬性，也可以一定程度上解決這類問題。

值得注意的是，工作者的屬性特征并不是固定不變的。例如，對于不同領(lǐng)域的群智任務(wù)，工作者興趣也會不同；隨著年齡、工作經(jīng)驗、工作時長的增加，其能力水平、興趣愛好、工作狀態(tài)也會隨之變化。因此，感知的動態(tài)性是研究中的一個關(guān)鍵因素。文獻(xiàn)[50-51]采用迭代感知的思想動態(tài)感知工作者的屬性特征。在初始時，對工作者建立初始模型，每當(dāng)工作者承擔(dān)并完成任務(wù)之后，就主動分析工作者的特征，并按照當(dāng)前特征屬性為其分配任務(wù)，隨著工作者完成任務(wù)數(shù)量的增加，對工作者屬性的感知也越準(zhǔn)確。

2.2.3 工作者模型總結(jié)

在建立工作者的特征模型時，工作者的能力水平、信譽(yù)值、興趣愛好是工作者篩選的主要元素。對于時空任務(wù)，需要增加位置信息的考慮。

為方便在工作者屬性建模中的屬性選取和研究，本文從適用任務(wù)、約束、出現(xiàn)頻率和感知難度方面對工作者的常用屬性做了對比（表2）。任務(wù)的復(fù)雜程度越高，任務(wù)約束也越多，所以工作者的篩選往往不依賴于單一工作者屬性，而更多的是采用多個屬性的結(jié)合來完成對工作者更完整、更準(zhǔn)確的描述。

表2 工作者常見屬性Table 2 Common attributes of workers

3 任務(wù)分配算法

任務(wù)分配即完成工作者與任務(wù)的最佳匹配。主要包括以下幾種方式。

3.1 基于推薦算法的分配

為了實現(xiàn)個性化的任務(wù)分配，研究者將傳統(tǒng)推薦算法引入群智協(xié)同任務(wù)分配中，提出推薦式任務(wù)分配。

仲秋雁等人[16]基于協(xié)同過濾的推薦思想，通過TFIDF主題模型和勝任力理論構(gòu)建了融合工人興趣偏好和勝任能力的工作者模型，利用相似性公式來計算工作者的綜合相似度以選取近鄰集來生成推薦結(jié)果，取得了較好的效果。Mao等人[52]在基于內(nèi)容的推薦算法上做了嘗試，首先通過任務(wù)的自身屬性對任務(wù)進(jìn)行建模，并計算任務(wù)之間的相似度，然后根據(jù)工作者的歷史任務(wù)記錄，將與其完成的歷史任務(wù)相似度高的新任務(wù)推薦給他。為了提高任務(wù)推薦算法的通用性和自適應(yīng)性，Shao等人[53]在此基礎(chǔ)上引入了神經(jīng)網(wǎng)絡(luò)的機(jī)制，自適應(yīng)地調(diào)整模型參數(shù)以達(dá)到更好的推薦結(jié)果。

上述兩種推薦方式都需要大量工作者的歷史任務(wù)數(shù)據(jù)來感知工作者的特征，因此只對擁有較多交互信息的工作者有較好的推薦效果，但平臺上新加入或缺少交互信息的工作者不在少數(shù)。為解決這類問題，部分研究提出基于社交網(wǎng)絡(luò)的任務(wù)推薦方法：文獻(xiàn)[46-48]針對新加入或缺少交互信息的工作者，通過挖掘他們社交平臺上的交互信息來為其推薦合適的任務(wù)。文獻(xiàn)[54]認(rèn)為關(guān)系較為親密的工作者更有可能對同一類任務(wù)感興趣，因此提出在挖掘工作者社交活動的同時也考慮不同工作者之間的互動程度。為了找到更適合完成任務(wù)的工作者，文獻(xiàn)[55]根據(jù)任務(wù)發(fā)布方和工作者之間的社交關(guān)系提出了一個基于社交關(guān)系認(rèn)知的任務(wù)推薦模型TDSRC，實驗表明該模型能夠有效解決工作者的欺騙行為。

基于傳統(tǒng)推薦算法的任務(wù)分配方式引入了工作者或任務(wù)的相似度概念，結(jié)合工作者與任務(wù)的自身信息和歷史交互信息來完成任務(wù)與工作者之間的匹配，提高了任務(wù)分配的準(zhǔn)確性。但無論是基于內(nèi)容的推薦還是基于協(xié)同過濾的推薦，都需要從歷史信息中分析出工作者屬性特征，雖然通過社會推薦的方式能夠從不同途徑獲取工作者屬性，但由于隱私保護(hù)等問題這種方式并不容易實現(xiàn)。因此，對于工作者冷啟動問題需要引入其他解決方案。另外，前兩種推薦方式都需要通過構(gòu)建工作者-任務(wù)矩陣，當(dāng)系統(tǒng)中工作者和任務(wù)數(shù)量急劇增多時，數(shù)據(jù)稀疏性問題也是一個必須解決的問題。

3.2 基于矩陣分解的分配

基于概率矩陣分解的任務(wù)分配方法能夠有效地解決任務(wù)推薦中的數(shù)據(jù)稀疏性問題。其核心思想是通過概率矩陣分解的方法將高維的工作者-任務(wù)矩陣A分解成一個低維的工作者潛在特征矩陣W和任務(wù)潛在特征矩陣T，使得A≈WT。而矩陣W和矩陣T的乘積則為工作者和任務(wù)的匹配預(yù)測矩陣。例如，對于WT=A1，若A1的第一行第一列值為10，則表示將1號任務(wù)分配給1號工人的可信度為10。通過這種方式能夠預(yù)測工作者-任務(wù)矩陣中的缺失值，不僅解決了數(shù)據(jù)稀疏的問題，也完成了任務(wù)的分配。

文獻(xiàn)[51]根據(jù)工作者的歷史表現(xiàn)信息和任務(wù)搜索信息建立工作者-任務(wù)評分矩陣，然后采用概率矩陣分解的方式來預(yù)測矩陣中的缺失值，從而完成任務(wù)的分配。針對新任務(wù)與新工作者的問題，文獻(xiàn)[56]將任務(wù)分別交給較為擅長的工作者和新工作者完成，通過兩類工作者的結(jié)果反饋數(shù)據(jù)訓(xùn)練模型用來衡量新工作者的能力，以此解決新用戶的冷啟動問題。針對在矩陣分解的過程中，由于沒有考慮負(fù)值而導(dǎo)致矩陣可解釋性較差的問題，文獻(xiàn)[57]在此基礎(chǔ)上引入了非負(fù)矩陣分解的方法提高算法的可解釋性。

通過直接分解工作者-任務(wù)關(guān)系矩陣的方式能夠有效預(yù)測矩陣中的缺失值，在解決數(shù)據(jù)稀疏的同時也完成了任務(wù)的分配，但是不能很好地反映工作者對不同類任務(wù)的能力差別。因此，作者在文獻(xiàn)[51]的基礎(chǔ)上對算法作了進(jìn)一步的改進(jìn)工作[58-59]，首先對工作者在任務(wù)上的行為表現(xiàn)分為5個等級，形成工作者-任務(wù)等級矩陣，然后又構(gòu)建了任務(wù)-任務(wù)類別矩陣和工作者-任務(wù)類別矩陣，分別反應(yīng)任務(wù)的類別信息和工作者與任務(wù)類別的興趣程度，并分別分解以上三個矩陣，最后進(jìn)行整合，從而提高了任務(wù)推薦的質(zhì)量。但這種方式對工作者的屬性考慮比較單一，無法滿足多因素工作者的考慮，另外，工作者的能力和興趣隨時可能會改變，該方法也無法做出及時的調(diào)整。為了解決第一個問題，Safran等人[60]對先前的工作進(jìn)行了改進(jìn)，通過分別計算工作者在某一類任務(wù)上的能力和興趣水平，然后將二者統(tǒng)一成工作者對這一類任務(wù)的總體表現(xiàn)分?jǐn)?shù)，實現(xiàn)了工作者多特征的結(jié)合。針對第二個問題，Yuen等人[61]在其原有的工作上引入了時間衰減的概念，認(rèn)為工作者近期的表現(xiàn)比其歷史表現(xiàn)更能反映他的特征，因此通過加入時間因子的方式增強(qiáng)了工作者近期交互信息的表現(xiàn)能力。為了提高矩陣分解算法的計算效率，Yuen等人[62]又進(jìn)一步改進(jìn)了他們的工作，提出批次更新的概念，當(dāng)某一工作者完成任務(wù)時不再更新模型，而是等到一定數(shù)量的工作者全部完成任務(wù)后再對模型進(jìn)行更新，從而節(jié)省了計算時間。針對在矩陣分解算法中采用梯度下降進(jìn)行迭代容易導(dǎo)致局部最優(yōu)的問題，文獻(xiàn)[63]通過引入遺傳算法的方式在工作者-任務(wù)矩陣搜索中進(jìn)行全局迭代，較好地解決了這個問題。

3.3 基于隱私保護(hù)的分配

近年來，隨著群智協(xié)同應(yīng)用的快速發(fā)展和人們隱私意識的不斷提高，基于隱私保護(hù)的群智協(xié)同任務(wù)分配方式被國內(nèi)外學(xué)術(shù)界廣泛研究。這些方法主要可以分為三類：單邊隱私保護(hù)、雙邊隱私保護(hù)和全局隱私保護(hù)。

最初，部分研究注意到了工作者或任務(wù)的隱私安全問題，提出基于單邊隱私保護(hù)的任務(wù)分配方法[64-74]。為了保護(hù)工作者的敏感信息，部分研究將區(qū)塊鏈[64-65]、差分隱私[66-67]、k-匿名[68-69]等經(jīng)典的隱私保護(hù)方法融合到任務(wù)分配策略中，能夠在特定的場景下取得較好的效果，但不能在保護(hù)工作者屬性、身份等隱私的同時實現(xiàn)細(xì)粒度的任務(wù)分配；為此，文獻(xiàn)[70]引出基于屬性加密的方法對其進(jìn)行了優(yōu)化。對于敏感類任務(wù)的隱私保護(hù)問題，文獻(xiàn)[71-72]通過將任務(wù)按照敏感信息進(jìn)行拆解，再分別分配給不同的工作者，這種方式在一定程度上保護(hù)了任務(wù)的重要信息，但是當(dāng)多個工作者串通起來時，仍然有較大風(fēng)險?；诖?，文獻(xiàn)[73-74]提出對密謀工作者進(jìn)行檢測的方法來解決。

單邊隱私保護(hù)在一定程度上可以保護(hù)工作者或任務(wù)的隱私，但是仍然存在較大風(fēng)險。例如，第三方可以通過分析工作者的歷史任務(wù)行為來推斷出他的敏感屬性等，為此提出了雙邊隱私保護(hù)的任務(wù)分配策略。針對部分傳統(tǒng)加密機(jī)制對任務(wù)與工作者信息加密后無法檢索的問題，文獻(xiàn)[75-76]采用可搜索加密技術(shù)，結(jié)合多屬性加密方法加密任務(wù)內(nèi)容和工作者屬性，保證了基于工作者屬性和內(nèi)容的任務(wù)分配。Xu等人[77]較早將內(nèi)積加密方式應(yīng)用到群智任務(wù)分配的隱私保護(hù)之中，由于該方式能夠支持多種類型的約束表達(dá)式，所以能夠更加靈活地支持多場景下的工作者與任務(wù)的關(guān)鍵字匹配；考慮到匿名后的工作者可能多次重復(fù)提交的問題，作者又在文獻(xiàn)[77]的基礎(chǔ)上增加了知識證明（Proof of Knowledge，POK）協(xié)議，用來限制結(jié)果的多次提交[78]。為減輕由于隱私保護(hù)所帶來的巨大計算壓力，文獻(xiàn)[79]采用fog計算的方法，將部分計算任務(wù)平衡到fog節(jié)點，提高了系統(tǒng)的整體效率。

雙邊隱私保護(hù)的任務(wù)分配機(jī)制擁有同時保護(hù)工作者和任務(wù)隱私的能力，但傳統(tǒng)任務(wù)分配過程中，數(shù)據(jù)存儲在集中服務(wù)器上的方式也很容易遭到隱私威脅，為此，最新的一些研究[80-82]利用區(qū)塊鏈技術(shù)，通過構(gòu)建基于區(qū)塊鏈?zhǔn)跈?quán)的分散式框架來代替集中服務(wù)器的功能，在全局上實現(xiàn)了任務(wù)分配流程中的隱私保護(hù)。

3.4 其他分配方法

除以上主流的任務(wù)分配方法外，還有一些研究工作值得討論，歸納分析如下：

組合優(yōu)化策略：部分研究將任務(wù)分配問題形式化為帶約束的組合優(yōu)化問題，以實現(xiàn)特定利益的最大化。Gong等人[83]為了最大化工作者的收入，將任務(wù)到工作者的匹配定義為帶有一個未知參數(shù)的約束優(yōu)化問題，將工作者完成一項任務(wù)的時間消耗作為參數(shù)，通過計算工作者完成其他相似任務(wù)的時間來估計其完成本次任務(wù)的時間，并利用遺傳算法解決優(yōu)化問題從而生成對該工作者的任務(wù)推薦列表。文獻(xiàn)[84]以眾包任務(wù)完成的質(zhì)量、時間、效率最大化為目標(biāo)，針對新任務(wù)與工作者匹配準(zhǔn)確性低的問題，建立了任務(wù)推薦的多目標(biāo)優(yōu)化模型，然后通過適當(dāng)?shù)哪Ｐ妥儞Q，采用匈牙利算法對模型進(jìn)行求解，實驗證明了該方法可以提高任務(wù)推薦的準(zhǔn)確性。文獻(xiàn)[85]考慮了在線任務(wù)分配中的任務(wù)優(yōu)化選擇問題，目的是在工作者數(shù)量有限的前提下最大化潛在完成任務(wù)的數(shù)量，提出一個保證質(zhì)量的同步任務(wù)分配方法，并采用兩種貪婪算法完成問題求解。為了實現(xiàn)任務(wù)分配中的整體利益最大化，針對分配中的多維大規(guī)模復(fù)雜任務(wù)和多維特征的工作者，文獻(xiàn)[86]和[87]分別提出基于多臂賭博機(jī)和蟻群優(yōu)化算法的任務(wù)分配策略。

機(jī)器學(xué)習(xí)策略：以往的群智協(xié)同任務(wù)分配研究中，文獻(xiàn)[28，88-90]通過聚類、分類技術(shù)，利用工作者與任務(wù)的互動數(shù)據(jù)訓(xùn)練模型，以支持后續(xù)任務(wù)與工作者的匹配，這種方式準(zhǔn)確性高，但是需要大量交互數(shù)據(jù)，后續(xù)的模型維護(hù)也很繁瑣，對新任務(wù)與新工作者的支持也不夠好。近年，也有將強(qiáng)化學(xué)習(xí)應(yīng)用到任務(wù)分配中[91-94]，通過貝葉斯推理、馬爾科夫決策等方法設(shè)計出實時的任務(wù)推薦模型的方法，不僅緩解了冷啟動問題，也提高了算法的動態(tài)性與靈活性。

反向拍賣機(jī)制：部分研究者將任務(wù)分配問題建模為反向任務(wù)拍賣問題[95-96]，工作者和任務(wù)雙方分別代表叫價者和拍賣方，自身能力與發(fā)布方要求最大程度實現(xiàn)匹配的工作者贏得拍賣，獲得任務(wù)。這種方式可以滿足在線分配要求，能夠在工作者與發(fā)布方的利益之間做到較好平衡，但是只在有足夠多的參與者和任務(wù)的情況下才會有較好結(jié)果。

3.5 任務(wù)分配方法總結(jié)

本節(jié)中，對現(xiàn)有的任務(wù)分配算法按照不同類別進(jìn)行了整理與分析，并在表3中給出了上述三種分配算法的對比情況。

表3 任務(wù)分配算法對比Table 3 Comparison of task allocation methods

基于推薦算法的任務(wù)分配方式不僅能夠精確地完成任務(wù)分配，而且可以滿足工作者的個性化需求，提高工作者的積極性?；趨f(xié)同過濾的推薦方法利用工作者或任務(wù)間的相似性進(jìn)行任務(wù)推薦，可在較高的效率下提供較精確的結(jié)果，但過于依賴任務(wù)或工作者間的相似度計算；基于內(nèi)容的推薦方式多從任務(wù)自身的內(nèi)容入手，根據(jù)元數(shù)據(jù)將任務(wù)推薦給相似任務(wù)的優(yōu)質(zhì)工作者，一定程度上解決了任務(wù)冷啟動的問題，但通用性不足；社交推薦方法通過挖掘工作者社交數(shù)據(jù)的方式精確感知工作者的屬性特征和工作者間的社交關(guān)系，從而更準(zhǔn)確和高效地完成任務(wù)推薦，但該方法涉及到隱私問題，并且不是所有工作者都有豐富的社交數(shù)據(jù)。

基于推薦算法的任務(wù)分配需要構(gòu)建工作者-任務(wù)矩陣，當(dāng)工作者和任務(wù)數(shù)量急劇增多時，數(shù)據(jù)稀疏性問題凸顯?；诰仃嚪纸獾姆峙渌惴ㄍㄟ^將高維的任務(wù)-工作者矩陣分解成數(shù)個低維的特征矩陣，并通過對矩陣的整合來預(yù)測其中的缺失值，能夠在完成分配的同時解決數(shù)據(jù)稀疏性問題，但是數(shù)據(jù)量過大會嚴(yán)重影響模型計算效率，不適用于實時分配。

近年來，隱私保護(hù)問題敏感而突出，在群智協(xié)同任務(wù)分配中，同樣存在隱私安全問題。傳統(tǒng)方法中的加密、匿名等措施可一定程度完成保護(hù)，但造成任務(wù)推薦流程復(fù)雜，數(shù)據(jù)可讀性下降。

任務(wù)的實時分配在某些特定場景下至關(guān)重要，基于拍賣和組合優(yōu)化的任務(wù)分配方法有一定的實時性，比較適用于在線任務(wù)分配；但與離線任務(wù)分配方法相比，其準(zhǔn)確率和個性化效果相對較差。另外，由于機(jī)器學(xué)習(xí)在特征學(xué)習(xí)等方面的良好表現(xiàn)，基于強(qiáng)化學(xué)習(xí)的任務(wù)分配方法具有一定的主動學(xué)習(xí)特征，往往在一些復(fù)雜或自動化的群智系統(tǒng)上有較好表現(xiàn)。

4 任務(wù)分配研究的關(guān)鍵問題與研究趨勢

4.1 冷啟動問題

在群智協(xié)同推薦式任務(wù)分配中，冷啟動主要包括任務(wù)冷啟動和工作者冷啟動。一方面，活躍度低或新的協(xié)同工作者由于缺乏歷史信息，無法完成準(zhǔn)確推薦。另一方面，全新類別的任務(wù)由于尚未由工作者完成，也很難推薦。群智應(yīng)用中新工作者和任務(wù)的情況普遍存在，隨著任務(wù)的復(fù)雜性、數(shù)量和工作者規(guī)模的增加，冷啟動問題不斷加劇，是今后研究的關(guān)鍵問題之一。

目前最常用的是利用工作者注冊信息來完成任務(wù)推薦，未來可考慮采用基于先驗知識的推薦方式。例如向工作者推薦較受歡迎的任務(wù)；也可進(jìn)行多樣化推薦，將冷啟動任務(wù)交給綜合表現(xiàn)較突出的工作者完成；或者結(jié)合快速試探策略，將任務(wù)分別交給不同屬性工作者，完成質(zhì)量最好的幾類工作者就是這類新任務(wù)的合適工作者；此外，還可以通過社交關(guān)系挖掘等新興工作者屬性感知策略來解決冷啟動問題。

4.2 結(jié)合隱私保護(hù)的任務(wù)分配問題

群智協(xié)同所處的開放網(wǎng)絡(luò)環(huán)境和協(xié)同工作者的不確定性使得任務(wù)分配中的隱私安全問題一直是一個熱點話題。文獻(xiàn)[97]系統(tǒng)分析了不同類型眾包中的隱私威脅。在群智協(xié)同任務(wù)分配問題中，隱私保護(hù)至關(guān)重要，直接關(guān)系著群智協(xié)同計算的發(fā)展和實際應(yīng)用。

本文建議可考慮以下思路進(jìn)行后續(xù)研究：首先是結(jié)合傳統(tǒng)隱私保護(hù)算法和群智協(xié)同任務(wù)分配的特定場景；其次，可在全局隱私保護(hù)情況下，設(shè)計安全高效的任務(wù)分配流程；然后是群智協(xié)同任務(wù)分配算法中隱私保護(hù)機(jī)制的性能效率優(yōu)化；最后，可融合區(qū)塊鏈等新興隱私保護(hù)模型，設(shè)計覆蓋工作者、任務(wù)、平臺和全局流程的多邊隱私保護(hù)機(jī)制。

隨著人們隱私保護(hù)意識的增強(qiáng)和網(wǎng)絡(luò)信息共享程度的不斷加大，隱私保護(hù)已成為群智協(xié)同任務(wù)分配中的一個關(guān)鍵問題，也是未來研究的一個熱點。

4.3 大數(shù)據(jù)環(huán)境下的任務(wù)分配

大數(shù)據(jù)環(huán)境下的信息過載對群智協(xié)同任務(wù)分配的影響不容小覷。龐大的工作者和任務(wù)數(shù)量不僅給任務(wù)分配方法帶來數(shù)據(jù)稀疏問題，影響著任務(wù)分配的效率和質(zhì)量，而且增加了工作者和群智任務(wù)屬性提取的難度，降低了任務(wù)分配的準(zhǔn)確性。隨著工作者與任務(wù)數(shù)量的日益增多，大數(shù)據(jù)環(huán)境下的任務(wù)分配問題成為今后群智協(xié)同任務(wù)分配領(lǐng)域的一個關(guān)鍵問題和研究熱點。

針對數(shù)據(jù)稀疏性問題，建議結(jié)合分類、聚類等機(jī)器學(xué)習(xí)方法，將單個任務(wù)分配轉(zhuǎn)變?yōu)槿蝿?wù)群到工作者群的分配問題；也可通過設(shè)計適當(dāng)策略剔除平臺上的“僵尸工作者”加以解決。對于分配效率問題，可設(shè)計并行化、多批次的任務(wù)分配模型，或嘗試將主動學(xué)習(xí)、強(qiáng)化學(xué)習(xí)等方式應(yīng)用到任務(wù)分配中。

5 總結(jié)

任務(wù)分配一直是群智協(xié)同計算和眾包領(lǐng)域研究中的一個核心問題。本文從群智協(xié)同任務(wù)分配現(xiàn)存的問題出發(fā)，闡述了其研究的重要性。然后根據(jù)任務(wù)分配的流程提出了一個任務(wù)分配的通用框架，并基于該框架，詳細(xì)分析和總結(jié)了各個部分的研究進(jìn)展，概括歸納了任務(wù)模型、工作者模型中的任務(wù)屬性、任務(wù)約束和工作者屬性特征及其感知方式，對任務(wù)分配的主要算法進(jìn)行了歸類對比。最后，提出了群智協(xié)同任務(wù)分配研究所面臨的關(guān)鍵問題和未來的研究趨勢，為今后該領(lǐng)域的研究提供參考和幫助。