群體計(jì)算中基于博弈論的任務(wù)分配策略*

劉 鳴 彭 成 滿君豐 劉美博 杜 坤

(湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院 株洲 412007)

?

群體計(jì)算中基于博弈論的任務(wù)分配策略*

劉 鳴 彭 成 滿君豐 劉美博 杜 坤

(湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院 株洲 412007)

大數(shù)據(jù)的快速發(fā)展,推動(dòng)了社會(huì)經(jīng)濟(jì)和科技的發(fā)展,但大數(shù)據(jù)的價(jià)值密度低等特點(diǎn)為其發(fā)展帶來了挑戰(zhàn)。大數(shù)據(jù)的這些特點(diǎn)使得大數(shù)據(jù)迫切需要復(fù)雜認(rèn)知的推理技術(shù),而人機(jī)協(xié)作的群體計(jì)算成為了復(fù)雜認(rèn)知推理技術(shù)的有效途徑,但其任務(wù)分配策略還尚未完善。盡管已經(jīng)有學(xué)者提出了基于用戶主題感知的任務(wù)分配策略,解決了涉及不同專業(yè)背景及不同知識(shí)水平的任務(wù)分配,但并未解決處于同層次知識(shí)水平和專業(yè)背景的用戶如何分配任務(wù),使得計(jì)算效率更高。針對(duì)此問題,提出了基于博弈論的任務(wù)分配算法,檢測(cè)相同專業(yè)背景和知識(shí)水平的人群完成任務(wù)的準(zhǔn)確率,與任務(wù)隨機(jī)分配相比較,突出博弈論算法的準(zhǔn)確性。

群體計(jì)算; 博弈論; 大數(shù)據(jù); 任務(wù)分配

Class Number TP301.6

1 引言

隨著大數(shù)據(jù)的發(fā)展與應(yīng)用,越來越多的研究和應(yīng)用領(lǐng)域需要用到大數(shù)據(jù)處理技術(shù),大數(shù)據(jù)已經(jīng)逐步滲透到人民生活和社會(huì)經(jīng)濟(jì)的方方面面中,在社會(huì)發(fā)展中起著越來越重要的作用。當(dāng)前大數(shù)據(jù)技術(shù)的發(fā)展已經(jīng)取得一定的發(fā)展,如大數(shù)據(jù)的大規(guī)模性和高速增長(zhǎng)性,使得大數(shù)據(jù)計(jì)算任務(wù)需要海量的存儲(chǔ)計(jì)算技術(shù),近幾年集群如Hadoop集群等的發(fā)展很好解決了海量數(shù)據(jù)的存儲(chǔ),降低了海量數(shù)據(jù)的存儲(chǔ)成本,而MapReduce也較好地適應(yīng)了大數(shù)據(jù)計(jì)算技術(shù)。盡管如此,大數(shù)據(jù)還存在著很多嚴(yán)峻的挑戰(zhàn),如單純的計(jì)算技術(shù)難以處理形式多樣、價(jià)值密度低等的大數(shù)據(jù),這就需要研究新的大數(shù)據(jù)計(jì)算任務(wù)高度依賴復(fù)雜認(rèn)知推理技術(shù),我們認(rèn)為基于人機(jī)協(xié)作的群體計(jì)算是解決復(fù)雜認(rèn)知推理的有效途徑。

群體計(jì)算[1]在學(xué)術(shù)界并沒有明確的定義,維基百科給出一種闡述：“群體計(jì)算是人群和集群合作的一種模型,以此來處理計(jì)算技術(shù)難以解決的復(fù)雜任務(wù)”,即群體計(jì)算是以互聯(lián)網(wǎng)為平臺(tái),通過合理的體制機(jī)制來整合網(wǎng)絡(luò)資源和用戶群體資源,協(xié)同完成大數(shù)據(jù)計(jì)算任務(wù)[2]。群體計(jì)算任務(wù)往往涉及到不同專業(yè)領(lǐng)域的子任務(wù),需要這些子任務(wù)進(jìn)行協(xié)同處理,其中一部分子任務(wù)涉及到先進(jìn)的算法和強(qiáng)大的推理能力,并且很多子任務(wù)之間存在著復(fù)雜的關(guān)聯(lián)關(guān)系[3～4]。這些子任務(wù)需要分配給用戶群體協(xié)作完成,而由于用戶群體知識(shí)水平和專業(yè)背景不同,所完成任務(wù)的水平也會(huì)不同,再加上任務(wù)設(shè)置者與任務(wù)完成者的利益訴求不一樣,所以任務(wù)最終的完成質(zhì)量并不能取得滿意的效果,這就需要一個(gè)合理的任務(wù)分配策略,將不同領(lǐng)域的任務(wù)分配給相應(yīng)領(lǐng)域的用戶群體處理,從而提高任務(wù)完成質(zhì)量,這就是本文要闡述的基于博弈論的任務(wù)分配策略。

