Multi-objective Task Assignment Based On Improved Hydrological Cycle Algorithm In Spatial Crowdsourcing

The development of wireless communication and the popularization of smart phones have prompted the emergence of a new crowdsourcing mode,namely spatial crowdsourcing.Unlike traditional crowdsourcing,the spatial crowdsourcing requires mobile users with smartphones,i.e.,workers,to move to the designated location and complete the specific spatial task.The large-scale and complex spatial tasks can be completed efficiently at low cost by great mobility of workers.Therefore,the spatial crowdsourcing has received wide attention in both academia and industry.In spatial crowdsourcing,how to recruit appropriate workers to complete tasks is crucial.At present,scholars have studied the single-objective task assignment problem in spatial crowdsourcing,which takes a certain performance metrics of the spatial crowdsourcing system as the optimization objective in different scenarios.However,in practical applications,it usually needs to optimize multiple performance metrics at the same time.Therefore,it is necessary to study the problem of multi-objective task assignment.Specifically,the reliability and completion rate are quite important metrics in task assignment.Although some scholars have studied the multi-objective task assignment,they have not considered these two important performance metrics simultaneously,and the multi-objective task assignment problem in multiple platform scenarios.Therefore,we investigate multi-objective task assignment problems in single-platform and multi-platform spatial crowdsourcing systems respectively in this dissertation.Since these problems are NP-Hard and there is no computationally efficient optimal algorithm,we design the corresponding solution algorithms based on the improved hydrological cycle algorithm.The main workers are summarized as follows:(1)We improve the hydrological cycle algorithm.Firstly,we analyze the limitations of this algorithm,and find its slow convergence rate,low search accuracy and long running time in the problem-solving process.Then in the population initialization stage,the chaotic initialization was used to improve the global search ability.In the flow stage,the temperature updating parameter was adaptively adjusted to reduce the running time.In the condensation stage,the inverse flow procedure was introduced to enhance the search accuracy.Finally,in order to verify the effectiveness of the improvement,we compare improved algorithms with the hydrological cycle algorithm,classical intelligent optimization algorithms and new intelligent optimization in simulation experiments.The results show that improved hydrological cycle algorithms have better performance.(2)We research the multi-objective task assignment problem in the single-platform spatial crowdsourcing system.Firstly,we define the hard and soft requirements of tasks,the matching degree of workers and tasks,the workers' proficiency,and the temporal and spatial correlation between tasks.Then we propose the multi-objective optimization problem to maximize the task reliability and completion rate simultaneously,which is proved to be NP-hard.Secondly,the corresponding multi-objective task assignment algorithm is designed based on the improved hydrological cycle algorithm.Finally,simulation experiments are conducted by using synthetic data and real-world data.The simulation results verify that the designed task assignment algorithm has better performance compared with other optimization algorithms.(3)We research the multi-objective task assignment problem in the multi-platform spatial crowdsourcing system.Firstly,we propose its architecture and the optimization problem,which maximizes the task completion rate of multiple platforms simultaneously under the complex time constraints of workers and tasks.Secondly,this problem is proved to be NP-hard,and we adopt the improved hydrological cycle algorithm to solve it.Finally,the designed algorithm is verified outperform other algorithms by utilizing synthetic data and real-world data,which obtains better task completion rates on multiple platforms simultaneously.In this dissertation,the hydrological cycle algorithm is improved,and the multi-objective task assignment problems in the single-platform and the multi-platform spatial crowdsourcing system are solved by using the improved hydrological cycle algorithm.The related work can provide a reference for the realization of the spatial crowdsourcing system.