Biomedical Engineering Reference
In-Depth Information
Figure 7-8. Genetic Algorithm Operation.
When the algorithm is initialized, a population of bit strings is generated, using a random number
generator. Although only four bit strings are shown here in the initial population, a typical population
may include hundreds or even thousands of patterns. The larger the initial population, the more likely
a high-scoring or "fit" solution will emerge, at the expense of computation time. From this initial
population, two children are selected, based on the two highest-scoring patterns. All other bit strings
are discarded. These children are then allowed to "mate" with crossovers (bottom, left) and point
mutations (bottom, right).
As in the initial population, there are hundreds or even thousands of crossovers and mutations
created, and each resulting bit string is ranked by the fitness function to identify two new children.
There are various combinations of crossover and mutations possible. For example, the fittest two
children from the crossover population can each be subject to point mutations at each position in
their strings, and the fittest children with mutations can be mated with the highest-ranking crossover
children or with the parents. In this way, the string with the highest score from the fitness function is
iteratively generated. The process can continue indefinitely or, as is normally done, terminated after
a set number of generations.
Both the encoding of bit strings and the fitness function are domain-specific. For example, the first
position in the bit string might represent the presence of a particular amino acid in a protein, the
presence of a start codon in a nucleotide sequence, or the presence of a hydrogen bond at a position
on an alpha helix. Similarly, the fitness function can be as simple as positive and negative weightings
for each of the 12 bits (for example, 1s at odd positions are weighted with -1, and 1s at even
positions are weighted with +1) for a sequence analysis problem or as a complex trigonometric
