This post’s subject is an introduction of another artificial intelligence area: The genetic algorithm. It is an optimization method based in biological evolution, searching the best solution to a problem.
Definitions
There is a objective function, which is the answer, and a group of candidates, whose name is population, to see which approach more of the solution. Each solution has a group of bits, called chromosome. And each bit is a gene.
The crossover consist in get the genes of solutions which passed in the first test and create a new generation. The next generation have its genes modified by mutation. The genetic operators make the mutation and crossover in the chromosomes.
Every genetic algorithm has 4 parameters:
- Population size: Very low population decrease the performance, while a very high population requires a greater computational power;
- Cross rate: Very low value make the algorithm slow, but a very high value can eliminate adaptable chromosomes;
- Mutation rate: Determine the mutation degree in the chromosomes;
- Generation interval: Determine part of population which will be replaced by the next generation.
Procedure
This is the genetic algorithm’s basic flowchart.
First the candidates are generated randomly and coded in a group of bits, then the adaptation calculation is made. The closest chromosomes from the solution are selected and shuffled creating partners pairs to make the crossover. There are three ways of crossover, one-point crossover, where one point for crossing is chosen.
There is the multiple points crossover.
Or can cut and splice, this method can change the size of bits set.
The mutation genetic operator switch bits in a chromosome randomly, mutation is useful to find the best solution.
The new generation is evaluated by adaptation function, the cycle continues until the problem’s resolution is found.
Some applications
These algorithms can be used in robots which self program and adapt to different situations and patterns. Applications out of robotics involve:
- Optimization problem resolution like the traveling salesman problem;
- Management of wireless networks to find out the best route to connections;
- Electronic circuits synthesis;
- Biological models simulation.
