眾包是一種新的解決問題的手段,它集結互聯網大眾的智慧來處理機器難處理的任務,如實體解析、語義分析、圖片標注等。近幾年來,眾包在機器學習、數據清洗和數據集成等多個領域得到了廣泛應用。在眾包技術中,質量控制、成本控制和時間控制是三個主要的研究問題,而有效的任務分配是平衡三者的重要手段,現有任務分配方法大都聚焦于固定工人數量的前提下最大化任務答案質量,這種任務分配方式沒有考慮任務難易程度對分配算法的影響,導致簡單任務分配的工人數量過多而困難任務分配的工人數量不夠的情況發(fā)生。少數任務分配算法目的是保證任務答案質量下最小化成本,但它們并未考慮到工人的到來順序對經濟成本的影響。此外,現有的算法對于任務完成時間的控制多基于報酬激勵,吸引工人做任務,不適用于基于推模式的任務分配場景。針對上述問題,本文提出基于時間窗的眾包任務動態(tài)分配算法,主要研究工作如下:(1)針對質量限定下最小化成本問題,本文提出了基于加權二分圖的時間窗內任務分配算法(TAWBG)。首先定義了一個適合時間窗內進行任務分配的任務答案可信度連續(xù)預測方法,能夠連續(xù)預測多個工人回答某任務后該任務的答案可信度,然后為時間窗內的可用工人集和可分配任務集構建加權二分圖,權值為預測的答案可信度增益,優(yōu)先將權值最大的邊相連的任務分配給相應的工人;設計優(yōu)化算法(TAWBGO),剪枝擅長程度低的工人和減少更新整個加權二分圖和對邊重排序的次數,以提高算法時間效率和降低經濟成本。實驗結果顯示,與其他任務分配算法相比,TAWBG和TAWBGO算法不僅保證了任務答案質量,而且降低了經濟成本,TAWBGO算法還以40倍的執(zhí)行速度加快了 TAWBG算法的分配時間,降低了該算法的時間復雜度。(2)針對答案質量、花費成本和完成時間的平衡問題,本文提出了質量限定下最大化完成度的任務分配算法,包括早截止任務優(yōu)先分配算法(TPAED)和基于緊迫度的任務分配算法(TAU)。實驗結果表明這兩種算法不僅能有效地控制任務答案質量,還能提高任務完成度和降低經濟成本。
【學位單位】：北京交通大學
【學位級別】：碩士
【學位年份】：2019
【中圖分類】：TP181
【部分圖文】：

圖２－３眾包工作流程圖逡逑Ｆｉｇｕｒｅ邋２－３邋Ｗｏｒｋ邋ｆｌｏｗ邋ｃｈａｒｔ邋ｏｆ邋ｃｒｏｗｄｓｏｕｒｃｉｎｇ逡逑圖２－３為典型的眾包工作流程圖。任務發(fā)布者使用眾包完成任務的步驟如下：逡逑（１）

圖３－２任務所需平均工人數量對比逡逑Ｆｉｇｕｒｅ邋３－２邋Ｃｏｍｐａｒｉｓｏｎ邋ｏｆ邋Ｑｕａｎｔｉｔｙ逡逑從圖３－２ａ）和圖３－２ｂ）中可以看出，隨著可信度閾值的增大，ＴＡＷＢＧ、ＴＡＷＢＧＯ逡逑和ＣＤＡＳ算法需要的平均工人數量也隨之增多，ＤＯＣＳ需要的工人數量不變。當逡逑可信度閾值小于０．８時，ＴＡＷＢＧ、ＴＡＷＢＧＯ要比ＣＤＡＳ需要的工人數量多，這是逡逑因為ＣＤＡＳ根據可信度閾值和工人平均質量計算出完成任務需要的工人數量為１，逡逑即使任務困難，也只考慮一個工人的回答，不會出現其他有爭議答案的情況，所逡逑以結果中ＣＤＡＳ需要的工人數量較少，但這很可能決策出錯誤的答案。而ＴＡＷＢＧ逡逑和ＴＡＷＢＧＯ兩個算法對于任務需要的工人數量設定了一個上限ａ，對于困難任務逡逑可以分配給更多的工人。當可信度閾值較小時，一般情況下不需要３個工人就可逡逑完成任務

圖３－３任務實際平均可信度對比逡逑Ｆｉｇｕｒｅ邋３－３邋Ｃｏｍｐａｒｉｓｏｎ邋ｏｆ邋Ｃｏｎｆｉｄｅｎｃｅ逡逑從圖３－３ａ）和圖３－３ｂ）中可以看出，ＴＡＷＢＧ、ＴＡＷＢＧＯ和ＣＤＡＳ三個算法逡逑在可信度閾值小于等于０．９時任務實際可信度都能達標，當可信度閾值為０．９５時，逡逑ＴＡＷＢＧＯ和ＣＤＡＳ實際平均答案可信度可以達到０．９５，邋ＴＡＷＢＧ算法實際平均答逡逑案可信度僅達到０．９４，這是因為ＴＡＷＢＧＯ對工人進行剪枝，僅分配了擅長程度大逡逑于０．６的工人。如果ＴＡＷＢＧ算法想要實際平均答案可信度更高，則需要設置更大逡逑的（Ｘ，但對于本身答案爭議較大的任務，并不需要為了達到很高的答案可信度而浪逡逑費成本。當可信度閾值小于等于０．８５時，使用本文提出的ＴＡＷＢＧ和ＴＡＷＢＧＯ逡逑算法分配時任務實際達到的平均答案可信度要比ＣＤＡＳ高，這是因為ＴＡＷＢＧ和逡逑ＴＡＷＢＧＯ算法充分考慮了工人在每個領域的質量

