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

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

?

群體計算中基于博弈論的任務分配策略*

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

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

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

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

Class Number TP301.6

1 引言

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

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

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

2 相關工作

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

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

3 基于博弈論的任務分配策略

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

3.1 合作博弈定義

3.2 合作博弈

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

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

圖1 總體思路圖

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

(1)

其中

(2)

(3)

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

3.3 博弈論任務分配過程

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

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

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

1.從任務自動切分中獲得g個相關任務子集：X1…Xg

2.FORi=1;g

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

4.pk←lowest_Ld(P)//當前負載最小的核pk

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

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

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

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

9.pk←lowest_Ld(P)//當前負載最小的核pk

10.IF任務自動分配算法返回FAILURE

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

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

13.WHILE?Xi未分配

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

15.pk←lowest_Load(P)//當前負載最小的核pk

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

4 實驗分析

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

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

圖2 實驗模擬圖

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

圖3 任務完成的有效性對比

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

5 結(jié)語

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

[1] 李國良.人機協(xié)作的群體計算[J].中國計算機學會通訊,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)絡中基于博弈論的資源分配研究[D].北京:北京郵電大學,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] 李國杰,程學旗.大數(shù)據(jù)研究：未來科技及經(jīng)濟社會發(fā)展的重大戰(zhàn)略領域-大數(shù)據(jù)的研究現(xiàn)狀與科學思考[J].中國科學院院刊,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)濟學[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īng)典[M]. 韓松,譯.北京:中國人民大學出版社,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].武漢:武漢大學出版社,2013:360-480. FAN Ruguo, HAN Minchun. Game Theory[M]. Wuhan: WuHan University Press,2013:360-480.

[10] 張曉航,李國良,馮建華.大數(shù)據(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].中國計算機學會通訊,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日

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

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

TP301.6

10.3969/j.issn.1672-9722.2016.11.010