Genetic Algorithm

Genetic algorithm implementation in neural network

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.
    I_{a}=\sum_{i=1}^{n}{|x_a-x_i|}
    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:

    Accu_{a}=\frac{ Accu_{a}}{ impAccu \cdot \sum{n}Accu_{n}}
    Div_{a}=\frac{Div_a}{impDiv \cdot \sum{n}Div_n}

    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.

 

15 thoughts on “Genetic Algorithm”

  1. Just desire to say your article is as surprising. The clarity in your publish is simply spectacular and that i could suppose you are knowledgeable on this subject. Fine along with your permission allow me to grab your feed to keep updated with imminent post. Thanks a million and please continue the enjoyable work.

  2. Wow, this was great. Keep writing this kind of blogs, you will get a lot of people to this page if you continue doing this. I will be coming back to this website more often. thx

  3. excellent points altogether, you simply gained a new reader. What would you recommend in regards to your post that you made a few days ago? Any positive?

  4. I’m gone to say to my little brother, that heshould also go to see this webpage on regular basis to obtain updated frommost recent news.

  5. I have read so many articles or reviews about the blogger lovers but this paragraph is in fact a good article, keep it up.

  6. Just wanted to say I love reading your blog and look forward to all your posts!
    Carry on the outstanding work!

  7. Howdy! I could have sworn I’ve visited this website before but after looking at a few of the articles I realized it’s new to me. Regardless, I’m certainly delighted I stumbled upon it and I’ll be bookmarking it and checking back regularly!

Leave a Reply

Your email address will not be published. Required fields are marked *