基于时间窗的众包任务动态分配算法研究

发布时间：2020-09-27 10:09

　　 众包是一种新的解决问题的手段,它集结互联网大众的智慧来处理机器难处理的任务,如实体解析、语义分析、图片标注等。近几年来,众包在机器学习、数据清洗和数据集成等多个领域得到了广泛应用。在众包技术中,质量控制、成本控制和时间控制是三个主要的研究问题,而有效的任务分配是平衡三者的重要手段,现有任务分配方法大都聚焦于固定工人数量的前提下最大化任务答案质量,这种任务分配方式没有考虑任务难易程度对分配算法的影响,导致简单任务分配的工人数量过多而困难任务分配的工人数量不够的情况发生。少数任务分配算法目的是保证任务答案质量下最小化成本,但它们并未考虑到工人的到来顺序对经济成本的影响。此外,现有的算法对于任务完成时间的控制多基于报酬激励,吸引工人做任务,不适用于基于推模式的任务分配场景。针对上述问题,本文提出基于时间窗的众包任务动态分配算法,主要研究工作如下:(1)针对质量限定下最小化成本问题,本文提出了基于加权二分图的时间窗内任务分配算法(TAWBG)。首先定义了一个适合时间窗内进行任务分配的任务答案可信度连续预测方法,能够连续预测多个工人回答某任务后该任务的答案可信度,然后为时间窗内的可用工人集和可分配任务集构建加权二分图,权值为预测的答案可信度增益,优先将权值最大的边相连的任务分配给相应的工人;设计优化算法(TAWBGO),剪枝擅长程度低的工人和减少更新整个加权二分图和对边重排序的次数,以提高算法时间效率和降低经济成本。实验结果显示,与其他任务分配算法相比,TAWBG和TAWBGO算法不仅保证了任务答案质量,而且降低了经济成本,TAWBGO算法还以40倍的执行速度加快了 TAWBG算法的分配时间,降低了该算法的时间复杂度。(2)针对答案质量、花费成本和完成时间的平衡问题,本文提出了质量限定下最大化完成度的任务分配算法,包括早截止任务优先分配算法(TPAED)和基于紧迫度的任务分配算法(TAU)。实验结果表明这两种算法不仅能有效地控制任务答案质量,还能提高任务完成度和降低经济成本。
【学位单位】：北京交通大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TP181
【部分图文】：

图２－３众包工作流程图逡逑Ｆｉｇｕｒｅ邋２－３邋Ｗｏｒｋ邋ｆｌｏｗ邋ｃｈａｒｔ邋ｏｆ邋ｃｒｏｗｄｓｏｕｒｃｉｎｇ逡逑图２－３为典型的众包工作流程图。任务发布者使用众包完成任务的步骤如下：逡逑（１）

图３－２任务所需平均工人数量对比逡逑Ｆｉｇｕｒｅ邋３－２邋Ｃｏｍｐａｒｉｓｏｎ邋ｏｆ邋Ｑｕａｎｔｉｔｙ逡逑从图３－２ａ）和图３－２ｂ）中可以看出，随着可信度阈值的增大，ＴＡＷＢＧ、ＴＡＷＢＧＯ逡逑和ＣＤＡＳ算法需要的平均工人数量也随之增多，ＤＯＣＳ需要的工人数量不变。当逡逑可信度阈值小于０．８时，ＴＡＷＢＧ、ＴＡＷＢＧＯ要比ＣＤＡＳ需要的工人数量多，这是逡逑因为ＣＤＡＳ根据可信度阈值和工人平均质量计算出完成任务需要的工人数量为１，逡逑即使任务困难，也只考虑一个工人的回答，不会出现其他有争议答案的情况，所逡逑以结果中ＣＤＡＳ需要的工人数量较少，但这很可能决策出错误的答案。而ＴＡＷＢＧ逡逑和ＴＡＷＢＧＯ两个算法对于任务需要的工人数量设定了一个上限ａ，对于困难任务逡逑可以分配给更多的工人。当可信度阈值较小时，一般情况下不需要３个工人就可逡逑完成任务

图３－３任务实际平均可信度对比逡逑Ｆｉｇｕｒｅ邋３－３邋Ｃｏｍｐａｒｉｓｏｎ邋ｏｆ邋Ｃｏｎｆｉｄｅｎｃｅ逡逑从图３－３ａ）和图３－３ｂ）中可以看出，ＴＡＷＢＧ、ＴＡＷＢＧＯ和ＣＤＡＳ三个算法逡逑在可信度阈值小于等于０．９时任务实际可信度都能达标，当可信度阈值为０．９５时，逡逑ＴＡＷＢＧＯ和ＣＤＡＳ实际平均答案可信度可以达到０．９５，邋ＴＡＷＢＧ算法实际平均答逡逑案可信度仅达到０．９４，这是因为ＴＡＷＢＧＯ对工人进行剪枝，仅分配了擅长程度大逡逑于０．６的工人。如果ＴＡＷＢＧ算法想要实际平均答案可信度更高，则需要设置更大逡逑的（Ｘ，但对于本身答案争议较大的任务，并不需要为了达到很高的答案可信度而浪逡逑费成本。当可信度阈值小于等于０．８５时，使用本文提出的ＴＡＷＢＧ和ＴＡＷＢＧＯ逡逑算法分配时任务实际达到的平均答案可信度要比ＣＤＡＳ高，这是因为ＴＡＷＢＧ和逡逑ＴＡＷＢＧＯ算法充分考虑了工人在每个领域的质量

