Attend FREE Webinar on Digital Marketing for Career & Business Growth Register Now

Data Analytics Blog

Data Analytics Case Studies, WhyTos, HowTos, Interviews, News, Events, Jobs and more...

Genetic Algorithm Tutorial: What It Is And How They Work

5 (100%) 6 votes

Before we start

Genetic Algorithm is one advance topic. Even though I will write this post in a manner that it will be easier for beginners to understand, reader should have fundamental knowledge of programming and basic algorithms before starting with this tutorial.

In this tutorial with example, I will talk about the general idea behind Genetic Algorithms followed by the required Genetic Algorithm steps to create your own Algorithm for a totally different problem. And before concluding, I will give you some real-life Genetic Algorithm examples that can be useful in learning more about Genetic Algorithms. Ready to learn something new? Let’s get started this Genetic Algorithm Python tutorial.

Introduction to Genetic Algorithms

To understand Genetic Algorithm better, let us first answer a question: How to create good Artificial Intelligence? The naïve solution is that we generate empirical algorithm, which is basically set of rules. The standard procedure is, “if you meet this condition, act like that”. However, no matter how much of work you pour into this method, the final solution will never be able to outsmart its creator.

To avoid this, a new idea called Genetic Algorithms was developed. Before learning what Genetic Algorithm is, let us first understand the theory behind it, the theory of natural selection by Darwin. The theory is simple:

If a population want to thrive, it must improve by itself constantly, it’s the survival of the fittest. The best element of the population should inspire the offspring, but the other individuals must not be forgotten in order to maintain some diversity and be able to adapt in case of a variation of the natural environment.

In simple terms, instead of creating direct solution, we recreate evolution. This idea is called Genetic Algorithm. They are mainly efficient for optimization problems. We will create our own algorithm for a problem later in this post. But before doing that, let’s understand this better with an example.

Data Analytics Course by Digital Vidya

Free Data Analytics Webinar

Date: 25th Oct, 2018 (Thursday)
Time: 3 PM to 4 PM (IST/GMT +5:30)

Genetic Algorithm Steps

The chart here shows steps you require in creating a Genetic Algorithm.

Initial Population

First, we create individuals and then we group them and call Population. An individual is distinguished by set of variables known as Genes. These Genes are combined into a string to form Chromosome, which is basically the solution.

In order to understand whole process better, let’s solve a simple problem by Genetic Algorithm: How could I crack my workmate’s password?

Creating Individuals

In this scenario, our individuals are going to be words, with of course equal length as the password. Now the tricky part, each letter is a gene and the value of that letter is allele. You know what a gene is, but allele in simple terms means one of the possible forms of a gene. Once we create individuals with same length as password, our genetic algorithm can now explore all possible amalgamations.

Creating our first population

Whenever we are creating our population, the main idea to keep in mind is that we should not point it towards the solution which seems good. Rather than that we must make it as wide as possible so that we can make a nearly perfect Genetic Algorithm which covers as many possibilities as possible. So, in our case, we will just create world only composed of random letters with equal length of password.

Fitness Function

Fitness function determines the fitness of individual, in general terms, its ability to compete with other individuals and be the final desired output. It gives fitness score to everyone and probability of that an individual will be selected for reproduction is dependent on its fitness score. The basic solution is,

fitness score = (number of char correct) / (total number of char)

This way, individual with higher fitness score is a specimen genetically closer to success that the others. Our fitness function will precisely sort the population.

 

Selection

As we now have the fitness score, in this phase we select the individuals with the highest scores and let them pass their genes to the next generations. After selecting individuals, we now group them into pair of two(parents) based on their fitness score because obviously it’s not possible to reproduce without two entities.

There are many ways to do this, however; we should keep two things in our mind. Firstly, to generate best solution of the previous generation but not keeping others aside. And secondly, also the hazard, if you select only good solutions at the beginning, you will quickly reach towards the local minimum, which is the limitation of Genetic Algorithms, and not towards the best solution.

To do this, we will take N better specimen (N = best_sample) on the one hand and on the other we will take random individuals (M = lucky_few).

Crossover

The ultimate goal of reproduction is to mix the DNA of two individuals. So, we will do the same thing here. Let’s take two individuals Oswald and Daisy, their DNA is defined by their alleles (value of each letter). Therefore, in order to mix their DNA, we just have to mix their letters. Thus, for each letter of child, we will take random letter of Oswald and Daisy.

One thing to note here is that, Oswald and Daisy isn’t going to reproduce only one child. You have to define the number of children per couple in order to keep stabilization in the population of your Genetic Algorithm.

Mutation

The primary goal of this step is to prevent our algorithm to be blocked in a local minimum. After the crossover, each individual must have a small probability to see change in their DNA.

To find out how to choose precise mutation rate for our Genetic Algorithm, I followed this article.

We have come to an end. You have all it needs to get started with Genetic Algorithms. Also, for each step, there are many solutions possible. Take your time to study more about it and choose the fittest to solve your problem for accurate solution.

A Step Further

There are several resources out there for understanding, training your own algorithm and even competing. Let’s look at some of them here.

BoxCar— A Web App

It is an example, which is online, of a genetic algorithm. The primary goal is to create vehicles that are most efficient with two wheels, the body of the vehicle is basically geometry shapes.

Evolution— A Mobile Application

More solicited than the previous one, in this you have to create a creature with joints, muscles, and bones. After you create your creature, the Genetic Algorithm tries to optimize the moves of your creature in order to execute a task which may include jump, run, climb, stairs and so on.

Practice Practice and Practice

Finally, to code is the best way to learn. Codingame.com is the platform that link lots of developers with common passion, Artificial Intelligence. Once a month they host contest which lasts one-week long, and you must create best AI possible. Most winners use Genetic Algorithms to solve problems. So, take a deep breath and dive right in.

End Notes

As I mentioned earlier, this is an advance topic. It takes a while to get around it. I tried my best to explain this in the simplest way possible. if you are currently working on a problem try Genetic Algorithm optimization to solve it even better and faster. Apart form that, if you still have any doubts or confusion in any of the step mentioned above, feel free to ask your queries. The key to success is asking the right question.

Happy Learning.

Guest Blogger (Data Science) at Digital Vidya. A Data passionate who loves reading and diving deeper into the Machine Learning and Data Science arts. Always eager to learn about new research and new ways to solve problems using ML and AI.

  • Data-Analytics

  • Your Comment

    Your email address will not be published.