April 10, 2021

What are genetic algorithms? | Science

An algorithm is a series of steps that describe the search process of a solution to a specific problem. And a genetic algorithm is when you use mechanisms that simulate those of the evolution of the species of biology to formulate those steps. It is an artificial intelligence technique inspired by the idea that the one that survives is the one that is better adapted to the environment, that is to say the same one that underlies the theory of evolution that Charles Darwin formulated and that combines this idea of ​​evolution with the genetics.

But of course, how is this implemented with mathematical formulas? So what you do is transform the resolution of any problem into a set of solutions in which each of them works as if it were an individual. You approach the problems in a way that you can say, this set of solutions is like a population, a population of solutions. Imagine that your problem to solve is that you want to know which is the shortest way to go from Madrid to St. Petersburg and you have thousands of solutions. Every path you find could be an option, if you apply a genetic algorithm, each path you find would be an individual. To apply algorithms You must be able to convert the solutions to your problem into mathematical vectors, so a vector to go from here to Saint Petersburg can be one that lists the cities you are going through. There can be many routes: some longer and others shorter, some will have more traffic, others will have less traffic …

The genetic algorithms have as starting point a set of random solutions. If we continue with the example of St. Petersburg, I can start setting cities and I can go through Australia to go to Russia. Obviously that combination will not be very efficient but the procedure will end up discarding it. Once I have that initial set of random solutions I apply what is called a Adjustment function or objective function, which in this case is to arrive in the shortest time possible to St. Petersburg. My objective function would be the time that takes taking into account the traffic and taking into account the kilometers that I travel. This objective function serves to classify the random solutions: those that last less time are better and those that last longer are worse. Once I have classified what I do, and here comes the genetics, is to reproduce them. I reproduce the solutions, how individuals reproduce in a population, and implement the three mechanisms that intervene in the selection of species: reproduction itself, crossing and mutation.

To imitate reproduction there are different mathematical mechanisms, one of them is from the objective function, that is to say that those solutions that are better are reproduced more and therefore those that are worse will disappear; when applying the cross, you combine some solutions with others. For example, I take half of a solution that went through Australia and combine it with another solution that went through China … You go combining ensuring that they are logical and then, finally, you apply a mutation procedure in a mathematical way, because if I used to go through Sydney, I mathematically implement Sydney, for example, for any other Australian city and no longer goes through Sydney, passes through Melbourne or wherever. That would be a bit like applying the three dynamics that exist in the biological world when the species are reproduced.

Once I have applied all this, again we must calculate the objective function of the new population. I will see that some solutions will have improved and others will have worsened. Maybe it gives me solutions that take less from Madrid to St. Petersburg and others in reverse, which take a lot longer. As I re-apply the mechanism of reproduction that is based on the objective function, what happens is that it will reproduce in larger numbers the solutions that take less time and will eliminate those that take a long time. And again I apply crossbreeding and mutations among the best solutions. This is how genetic algorithms work. When you are looking to solve problems in a huge field, the enumerative procedure of going one at a time is not viable because you can have millions and millions of possible solutions. These genetic algorithms combine randomness because they start with a set of totally random solutions but then they are also directed because they seek the most optimal result. And thanks to that you find very efficient solutions in very little computing time.

Laura Núñez She is a PhD in Economics, Professor of Finance at the IE Business School, IE University.

Question done via email by Myriam García Sánchez

We respond is a weekly scientific office, sponsored by the Dr. Antoni Esteve Foundation, which answers readers' doubts about science and technology. They are scientists and technologists, members of AMIT (Association of Women Researchers and Technologists), those that answer those doubts. Send your questions to us [email protected] or Twitter #nosotrasresponder.

Coordination and writing: Victoria Toro