Genetic Algorithms
What is a genetic algorithm?
Genetic algorithms are a search mechanism based on natural
evolution. Its roots are found in biology and not computer science.
How does it work?
In the first population all chromosomes are
generated randomly. Their fitness is then determined. At this point the
genetic algorithm can start generating new populations.
Reproduction consists of three distinct steps:
- selection
- crossover
- mutation
Selection is based on their "fitness." In our checkers program, this is
determined by playing a game against an already wise checkers program. The
resulting board at the end of the game is used to determine fitness. The
evaluation of this board is not a simple win or lose algorithm. The
selection is a weighted selection, those with a better fitness have a
higher chance of being selected, and an individual may be selected twice.
We have not perfected this segment of the program yet.
Crossover is performed by selecting a single crossover point and switching
the chromosomes from there.
Mutation randomly selects a bit and flips it. The randomize function is
seeded off the system clock so that the bit selected is truly random.
back to main