偏好匹配满意度最大化的众包任务分配

众包任务分配机制对众包任务完成质量起着至关重要的作用,然而现有的分配方法未在稳定性条件下考虑众包用户双边偏好,分配结果的准确性有待提高,并且存在众包用户因不满意当前分配对象而导致众包任务完成质量较低的问题。为此提出一种基于偏好匹配的众包任务分配方法,该方法首先考虑众包任务与工人的双边偏好,根据偏好序计算任务与工人的满意度,生成满意度矩阵;其次,该方法借鉴稳定匹配思想在考虑分配主体偏好的基础上,使分配主体对当前分配对象尽可能满意,以保障分配结果的稳定性;然后,将众包任务分配问题建模为稳定匹配规则下寻找任务最大满意度的优化问题;最后,使用贪心算法对该问题进行求解,得到众包任务分配方案。通过实验验证了该方法的有效性,实验结果表明,该方法提高了分配方案的准确性,并有效减少了无效分配的数量,从而提高了众包任务完成质量。     

基于改进粒子群算法的空间众包任务分配模型

如何进行高效合理的任务分配是当前空间众包（SC）研究中的关键问题之一。针对SC分配效能低的问题,建立了最佳质量任务分配模型（maximum quality task assignment model,MQTAM）,并提出了基于改进粒子群算法的空间众包任务分配算法（SCTAM_PSO）。该模型充分考虑了工作者到达工作地点后完成任务的时间延迟、完成任务的可信度等因素,通过SCTAM_PSO算法智能搜索最佳分配方案以最大化提高任务完成质量。实验结果及分析表明MQTAM和SCTAM_PSO具有一定的有效性与可行性。     

基于位置隐私保护的空间众包任务分配方法

针对当前空间众包任务分配中存在用户等待时间长和工人位置隐私保护度低的问题，提出一种面向位置隐私保护的空间众包任务分配方法。利用虚拟生成算法为众包工人提供一个虚拟位置，并发送到空间众包服务器中；为了提高任务分配效率，设计一种基于ε-贪婪算法的自适应批处理机制；根据动态批量大小，采用最大分数分配策略来解决众包平台中动态任务分配问题。该方法不仅减少了工人行进距离和保护了工人的隐私信息，还最大程度地降低了任务等待时间，提升了用户体验。     

基于用户满意效用的空间众包任务分配方法

针对生活中专车类空间众包用户存在偏好和延时等待的实际情况,提出一种基于用户满意效用的空间众包任务分配方法 IGSO-SSCTA。首先,定义了由用户偏好效用、延时等待效用和任务完成期望组成的用户满意效用;其次,构建了基于用户满意效用的空间众包任务分配（SSCTA）模型;接着,通过离散编码、反向学习协同初始化、四种改进移动策略、自适应选择和不可行解处理,提出一种适用该模型的改进离散萤火虫群优化（IGSO）算法;最后,利用IGSO算法对前述模型进行求解。不同规模数据集上的实验结果表明,所提方法和考虑时间最小化分配、考虑路程最小化分配、随机分配三种策略相比,用户满意效用分别提高了提升了9.64%、11.77%、15.70%;所提算法与贪婪算法和其他改进萤火虫算法相比,也有更好的稳定性和收敛性。     

基于用户激励的共享单车调度策略

针对共享单车的调度问题,在考虑预算限制、用户最大步行距离限制、用户时空需求以及共享单车分布动态变化的情况下,提出一种用户激励下的共享单车调度策略,以达到提高共享单车平台长期用户服务率的目的。该调度策略包含任务生成算法、预算分配算法和任务分配算法。在任务生成算法中,使用长短期记忆（LSTM）网络预测用户未来的单车需求量;在预算分配算法中,采用深度策略梯度（DDPG）算法来设计预算分配策略;任务分配完预算后,需要将任务分配给用户执行,因此在任务分配算法中使用贪心匹配策略来进行任务分配。基于摩拜单车的数据集进行实验,并把所提策略分别与无预算限制的调度策略（即平台不受预算限制,可以使用任意金钱激励用户将车骑行至目标区域）、贪心的调度策略、卡车拖运下的调度策略以及未进行调度的情况进行对比。实验结果表明,与贪心调度策略和卡车托运下的调度策略相比,用户激励下的共享单车调度策略能有效提高共享单车系统中的用户服务率。     