【相似文献】

相关期刊论文 前10条

1 李杰;;计算机负荷并行处理技术的智能化分配算法[J];电子制作;2013年08期

2 韩冬;梁茹冰;;分布式系统中多处理机分配算法探究[J];福建电脑;2006年07期

3 赵安军,吕向莉,郭雷,徐邦海;安全组播中密钥分配算法研究[J];微型机与应用;2005年02期

4 何江安,于泓涛,洪先龙;双层门阵布线系统中的端点分配算法[J];计算机辅助设计与图形学学报;1989年02期

5 袁玉洁;隋学敏;张英琛;;关于射入室内的太阳辐射分配算法的探讨[J];建筑科学;2016年08期

6 李晓辉;曹阳;王力纬;陈晨;;基于遗传算法的片上网络缓冲分配算法[J];北京邮电大学学报;2009年06期

7 路鹏飞;李俊;;在线计费系统中余额分配算法的优化[J];计算机工程;2011年07期

8 吴建国;刘路路;沙毅;;面向两级逻辑实现的按权状态分配算法[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系统中的码分配算法的研究与应用[A];2007年中国通信学会“移动增值业务与应用”学术年会论文集[C];2007年

4 邓钦元;范平志;;基于IEEE802．16的自适应带宽分配算法[A];2006中国西部青年通信学术会议论文集[C];2006年

5 林玉清;;认知无线电中一种新的信道与功率联合分配算法[A];2009年全国无线电应用与管理学术会议论文集[C];2009年

6 孙丽娥;;蜂窝网络中频率分配算法的研究[A];2011全国无线及移动通信学术大会论文集[C];2011年

7 李煜;彭浪;;基于优先级的数据链时隙分配算法研究[A];第三届中国指挥控制大会论文集（上册）[C];2015年

8 王磊;何宁;卢昱;;基于摄动分析的空间信息网络带宽分配算法[A];2007系统仿真技术及其应用学术会议论文集[C];2007年

9 陈超;蒋建春;丁治明;;基于时序片段评价的数据分配算法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

10 魏安贵;许宗泽;;一种基于线性规划无线网络最大最小公平性带宽分配算法[A];2008通信理论与技术新发展——第十三届全国青年通信学术会议论文集（下）[C];2008年

相关博士学位论文 前7条

1 梁晓雯;OFDM系统中自适应分配算法及其计算量的研究[D];中国科学技术大学;2006年

2 闵帆;基于试探的任务分配算法研究[D];电子科技大学;2003年

3 袁海龙;SSS巡天星表系统设计和光纤分配算法优化[D];中国科学技术大学;2011年

4 郑冠男;混合无源光网络关键技术研究[D];北京邮电大学;2011年

5 杨婷婷;协作超宽带系统资源优化分配算法研究[D];大连海事大学;2010年

6 张治中;IP over WDM网络的选路和波长分配算法研究[D];电子科技大学;2002年

7 郭淑明;无线资源管理中的前向链路带宽分配策略研究[D];解放军信息工程大学;2008年

相关硕士学位论文 前10条

1 王凯梅;基于时间窗的众包任务动态分配算法研究[D];北京交通大学;2019年

2 周荣;基于WebGIS技术的道路交通分配算法研究[D];长安大学;2019年

3 张健桐;空间众包中基于信息增益的任务分配算法研究[D];上海交通大学;2017年

4 孙炜策;移动边缘计算中基于强化学习的计算和通信资源联合分配算法研究[D];中国矿业大学;2019年

5 李志文;数据链动态时隙分配算法的仿真与分析[D];郑州大学;2018年

6 叶国栋;基于排队疏散场景的路径选择及分配算法研究[D];兰州大学;2018年

7 方文凤;群智感知系统中任务分配算法与激励机制的研究[D];四川师范大学;2018年

8 胡婷婷;移动群智感知中服务质量敏感的任务分配算法研究[D];中国科学技术大学;2017年

9 程龙;冲突保留协议动态虚拟流分配算法[D];湖南大学;2013年

10 张骏;便笺存储嵌入式系统中多层存储上的数据分配算法研究[D];湖南大学;2013年

本文编号：2827738