There are many areas of artificial intelligence that are inspired by biological processes. In this article, we will focus on the evolutionary algorithm (EA) which is one of them. This powerful technique can be beneficial in various problems, for example, optimization or even designing electronic circuits, which makes it worth learning about.
First, we will briefly cover a part of biological evolution that is essential to understanding EA. After looking at EA in more detail, we will solve the Travelling Salesman Problem at the end, so let’s get started!
inspiration from Biological evolution
Natural evolution is the underlying mechanism of EA with changing population through selection, mutation and reproduction. The ultimate goal is to produce better and better instances in subsequent populations.
Darwin’s theory of evolution consists of 4 principles:
Variation - Individuals in a population differ from each other in their genetic material which is known as the genotype.
Inheritance – Individuals can transmit their characteristics to offspring through reproduction.
Selection – There is a selection mechanism that controls which individuals are able to reproduce. The better capabilities they hold, the higher chances of survival or reproduction they have.
Time – Progress plays a key role because individuals tend to become better through time.
Artificial evolution
Artificial evolution systems start with an initial population of individuals, where their phenotypes are the different random solutions to the given problem.
The way how these individuals are genetically represented, which is called the genotype, can take many forms depending on the problem. In each round, the individuals of the current population are evaluated and the best ones are selected. The genotypes of the selected individuals are modified at this point by different genetic operators. With this, new individuals are created, then evaluated again and the best ones are selected to generate offspring and so on. This cycle continues for a fixed number of generations.
Initial population
The initial population has to be diverse and large enough to get the selection mechanism to work properly.
Genetic representation
Discrete
Binary alphabet with 0 and 1: e.g. <101100>
Genotypes using binary representation can be configuration strings, job schedules with morning and afternoon shifts or consider for example the Knapsack Problem, where we want to maximize the knapsack capacity with the most valuable items. In this case, each bit can be viewed as an item and 1 means we include it, and 0 if we left it behind. In the following example Item 1, 3 and 4 are selected.
Items in the knapsack problem | Item 1 | Item 2 | Item 3 | Item 4 | Item 5 | Item 6 |
|---|---|---|---|---|---|---|
Binary representation | 1 | 0 | 1 | 1 | 0 | 0 |
Include the item? | yes | no | yes | yes | no | no |
Alphabet: e.g. <ACABBA>, <ABDCFE>
Using the alphabet can also describe job schedules. For instance, there are three time slots that are represented by different letters (time slot A, B and C), and six different jobs have to be scheduled in one of them.
Jobs | Job 1 | Job 2 | Job 3 | Job 4 | Job 5 | Job 6 |
|---|---|---|---|---|---|---|
Scheduled time slot | A | C | A | B | B | A |
It can formulate a sequence as well, like in the Traveling Salesman Problem, where the task is to visit all cities with the least possible path length. In the case of six locations, each of them can be represented by a letter from A to F and their positions show the order of the visit.
Order of visit | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
Schedule | City A | City B | City D | City C | City F | City E |
Real-valued: e.g. <32.15 62.5 11.23 8.2>
Real-valued representation can be used in the case of high-precision parameter optimization to get the desired shape of a wing or describe parameters of components such as resistors in an analog circuit.
Parameters of a wing | Parameter 1 | Parameter 2 | Parameter 3 | Parameter 4 |
|---|---|---|---|---|
Values | 32.15 | 62.5 | 11.23 | 8.2 |
Tree-based
These kind of genotypes are able to represent hierarchical structures and are used in genetic programming. This genetic representation below means min(x1+x2, x3/x4).
Evaluation
The fitness function evaluates and scores the phenotype of each individual in the population. Its score is called the fitness value.
Selection
Through selection, the best individuals have higher chances to create offspring for the next generation. In the following, we present four types of selection procedures.
Roulette wheel
The reproduction probability of an individual is determined by the ratio of its fitness value and the sum of all fitness values in the population:
where f(i) is the fitness value of the i-th individual and N is the population size.
Individuals | Indiv. 1 | Indiv. 2 | Indiv. 3 | Indiv. 4 | Indiv. 5 | Indiv. 6 |
|---|---|---|---|---|---|---|
Fitness value f(i) | 3.2 | 8.2 | 1.4 | 1.2 | 0.5 | 1.6 |
Reproduction probability p(i) | 0.20 | 0.51 | 0.09 | 0.07 | 0.03 | 0.10 |
This data can be visualized as a roulette wheel, where each slot corresponds to an individual and the slot size is proportional to the reproduction probability of the individual. An individual is selected if the ball ends up in its slot by spinning the wheel. Thus, individuals with bigger slots have higher chances to get selected. To create a population of size N, this process is repeated N times. Therefore, the expected number of offspring for the i-th individual is N*p(i). For example, this number in the case of Individual 1 is 6*0.20 = 1.2, because the population size is 6 and its reproduction probability is 20%. This means that it will create at least one offspring in expectation.
Rank-based selection
Instead of using fitness values directly, rank-based selection ranks all individuals from best to worst and calculates the reproductive probability accordingly.
Individuals | Indiv. 1 | Indiv. 2 | Indiv. 3 | Indiv. 4 | Indiv. 5 | Indiv. 6 |
|---|---|---|---|---|---|---|
Fitness value f(i) | 3.2 | 8.2 | 1.4 | 1.2 | 0.5 | 1.6 |
Rank | 5 | 6 | 3 | 2 | 1 | 4 |
Reproduction probability p(i) | 0.24 | 0.29 | 0.14 | 0.09 | 0.05 | 0.19 |
For instance, Individual 2 is the best in the population and therefore has the highest rank. Its reproduction probability is calculated by dividing its rank by the sum of ranks, which is 21 (1+2+3+...+6=21). This gives 0.29, which is much less than in the previous example. This kind of ranking makes the differences between individuals more balanced. It is worth comparing the following graph with the previous one.
Truncated rank-based selection
This is a variant of rank-based selection that takes only the best k individuals that produce the same number of offspring. For example, from a population of size 6, the top 3 individuals produce 2-2 offspring to create a new population of the same size.
Tournament selection
In this mechanism, a tournament is organized between k randomly selected individuals. The one with the highest fitness value produces offspring. These participants are put back and can be selected in the next round of the competition.
Tournaments | Tournament 1 | ... | Tournament 6 |
|---|---|---|---|
Randomly selected group of size k=3 | Individual 2, f(2)=8.2 Individual 4, f(4)=1.2 Individual 5, f(5)=0.5 | ... | Individual 1, f(1)=3.2 Individual 5, f(5)=0.5 Individual 6, f(6)=1.6 |
Best in the tournament | Individual 2 | ... | Individual 1 |
Genetic operators
Special operators can modify the genetic representations of individuals.
Crossover
One-point crossover:
A crossover point is randomly selected and the genetic material is exchanged around this point. This can be applied in discrete and real-valued representations.
Individual 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
Individual 2 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
Offspring 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
Offspring 2 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
Multipoint crossover:
It is one-point crossover extended to multiple crossover points where the genetic material is swapped between these points.
Individual 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
Individual 2 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
Offspring 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
Offspring 2 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
Uniform crossover:
The genetic content is exchanged in k random positions.
Individual 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
Individual 2 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
Positions | x | | | | x | | x | |
Offspring 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
Offspring 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
Arithmetic crossover:
This takes the average of k random positions of genotypes. Alternative variants use different weights to calculate new gene values.
Individual 1 | 2.6 | 1.5 | 0.4 | 3.2 | 0.8 | 1.0 | 3.8 | 2.2 |
Individual 2 | 1.2 | 1.8 | 0.6 | 2.6 | 1.2 | 0.2 | 2.5 | 0.8 |
Positions | | | x | | | x | x | |
Offspring 1 | 2.6 | 1.5 | 0.5 | 3.2 | 0.8 | 0.6 | 3.15 | 2.2 |
Offspring 2 | 1.2 | 1.8 | 0.5 | 2.6 | 1.2 | 0.6 | 3.15 | 0.8 |
Using crossover operator for sequences
If the genetic material is a sequence, such as in the Travelling Salesman Problem, then the genotype modified by the crossover operator must contain all the symbols that are part of the problem. For example, in the case of multi-point crossover, a simple unconstrained application of the operator can result in an invalid offspring in which some cities are visited more than once (A and E) and some are completely absent (C and G). The correct way to apply multi-point crossover in sequences is to first copy the genes between the crossover points from one individual (Individual 1: H, A, E, F) and then fill in the remaining gaps with genes from the other individual in the same order as they appear in its genotype (Individual 2: D, C, G, B).
Individual 1 | C | B | H | A | E | F | D | G |
Individual 2 | A | D | F | H | C | G | E | B |
Invalid offspring | A | D | H | A | E | F | E | B |
Valid offspring | D | C | H | A | E | F | G | B |
Mutation
Mutations make small random changes to the genotype. For example, changing bit values in binary representations or adding random values to certain positions in real value representations. It can also be performed in sequences where two positions are exchanged.
Before mutation | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
After mutation | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
Replacement strategies
There are two different directions in the strategy of intergenerational replacement. While generational replacement completely puts the new offspring in place of the old generation, elitism keeps the best k individuals of the previous population and replaces only the remaining number of individuals.
Travelling Salesman Problem
After the overview of the different genetic representations, selection mechanisms and operators, you have enough background knowledge to solve the Travelling Salesman Problem. This problem contains a list of cities with distances between them, and the goal is to find the shortest path that visits each city only once and returns to the starting position.
Consider the following cities in Italy: Turin, Milan, Genoa, Venice, Bologna and Florence. Our task is to create the shortest tour with the conditions described above. Let's take a step-by-step approach to the problem!
1. Genetic representation
First, we need to determine the genetic representation of routes. The simplest way to formulate this problem is to create a sequence of symbols of the alphabet:
A=Turin, B=Milan, C=Genoa, D=Venice, E=Bologna, F=Florence
It is also important to use a representation that can be evaluated by the fitness function. E.g.: <ABCDEF> genotype means the route from Turin to Milan, Genova, Venice, Bologna and finally Florence. Its score is 125+120+290+130+80+320=1065 (with returning from Florence from Turin).
2. Initial population
The size of the population depends on the complexity of the problem. A population of size 6 seems sufficient for this task. In the case of more cities, a larger population size is reasonable. The random initial population is as follows:
<BAEDFC>, <FACEBD>, <CADFEB>, <CEDABF>, <AFECBD>, <DECFBA>
3. Evaluation
As a next step, the individuals are evaluated by the fitness function. This function scores the distance between cities, including the distance from the last destination to the starting point.
f(<BAEDFC>) = 125+295+130+205+200+120 = 1075
f(<FACEBD>) = 320+125+190+200+245+205 = 1285
f(<CADFEB>) = 125+365+205+80+200+120 = 1095
f(<CEDABF>) = 190+130+365+125+250+200 = 1260
f(<AFECBD>) = 320+80+190+120+245+365 = 1320
f(<DECFBA>) = 130+190+200+250+125+365 = 1260
4. Selection
By applying truncated rank-based selection, the top 2 individuals in the population are selected to generate offspring. In addition, the use of elitism keeps the best ones and replaces only the rest of the population.
Top 2 individuals (with the shortest path):
<BAEDFC>, <CADFEB>
5. Genetic operators
One-point crossover generates the following offspring:
Individual 1 | B | A | E | D | F | C |
Individual 2 | C | A | D | F | E | B |
Offspring 1 | B | A | E | C | D | F |
Offspring 2 | C | A | D | B | E | F |
Offspring 3 | A | E | B | D | F | C |
Offspring 4 | A | D | C | F | E | B |
Mutation exchanges two random genes in some individuals:
Offspring 2 before mutation | C | A | D | B | E | F |
Offspring 2 after mutation | C | F | D | B | E | A |
The resulting population:
<BAEDFC>, <CADFEB>, <BAECDF>, <CFDBEA>, <AEBDFC>, <ADCFEB>
6. Repeat steps 3-5.
These individuals are expected to have better path lengths than individuals in the previous population. The best individuals are selected again and then modified by crossover and mutation. This cycle continues until a certain threshold is reached, for example 50 generations, or when new generations are not significantly different from old ones.
At the end of the process, the best individual from the last population is the solution to the problem using EA, which is:
f(<ABFEDC>) = 125+250+80+130+290+125=1000
Applications
Applications of EA include transport and schedule optimization, object shape design, analog circuit design and parameter optimization.
Suggested reading
Dario Floreano and Claudio Mattiussi: Bio-Inspired Artificial Intelligence
Conclusion
Congratulations! You now understand how the bio-inspired EA works and how it can solve the Travelling Salesman Problem.
What other kinds of problems can evolutionary algorithms solve? What would be their genetic representation? Leave a comment down below!
Comments