Content list:
- What are evolutionary computations?
- How does all this work?
- Are evolutionary computations carried out by humans or complex algorithms?
- So it’s got nothing to do with Darwin and the theory of evolution?
- How confident can we be about a solution? Can it be double-checked?
- Why?
- What are evolutionary computations used for?
- What are some of the famous tasks solved using evolutionary computations?
- What else?
What are evolutionary computations?
Evolutionary computations are a part of a scientific field that deals with solving complicated tasks using algorithms that are inspired by the theory of evolution. The tasks can deal with different matters, such as developing the optimal operating schedule for a number of conveyor belts that would minimize idle time. Evolutionary computations can be categorized into several types according to the kind of optimization: for instance, there’s discrete and continuous optimization, as well as multi-objective optimization, which optimizes several values at once. The theory of evolutionary computations deserves a separate mention: it studies how quickly various algorithms are able to find solutions and how difficult different tasks can be.
How does all this work?
First, a set of random solutions (“specimens”) is generated. These solutions can be far from optimal. Then, the evolutionary process begins and the solutions are modified with random changes (mutations), with some solutions cross-bred with each other, producing “offspring.” Of the resulting solutions, the “fittest” ones are picked to join the next generation and the process begins anew. A solution’s fitness refers to what must be optimized. Depending on the task, it could be time, cost, strength of signal, and so on. Usually, each next generation produces fitter solutions that are ever closer to the optimal.
Are evolutionary computations carried out by humans or complex algorithms?
Humans decide how to calculate a solution’s fitness and how the solutions should be represented on a computer. Sometimes, special mutation and crossover operators are developed that take into account the specifics of the task at hand. The actual process of finding optimal solutions usually occurs not with human involvement but with the help of an evolutionary algorithm that exists as a special piece of software. But sometimes, calculations are extremely difficult to automate. For instance, how does one give a numerical definition of the aesthetic value of a generated image or melody? In cases such as this, it is possible to use the so-called interactive evolution method: the evolutionary algorithm “asks” a human observer to assess its interim solutions. In other cases, there might be a need for chemical or physical experiments to be conducted – in that event, the algorithm will wait for researchers to produce the necessary data.
So it’s got nothing to do with Darwin and the theory of evolution?
The creators of evolutionary algorithms were inspired by the theory of evolution. Today’s evolutionary algorithms may seem very different from the original idea and employ complex mathematical methods. But at their very core, they tend to rely on the same idea as biological evolution: the survival of the fittest. The use of biological concepts in the development of new evolutionary algorithms continues even today: researchers try to assign “gender” to their solutions or make them “age.” There is also research in which the results of evolutionary computations are applied to biology. For instance, we can assess the effectiveness of gene engineering methods by analyzing the effectiveness of similar evolutionary algorithms.
How confident can we be about a solution? Can it be double-checked?
It is important to differentiate between a solution’s correctness and its effectiveness, or proximity to the optimum. It is usually not all that difficult to find a correct solution to a task that’s tackled with evolutionary algorithms. For instance, if we’re looking for the shortest route, we can always generate a random one: it would be possible to walk the route (therefore making it correct), but it might be too long. Evolutionary algorithms usually contain mechanisms that ensure the viability of solutions.
Why?
Most interesting tasks are NP-hard, meaning that, from the viewpoint of modern science, the optimal solution cannot be found in a sensible amount of time regardless of the methods used. Evolutionary algorithms bring us closer to the optimal solution. And, as a rule, the more time you give an algorithm, the closer it’ll get to perfection. In practice, there are usually specific requirements set: for instance, a solution’s fitness must be above a certain value. If the results aren’t satisfying, we can run the algorithm for a longer time and, perhaps, give it a few useful modifications.
What are evolutionary computations used for?
The range of application is very wide: evolutionary computations can come in handy whenever something needs to be optimized and are used in the industry, such as in industrial design, logistics, and control, as well as other fields of science: bioinformatics, medicine, robotics, and machine learning (for example, to generate neural network structures). An active branch of the field of evolutionary computation is the so-called search-based software engineering, which deals with automated generation, modification, and testing of software code. Evolutionary computations may also be used to create art objects and generate levels or characters for video games.
What are some of the famous tasks solved using evolutionary computations?
One such example is an antenna developed by NASA using an evolutionary algorithm. The task was to develop an antenna structure in order to make it deliver signals better. At first, the researchers attempted to solve it using exact methods, but only an evolutionary algorithm was able to find the best shape – a rather peculiar one in appearance and one that couldn’t be designed by engineers.
What else?
It’s also worth mentioning that ideas from the field of evolutionary computations were used to improve upon the Lin-Kernighan-Helsgaun heuristic – today’s best algorithm that solves the traveling salesman problem, which centers on finding the optimal route between a multitude of points on a map. Commonplace in optimization theory, this problem also has great significance in logistics.
