Genetic Algorithm

Genetic algorithms (GAs) are a heuristic search and optimisation technique inspired by natural evolution. They have been successfully applied to a wide range of real-world problems of significant complexity.

It is an algorithm that was inspired by the theory of evolution by Charles Darwin. It simulates the process of natural selection where the fittest individuals have higher probabilities to transfer their genes to the next generation. It is usually divided into 5 parts:

1. Initialization

   The genes usually use booleans (0 or 1), but I have used a decimal number between -1 and 1 to depict the gene value.
   You need to design the neural net topology, for example: if I used 5 sticks to measure the distance to the nearest object and we want to return acceleration, right and left turn, this represents 5 inputs and 3 outputs, and you can change the hidden layers topology. We have used for my experiment 4 layers. Then, you need to initialize the weight values with a random number [-1..1].

2. Selection

   This process selects the best individuals from each generation. The fitness function returns a probability to survive to the next generation. There are lots of different variant of this step, I have designed a function that uses 2 important variables: accuracy and diversity. Genetic algorithms, like others, have a paramount problem while you are trying to reach the global minimum, it usually comes to a standstill in a local minimum. To solve this problem, I have used a measure of the distance from one individual to the rest of the individuals.
   
   In such a way, we can get the individuals diversity.
   The accuracy can be measured using the positioning system that can tell us the percentage of the circuit traveled.
   Once we have the accuracy and the diversity of each individual, we can transform absolute data to a relative to make easier to understand for us and the machine. The results will be given with a decimal number between 0 and 1. We would create a variable that represents the importance of diversity lies in the total. Eg: impDiv=0.3, ergo impAccu=0.7
   We will do that in this way:

   
   

   The probability to be in the next generation would be the sum of the diversity and the accuracy. We make a roulette filling with each individual and we select n-individuals from the roulette randomly.

3. Crossover

   The elements we have chosen will experiment the crossover operation. It is the process of exchanging genes among parents to reach a new individual made by progenitors. This part can be modified to your necessities, you can design it with some hyper-parameters: crossover rate, number of progenitors.

4. Mutation

   We change some of the genes with a random number generator. By the fact that if chosen decimal numbers, we need some hyper-parameters: mutation rate, mutation change.

5. Termination

   This process determines whether our prototype has reached our expectations or we conform with the results.