Genetic Algorithms

Last modification on

A genetic algorithm (GA) is an optimization technique and is a type of evolutionary algorithm that tries to mimic natural selection, i.e., by the selection, crossover and mutation of genes, the system.

For example, in sexual reproduction, the cells have a nucleus with male and female chromosomes. The cell then copies those chromosomes to make two child with a pair on each one (see figure 1). This process is called mitosis.

Figure 1.

Just like chromosomes are made of deoxyribonucleic acid (DNA) coded in the spelling ACTG, a genotype is coded in a binary string (e.g., 10010110001), but other encodings are also possible.

So, the process is the following:

flowchart TD
	init([Initialize]) --> pop[Population]
	pop --> mut[Mutation]
	mut --> cros[Crossover]
	cros --> gen[Genotype-to-phenotype 
 transition]
	gen --> fit[Fitness]
	fit --> prob[Probability of survival]
	prob --> Q{Satifies 
 requirements?}
	Q -->|Next generation| pop[Population]
	Q -->|Yes| E([End])

  1. Initial population
  2. Mutation
  3. Crossover
  4. Genotype-to-phenotype transition
  5. Evaluate fitness (to the function)
  6. The fitness $f$ produces the probability $p$ of survival onto the next generation
  7. Selection
  8. New generation is born

There are several ways to compute the probability, such as

\[ p_{i} = \frac{f_{i}}{\sum_{i} f_{i}} \]