Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

8.3 GENETIC ALGORITHMS

Genetic algorithms (GAs) are a stochastic search technique inspired by the biological evolution of species. It was introduced by J. Holland in 1975 and are based on the natural selection principle by Charles Darwin in 1859: “The fittest individuals have more chances to survive into the next generation.” [11] GAs are an attractive search technique due to their simplicity and the intrinsic parallelism they offer. This technique has been applied to combinatorial problems in various fields, including the TMP. This section overviews some of the basics of GAs, parallel GAs, then it surveys the work done in TMP using GAs.

8.3.1 GAs for Optimization Problems

GAs are computational approaches that make up an interesting family of optmization algorithms. The search space is defined as the solution space where each chromosome represents one possible solution to the problem. Given a well-defined search space S of size M^N, each solution can be represented by a string (a chromosome) of length N, where each position in the string can be one of M possible symbols (alphabet). A GA is then employed to determine an efficient (optimal or acceptable suboptimal) solution according to a specific objective function, and in an evolutionary manner. Starting from a population of solutions generated randomly (or according to other rules), reproduction steps are applied with the objective of improving the quality of solutions. During the reproduction phase, some points of S are replaced, ...