考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解

doi:10.11772/j.issn.1001-9081.2020060940

计算机应用 ›› 2021, Vol. 41 ›› Issue (3): 794-802.DOI: 10.11772/j.issn.1001-9081.2020060940

所属专题：先进计算

考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解

冉家敏^1,2, 倪志伟^1,2, 彭鹏^1,2,3, 朱旭辉^1,2

1. 合肥工业大学管理学院, 合肥 230009;
2. 过程优化与智能决策教育部重点实验室(合肥工业大学), 合肥 230009;
3. 北方民族大学, 银川 750021

收稿日期:2020-07-02 修回日期:2020-10-14 出版日期:2021-03-10 发布日期:2021-01-15
通讯作者: 倪志伟
作者简介:冉家敏(1996-),女,安徽六安人,硕士研究生,主要研究方向:空间众包、人工智能;倪志伟(1963-),男,安徽合肥人,教授,博士,主要研究方向:人工智能、机器学习、大数据、空间众包;彭鹏(1988-),男,安徽合肥人,讲师,博士研究生,主要研究方向:智能计算、数据挖掘;朱旭辉(1991-),男,安徽阜阳人,讲师,博士,主要研究方向:深度学习、智能计算。
基金资助:
国家自然科学基金资助项目（91546108，71521001，71901001）；安徽省科技重大专项（201903a05020020）；安徽省自然科学基金资助项目（1908085QG298）。

Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution

RAN Jiamin^1,2, NI Zhiwei^1,2, PENG Peng^1,2,3, ZHU Xuhui^1,2

1. School of Management, Hefei University of Technology, Hefei Anhui 230009, China;
2. Key Laboratory of Process Optimization and Intelligent Decision-Making, Ministry of Education(Hefei University of Technology), Hefei Anhui 230009, China;
3. North Minzu University, Yinchuan Ningxia 750021, China

Received:2020-07-02 Revised:2020-10-14 Online:2021-03-10 Published:2021-01-15
Supported by:
This work is partially supported by the National Natural Science Foundation of China (91546108, 71521001, 71901001), the Science and Technology Major Project of Anhui Province (201903a05020020), the Natural Science Foundation of Anhui Province (1908085QG298).

摘要/Abstract

摘要： 针对空间众包中的任务分配问题，考虑空间众包工作者的服务质量对分配结果的影响，从而提出了一种加入了工作者服务质量评价的任务分配策略。首先，在每个时空环境下，加入工作者的评价要素以建立充分考虑工作者服务质量和距离成本的多目标模型；其次，通过改进离散型萤火虫群优化算法的初始化及编码策略、位置移动策略、邻域搜索策略使算法收敛速度加快、全局寻优能力提高；最后，利用改进后的算法来求解模型。在模拟和真实数据集上的实验结果表明，该算法在不同规模数据集上较其他群智能算法可提高2%~25%的任务分配总得分。该算法考虑了工作者的服务质量后，可有效提高任务分配效率和最终总得分。

关键词: 工作者服务质量评价, 工作者评价得分更新机制, 空间众包, 任务分配, 离散型萤火虫群优化算法

Abstract: Focusing on the task allocation problem in spatial crowdsourcing, with the consideration of the influence of the spatial crowdsourcing workers' service quality on the allocation results, a task allocation strategy with the quality evaluation of worker's service was proposed. Firstly, in each spatio-temporal environment, the evaluation element of spatial crowdsourcing workers was added to establish a multi-objective model that fully considers the service quality and distance cost of the workers. Secondly, the algorithm convergence speed was increased and the global optimization ability was improved by improving the initialization and coding strategy, position movement strategy and neighborhood search strategy of the discrete glowworm swarm optimization algorithm. Finally, the improved algorithm was used to solve the model. Experimental results on the simulated and real datasets show that, compared with other swarm intelligence algorithms, the proposed algorithm can improve the total score of task allocation by 2% to 25% on datasets with different scales. By considering the service quality of workers, the proposed algorithm can effectively improve the efficiency of task allocation and the final total score.

Key words: quality evaluation of the worker's service, worker's evaluation score updating mechanism, spatial crowdsourcing, task allocation, discrete glowworm swarm optimization algorithm

中图分类号:

TP301.6

冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.

RAN Jiamin, NI Zhiwei, PENG Peng, ZHU Xuhui. Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution[J]. Journal of Computer Applications, 2021, 41(3): 794-802.