博弈論是研究決策主體的行為發(fā)生直接相互作用時(shí)侯的決策以及這種決策的均衡問題的理論[5]。最初的博弈論應(yīng)用于經(jīng)濟(jì)學(xué)領(lǐng)域[6～7],只是經(jīng)濟(jì)學(xué)的分支學(xué)科,后來博弈論在有理性行為和非對(duì)稱信息的分析發(fā)揮了強(qiáng)大作用,迅速成為經(jīng)濟(jì)學(xué)的重要組成部分,廣泛應(yīng)用于政治、經(jīng)濟(jì)等諸多領(lǐng)域,如今在計(jì)算機(jī)和通信領(lǐng)域也得到了廣泛的應(yīng)用。在博弈過程中參與者之間能否達(dá)成具有約束力的協(xié)議可以將博弈分為合作博弈與非合作博弈,而本文主要闡述基于合作博弈的任務(wù)分配策略。

2 相關(guān)工作

目前,群體計(jì)算發(fā)展還處于發(fā)展的階段,遠(yuǎn)沒有達(dá)到成熟的地步?，F(xiàn)有的群體計(jì)算的任務(wù)分配結(jié)構(gòu)還比較單一,甚至還存在隨機(jī)任務(wù)分配,對(duì)于任務(wù)所屬領(lǐng)域、任務(wù)之間的關(guān)聯(lián)度和任務(wù)完成者的網(wǎng)絡(luò)使用習(xí)慣、教育水平與知識(shí)背景等,隨機(jī)的任務(wù)分配策略并不給予考慮,只是將任務(wù)隨機(jī)的分配給用戶群體,因而任務(wù)難以得到具有專業(yè)知識(shí)的用戶處理,致使任務(wù)完成的質(zhì)量不能令人滿意,人機(jī)協(xié)作的群體計(jì)算優(yōu)勢(shì)并不能很好地發(fā)揮出來。

傳統(tǒng)的眾包平臺(tái)便是將任務(wù)簡(jiǎn)單的隨機(jī)分配下去,這種分配方式有其本身的優(yōu)點(diǎn),但缺點(diǎn)也是顯而易見,例如填寫病人的病例,如果將這種任務(wù)交給不具備醫(yī)學(xué)背景的人來完成,很難將數(shù)千份的病例無誤地輸入到計(jì)算機(jī)中；2004年天津大學(xué)的楊冬等將螞蟻算法進(jìn)行改進(jìn),使得該算法具有正反饋和分布式計(jì)算以及全局搜索的能力等特點(diǎn),但是該算法容易陷入局部極小點(diǎn)的陷阱,而得不到任務(wù)分配的最優(yōu)解[8]；2009年沈陽自動(dòng)化研究所聶明鴻等提出了總體極小任務(wù)分配算法,討論將任務(wù)如何分配,使完成n個(gè)任務(wù)所需的代價(jià)最小,但其計(jì)算量較大,不適合大規(guī)模的任務(wù)分配[9]?；谝陨蠁栴},張曉航和李國良[10]等提出了基于用戶主題感知的任務(wù)分配模型。李國良等人對(duì)用戶的行為進(jìn)行了分析和研究,認(rèn)為用戶的行為具有同質(zhì)性,即不同用戶的行為被認(rèn)為提供了同等質(zhì)量水平的隱式或顯式反饋信息[11～13],設(shè)計(jì)了一種針對(duì)用戶主題的任務(wù)分配算法,很好地解決了任務(wù)隨機(jī)分配的盲從性,并通過分析用戶的歷史任務(wù)數(shù)據(jù)以及明測(cè)、暗測(cè)任務(wù)了解用戶真實(shí)的主題分布,很大程度上提高了任務(wù)整體的完成質(zhì)量[14～19]。但針對(duì)具有相同教育水平和知識(shí)背景的人,如何分配任務(wù)使得任務(wù)的完成質(zhì)量較高就是本文需要闡述的基于博弈論的任務(wù)分配策略。

