In this workbook we gonna implement a Genetic Algorithm to find a good solution (can be different to the optimal one) to the Traveling Salesman Problem.

This problem is well known as it is a part of the NP-Complet Problem in in combinatorial optimization and theoretical computer science.

The principle is simple :

*Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once?*

To do so, we can think about creating all combinations on path, calculate every distances and keep the shortest one. The issue with this solution is the combinatory explosion. For example, if you consider only 70 cities, you have :

$$\begin{eqnarray} Nb_{path} &=& Nb_{cities}! => 1.19 * 10^{100} \text{ with 70 cities} \end{eqnarray}$$If we consider a computer able to run 1 000 000 paths par seconds, you will need 3.8 * 10^86 years ... Impossible

One good solution in such cases is to go for Genetic Algorithms

To know more how it works you can take a look to this webpage.

Now let's code it ! (For information, a version with an OpenGL visualization is available on my github)

In [1]:

```
import random
import math
import matplotlib.pyplot as plt
%matplotlib inline
```

For this problem, we can considere a mutation as the swap of 2 points. We cannot exchange only a point by another one as all points must be only once in the path. Also for the crossover, usually we should keep the beginning of one element of the population and finish with the end of another one. The invert is done on the other element. Unfortunately, this cannot be done as simply in this example for the same reason (we cannot go twice in the same city or no go in one). So for this we only cut the fist element and fill the end with non visited cities in the order of the second list. for e.g. :

A = [2, 4, 5, 3, 1]

B = [1, 5, 4, 3, 2]

if we cut A at position 3, we have :

A = [2, 4, 5] + [1, 3] as 1 is before 3 in B and both are not in A[:3]

In [2]:

```
class Individu:
def __init__(self, P):
self.path = P
self.score = 0
self.set_score()
def set_score(self):
for i in range(len(self.path) - 1):
self.score += math.pow(self.path[i+1][0] - self.path[i][0], 2) + \
math.pow(self.path[i+1][1] - self.path[i][1], 2)
def __repr__(self):
return "{} - {}".format(self.path, self.fitness)
def mutate(self):
a = random.randrange(len(self.path))
b = random.randrange(len(self.path))
new_path = self.path[:]
new_path[a], new_path[b] = new_path[b], new_path[a]
return [Individu(new_path)]
def cross_over(self, other):
a = random.randrange(len(self.path))
b = random.randrange(len(self.path))
if a != b :
start = min(a, b)
end = max(a, b)
else:
start = 0
end = len(self.path) // 2
new1 = self.path[start:end]
new2 = self.path[:start] + self.path[end:]
for each in other.path:
if each not in new1:
new1 += [each]
for each in self.path:
if each not in new2:
new2 += [each]
return [Individu(new1), Individu(new2)]
```

Now we can setup our problem

In [3]:

```
nb_cities = 35
best_every_gen = []
w, h = 1000, 1000 #space for cities
#define genetic parameter
mutation_ratio = 5e-1
cross_ratio = 0.7
population = 100
population_list = []
```

setup the list of cities and the population

In [4]:

```
cities = [( random.randrange(w), random.randrange(h) ) for _ in range(nb_cities)]
```

In [5]:

```
for i in range(population):
random.shuffle(cities)
population_list.append(Individu(cities[:]))
```

In [6]:

```
improvement = 0
previous_best = 1e20
max_generation = 1000
current_generation = 0
while current_generation < max_generation and improvement < 100:
# ranking
population_list.sort(key = lambda x : x.score)
# Selection
to_delete = population_list[population//2:]
population_list = population_list[:population//2]
# Delete all instances not kept to free memory
for each in to_delete:
del each
# For each remaining elements, we do crossover
new_indiv = []
for elem in population_list:
if random.random() < cross_ratio and len(new_indiv) < population//2:
elem2 = random.choice(population_list)
while elem == elem2:
elem = random.choice(population_list)
new_indiv += elem.cross_over(elem2)
# and mutation
for each in population_list:
if random.random() <= mutation_ratio:
new_indiv += each.mutate()
population_list.extend(new_indiv)
best_this_generation = population_list[0].score
if best_this_generation < previous_best:
previous_best = best_this_generation
improvement += 1
best_every_gen.append((current_generation, best_this_generation))
print(current_generation, best_this_generation)
final_elem = population_list[0]
current_generation += 1
```

We can now check distances related to generations by unzipping values from best_every_gen

In [7]:

```
X, Y = zip(*best_every_gen)
print(X, "\n\n", Y)
```

In [8]:

```
plt.plot(X, Y)
plt.xlabel('Generation')
plt.ylabel('Distance')
plt.show()
```

As we stored the best element, we can also display his path between every cities.

In [9]:

```
X, Y = zip(*cities)
plt.scatter(X, Y)
for i in range(1, nb_cities):
X, Y = zip(*final_elem.path[i-1:i+1])
plt.plot(X, Y, color="red")
plt.xlabel('Generation')
plt.ylabel('Distance')
plt.show()
```