Q-Learning-Based Hyperheuristic Evolutionary Algorithm for Dynamic Task Allocation of Crowdsensing
针对移动群智感知中用户突然离开和任务类型差异导致的数据质量问题，提出一种动态任务分配模型，并设计基于Q学习的超启发式进化算法，通过记忆初始化与综合强度邻域搜索，在30个静态和20个动态实验中优于现有算法。
Task allocation is a crucial issue of mobile crowdsensing. The existing crowdsensing systems normally select the optimal participants giving no consideration to the sudden departure of mobile users, which significantly affects the sensing quality of tasks with a long sensing period. Furthermore, the ability of a mobile user to collect high-precision data is commonly treated as the same for different types of tasks, causing the unqualified data for some tasks provided by a competitive user. To address the issue, a dynamic task allocation model of crowdsensing is constructed by considering mobile user availability and tasks changing over time. Moreover, a novel indicator for comprehensively evaluating the sensing ability of mobile users collecting high-quality data for different types of tasks at the target area is proposed. A new Q -learning-based hyperheuristic evolutionary algorithm is suggested to deal with the problem in a self-learning way. Specifically, a memory-based initialization strategy is developed to seed a promising population by reusing participants who are capable of completing a particular task with high quality in the historical optima. In addition, taking both sensing ability and cost of a mobile user into account, a novel comprehensive strength-based neighborhood search is introduced as a low-level heuristic (LLH) to select a substitute for a costly participant. Finally, based on a new definition of the state, a Q -learning-based high-level strategy is designed to find a suitable LLH for each state. Empirical results of 30 static and 20 dynamic experiments expose that this hyperheuristic achieves superior performance compared to other state-of-the-art algorithms.