考虑工人路径的多智能体强化学习空间众包任务分配方法

针对工人和任务进行匹配是空间众包研究的核心问题之一,但已有的方法通常会忽略工人路径对任务分配结果产生的影响.传统的任务分配方法存在计算速度慢、适用范围小和协作效果不突出等问题.对此,从空间众包平台的角度出发研究面向路网的空间众包任务分配问题,以任务完成时间最短为目标,提出考虑工人路径规划的基于多智能体强化学习的QMIX-A*算法,缩短任务的平均完成时间,进而提高用户的满意度.大量的数值仿真研究验证了QMIX-A*的有效性和稳定性,为空间众包服务平台的任务分配与路径优化策略的选择提供决策支持.     

面向全局优化的时空众包任务分配算法

针对时空众包任务分配研究中未考虑多方参与对象的效益和连续任务分配的全局优化,导致分配效果不佳的问题,提出一种面向三方综合效益全局优化的在线任务分配算法。首先,基于在线随机森林和门控循环单元网络预测出下一时间戳内众包对象（众包任务和工人）的分布情况,进而结合当前时间戳内众包对象的情况构造二分图模型,最后采用带权二分图最优匹配算法完成任务分配。实验结果证明了所提算法在连续任务分配过程中实现了综合效益的全局优化。与贪心算法对比,该算法在任务分配成功率方面提升25.7%,在平均综合效益方面提升32.2%,在工人平均机会成本方面提升37.8%;与随机阈值算法对比,该算法在任务分配成功率方面提升27.4%,在平均综合效益方面提升34.7%,在工人平均机会成本方面40.2%。     

空间众包环境下的3类对象在线任务分配

随着移动互联网技术与O2O（offline-to-online）商业模式的发展,各类空间众包平台变得日益流行,如滴滴出行、百度外卖等空间众包平台更与人们日常生活密不可分.在空间众包研究中,任务分配问题更是其核心问题之一,该问题旨在研究如何将实时出现的空间众包任务分配给适宜的众包工人.但大部分现有研究所基于的假设过强,存在两类不足:（1）现有工作通常假设基于静态场景,即全部众包任务和众包工人的时空信息在任务分配前已完整获知.但众包任务与众包工人在实际应用中动态出现,且需实时地对其进行任务分配,因此现存研究结果在实际应用中缺乏可行性;（2）现有研究均假设仅有两类众包参与对象,即众包任务与众包工人,而忽略了第三方众包工作地点对任务分配的影响.综上所述,为弥补上述不足,本文提出了一类新型动态任务分配问题,即空间众包环境下的三类对象在线任务分配.该问题不但囊括了任务分配中的三类研究对象,即众包任务、众包工人和众包工作地点,而且关注动态环境.本文进而设计了随机阈值算法,并给出了该算法在最差情况下的竞争比分析.特别的是,本文还采用在线学习方法进一步优化了随机阈值算法,提出自适应随机阈值算法,并证明该优化策略可逼近随机阈值算法使用不同阈值所能达到的最佳效果.最终,本文通过在真实数据集和具有不同分布人造数据集上进行的大量实验验证了算法的效果与性能.     

防恶意竞价的众包多任务分配激励机制