3 基于博弈論的任務(wù)分配策略

經(jīng)過第2節(jié)了解到博弈論之后,將在本節(jié)詳細(xì)敘述基于博弈論的任務(wù)分配策略。

3.1 合作博弈定義

3.2 合作博弈

合作是在合作之后根據(jù)收益情況分為本質(zhì)性合作和非本質(zhì)性合作,如果合作比非合作的收益多,則此合作博弈是本質(zhì)性的,若是未增加甚至下降,則此合作博弈是非本質(zhì)性合作。例如,我國存在一些效率低、收益低的一些商業(yè)合作組織可看作是非本質(zhì)性合作,因?yàn)槠涫找孢h(yuǎn)低于不合作時(shí)的收益。

本章研究了一個(gè)復(fù)雜任務(wù)和用戶群體的聯(lián)合分配問題。在群體用戶知識(shí)水平和專業(yè)背景一致的約束下,同時(shí)考慮系統(tǒng)效率和群體用戶間的公平性?；诤献鞑┺睦碚?將復(fù)雜任務(wù)分解成的小任務(wù)資源分配問題建模為群體用戶的任務(wù)分配議價(jià)博弈(Tasks Allocation of Group User Bargaining Game,TAGUBG),提出了一種動(dòng)態(tài)協(xié)作的任務(wù)分配方案。首先,引入用戶完成該任務(wù)之后期望獲得的信息增益以決定分解后的小任務(wù)對(duì)于不同可信度用戶的分配模式。進(jìn)而,將同背景、同領(lǐng)域的小任務(wù)在不同可信度用戶間動(dòng)態(tài)分配。然后,基于動(dòng)態(tài)任務(wù)分配的結(jié)果,通過自適應(yīng)任務(wù)分配算法在每個(gè)用戶分得的任務(wù)上調(diào)整任務(wù)量和難易程度。在任務(wù)分配過程中,TAGUBG實(shí)現(xiàn)了效率和公平性的折衷。借助計(jì)算機(jī)仿真,從復(fù)雜任務(wù)的切分機(jī)制和小任務(wù)的選擇以及不同用戶可信度的角度分析了相互作用的理性用戶的決策過程,理論分析與仿真結(jié)果證實(shí),與任務(wù)隨機(jī)分配方案相比較,所提出的TAGUBG方案在任務(wù)完成質(zhì)量、群體用戶間的公平性等方面都得到了改善。其總體思路圖如圖1所示。

圖1 總體思路圖

為了簡(jiǎn)化任務(wù)與群體用戶之間的分配,引入等效信息增益G,同時(shí)為了在效率和公平性之間取得更好的折衷,對(duì)單任務(wù)多用戶分配問題建模為

(1)

其中

(2)

(3)

其中,pr(x|θ)表示用戶給出正確答案的概率,pr(x)則表示問題本身得到某一個(gè)答案的概率,T表示具有不同合作能力的參與人期望效用的對(duì)比。

3.3 博弈論任務(wù)分配過程

將自動(dòng)切分獲得的小任務(wù)劃分為相關(guān)任務(wù)子集和獨(dú)立的任務(wù)子集,并將它們按照最優(yōu)利用率進(jìn)行排序,采用博弈論算法將關(guān)聯(lián)的小任務(wù)分配到同一組中,不關(guān)聯(lián)的任務(wù)則不進(jìn)行分配。其任務(wù)分配算法如下：

輸入：X={x1,x2,…,xn}

輸出：任務(wù)分配結(jié)果

1.從任務(wù)自動(dòng)切分中獲得g個(gè)相關(guān)任務(wù)子集：X1…Xg

