Genetic Algorithm
Overview
Genetic Algorithms are a class of algorithms, inspired by fittest theories of evolutionary biology,
that solve optimization problems. The framework for genetic algorithms is fairly general and
needs to be adapted to each individual problem.
The algorithm works by randomly generating a population of possible solutions to the problem being solved. Each solution is evaluated
for its fitness. The best solutions are retained. Next, a new set of solutions is generated by taking the best solutions and
merging them somehow. (the reproduction step) The "offspring" of two parent solutions contains elements of each of its parents.
The offspring may also be randomly mutated a bit. Then the offspring are added back to the population and the best solutions
are retained, beginning the process all over again.
Rules
The rules of a genetic algorithm can be summarized as the following
- Individuals vary in their traits and compete, with successful individuals reproducing
- Trait variants affect an individuals ability to reproduce
- Traits are passed along, often with some changes, to an individuals offspring
Algorithm
The genetic algorithm engages the following steps.
- Initialization
- create an initial popluation of items to be evaluated
- Select Parents and Crossover
- evaluate each item in the population and retain the best ones.
Then create a new set of items to be added to the population through a process of merging items from the list of the best items.
- Mutate Offsprings
- add a small random change to items in the list
- Merge main population nad offspring
merge both populations and circle back the select parents and crossover step.
Examples
