Parallel Meta-heuristic Search

This chapter presents an unified and up-to-date overview of the parallel meta-heuristics field. It synthesizes, classifies, and describes the main concepts and general parallelization strategies for meta-heuristics, including their instantiation for neighbourhood- and population-based methods. It also recalls the main contributions to the field, and identifies open questions and research challenges. The presentation is structured according to a three-dimensional classification of parallel meta-heuristics design strategies: the number of levels indicating whether decomposition is applied once only or recursively; the decomposition strategy reflecting the sources of parallelism in meta-heuristics, algorithm, search space, or mathematical structure; and the search strategy, given a particular level and decomposition approach, defined by the number of processes controlling the search, the communication and learning mechanism, and the diversity of the individual methods and initial solutions involved. Six major classes of parallel meta-heuristics strategies are thus discussed: low-level decomposition of computing-intensive tasks with no modification to the original algorithm, explicit decomposition of the search space, independent multi-search, as well as synchronous, asynchronous, and knowledge-creating cooperative multi-search.