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

9.3 OVERVIEW OF GENETIC ALGORITHMS

Genetic algorithms (GAs), introduced by Holland in the 1970s [16], are search techniques that are designed based on the concept of evolution [6, 9, 15, 29], In simple terms, given a well-defined search space in which each point is represented by a bit string, called a chromosome, a GA is applied with its three genetic search operators—selection, crossover, and mutation—to transform a population of chromosomes with the objective of improving the quality of the chromosomes. A GA is usually employed to determine the optimal solution of a certain objective function. And the search space therefore is defined as the solution space so that each feasible solution is represented by a distinct chromosome. Before the search starts, a set of chromosomes is randomly chosen from the search space to form the initial population. Then the three genetic search operations are applied one after the other to obtain a new generation of chromosomes in which the expected quality over all the chromosomes is better than that of the previous generation. This process is repeated until the stopping criterion is met and the best chromosome of the last generation is reported as the final solution. An outline of a generic GA is as follows. The detailed mechanism of the three operators is elaborated afterwards.

Standard Genetic Algorithm (SGA): (1) Generate initial population; (2) while number of generations not exhausted do (3) for i=l to PopulationSize do (4) Randomly select ...