2.FORi=1;g

3.Xk←Highest_UT()//未分配的最大相關(guān)子集

4.pk←lowest_Ld(P)//當(dāng)前負(fù)載最小的核pk

5.IFSched(Xk,pk)isTRUE//Xk在pk上可調(diào)度

6.Alloc(Xk,pk)//將Xk分配到pk上

7.WHILE?Xi∈(X1…Xg)//存在未分配的任務(wù)

8.Xk←Highest_UT()//未分配任務(wù)的最大相關(guān)子集

9.pk←lowest_Ld(P)//當(dāng)前負(fù)載最小的核pk

10.IF任務(wù)自動(dòng)分配算法返回FAILURE

11.Roll_Back()//取消本次任務(wù)分配

12.Taskset_Broken()//將任務(wù)分散

13.WHILE?Xi未分配

14.Xλ←Highest_UT()//最大的未分配獨(dú)立任務(wù)

15.pk←lowest_Load(P)//當(dāng)前負(fù)載最小的核pk

16.IFSched(Xk,pk)isTRUE//分配后可調(diào)度17.Alloc(Xk,pk)//將Xk分配到pk上

4 實(shí)驗(yàn)分析

首先通過模擬實(shí)驗(yàn),在Matlab平臺(tái)上驗(yàn)證基于合作博弈的任務(wù)分配算法的效果。模擬實(shí)驗(yàn)過程中,以螞蟻分配算法作為對(duì)照實(shí)驗(yàn),從而體現(xiàn)合作博弈的任務(wù)分配算法的優(yōu)越性。試驗(yàn)中總的小任務(wù)數(shù)n=200,這n個(gè)任務(wù)的主題是一樣的或相似的,選擇的群體用戶的專業(yè)水平和背景知識(shí)相同或相似,和任務(wù)主題相一致,將自動(dòng)切分的小任務(wù)分別按照隨機(jī)分配方法和合作博弈的方法分配給用戶群體,用戶群體完成任務(wù)的有效性服從gauss(0.8,0.2)分布,假定有20個(gè)用戶符合上述條件。

在實(shí)驗(yàn)中,每次分發(fā)20個(gè)任務(wù),即m=20,因此任務(wù)分配一共進(jìn)行R=10輪。設(shè)定三個(gè)參數(shù)α、β和γ,使α和β的值都為1,γ的初始值為10,在之后的每一輪任務(wù)分配中γ的值都減半,使任務(wù)的困難程度服從伽瑪函數(shù)分布,從beta(x,y)中獲取任務(wù)完成的正確率。(x,y)的值分別取(2,1),(6,1)和(10,1),表示任務(wù)從易到難的難易程度,(x,y)所取得每一對(duì)值都是通過重復(fù)200次算法得到的平均值。如圖2所示。

圖2 實(shí)驗(yàn)?zāi)M圖

從圖2中可以看出,兩種分配算法不同,其所對(duì)應(yīng)的用戶完成的任務(wù)準(zhǔn)確率也不同,縱觀整體,通過博弈論算法將小任務(wù)分配給群體用戶所反饋結(jié)果的有效性明顯比隨機(jī)分配算法要好,隨著x的值越高,其有效性對(duì)比越明顯。我們從beta(10,1)中進(jìn)行采樣,觀察兩種算法所對(duì)應(yīng)任務(wù)準(zhǔn)確率的變化情況,其結(jié)果如圖3所示。

圖3 任務(wù)完成的有效性對(duì)比

從圖3中可以看出,選擇合作博弈的任務(wù)分配算法所得的準(zhǔn)確率明顯要比選擇隨機(jī)分配算法所得的準(zhǔn)確率要高,兩種算法所得的結(jié)果都比較平穩(wěn),沒有較大的波動(dòng)性,隨機(jī)分配所得的平均準(zhǔn)確率基本保持在70%,而合作博弈算法準(zhǔn)確率基本穩(wěn)定在83%左右。由于剛開始并沒有用戶的歷史數(shù)據(jù),所以第一輪的平均準(zhǔn)確率相同。針對(duì)不同的用戶會(huì)根據(jù)用戶的可信度和歷史完成任務(wù)的質(zhì)量來分配難易度合適的任務(wù),從而提高用戶回答任務(wù)的效率和準(zhǔn)確率。