众包的飞速发展丰富了任务执行者的阅历和技能,使他们更加了解任务且倾向于同时完成多种任务,因此根据执行者对任务的主观偏好进行分配成为一种常见的任务分配方式;但是出于个人利益,执行者可能采取恶意竞价行为换取更高的收益,这对众包平台的发展是不利的。为此,提出一种防恶意竞价的众包多任务分配激励机制GIMSM(Greedy Incentive Mechanism for Single-Minded)。该机制定义了一个线性比值作为分配依据,再根据贪心策略从执行者比值递增的序列中依次选取并分配任务,最后按照支付函数对分配算法选中的任务执行者进行支付,得到最终的任务分配结果。在Taxi and Limousine Commission Trip Record Data数据集上进行实验。相较于TODA(Truthful Online Double Auction mechanism)、TCAM(Truthful Combinatorial Auction Mechanism)和FU方法,GIMSM在不同工人数下的任务结果平均质量水平分别提高了25.20、13.20和4.40个百分点,GIMSM在不同任务...     

基于工作者多属性特征模型的任务分配方法

针对众包任务分配中工作者个性特征和任务需求描述难以有效匹配的问题,提出通过建立工作者的分层属性特征模型,完成任务分配的方法。以众包协同翻译为例,根据具体任务需求特征分解工作者属性需求,设计出分层属性指标用于精确描述众包工作者能力,计算出多层次指标组合权重向量个性特征模型,据此完成工作者筛选和任务分配。经实验验证,该方法提高了众包工作者和任务特征的匹配度,提高了任务完成效率和结果质量。     

群智协同任务分配研究综述

任务分配是群智协同计算和众包中的核心问题之一,即通过设计合理的任务分配策略,在满足任务约束条件下,将群智任务分配给合适的工作者,以提高群智任务的完成效率和结果质量。分析了目前任务分配方法存在的问题,总结并提出了一个通用的任务分配框架,并分别从工作者模型、任务模型、任务分配算法三个方面对国内外相关研究工作进行了分析、归纳和总结。提出了群智协同任务分配研究中的关键问题与今后的研究趋势。     

Task assignment for social-oriented crowdsourcing

Crowdsourcing has become an efficient measure to solve machine-hard problems by embracing group wisdom, in which tasks are disseminated and assigned to a group of workers in the way of open competition. The social relationships formed during this process may in turn contribute to the completion of future tasks. In this sense, it is necessary to take social factors into consideration in the research of crowdsourcing. However, there is little work on the interactions between social relationships and crowdsourcing currently. In this paper, we propose to study such interactions in those social-oriented crowdsourcing systems from the perspective of task assignment. A prototype system is built to help users publish, assign, accept, and accomplish location-based crowdsourcing tasks as well as promoting the development and utilization of social relationships during the crowdsourcing. Especially, in order to exploit the potential relationships between crowdsourcing workers and tasks, we propose a “worker-task” accuracy estimation algorithm based on a graph model that joints the factorized matrixes of both the user social networks and the history “worker-task” matrix. With the worker-task accuracy estimation matrix, a group of optimal worker candidates is efficiently chosen for a task, and a greedy task assignment algorithm is proposed to further the matching of worker-task pairs among multiple crowdsourcing tasks so as to maximize the overall accuracy. Compared with the similarity based task assignment algorithm, experimental results show that the average recommendation success rate increased by 3.67%; the average task completion rate increased by 6.17%; the number of new friends added per week increased from 7.4 to 10.5; and the average task acceptance time decreased by 8.5 seconds.     

云环境下基于模板遗传算法的任务调度方法

云任务调度是云计算研究的一个热点。云任务调度方法的好坏直接影响云平台的整体性能。提出一种基于模板遗传算法(TBGA)的任务调度方法。首先,根据处理机的运算速度和带宽等条件,计算出每个处理机应分配的任务量模板大小;然后,根据模板大小将任务集合中的任务划分为多个子集合;最后,利用遗传算法将集合中的任务分配到对应的处理机。实验证明通过此方法能得到总任务完成时间较短的调度结果。通过仿真实验将TBGA算法与Min-Min算法和遗传算法(GA)进行比较,实验结果表明,TBGA算法与Min-Min算法相比任务集合完成时间降低了20%左右,与遗传算法相比任务集合完成时间降低了30%左右,是一种有效的任务调度算法。     

