时间连续型空间众包任务的效率和质量问题研究

来源 :中国科学技术大学 | 被引量 : 0次 | 上传用户:fragile2001000
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着智能移动设备的广泛使用,一种新的众包形式-空间众包应运而生。空间众包要求工作者到达指定任务位置才能执行任务。本文提出了一种新的空间众包形式,称为时间连续型空间众包。时间连续型空间众包与以往空间众包的不同在于,时间连续型空间众包任务需要长时间的任务周期才能完成任务。时间连续型空间众包在实际生活中存在广泛应用,包括环境监测、交通检测等。
  由于任务预算和可分配工作者数量有限,时间连续型空间众包任务无法在任务周期内被全部执行,使得所获得的结果数据往往不完整,出现数据缺失的问题。为了解决数据缺失问题,本文采用插值技术对缺失值进行估计,但同样会影响数据的准确性。因此对于时间连续型空间众包任务来说,任务质量是非常重要的衡量指标。基于此,本文提出一种基于熵的任务质量函数。在此基础上,本文分别研究了单任务场景和多任务场景下的时间连续型空间众包任务分配问题,具体研究内容如下:
  (1)本文提出时间连续型空间众包模式及相关定义,提出时间连续型空间众包任务质量函数,并研究以任务质量为优化目标的任务分配算法。
  (2)在单任务分配场景下,本文提出最大化单任务质量问题,并分析该问题的时间复杂度。接着,本文证明最大化单任务质量问题是NP-hard问题,并给出了带有近似比的近似算法来完成任务分配。同时为了提高算法运行效率,本文还提出一系列优化策略。
  (3)在多任务分配场景下,本文提出最大化多任务总质量问题和最大化最小单任务质量问题。在最大化多任务总质量问题中,本文发现了多任务之间的关联冲突,并提出并行化框架来加快优化过程。在最大化最小单任务质量问题中,本文采用启发式近似算法来完成任务分配。
  (4)本文采用模拟数据集和真实数据集,通过实验分析不同参数对算法的影响。对于单任务分配场景下的最大化单任务质量问题,通过对比实验显示优化策略对算法效率的提升。在多任务分配场景下,针对最大化多任务总质量问题,本文对比无并行化算法、独立任务组级并行化算法和任务级并行化算法的实验结果,表现任务级并行化算法的高效性;针对最大化最小单任务问题,通过设置对比试验显示本文所提算法的有效性。
其他文献
城市轨道交通具有运量大、安全、便捷等优点,是解决各城市交通拥堵问题的首选方法。随着我国城轨运营里程快速增加,其城轨再生制动能量回馈系统也大量随之投入运行。城轨再生制动能量回馈系统运行环境复杂多变,频繁的处于开、停机状态,并且受到较高电压的冲击。因此,在实际运行中,再生制动能量回馈系统中逆变器的功率元件IGBT极易发生故障。通常逆变器中IGBT故障主要包括IGBT短路故障和IGBT开路故障。由于IG
学位
风机的偏航系统用于驱动机舱旋转,保持桨叶对准风向,以获取最大的风能。早期,偏航系统多采用电机开关直投方式驱动机舱,当机舱与风向角度相差超过15度时,直接投入驱动电机以调整偏航角度,但直投方式必然带来电流和机械冲击。机械冲击导致齿轮磨损,使得偏航系统机械寿命缩短,维护成本增加;电流冲击会导致开关跳闸,无法偏航,只能通过人工恢复。采用变频控制技术可以消除直投偏航电机带来的问题,本论文开发用于偏航系统的
学位
随着人类社会发展对能源需求的不断增加,化石能源短缺的问题逐渐引起了人们的重视。可再生能源以分布式电源的形式规模化地接入到配电网中,改变了配电网的拓扑和潮流。在配电网发生故障后,对配电网的安全可靠运行提出了新的要求。  本文通过调研分析国内外现行配电网故障区段定位方法,基于遗传算法以及粒子群算法,提出了一种新的含分布式电源的配电网故障定位方法,论文主要工作如下:  首先给出了分布式电源的简介,包括风
学位
该论文主要研究配电网规划,包括配网网架规划和配网重构,以及为之服务的负荷预测.配网网架规划又包括水平年网架规划和多阶段网架规划.对负荷预测,主要介绍了负荷预测的常用方法和各种方法的优缺点,并提出改进的人工神经元网络法用于负荷预测,以及算法实现和算例分析.对配网网架规划和配网重构,在综合各种方法的优缺点的基础上,提出了改进的多种群遗传算法用于配网网架规划和配网重构.并针对配网的特殊约束条件,提出了行
近年来,随着机器学习技术的兴起尤其是深度学习技术的蓬勃发展,人类社会迎来了人工智能的黄金时代。在新时代背景下,大量卫生保健数据加速创建,传统医疗正逐渐向智能模式转变。如何从海量电子病历中获得有价值的医学信息,是智慧医疗发展的需求,也是目前构建智慧医疗体系所面临的重大挑战。  相关实验研究表明,大量的准确标注的训练样本是使用机器学习方法获得准确率高、泛化性能好的模型的基础。然而,在医疗领域,对于某些
学位
随着各种数据密集型应用(如智能终端、多媒体、自主交通和虚拟现实)的兴起,第五代(the Fifth Generation,5G)移动通信系统的主要需求是增加容量、提高数据速率、减少延迟和改进服务质量。针对上述需求,迎接未来的挑战,一些关键的技术被提出,如非正交多址技术、物理层传输技术、大规模天线和毫米波。其中,速率分割多址技术(Rate Splitting Multiple Access,RSMA
多智能体路径规划问题是为多个智能体在地图上寻找它们从各自不同的起始位置到目标位置的无冲突路径集合的问题,属于NP-hard问题。该问题作为人工智能领域的重要问题之一,在物流仓储、交通控制、机器人等领域中也有非常多的应用。在研究该问题的历程中,产生了次维扩展、代价增长树路径搜索和基于冲突的路径搜索等求解方法。次维扩展作为其中表现最好的方法之一,是一种具备完整性和最优性的多智能体路径规划问题求解框架。
学位
网络在生活和生产中无处不在,例如社交网络,而网络表示学习(也称网络嵌入)是一种对网络型数据非常有效的处理方法,其旨在为网络中的每个节点都学习一个低维的向量表示。在现实世界中许多网络都是动态的不断变化的,然而大部分现有的算法只能对静态的网络取得较好的效果。动态网络通常可以分成两类:一种是随着时间推移其拓扑图的节点和边会增加或者减少;第二类则是网络的边会包含时间信息,如电话网络。动态网络表示学习算法大
学位
近年来,基于LSM-tree的键值(key-value)存储系统在数据存储领域发挥着重要作用,作为后端存储引擎被广泛部署在数据密集型应用场景下。然而,LSM-tree层次化的、高度有序的数据组织结构需要通过大量的数据合并操作维护,引起了严重的写放大问题。最近的研究工作针对系统架构提出了几类优化方案,虽然缓解了写放大问题,但是不同程度地牺牲了查询性能和空间利用率。为了获得均衡的高性能表现,本文通过分
随着现代城市的迅速发展,大型城市综合体内部及周边巨大的人流量为公共安全带来了严峻的挑战。为了应对这一挑战,需要针对性的人流管理措施,而人流统计和预测则是人流管理的数据基础。  由于人流在时间和空间两个维度上的不确定性,以及缺失数据的存在,精确的人流预测一直是一个具有极高挑战性的任务。近年,已有一些针对城市范围的人流密度预测算法,但这些模型均没有考虑建筑物内部,如城市综合体内的人流模式。  本论文的