5 結(jié)語

研究基于博弈論的任務(wù)分配策略,對(duì)提高群體計(jì)算效率與質(zhì)量有著重要的作用。通過模擬仿真實(shí)驗(yàn),驗(yàn)證了博弈論中合作博弈算法的有效性,為群體計(jì)算的高效任務(wù)分配做出了重要的貢獻(xiàn)。未來群體計(jì)算將采用更加靈活的任務(wù)分配策略,其中博弈論將在任務(wù)分配中發(fā)揮更大的作用。如何更好地運(yùn)用博弈論在任務(wù)分配中任務(wù)優(yōu)化分配,還有很多的工作值得研究和探索。

[1] 李國良.人機(jī)協(xié)作的群體計(jì)算[J].中國計(jì)算機(jī)學(xué)會(huì)通訊,2015,11(7):20-26. LI Guoliang. Crowd computing of human-machine collaboration[J]. Communications of the China Computer Federation,2015,11(7):20-26.

[2] 劉蔚.協(xié)作和感知網(wǎng)絡(luò)中基于博弈論的資源分配研究[D].北京:北京郵電大學(xué),2011:101-112. LIU Wei. Research on resource allocation based on Game Theory in the network of cooperation and perception[D]. Beijing: Beijing University of Posts and Telecommunications,2011:101-112.

[3] 李國杰,程學(xué)旗.大數(shù)據(jù)研究：未來科技及經(jīng)濟(jì)社會(huì)發(fā)展的重大戰(zhàn)略領(lǐng)域-大數(shù)據(jù)的研究現(xiàn)狀與科學(xué)思考[J].中國科學(xué)院院刊,2012,27(6):647-657. LI Guojie, CHENG Xueqi. Research status and scientific thinking of big data[J]. Bulletin of Sciences,2012,27(6):647-657.

[4] Wang J. Kraska T, Franklin M J. et al. Crowder:Crowdsourcing entity resolution [J]. Proceedings of the VLDB Endowment, 2012,5(11):1483-1494.

[5] Franklin M J, Kossmann D, Draska T, et al. CrowdDB:Answering queries with crowdsourcing [C]//Proc of the 2011 ACM SIGMOD Int Conf on Management of Data. New York:ACM,2011,8(11):61-72.

[6] Park H, Garcia-Molina H, Pang R, et al. Deco: A system for declarative crowdsourcing [J].Proceedings of the VLDB Endowment,2012,5(12):1900-1993.

[7] 張維迎.博弈淪與信息經(jīng)濟(jì)學(xué)[M].上海:上海格致出版社,上海三聯(lián)出版社,上海人民出版社,2012:363-380. ZHANG Weiying. Game Theory and Information Economics [M]. Shanghai:Shanghai Gezhi press, Shanghai Sanlian Publishing House, Shanghai people’s Publishing House,2012:363-380.[8] 約翰·F·納什,勞埃德·S·沙普利,約翰·C·海薩尼,萊因哈德·澤爾騰. 諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)獲得者叢書·博弈論經(jīng)典[M]. 韓松,譯.北京:中國人民大學(xué)出版社,2013,12(6):545-559. John F Nash, Lloyd S Shapley, John - C - Harder Selten Harsanyi, Rhine. Nobel Economics Prize Winner Series: Classic Game Theory [M]. Han Song, translation. Beijing: Chinese People’s University Press,2013,12(6):545-559.

[9] 范如國,韓民春.博弈論[M].武漢:武漢大學(xué)出版社,2013:360-480. FAN Ruguo, HAN Minchun. Game Theory[M]. Wuhan: WuHan University Press,2013:360-480.

[10] 張曉航,李國良,馮建華.大數(shù)據(jù)群體計(jì)算中用戶主題感知的任務(wù)分配[J].計(jì)算機(jī)研究與發(fā)展,2015,52(2):309-317. ZHANG Xiaohang, LI Guoliang, FENG Jianhua. Theme-Aware Task Assignment in Crowd Computing on Big Data[J]. Journal of Computer Research and Development,2015,52(2):309-317.