精英蜂群算法及考虑利益相关者的众包定价模型

任务分配是众包流程的关键所在,也是众包价值的重要体现。从众包活动参与者即主体企业、众包平台、平台会员的视角出发,研究服务众包定价问题。在考虑会员信誉度和任务聚集度的基础上,针对含有地理因素的众包任务设计打包分配定价方案。以服务成本、任务价值、会员收益等为导向,对不同任务进行组合配置,从而设计多目标规划任务配置及定价模型,并针对该模型构建了精英蜂群算法。在精英蜂群算法中,充分利用蜜源信息并着重考虑成长性较好的蜜蜂,进而避免了局部最优问题,提高了搜索效率。通过对众包服务企业运营数据分析,获取到众包服务会员特征及任务完成相关基础信息,以此进行仿真实验。仿真结果表明通过众包任务打包定价机制,任务完成率、企业总成本、三方总收益等方面均有显著优化。综合模型及数据实验可知,众包任务在定价与发布过程中根据自身特征差异,在无差异服务中只需要考虑会员信誉度,对于具有服务差异性的任务则需要考虑打包发布。     

软件众包工人能力动态度量算法

针对现有软件众包平台对工人能力考虑不足，导致分配给工人的任务完成质量低下的问题，提出了一种软件众包工人能力动态度量算法（ADM），实现工人能力的动态度量。首先，基于静态技能覆盖率，实现工人初始能力的计算；其次，对于工人历史完成的单个任务，综合任务复杂度、任务完成质量及任务开发时效，实现开发能力的计算，并根据时间因子计算随时间衰减的开发能力；然后，根据所有历史完成任务的时间先后顺序，实现能力度量值的动态更新；最后，基于历史任务技能覆盖率，计算工人对于待分配任务的开发能力。实验结果表明，与用户可靠性度量算法相比，所提出的能力动态度量算法具有较好的合理性与有效性，使能力度量吻合度平均值最高达到90.5%，能有效指导任务分配。     

基于Pareto分布的众包工人欺骗行为处理方法

由于众包的组织模式自由松散,致使众包工人在完成任务的过程中存在欺骗行为。如何识别工人的欺骗行为并降低其影响,从而保障众包任务的完成质量,已经成为众包领域的研究热点之一。通过对任务结果的评估与分析,针对众包工人统一型欺骗行为,提出了一种基于广义Pareto分布（GPD）的权重设置算法（WSABG）。该算法对GPD进行极大似然估计,并用二分法逼近似然函数的零点以计算出尺度参数σ和形状参数ε。算法中定义了新的权重公式,并利用众包工人完成当前任务的反馈数据赋予每位工人一个绝对影响权重,最终设计出了基于GPD的众包工人权重设置框架。所提算法可以解决任务结果数据之间差异性小且容易集中在两极的问题。以烟台大学学生评教数据为实验数据集,提出了区间转移矩阵的概念,证明了WSABG算法的有效性和优势。     

云计算环境下基于模板的任务调度策略与算法

针对云计算任务调度,提出了一种基于模板的任务调度（Template-based Task Scheduling,TTS）策略。该策略充分考虑了通信开销,在对任务分配进行预处理的基础上实现任务调度,主要分为两步：针对一个任务集合,采用可分任务调度求解子任务大小的方法,求出各个处理机应该分担的任务量模板;根据求出的模板,采用合理的调度算法对任务进行调度,从而得到较优的调度结果。在TTS策略下,对传统贪心算法加以改进,最终提出基于模板的任务调度贪心算法（Template-based Task Scheduling Greedy Algorithm,TTSGdA）。与Min-min算法和遗传算法的对比实验结果表明,TTSGdA能够有效减少任务集合完成时间。