Genetic Algorithm
A genetic algorithm (GA) is a stochastic global optimization algorithm that is inspired from natural selection. It is also a metaheuristic
- Fitter individuals pass on their genes to the next generation directly. This is called elitism and is used to preserve good solutions
- A chromosome is a possible solution candidate. Genes are elements in a chromosome
- One iteration in the algorithm = one evolutionary generation
The algorithms uses the following analogies
| Biological | Programmatic |
|---|---|
| Genetic representation | Bitstrings |
| Fitness | Function evaluations |
| Selection | Choosing strings from the population |
| Genetic recombination | Crossover of bitstrings |
| Mutation | Bit flipping |
| Genetic recombination is when the chosen parents “combine” their genes to pass them on to children |
- This is probabilistic - There is some chance that the parent’s genes are copied over to the child
- In other cases, crossover methods are used such as one-point crossover
- Hyperparameter used: Some large value (80% - 90%)
Mutation hyperparameter (rate): 1/L (L = Bitstring length)
- Mutation introduces genetic diversity and allows the algorithm to explore new areas of the solution space
flowchart TD
A["Create population of fixed bitstrings"]
B["Evaluation using objective (fitness) function"]
C["Parents are chosen based on fitness from k random bitstrings"]
D["Recombination using crossover methods"]
E["Mutation in children"]
A --> B --> C --> D --> E
Use encoding to present the solution spacea in a manner that the GA can process