top of page

Evolutionary Algorithm: A Nature-Inspired AI Technique

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!


Travel destinations of the Travelling Salesman Problem, labelled with the distance between them.

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!


Related Posts

See All

Comments


bottom of page