Alba E. (ed.) Parallel Metaheuristics. A New Class of Algorithms

John Wiley, 2005. — 575.The present book is the result of an ambitious project to bring together the various visions of researchers in both the parallelism and metaheuristic fields, with a main focus on optimization. In recent years, devising parallel models of algorithms has been a healthy field for developing more efficient optimization procedures. What most people using these algorithms usually miss is the important idea that parallel models that run in multiple computers are quite modified versions of the sequential solvers they have in mind. This of course means that not only the resulting algorithm is faster in wall clock time, but also that the underlying algorithm performing the actual search is a new one. These new techniques have their own dynamics and properties, many of them coming from the kind of separate decentralized search that they perform, while many others come from their parallel execution.
Creating parallel metaheuristics is just one way for improving an algorithm. Other different approaches account for designing hybrid algorithms (merging ideas from existing techniques), creating specialized operations for the problem at hand, and a plethora of fruitful research lines of the international arena. However, designing parallel metaheuristics has an additional load of complexity, since doing it appropriately implies that the researcher must have background knowledge from the two combined fields: parallelism and metaheuristics. Clearly, this is difficult, since specialization is a must nowadays, and these two fields are naturally populated by often separate groups of people. Thus, many researchers in mathematics, engineering, business, physics, and pure computer science deal quite appropriately with the algorithms, but have no skills in parallelism. Complementary, many researchers in the field of parallelism are quite skilled with parallel software tools, distributed systems, parallel languages, parallel hardware, and many other issues of high importance in complex applications; but the problem arises since these researchers often do not have deep knowledge in metaheuristics. In addition, there are also researchers who are application-driven in their daily work; they only want to apply the techniques efficiently, and do not have the time or resources (nor maybe the interest) in the algorithms themselves nor in parallelism, just in the application.
This book is intended to serve all of them, and this is why I initially said that it tries to fulfill an ambitious goal. The reader will have to judge to which extent this goal is met in the contents provided in the different chapters. Most chapters contain a methodological first part dealing with the technique, in order to settle its expected behavior and the main lines that could lead to its parallelization. In a second part, chapters discuss how parallel models can be derived for the technique to become more efficient and what are the implications for the resulting algorithms. Finally, some experimental analysis is included in each chapter in order to help understand the advantages and limits of each proposal from a practical point of view. In this way, researchers whose specialities are in either domain can profit from the contents of each chapter. This is the way in which the central part of the book, entitled Parallel Metaheuristic Models (Chapters 5 to 17) was conceived.Part I Introduction to Metaheuristics and Parallelism
An Introduction to Metaheuristic Techniques
Measuring the Performance of Parallel Metaheuristics
New Technologies in Parallelism
Metaheuristics and Parallelism
Part II Parallel Metaheuristic Models
Parallel Genetic Algorithms
Parallel Genetic Programming
Parallel Evolution Strategies
Parallel Ant Colony Algorithms
Parallel Estimation of Distribution Algorithms
Parallel Scatter Search
Parallel Variable Neighborhood Search
Parallel Simulated Annealing
Parallel Tabu Search
Parallel Greedy Randomized Adaptive Search Procedures
Parallel Hybrid Metaheuristics
Parallel Multiobjective Optimization
Parallel Heterogeneous Metaheuristics
Part III Theory and Applications
Theory of Parallel Genetic Algorithms
Parallel Metaheuristics Applications
Parallel Metaheuristics in Telecommunications
Bioinformatics and Parallel Metaheuristics