Genetic Algorithm – A very brief introduction

Artificial Intelligence and Machine Language
Share on Facebook13Share on LinkedIn3Tweet about this on TwitterShare on Google+0
Please Share!!

Back in college, our professor used to say that you are not going to use even 5% of what you are going to study in next 4-5 years, in your entire career and boy they were so right. Today I am going to write about Genetic Algorithm. I have never used genetic algorithm after my IIT days but it is something which is interesting and unique and in the fast computing era, gaining more and more popularity. So, let’s see what really is Genetic Algorithm.

Genetic Algorithm is one of the soft computing technique, where the focus is to find an optimal solution rather than the best solution. So, the first thing we need to understand is – the difference between the best and optimal solution. Now we all now, what is meant by a “best solution”. An Optimal solution is a good solution which may or may not be the best solution but finding the best solution is either too difficult or simply too costly.

If you see this graphical representation, X axis has the Cost of influencing factors and the Y axis has Quality Results. In this case, the small red circle denotes the best result, but it is costly to find. Client or the program may be happy with Yellow or even the Blue ones, they may not be as good as Red but are certainly more cost effective. Most real life problems are far more complicated to define or to compute and traditional search for the best result is not even possible or known.

Genetic Algorithm(GA) as the name suggest, evolve with repetition. First and foremost thing to solve any problem using GA is to first define it by a measurable parameter. Suppose we define our problem in hand as an equation of 2 variables as f(x,y). Now random solution – x1, y1 are chosen and measured against the equation and the result is noted down. The same process is repeated for some more random samples and their results are noted. Depending on how good is a result, a weight is applied to each solution. Better results get more weight. After this, two random solutions are picked and based on their weight, they are randomly “Crossed Over”. To simplify this means, there is a higher probability that the crossed over solution will have more percentage from the solution with higher weight. It is still just a probability and odds can win in the cross-over. Nonetheless, the result is again recorded and depending on its result, is assigned a weight and is added to “Gene Pool” or sample set. Again two random solutions are picked and are crossed over to get another solution and thus the sample set keep increasing.

Just like our evolution process, gradually the less favourable solution will lose out as the solution set keep increasing and in theory, we will be reaching towards an optimal solution after enough iterations. The idea is that processing random samples will take far less computing time than the using the traditional way to find the best solution. This seems long but happens way faster than traditional methods of finding the optimal solution and this is how Genetic Algorithm works. It is meant to solve complicated and tough problems.

Please let me know your comments and feedback in the comment section. If you have any query let me know, may be I will be able to cover it in my next blog. You can imagine, why it is called Genetic Algorithm. Now you ask me why this topic is on SAPYard? To answer, SAP uses Genetic Algorithm to determine the Model Mix Planning in APO. 😉

Share on Facebook13Share on LinkedIn3Tweet about this on TwitterShare on Google+0
Please Share!!

4 Comments on "Genetic Algorithm – A very brief introduction"

  1. Please check a dictionary. BEST and OPTIMAL have identical meaning. .

    • Dear Dunur – Thank you for stopping by and leaving your thoughts. We should not take BEST and OPTIMAL from the face value of the dictionary meaning. It might change with the usage. Best is the Perfect case but it might be unattainable or very difficult. Optimal is the most practicable one.

      Team SAPYard.

  2. Nice to know. Nicely covered the topic. Could you add some example or formula will help more.

    • Hello Chetan

      Formula depends on the problem. Suppose you are trying to solve the Travelling Salesman problem, then formula could be simple addition (total distance covered by the salesman). In this case, higher value will mean lower efficiency and hence will get lower weights.

Comments are closed.