What Is Evolutionary Computation?

Evolutionary computation (EC from now on) is a branch of Artificial Intelligence used to solve combinatorial optimization problems. EC is inspired by the biological evolution mechanisms proposed by Darwin, Mendel and Lamarck. Without going into much detail about these scientists’ studies, we will just briefly mention what they proposed. Darwin proposed the "Natural selection of the fittest", Mendel proposed the "Particulate theory of inheritance" and Lamarck proposed the "Inheritance of acquired characteristics".

As many of you probably know, the main problem with artificial intelligence is that it has no easy or formal definition, but to keep it simple we can say that artificial intelligence is a branch that tries to "imitate" natural intelligence, and therefore evolutionary computation is based on imitating biological evolution as we understand it today. As you can guess, EC tries to solve combinatorial optimization problems in order to find the best result to the problem, just like what happens in nature, where the big problem, especially in the animal world, is survival: only the strongest and best adapted to the environment are able to survive and reproduce; in other words, they are the best possible individuals, or the best solution to the problem.

Although we could "get really fancy", evolutionary computation is based on the following metaphor, called the evolutionary metaphor:

• A population of individuals coexists in a given environment with limited resources.
• Competition for resources causes the selection of those individuals that are best adapted to the environment.
• These individuals become the parents of new individuals through mutation and recombination processes.
• The new individuals then compete for survival.
• Over time, this natural selection increases the “quality” of the individuals in the population.

Evolutionary computation includes several strategies for solving optimization problems. These strategies are the following:

1. Evolutionary Search Processes: Proposed by Alan Turing in 1948.
2. Evolution Strategies (ES): Proposed by Rechenberg in 1964. They represent individuals with real-valued vectors.
3. Evolutionary Programming (EP): Proposed by Fogel in 1965. They use finite state machines.
4. Genetic Algorithms (GA): Proposed by Holland in 1975. They represent individuals as binary strings.
5. Genetic Programming (GP): Proposed by Koza in 1992. They use LISP trees.

We can say that the difference between these evolutionary algorithms is the way they represent individuals. In fact, the difference between them is mostly irrelevant, since conceptually they all do the same thing with different ways of representing individuals. So when using evolutionary algorithms, the best approach is to choose the most suitable representation and the most suitable variation operators for the problem you have to solve.

The general scheme of an evolutionary algorithm is shown in the following image:

Below is the pseudocode of an evolutionary algorithm:

BEGIN
INICIALIZAR de forma aleatoria una población con soluciones candidatas EVALUAR cada candidato
REPEAT UNTIL ( CONDICIÓN DE TERMINACIÓN == true )
1. SELECCIONAR progenitores
2. RECOMBINAR progenitores seleccionados obteniendo descendencia 
3. MUTAR descendencia
4. EVALUAR nuevos candidatos
5. SELECCIONAR individuos para la próxima generación
END REPEAT 
END

So far we have seen, in broad strokes, what EC is based on and the pseudocode of evolutionary algorithms, but how do we represent individuals? How do individuals reproduce and mutate? And what does it mean for an "individual to be good enough"? Let’s answer these questions:

How do we represent individuals?

Based on human knowledge and simplifying a bit, we can say that each person has unique genetic information that can be seen in each person’s DNA. This DNA is made up of 4 types of "elements": "Adenine" (A), "Thymine" (T), "Cytosine" (C) and "Guanine" (G). So, simplifying a lot, we can say that people are represented by an "ARRAY" made up of some of these 4 "elements", and with that we already have a way (or data structure) to represent individuals. Applied to a combinatorial optimization problem, this means that a possible result of the problem can be turned into an array (for example, a binary array of zeros and ones) to which we give a certain meaning. This array that represents an individual of the problem, or a possible solution, is called a Chromosome.

How do individuals reproduce and mutate?

Continuing with the simplifications, we can say that reproduction is nothing more than creating a new individual from two given individuals, that is, combining the two arrays that represent them. Below is an example of how we get a new individual from two:

In broad strokes, this is how human reproduction works, since when we are born we inherit some characteristics from our mother and others from our father. As you can see, the characteristics of both parents don’t have to be inherited in equal parts.

Finally, regarding the generation of new individuals, there is a chance that some gene "mutates"; that is, that for no apparent "logic" (although I suppose biologically there is one) a certain element of the chromosome changes its value, for example to the complementary value:

What does it mean for an "individual to be good enough"?

As mentioned, evolutionary algorithms are used to solve combinatorial optimization problems, but they don’t always reach the best solution. So we have to define a threshold from which we consider the solution we are looking for to be good enough. This threshold must be obtained from an "evaluation function" that has to be defined whenever evolutionary algorithms are used. This evaluation function is known as the "Fitness Function", although it is also commonly called the quality function, aptitude function or objective function.

As I was saying, this fitness function evaluates how good or bad an individual (or possible solution to the problem) is. With this function we can use two strategies to obtain the best solution to the problem, depending on how much we know about the problem:

1. If we don’t have much idea of what solution the problem will give us, we let the evolutionary algorithm run until it completes 'N' generations; at generation 'N' we evaluate all the individuals with the fitness function and take as the solution the individual that gave the best fitness result.
2. The second strategy is used when we know the quality threshold we want to reach for the solution. In this case, generations are run (one by one) and after each generation all the individuals are evaluated with the fitness function; if any of them meets a given quality threshold, the algorithm stops running, since it has reached a good solution.

Summary and Comments on Evolutionary Computation

Up to this point we have tried to explain (in broad strokes) what Evolutionary Computation is at a theoretical level. EC is a very interesting branch of artificial intelligence (especially for those of us who like artificial intelligence), but it must also be made very clear that it is not "the panacea" and that EC should not be applied to just any problem, since EC doesn’t give the best possible result to a problem, although it can give a good or "decent" result for certain problems we have no clue about. What I mean is that when solving a problem you have to analyze it well and see how the best solutions can be reached. There are algorithms like Backtracking (which many of us have suffered through 😉 ) that give the best solution to a combinatorial optimization problem as long as the problem has a "tractable and finite" search space, and in those cases it is better to use that algorithm than an evolutionary one. If the problem had so much data that Backtracking couldn’t give us results in a "reasonable" time, then you could use evolutionary algorithms.

Another misuse I have come across is using genetic algorithms to find the minimum of a given function. To solve that problem it is as simple as differentiating the function and setting it equal to zero to obtain its minimum. I mention this example because in many places you find "didactic examples" of how to get the minimum of a function with evolutionary algorithms, and indeed the best way to understand an evolutionary algorithm is by solving this kind of problem, which is why they are "didactic examples", but they are not efficient examples, so be careful when using these algorithms.

Later on we will present an example of how to solve a specific problem with genetic algorithms and look closely at its execution.

Bibliography

Part of the information shown in this post was obtained from notes taken in the "Intelligent Systems" course, taught in the third year of the Computer Engineering degree at the Escuela Universitaria de Informática of the UPM by professor Angel Arroyo, and from the "Artificial Intelligence" course, taught in the second year by professors Jesus Bernal and Jesus Bobadilla.