A genetic algorithm (GA) is a search algorithm often used in nonlinear discrete optimization problems. The development of GAs was inspired by the biological notion of evolution. Initially described by John Holland, they were popularized by David Goldberg who described the basic genetic algorithm very well. In a GA, data, initialized randomly in a data structure appropriate for the solution to the problem, evolves over time and becomes a suitable answer to the problem. An entire population of candidate solutions (data structures with a form suitable for solving for the problem being studied) is “randomly” initialized and evolves according to GA rules. The data structures often consist of strings of binary numbers that are mapped onto the solution space for evaluation. Each solution (often termed a creature) is assigned a fitness; a heuristic measure of its quality. During the evolutionary process, those creatures having higher fitness are favored in the parent selection process and are allowed to procreate.
The parent selection is essentially a random selection with a fitness bias. The type of fitness bias is determined by the parent selection method. Following the parent selection process, the processes of crossover and mutation are utilized and new creatures are developed that ideally explore a different area of the solution space. These new creatures replace less fit creatures from the existing population. Figure 12.11 shows a block diagram of the general GA.
The parent selection is essentially a random selection with a fitness bias. The type of fitness bias is determined by the parent selection method. Following the parent selection process, the processes of crossover and mutation are utilized and new creatures are developed that ideally explore a different area of the solution space. These new creatures replace less fit creatures from the existing population. Figure 12.11 shows a block diagram of the general GA.
 |
| FIGURE 12.11 A simple genetic algorithm. |