Algorithms inspired by the evolution to make life easier22/07/2020
These algorithms expand the variety of options in order to generate an optimal solution by applying mechanisms of genetics, such as crossing and mutation. Credit: Geralt.
FRANCESCO RODELLA | Tungsteno
In every city in the world, thousands of drivers are confronted with a daily dose of traffic jams and long minutes waiting in front of traffic lights, a situation that generates not only pollution but also high levels of stress that affect the health of people. But reducing these annoyances is not easy; it requires the consideration of multiple factors ranging from traffic density to the frequency of traffic-light signals. One possible solution is offered by algorithms that take the evolution of living beings as a model. They are capable of reproducing a selective process in search of an optimal solution to the problem at hand. This type of computing is already being applied in many areas ranging from product distribution to financial markets.
One example of how these algorithms can help solve the headache of urban traffic is that proposed by a team of researchers from the University of Malaga, led by Professor Enrique Alba. This group has designed a system to optimise the traffic-light network of this Andalusian city and that of Paris, France, with the perspective that it will be applicable to other cities with more than 200,000 inhabitants. To achieve this, they apply defined cellular algorithms, inspired by the mechanisms of genetics. The result improves traffic flow and reduces pollution without the need for additional infrastructure and extra costs, although it does take into account multiple parameters.
By applying bio-inspired algorithms to traffic regulation, the traffic light network can be optimized by setting the most optimal frequency. Credit: Wikimedia Commons.
Applying biology to reach the most optimal solutions
Why is it necessary to resort to biology? How can this model help us? Alba explains that evolutionary algorithms are based on iterative processes: "They repeat a series of steps and in each one of them they look for a better solution than the one they had in the previous step until the most suitable one is found, in an outcome that reminds us of Charles Darwin's theory of the evolution of species." For Laura Núñez, a professor at IE Business School, "they can be successful, particularly when the size of the problem is large and it is not feasible to analyse the possible solutions one by one." In those cases, she maintains, these techniques obtain very good results in a short time.
Based on the initial variables of the problem studied, a genetic algorithm randomly develops a first generation or population of tentative solutions, the two experts explain. As the algorithm incorporates a function that allows it to classify the quality of each solution according to the final objectives of whoever designs it (for example, to reduce the frequency of stops at traffic lights, waiting times and pollution), the program will evaluate which of the solutions are more in line with the established criteria.
The algorithm will thus be able to reproduce new generations of solutions, both in accordance with this quality-based selection, and also by applying other mechanisms inherent in genetics, such as cross-breeding and mutation, which make it possible to widen the range of options and have a greater chance of generating an optimum one. "In the next generation there has to be the same number of chains [solutions], but they will have changed. Some will have crossbred, some will have mutated, and some will remain the same as before," explains Núñez. The idea, she adds, is that over generations a higher reproduction factor will be attributed to the solutions that best meet the initial needs. In the end, the less suitable ones will be discarded, while the one that comes closest to the ideal result will succeed.
The evolutionary algorithms, applied to the financial market, allow establishing the strategies that give the highest profitability with the lowest risk. Credit: Wikimedia Commons.
From smart cities to law firms
The application of evolutionary algorithms is not a science fiction scenario but is already present in many real situations, according to the experts consulted. "Can we apply them to industry 4.0, to the smart city, to bioinformatics, to the problems of the economy, to suggesting to a lawyer what to do, to translating from one language to another, to security in airports or to organising a port full of ships? The answer to all of these is yes," says Alba. According to the professor, these examples represent solutions that already exist, although he says that to develop and implement them correctly one must be a specialist in many domains, including programming, mathematical theory and statistics.
Laura Núñez explains that she has used evolutionary algorithms in the financial field, for example. In that case, she points out, what is usually sought is the strategy that gives the highest return with the least risk. Therefore, once these two parameters are determined, the system can be designed so that those strategies that give greater profitability and less risk will be reproduced more. "They will crossbreed with other strategies, mutate and, in the end, you will have a set of very good strategies," says Núñez. The solutions generated, she concludes, can suggest clues about when to buy and when to sell.
In Spain, the field of bio-inspired algorithms began to emerge in the early 1990s, says Alba. At that time, she says, very few people were working with this type of computing. Things changed in the following decade. "I remember people, researchers and companies that were very reluctant in the 1990s, but that since 2000 have generated businesses that can't live without this type of algorithm," the professor notes.
· — —
Tungsteno is a journalism laboratory to scan the essence of innovation. Devised by Materia Publicaciones Científicas for Sacyr’s blog.