基于Spark的并行Metaheuristic算法研究

Metaheuristic algorithms are commonly regarded as one of efficient ways to deal with NP-hard problems. However, this sort of algorithms, when running in series processing machines, can hardly solve very large problems or complex problems occurring in big data environment. Based on Spark cloud computing platform, this project plans to carry out researches on parallel design and implementation of metaheuristic algorithms such as simulated annealing, tabu search, genetic algorithm, and MOEA/D algorithm. The main research contents include: (I) implementation of parallel metaheuristic algorithms, (II) design of parallel framework, (III) sharing and transmission of information. In order to evaluate the performance of the proposed parallel metaheuristic algorithms, classic satisfiability problem and vehicle routing problem will be solved. In particular, the proposed algorithms will be used to solve a vehicle routing problem with real-world constraints in a big data environment. This project will develop a new parallel method for solving NP-hard problems in big data environment and will provide help and service for researchers and practitioners to solve computation-intensive large-scale optimization problems.

Metaheuristic算法是处理NP困难问题的有效方法。但是对于很大规模的问题或者大数据环境中的复杂问题，这类算法在串行机上仍然耗时严重而难以实用。本项目将选择代表性的Metaheuristic算法如模拟退火、禁忌搜索、遗传算法和MOEA/D算法，基于最新的Spark云计算平台，研究他们的并行实现。其中，并行Metaheuristic算法的设计和实现问题、并行框架的设计问题、信息的共享和传递问题是重点研究内容。两类经典问题的代表可满足性问题和车辆调度问题将被用来验证并行Metaheuristic算法的有效性。特别地，提出的并行算法将被进一步用于解决大数据环境下带现实约束的车辆调度问题。本项目的完成，可以为大数据环境中NP困难问题的并行化求解提供新思路和新方法，为学术界和工业界求解大规模复杂优化问题提供帮助和服务。

对于很大规模的问题或者大数据环境中的复杂问题，Metaheuristic算法或者深度学习算法等在串行机上仍然耗时严重而难以实用。本项目将选择代表性的算法如模拟退火、禁忌搜索、遗传算法、MOEA/D算法、蚁群算法以及深度学习算法等，基于Spark云计算平台，研究他们的并行实现。具体研究了云计算环境下的调度问题，并行Metaheuristic算法的设计和实现问题、并行框架的设计问题、信息的共享和传递问题以及深度学习的应用问题。两类经典问题的代表可满足性问题和车辆调度问题将被用来验证并行Metaheuristic算法的有效性。特别地，提出的并行算法将被进一步用于解决大数据环境下带现实约束的车辆调度问题。特别研究了机器学习的高性能实现及其在病虫害识别领域的初步研究。本项目的完成，可以为大数据环境中NP困难问题的并行化求解以及复杂的机器学习问题提供新思路和新方法，为学术界和工业界求解大规模复杂优化问题提供帮助和服务。