[11] Karger D R,Oh S, Shah D. Iterative learning for reliable crowdsourcing systems [C]// Advances in Neural Information Processing Systems. La Jolla: NIPS, 2011:1953-1961.

[12] 劉云浩.群智感知計(jì)算[J].中國計(jì)算機(jī)學(xué)會(huì)通訊,2012,8(10):38-41. LIU Yunhao. Crowd sensing computing[J].Communications of the China Computer Federation,2012,8(10):38-41.

[13] Feng Jianhong, Li Guoliang, Wang Henan et al. Incremental Quality Inference in Crowdsourcing [M]. Database Systems for Advanced Applications. Berlin: Springer,2014:435-467.

[14] Wei Wei,Qi Yong. Information potential fields navigation in wireless Ad-Hoc sensor networks[J]. Sensors,2011,11(5):4794-4807.

[15] Wei W, Xu Q, Wang L, et al. GI/Geom/1 queue based on communication model for mesh networks[J]. International Journal of Communication Systems,2014,27(11):3013-3029.

[16] Wei W, Yang X L, Shen P Y, et al. Holes detection in anisotropic sensornets: Topological methods[J]. International Journal of Distributed Sensor Networks,2012,23(5):233-256.

[17] Song, Houbing, and Maté Brandt-Pearce. “A 2-D discrete-time model of physical impairments in wavelength-division multiplexing systems.” Journal of Lightwave Technology 30.5 ,2012:713-726.

[18] Song, Houbing, and Maté Brandt-Pearce. “Range of influence and impact of physical impairments in long-haul DWDM systems.” Lightwave Technology, Journal of 31.6,2013:846-854.

[19] Song, Houbing, Maite Brandt-Pearce. Model-centric nonlinear equalizer for coherent long-haul fiber-optic communication systems[C]//Global Communications Conference (GLOBECOM),2013,24(8):233-235.

Task Allocation Strategy Based on Game Theory in Group Computing

LIU Ming PENG Cheng MAN Junfeng LIU Meibo DU Kun

(College of Computer and Communication, Hunan University of Technology, Zhuzhou 412007)

The rapid development of big data promotes the progress of economy and technology, but the features, low value density, bring challenges to the big data. These features make that it need urgently complex cognitive reasoning,which is effectively solved by human-machine collaboration based crowd computing.However, crowd computing’s task allocation strategy is not maturity completely.some scholars have come up with a theme-aware task assignment framework, which solves task allocation to different professional background and knowledge level, but it does not deal with task allocation involving same knowledge level and professional background, which makes higher computational efficiency. To deal with this problem, it propose a task allocation algorithm based on game theory, which detects the accuracy with same professional and knowledge level. The task allocation algorithm based on game theory, compared with randomly task allocation, shows the accuracy of game theory algorithm.

crowd computing, game theory, big data, task allocation

2016年5月12日,

2016年6月22日

國家自然科學(xué)基金項(xiàng)目(編號(hào)：61350011,61379058);湖南省自然科學(xué)基金項(xiàng)目(編號(hào)：14JJ2115,12JJ2036); 湖南工業(yè)大學(xué)研究生校級(jí)創(chuàng)新基金項(xiàng)目(編號(hào)：CX1605);互聯(lián)網(wǎng)+環(huán)境下協(xié)同云制造業(yè)務(wù)流程監(jiān)管方法研究(編號(hào)：16A059);基于多源大數(shù)據(jù)融合的裝備健康評(píng)估與預(yù)測(cè)(編號(hào)：16B071)資助。

劉鳴，男，碩士研究生,研究方向：大數(shù)據(jù)和群體。彭成，男，博士，研究方向：軟件工程，大數(shù)據(jù)分析。滿君豐，男，博士，教授, 碩士生導(dǎo)師,研究方向：可信軟件、軟件工程。劉美博，男，碩士研究生，研究方向：大數(shù)據(jù)和群體計(jì)算。杜坤，男，碩士研究生，研究方向：大數(shù)據(jù)和群體計(jì)算。

TP301.6

10.3969/j.issn.1672-9722.2016.11.010