【相似文獻】

相關期刊論文 前10條

1 李杰;;計算機負荷并行處理技術的智能化分配算法[J];電子制作;2013年08期

2 韓冬;梁茹冰;;分布式系統(tǒng)中多處理機分配算法探究[J];福建電腦;2006年07期

3 趙安軍,呂向莉,郭雷,徐邦海;安全組播中密鑰分配算法研究[J];微型機與應用;2005年02期

4 何江安,于泓濤,洪先龍;雙層門陣布線系統(tǒng)中的端點分配算法[J];計算機輔助設計與圖形學學報;1989年02期

5 袁玉潔;隋學敏;張英琛;;關于射入室內的太陽輻射分配算法的探討[J];建筑科學;2016年08期

6 李曉輝;曹陽;王力緯;陳晨;;基于遺傳算法的片上網絡緩沖分配算法[J];北京郵電大學學報;2009年06期

7 路鵬飛;李俊;;在線計費系統(tǒng)中余額分配算法的優(yōu)化[J];計算機工程;2011年07期

8 吳建國;劉路路;沙毅;;面向兩級邏輯實現的按權狀態(tài)分配算法[J];安徽大學學報(自然科學版);2005年06期

9 王玉萍;曾毅;;基于智能化分配算法的計算機負荷并行處理技術探究[J];計算機光盤軟件與應用;2014年11期

10 周芳;吳寧;周磊;張穎;;面向低功耗的片上網絡虛通道分配算法[J];東南大學學報(自然科學版);2013年02期

相關會議論文 前10條

1 何興;范紅;徐偉亮;季尹禹;;EPON上行接入帶寬分配算法的研究[A];全國第十一次光纖通信暨第十二屆集成光學學術會議（OFCIO’2003）論文集[C];2003年

2 郭淑明;唐曉梅;鄔江興;;一種OVSF碼的改進型快速分配算法[A];通信理論與信號處理新進展——2005年通信理論與信號處理年會論文集[C];2005年

3 周一青;王江舟;吳冬生;;OFCDM系統(tǒng)中的碼分配算法的研究與應用[A];2007年中國通信學會“移動增值業(yè)務與應用”學術年會論文集[C];2007年

4 鄧欽元;范平志;;基于IEEE802．16的自適應帶寬分配算法[A];2006中國西部青年通信學術會議論文集[C];2006年

5 林玉清;;認知無線電中一種新的信道與功率聯合分配算法[A];2009年全國無線電應用與管理學術會議論文集[C];2009年

6 孫麗娥;;蜂窩網絡中頻率分配算法的研究[A];2011全國無線及移動通信學術大會論文集[C];2011年

7 李煜;彭浪;;基于優(yōu)先級的數據鏈時隙分配算法研究[A];第三屆中國指揮控制大會論文集（上冊）[C];2015年

8 王磊;何寧;盧昱;;基于攝動分析的空間信息網絡帶寬分配算法[A];2007系統(tǒng)仿真技術及其應用學術會議論文集[C];2007年

9 陳超;蔣建春;丁治明;;基于時序片段評價的數據分配算法[A];NDBC2010第27屆中國數據庫學術會議論文集(B輯)[C];2010年

10 魏安貴;許宗澤;;一種基于線性規(guī)劃無線網絡最大最小公平性帶寬分配算法[A];2008通信理論與技術新發(fā)展——第十三屆全國青年通信學術會議論文集（下）[C];2008年

相關博士學位論文 前7條

1 梁曉雯;OFDM系統(tǒng)中自適應分配算法及其計算量的研究[D];中國科學技術大學;2006年

2 閔帆;基于試探的任務分配算法研究[D];電子科技大學;2003年

3 袁海龍;SSS巡天星表系統(tǒng)設計和光纖分配算法優(yōu)化[D];中國科學技術大學;2011年

4 鄭冠男;混合無源光網絡關鍵技術研究[D];北京郵電大學;2011年

5 楊婷婷;協作超寬帶系統(tǒng)資源優(yōu)化分配算法研究[D];大連海事大學;2010年

6 張治中;IP over WDM網絡的選路和波長分配算法研究[D];電子科技大學;2002年

7 郭淑明;無線資源管理中的前向鏈路帶寬分配策略研究[D];解放軍信息工程大學;2008年

相關碩士學位論文 前10條

1 王凱梅;基于時間窗的眾包任務動態(tài)分配算法研究[D];北京交通大學;2019年

2 周榮;基于WebGIS技術的道路交通分配算法研究[D];長安大學;2019年

3 張健桐;空間眾包中基于信息增益的任務分配算法研究[D];上海交通大學;2017年

4 孫煒策;移動邊緣計算中基于強化學習的計算和通信資源聯合分配算法研究[D];中國礦業(yè)大學;2019年

5 李志文;數據鏈動態(tài)時隙分配算法的仿真與分析[D];鄭州大學;2018年

6 葉國棟;基于排隊疏散場景的路徑選擇及分配算法研究[D];蘭州大學;2018年

7 方文鳳;群智感知系統(tǒng)中任務分配算法與激勵機制的研究[D];四川師范大學;2018年

8 胡婷婷;移動群智感知中服務質量敏感的任務分配算法研究[D];中國科學技術大學;2017年

9 程龍;沖突保留協議動態(tài)虛擬流分配算法[D];湖南大學;2013年

10 張駿;便箋存儲嵌入式系統(tǒng)中多層存儲上的數據分配算法研究[D];湖南大學;2013年

本文編號：2827738