Division of computational load between multiple processing elements.
Published in Chapter:
Designing Parallel Meta-Heuristic Methods
Teodor Gabriel Crainic (Département de Management et Technologie, Université du Québec à Montréal, CIRRELT, Canada), Tatjana Davidović (Mathematical Institute, Serbian Academy of Science and Arts, Serbia), and Dušan Ramljak (Center for Data Analytics and Biomedical Informatics, Temple University, USA)
Copyright: © 2014
|Pages: 21
DOI: 10.4018/978-1-4666-5784-7.ch011
Abstract
Meta-heuristics represent powerful tools for addressing hard combinatorial optimization problems. However, real life instances usually cannot be treated efficiently in “reasonable” computing times. Moreover, a major issue in meta-heuristic design and calibration is to provide high performance solutions for a variety of problems. Parallel meta-heuristics aim to address both issues. The objective of this chapter is to present a state-of-the-art survey of the main parallelization ideas and strategies, and to discuss general design principles applicable to all meta-heuristic classes. To achieve this goal, the authors explain various paradigms related to parallel meta-heuristic development, where communications, synchronization, and control aspects are the most relevant. They also discuss implementation issues pointing out the characteristics of shared and distributed memory multiprocessors as target architectures. All these topics are illustrated by the examples from recent literature related to the parallelization of various meta-heuristic methods. Here, the authors focus on Variable Neighborhood Search and Bee Colony Optimization.