参考文献

[1] HOWE J. Crowdsourcing:Why the Power of the Crowd is Driving the Future of Business[M]. New York:Crown Publishing Group, 2008:2.
[2] 童咏昕, 袁野, 成雨蓉, 等. 时空众包数据管理技术研究综述[J]. 软件学报,2017,28(1):35-58.(TONG Y X,YUAN Y, CHENG Y R,et al. Survey on spatiotemporal crowdsourced data management techniques[J]. Journal of Software,2017,28(1):35-58.)
[3] 李洋, 贾梦迪, 杨文彦, 等. 基于树分解的空间众包最优任务分配算法[J]. 软件学报,2018,29(3):824-838.(LI Y,JIA M D, YANG W Y,et al. Optimal task assignment algorithm based on tree-decouple in spatial crowdsourcing[J]. Journal of Software, 2018,29(3):824-838.)
[4] 毛莺池, 穆超, 包威, 等. 空间众包中多类型任务的分配与调度方法[J]. 计算机应用,2018,38(1):6-12.(MAO Y C,MU C, BAO W,et al. Multi-type task assignment and scheduling oriented to spatial crowdsourcing[J]. Journal of Computer Applications, 2018,38(1):6-12.)
[5] 范泽军, 沈立炜, 彭鑫, 等. 基于约束的空间众包多阶段任务分配[J]. 计算机学报,2019,42(12):2722-2741.(FAN Z J,SHEN L W,PENG X,et al. Multi stage task allocation on constrained spatial crowdsourcing[J]. Chinese Journal of Computers,2019,42(12):2722-2741.)
[6] 余敦辉, 张灵莉, 付聪. 基于动态效用的时空众包在线任务分配[J]. 电子与信息学报,2018,40(7):1699-1706.(YU D H, ZHANG L L,FU C. Online task allocation of spatial crowdsourcing based on dynamic utility[J]. Journal of Electronics and Information Technology,2018,40(7):1699-1706.)
[7] 刘辉, 李盛恩. 时空众包环境下基于统计预测的自适应阈值算法[J]. 计算机应用,2018,38(2):415-420.(LIU H,LI S E.Adaptive threshold algorithm based on statistical prediction under spatial crowdsourcing environment[J]. Journal of Computer Applications,2018,38(2):415-420.)
[8] ZHANG X,YANG Z,LIU Y,et al. On reliable task assignment for spatial crowdsourcing[J]. IEEE Transactions on Emerging Topics in Computing,2019,7(1):174-186.
[9] CHENG P, LIAN X, CHEN L, et al. Prediction-based task assignment in spatial crowdsourcing[C]//Proceedings of the IEEE 33rd International Conference on Data Engineering. Piscataway:IEEE,2017:997-1008.
[10] LIU X,LU M,OOI B C,et al. CDAS:a crowdsourcing data analytics system[J]. Proceedings of the VLDB Endowment, 2012,5(10):1040-1051.
[11] TONG Y,SHE J,DING B,et al. Online minimum matching in real-time spatial data[J]. Proceedings of the VLDB Endowment, 2016,9(12):1053-1064.
[12] HOLLAND J H. Adaptation in Natural and Artificial Systems:An Introductory Analysis with Application to Biology,Control and Artificial Intelligence[M]. Cambridge:MIT Press,1992:32-58.
[13] DU Y,XIAO L,CHEN Y,et al. Aircraft engine gas path fault diagnosis based on hybrid PSO-TWSVM[J]. Transactions of Nanjing University of Aeronautics and Astronautics,2018,35(2):334-342.
[14] KRISHNANAND K N,GHOSE D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]//Proceedings of the 2005 IEEE Swarm Intelligence Symposium. Piscataway:IEEE,2005:84-91.
[15] 张小琼, 秦亮曦. 基于混合变异的萤火虫群优化算法[J]. 计算机应用与软件,2016,33(2):272-275,317.(ZHANG X Q, QIN L X. Glowworm swarm optimization based on hybrid mutation[J]. Computer Applications and Software,2016,33(2):272-275,317.)
[16] MIRYALA G,LUDWIG S A. Comparing Spark with MapReduce:glowworm swarm optimization applied to multimodal functions[J]. International Journal of Swarm Intelligence Research,2018,9(3):1-22.
[17] 邓晨曦, 周国雄. 基于萤火虫群优化算法的烟草香级集成分类方法[J]. 数学的实践与认识,2017,47(20):45-55.(DENG C X,ZHOU G X. Tobacco aroma ensemble classification method based on glowworm swarm optimization algorithm[J]. Mathematics in Practice and Theory,2017,47(20):45-55.)
[18] 周永权, 黄正新, 刘洪霞. 求解TSP问题的离散型萤火虫群优化算法[J]. 电子学报,2012,40(6):1164-1170.(ZHOU Y Q, HUANG Z X,LIU H X. Discrete glowworm swarm optimization algorithm for TSP problem[J]. Acta Electronica Sinica,2012,40(6):1164-1170.)
[19] 于宏涛, 高立群, 韩希昌. 求解旅行商问题的离散人工萤火虫算法[J]. 华南理工大学学报(自然科学版),2015,43(1):126-131,139.(YU H T,GAO L Q,HAN X C. Discrete artificial firefly algorithm for solving traveling salesman problems[J]. Journal of South China University of Technology(Natural Science Edition),2015,43(1):126-131,139.)
[20] LIU Z,GUO S,WANG L,et al. A multi-objective service composition recommendation method for individualized customer:Hybrid MPA-GSO-DNN model[J]. Computers and Industrial Engineering,2019,128:122-134.
[21] PANDEY P,SHUKLA A,TIWARI R. Three-dimensional path planning for unmanned aerial vehicles using glowworm swarm optimization algorithm[J]. International Journal of System Assurance Engineering and Management,2018,9(4):836-852.
[22] DONG W, ZHOU K, ZHANG G, et al. Modified discrete glowworm swarm optimization algorithm based on time window division for multi-objective VRPTW[J]. Journal of Internet Technology,2018,19(1):1-13.
[23] KRISHNANAND K N, GHOSE D. Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications[J]. Multiagent and Grid Systems,2006,2(3):209-222.
[24] 倪志伟, 张琛, 倪丽萍. 基于萤火虫群优化算法的选择性集成雾霾天气预测方法[J]. 模式识别与人工智能,2016,29(2):143-153.(NI Z W,ZHANG C,NI L P. Haze forecast method of selective ensemble based on glowworm swarm optimization algorithm[J]. Pattern Recognition and Artificial Intelligence, 2016,29(2):143-153.)*

