Evolutionary Algorithm (Travelling Salesman Problem)

A while ago I started to learn about neural networks and artificial intelligence.

The neural network worked very well in recognizing letters. My only problem was that I wanted something that optimizes itself without labeled data and a known solution.

This was the point I started reading about evolutionary algorithms. They are very useful for optimization problems as they evaluate their output and (hopefully) improve with every generation. This avoids the need for labeled data which is often used in neural networks. But it doesn't mean that you can't combine both.

First of all, I want to explain our optimization problem which is called the "Travelling Salesman Problem".

Imagine having 3 cities in your country. Then try to find the shortest route to connect them. This won't be a big problem even if you have to calculate the distances by hand. But If you increase the number of cities you come to the point where you can only use a computer to find the shortest route. At some point, the number of cities leads to a problem that can't be solved in our lifetime even with the fastest computers.

Just imagine finding the shortest path when connecting the points in the plot. There are ten dots but there are already so many options that it's impossible without a computer.

As we can't find the fastest route we want at least the fastest route we can find. And here comes the evolutionary algorithm which will be explained in the next section.

An evolutionary algorithm works like the evolutionary process we see in nature.

If we have a generation in a species it will have a set of behaviors and a physical appearance. But although they are all the same species they have few differences due to mutations. The next generation of the same species will be better fitted to the environment as only the best fitted will survive and propagate. This means that only performance-increasing mutations will propagate in nature.

Although this description is simplified it gives us an image of how an evolutionary algorithm works. You start with a generation that has a random set of behaviors. Then you pick the best-fitted ones and combine them with the hope that the best behaviors of each combine and make them stronger than the last generation. After the reproduction step, it is possible to add a random mutation which will be left out in my program. A mutation can improve our program but also adds difficulty which won't help this example.

The main point is that we can use this type of algorithm to find a good way to connect a large number of cities with a route as short as possible. It would be lucky to find the shortest route because it's most likely to drop in a local minimum.

In this step theory and MatLab code come together. This is my main Program but I also wrote a few functions to structure everything. The functions contain some very special MatLab functions which are necessary but they won't help to understand the characteristics of an evolutionary algorithm. This is why they are left out at this point.

All program files are attached at the end of this section (including all additional functions).

Define the number of cities:

n_cities = 10;

Give every city a random coordinate (I combined them to have both coordinates in one Matrix):

• coordinates are random between 0 and 10

%a = randi([0 10],1,n_cities);
%b = randi([0 10],1,n_cities);
cities = [a;b]

Set the number of individuals, parents and generations:

• individuals: The number of different routes which are created
• parents: 2 Parents combine to one new individual
• generations: how often the strongest individuals (parents) propagate
• All of them are variables!

individuals = 120;
parents = 10;
generations = 50;

Plot all cities in a coordinate system and add a grid:

plot(cities(1,:), cities(2,:), "o")
xlim([0 10])
ylim([0 10])
grid on

Preallocate the storage space for the routes:

• Increases the performance

route = zeros(individuals,length(cities));

Create for every individual a random path:

• First element equals first city
• Secone element equals second city
• ...

for i=1:individuals
route(i,:) = randperm(length(cities));
end

Preallocate the storage space for the distance of every individual:

s = zeros(generations,1);

Start of the for-loop which loops through the generations:

for x=1:generations

The function "dist()" calculates the distances for every route/individual we have:

• cities: gives the cities coordinates
• route: To calculate the distance we need the route / order in which the cities are visited
• individuals: gives the expected number of distances (interesting when looping through the "route")

dis = dist(cities,route,individuals);

For every generation we sort our distances in descending order and take the first element (the shortest) and save it in s(x):

• x in s(x) comes from the for loop (2) lines of code about this one

shortest = sort(dis,"descend");
s(x) = shortest(1);

In this step we determine the fitness of every individual and we find the weakest individuals:

[val, ind, weak] = fitness(dis,parents);

Recombination:

• give the strongest individuals combine them and say how many new individuals you want to have (parents/2)
• In this step we take two individuals and combine them without doubling numbers.
• Example: route1 = [1 3 4 2] and route2 = [4 3 1 2] combine to [1 3 4 2]
• First, take the first half of route1 and then fill up the missing elements with the numbers from route2 without sorting.

new = recom(route(ind,:), cities, parents/2);

With every generation, we create a defined number of new individuals. This would lead to a constantly increasing population. To avoid this behavior we remove every generation as much weak individuals as we create new individuals.

route(weak,:) = [];

To finish the circle of evolution we add our new individuals to the existing population:

route = [route;new];

Here ends the for loop

end

This plot shows all cities in a coordinate System. In addition to that, the fastest route is plotted. With the fastest I don't mean the absolute fastest route but the fastest our algorithm was able to find.

plot(s)
grid on
s = plot(cities(1,:),cities(2,:),"o")
hold on
plot(cities(1,route(individuals,:)), cities(2,route(individuals,:)))
plot(cities(1,1), cities(2,1),"ro")

for i=1:n_cities
text(a(i)+0.3,b(i)+0.3,num2str(i))

end
hold off

Below the last plot, the order of visits can be checked:

direction = route(individuals,:)

After playing around with the parameters (individuals, generations, and parents) we can see different graphs for our fastest individual per generation.

The left picture clearly shows a continuous decreasing distance and it seems like we simply don't have enough generations. But what would have happened if we increased the number of generations? Probably the right image would be the result. At a specific generation, it seems like we found the fastest route.

The problem is that we will never know. It is more likely that we dropped into a local minimum. This is no problem because we still decreased our travel distance compared to our first random route.

A random mutation could prevent from dropping in local minimums but at some point, we won't be able to find a faster route. Even if we restart our program ten times with the same city positions we get different results every time but they are all close to the same value. This is one more reason to expect that we ended in a local minimum.

All in all the algorithm shows its strength. The traveling distance decreases with nearly every evolution. But we should not forget that there is still room for improvement. It's possible to add functions like the mutation and to look for the best parameter combination (generations, individuals,...).