Genetic algorithms explained: Evolutionary way of problem-solving

I recently learnt about Genetic Algorithms (GA) and must say I've been quite fascinated by it. This is a two-part blog post on this topic. In this first post I will make an attempt to explain it in non-technical terms, with a simple example to illustrate the concept. The second post would be on applying this technique beyond the realm of business problems - by contemplating on how one could apply this to improving some aspects of our lives.

Now onto Part-1.

I had blogged earlier about Biomimicry, which in simple terms is design inspired by nature. Genetic Algorithms fall into the same category of solving human-faced problems, by getting inspiration from nature's solutions. In other words, this is the discipline of copying how nature operates in a bid to come up with similar harmonious solutions.

Placing Evolution in Perspective

To understand Genetic Algorithms, we'll try and understand the biologics of evolution, by using the bare minimum terminologies. 

• We are way too familiar with how one generation of humans are smarter than the previous ones. We, collectively are more evolved and (perhaps) smarter than our ancestors, while the same can be said of our kids who are way ahead of us, thanks to evolution. 
• Per the theory of natural selection, organisms better adapted to their environment tend to survive and produce more offspring. By survival of the fittest, the more evolved species reproduce more and pass on their genes down the line, while the weaker ones slowly die and get extinct.
• And, there is this quirky process midway wherein some organisms suddenly have completely unexpected traits. There are the geniuses, those highly regarded people in history of mankind with IQ levels closer to 200, like Leonardo Da Vinci. You've most likely heard of rare people with 6-fingers in a hand, which is also quite unusual. All these are likely cases of mutation, wherein suddenly an unexpected change happens, in otherwise linear, incremental evolution. If this change is strong enough to influence rest of the species, it spreads through reproduction and impacts the subsequent generations. Else, it just stays an aberration and doesn't get passed on. To get this in perspective, think X-Men!

In summary, a species of organism keep adapting to their environment, incrementally evolving and getting smarter. The smarter ones survive and reproduce more, while the weaker ones die. Once in a while, there is a sudden & unexpected change in traits of few organisms within the species and if this is remarkable and powerful enough, it gets passed on to the next generation and slowly spreads to become the defining characteristic of the entire species. Else, the mutated offspring dies and doesn't impact rest of the species.

GA: Application to Problems

What if we try and apply this evolutionary biological process to solve problems in the area of optimization. We can create a computer program that exactly mimics this process of evolution by keeping all the ground rules coded in its entirety, grow solutions from generation-to-generation, until we arrive at an optimized solution that is more efficient than a set threshold.

To illustrate with an example, lets take the popular problem of Travelling Salesman. Given a set of 5 cities that a Salesman has to travel to (exactly once to each city), the problem is to find the route that minimizes the distance travelled by the person. This is an optimization problem and while its simple to solve by hand for the 5 cities, it becomes non-trivial if you increase the number, to say 30 cities.

Applying Genetic algorithm to this problem: 

1. Start with a population containing a set of multiple random solutions - that is, multiple ways of ordering the 5 cities. 
2. For each of the solutions in this 1st generation population, evaluate by computing the total distance travelled. Order the solutions from best to worst (within this iteration).
3. Select the top 2 or 3 solutions with their ordering.
4. Marry within this solution by randomly exchanging routes between the solutions (while sticking to ground rules, such as no repetition of cities). This step mimics the reproduction or recombination, as it happens in nature.
5. The above step creates the next generation with a set of new potential solutions.
6. Once in a while (say every 10th iteration), introduce mutation by performing a random operation. For example, you could swap every pair of cities in the route created until that step.

Repeat the same process from step #2 through #6 above, until you arrive at the solution with the lowest distance travelled. Each iteration is the equivalent of one generation and through the process of evolution, each subsequent iteration would have atleast some solutions which are slightly better than the earlier ones. You might iterate through this 100s or 1000s of times depending on the problem, but this process is guaranteed to come up with the most optimal solution.

Summary

The fascinating aspect about this technique is that you can arrive at the best possible solution, and possibly the global minima to any optimization problem. You just need to code this in the structure & process as outlined above, and without getting into construction of complex mathematical equations or their solutions, you can get the best solution through an evolutionary search procedure. Check this article for a more detailed explanation. They seem to be applied to a variety of real-world problems, and they sure hold a lot of promise.