考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解

Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 计算机应用, 2021, 41(8): 2232-2241.
[2]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[3]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[4]	韩俊樱, 张振宇, 孔德仕. 移动群智感知中面向用户区域的分布式多任务分配方法[J]. 计算机应用, 2020, 40(2): 358-362.
[5]	秦海燕, 章永龙, 李斌. 社会网络下分配众包任务的真实机制[J]. 计算机应用, 2020, 40(10): 3019-3024.
[6]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[7]	张兴盛, 余敦辉, 张万山, 王晨旭. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019, 39(5): 1357-1363.
[8]	陈友玲, 左丽丹, 牛禹霏, 王龙. 基于知识相似度的产品开发任务分配方法[J]. 计算机应用, 2019, 39(2): 323-329.
[9]	李鑫滨, 章寿涛, 闫磊, 韩松. 基于鲁棒Restless Bandits模型的多水下自主航行器任务分配策略[J]. 计算机应用, 2019, 39(10): 2795-2801.
[10]	刘鹏飞, 毛莺池, 王龙宝. 基于云雾协作模型的任务分配方法[J]. 计算机应用, 2019, 39(1): 8-14.
[11]	赵焜松, 余敦辉, 张万山. 软件众包任务发布优先级计算方法[J]. 计算机应用, 2018, 38(7): 2032-2036.
[12]	刘辉, 李盛恩. 时空众包环境下基于统计预测的自适应阈值算法[J]. 计算机应用, 2018, 38(2): 415-420.
[13]	余敦辉, 王意, 张万山. 软件众包工人能力动态度量算法[J]. 计算机应用, 2018, 38(12): 3612-3617.
[14]	毛莺池, 穆超, 包威, 李晓芳. 空间众包中多类型任务的分配与调度方法[J]. 计算机应用, 2018, 38(1): 6-12.
[15]	施战, 辛煜, 孙玉娥, 黄河. 基于用户可靠性的众包系统任务分配机制[J]. 计算机应用, 2017, 37(9): 2449-2453.