Genetic Algorithm: A Quick Glance

Author(s): Abhijith S Babu

Originally published on Towards AI.

Science and technology have made rapid progress in the recent past. Humans are always in pursuit of answers to everything, and this led to a lot of innovative breakthroughs, ranging from remedies for deadly diseases to extra-terrestrial travel. The world of computer science has made great achievements in the recent past, with artificial intelligence being the buzzword of the modern world. Even though it is relatively new to the common man, the term AI is as old as the term computer. Ever since computers were invented, scientists have been thinking about inducing intelligence in them.

Gradually, the focus of the study shifted to the world of biology, where intelligence actually existed. In this regard, they studied three main concepts — the model of the brain, the learning mechanism of humans, and evolution. The first one led to the development of artificial neural networks, and the second one led to the concept of machine learning. The third one gave birth to a very interesting concept called genetic algorithm!

Before going to what the genetic algorithm is, let’s have a quick peek at why genetic algorithm. The pre-historic studies say that the world started with a big bang 14 billion years ago. 10 billion years later, the first life was formed on earth in the form of some microorganisms. 2 billion years later humans comparable to the species we see around us were formed. Assuming the theories are correct, evolution is what makes this transition possible. Through a series of evolutionary steps that occurred naturally without the interference of any intelligent force, a microbe evolved into humans. Magical isn’t it???

No. Not to someone with a mathematical background. Did you miss that I said, “2 billion years later”? The microbes take a day or less to reproduce. Even the small animals take months or maybe a few years. Humans reproduce on average every 25 years. So in the worst case, if I consider 4 generations per 100 years, it took “80 million” generations at the least for such a transformation. That is a lot more generations than you can imagine.

Being a natural process, genetic evolution was slow. If it was simulated artificially, it could have been much faster and better. That is where the computer scientists found the opportunity to mock the same process and solve problems.

The genetic algorithm comes from genetics, a basic concept in biology that explains evolution. In simple terms, every organism has some characteristics and abilities, that are defined by their genes. An organism has multiple genes, each of which can take multiple states. The set of genes contained in a structure called chromosomes can undergo various operations such as crossover, mutation, inversion, etc. After these operations, the resulting chromosomes can be stronger or weaker than the original. According to the survival of the fittest theory, the organisms that have the stronger chromosomes survive, while the one that has weaker chromosomes phases out, maybe without contributing to future generations.

So when we take the population as a whole, the average fitness of a generation is much likely to be higher than the past generations.

Now coming to computer science, this theory can be used to find good solutions to problems that are theoretically harder to solve. Let us take an example.

We aim to find a medicine that can cure a certain disease. To make that, we need a protein of a particular shape. Proteins are chains of amino acids. There are 20 possible amino acids, so a protein of length 10 can have 20¹⁰ possible combinations. All of these combinations will not align to the required shape. Every protein offers resistance when we try to bend it into the required shape, which can be measured using available equipment.

At first glance, we might think that the resistance offered depends on each of the amino acids. In that case, we could have found the 10 amino acids that offer the least resistance and built a protein with them. But that is not the case here. The contribution of an acid to its resistance depends on the other acids in the protein as well as its sequence. In this case, a genetic algorithm is the best possible solution.

Consider that a protein is a chromosome and each of its amino acids is a gene. We can define a fitness function such that the resistance offered by the protein decreases the fitness of the protein. By starting with a random set of proteins and evolving them with genetic operations, we can reach a good protein in less number of tests.

Step 1

Take a set of randomly selected proteins. We can fix a population size, say 50, and choose 50 random proteins. Now calculate the fitness of all these proteins.

Step 2

Choose two random proteins from the population and do a crossover. A crossover is an operation in which a certain area of both chromosomes is selected and exchanged. Suppose our proteins are AVGFTGATGH and NJGTHSRTFV. We take a part, say the first 4 acids, and exchange them between the chromosomes. So the resultant proteins will be NJGTTGATGH and AVGFHSRTFV. The resultant proteins will be added to a new population.

The choice of proteins to crossover is not completely random. The proteins with more fitness are more likely to be chosen (because in evolution, the fittest organisms survived and reproduced).

The step is repeated until the new population has the same number of elements as the original population.

Step 3

The elements in the new population may undergo mutation or rearrangement. Mutation is a process in which a random acid in a protein changes to some other acid. For example, a protein ABCDEF can be mutated at second position to form ATCDEF.

Steps 2 and 3 produced a new population which can be considered as a new generation. These steps can be repeated to form more generations, and each generation will be fitter on average compared to the previous generations.

The process of crossover helps here as one of the resultant proteins is very likely fitter than its parent proteins. Mutation is required to stop the process from converging to a subpopulation. For instance, if the initial population does not contain the amino acid B, then the only way to bring it into the algorithm is through mutation.

After several generations, we will get a much fitter population, which contains a protein that is good for our situation. Thus, we can solve the problem using a genetic algorithm quickly.

Though the protein we got might not be the best possible option, we got a good option in much less time. This is just one such example. There are many situations where a quick good answer is better than the slow best answer. For instance, a fast-moving driverless car has to make an action. While the car can compute the best possible action, there won’t be enough time to do it, instead, a nearly good action with quick response time will be ideal.

Genetic algorithm is a vast topic. It cannot be contained in a single article. More articles on the proofs and interesting applications will be discussed in future articles. Make good use of the commenting sectionU+1F605. Have a happy reading.

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI