Cellular genetic algorithms (Q935698)

This is a comprehensive and well written treatise on cellular genetic algorithms (cGAs). The authors show that cGAs are powerful tools to deal with hard combinatorial and continuous optimization problems that compare favourably to other well-known metaheuristics. Optimization problems appear in a large number of applications, and having good techniques for solving them is of fundamental importance. Many of these optimization problems belong to the class NP-hard, which means that there is theoretical evidence suggesting that their solution requires exponential time. Metaheuristics are interesting because although they cannot guarantee finding an optimum solution for an optimization problem, they frequently produce near optimum solutions in reasonable time. cGAs are a class of evolutionary algorithms. An evolutionary algorithm modifies a set of potential solutions by emulating the biological process of evolution found in nature, so that improved solutions are found. A cGA starts with an initial selection of potential solutions for the problem at hand and then iteratively modifies the set of solutions until a terminating condition is reached. Four operations are used to modify the set of solutions: selection, recombination, mutation, and replacement. The notion of neighbourhood is of primal importance in cGAs, as the above operations are performed over the neighbourhood of each solution in the set. cGAs work fast in large and complex optmization problems thanks to their ability to process multiple solutions simultaneously. The first chapter of the book gives a concise, but thorough, introduction to cGAs, while the second chapter gives an overview of the most important research that has been conducted in this field. Emphasis is given to experimental research conducted on parallel implementations of cGAs. Chapter 3 presents some experimental evidence of the suitability of cGAs for solving complex optimization problems, by comparing cGAs to other established optimization methods. This experimental study is complemented by theoretical models presented in Chapter 4 for characterizing the selection pressure, a feature related to the amount of time (or number of generations) needed for a cGA to compute a solution. The next 6 chapters of the book are devoted to the description of several kinds of cGAs differing by the manner in which they explore the search space. There is a tradeoff between the width of the search space that a cGA explores and the depth at which that space is searched. A cGA that quickly deepens the level at which some region of the search space is explored will likely be trapped in a so-called local optimum, thus not finding the best solution for the problem at hand. On the other hand a cGA that actively explores a large region of the search space might be very slow and it might also miss an optimum solution deeply embedded inside a particular part of the search space. Chapter 6 introduces adaptive cGAs, which automatically adjust the tradeoff between the width and depth of the search process. Chapter 7 is devoted to the design of cellular memetic algorithms; these algorithms combine cGAs and hybrid optimizers to effectively exploit the structure of a particular problem for its efficient solution. Parallel cGAs are studied in Chapter 8. In this chapter a parallel model is introduced, which is appropriate for modelling cGAs intended for grid computing environments. Chapter 9 deals with the design of cGAs for multi-objective optimization problems, while Chapter 10 introduces hierarchical cGAs. Chapter 11 is devoted to the \texttt{JCell} framework, a collection of object oriented libraries for working with cGAs and other cellular evolutionary algorithms. The last 5 chapters of the book deal with applications of cGAs to a variety of problems including continuous optimization problems, vehicle routing, broadcasting in mobile ad hoc networks, and the DNA fragment assembly problem.