from jyquickhelper import add_notebook_menu
add_notebook_menu()
%matplotlib inline
On part d'un ensemble de villes aléatoires.
import numpy
import matplotlib.pyplot as plt
villes = numpy.random.rand(20, 2)
plt.plot(villes[:, 0], villes[:, 1], 'b-o')
plt.plot([villes[0, 0], villes[-1, 0]],
[villes[0, 1], villes[-1, 1]], 'b-o');
Choisir les deux villes les plus proches, les relier, recommencer, puis... vous trouverez bien quelque chose pour finir.
On redessine le parcours entre les villes.
plt.plot(villes[:, 0], villes[:, 1], 'b-o')
plt.plot([villes[0, 0], villes[-1, 0]],
[villes[0, 1], villes[-1, 1]], 'b-o');
La première étape consiste à calculer la distance d'un chemin passant par toutes les villes.
def distance_ville(v1, v2):
return numpy.sum((v1 - v2) ** 2) ** 0.5
def distance_tour(villes, permutation):
tour = distance_ville(villes[permutation[0]],
villes[permutation[-1]])
for i in range(0, len(permutation) - 1):
tour += distance_ville(villes[permutation[i]],
villes[permutation[i + 1]])
return tour
distance_tour(villes, list(range(villes.shape[0])))
9.978361909201357
Ensuite, pour voir la solution, on insère le code qui permet de dessiner le chemin dans une fonction.
def dessine_tour(villes, perm):
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
ax.plot(villes[perm, 0], villes[perm, 1], 'b-o')
ax.plot([villes[perm[0], 0], villes[perm[-1], 0]],
[villes[perm[0], 1], villes[perm[-1], 1]], 'b-o')
ax.set_title("dist=%f" % distance_tour(villes, perm))
return ax
perm = list(range(villes.shape[0]))
dessine_tour(villes, perm);
On rédige l'algorithme.
def ameliore_tour(villes, perm=None):
# On copie la permutation perm pour éviter de modifier celle
# transmise à la fonction. Si la permutation est vide,
# on lui affecte la permutation identique.
perm = (perm.copy() if perm is not None
else list(range(villes.shape[0])))
# On calcule la distance actuelle.
dist_min = distance_tour(villes, perm)
# Initialisation.
cont = True
nb_perm, nb_iter = 0, 0
# Tant que la distance n'est pas améliorée dans les dernières
# len(perm) itérations.
while cont or nb_iter < len(perm):
nb_iter += 1
# On tire deux villes au hasard.
a = numpy.random.randint(0, len(perm) - 2)
b = numpy.random.randint(a + 1, len(perm) - 1)
# On permute les villes.
perm[a], perm[b] = perm[b], perm[a]
# On calcule la nouvelle distance.
dist = distance_tour(villes, perm)
# Si elle est meilleure...
if dist < dist_min:
# On la garde.
dist_min = dist
cont = True
nb_perm += 1
nb_iter = 0
else:
# Sinon, on annule la modification.
perm[a], perm[b] = perm[b], perm[a]
cont = False
return dist_min, nb_perm, perm
dist, nb_perm, perm = ameliore_tour(villes)
print("nb perm", nb_perm)
dessine_tour(villes, perm);
nb perm 10
C'est pas extraordinaire.
Lorsque deux segments du chemin se croisent, il est possible de construire un autre chemin plus court en retournant une partie du chemin.
def ameliore_tour_renversement(villes, perm=None):
perm = (perm.copy() if perm is not None
else list(range(villes.shape[0])))
dist_min = distance_tour(villes, perm)
cont = True
nb_perm, nb_iter = 0, 0
while cont or nb_iter < len(perm) ** 2:
nb_iter += 1
# Une partie qui change. On fait une copie de la permutation.
p0 = perm.copy()
a = numpy.random.randint(0, len(perm) - 2)
b = numpy.random.randint(a + 1, len(perm) - 1)
# On retourne une partie de cette permutation.
if a == 0:
perm[0:b] = perm[b:0:-1]
perm[b] = p0[0]
else:
perm[a:b+1] = perm[b:a-1:-1]
# La suite est quasi-identique.
dist = distance_tour(villes, perm)
if dist < dist_min:
dist_min = dist
cont = True
nb_perm += 1
nb_iter = 0
else:
# On reprend la copie. C'est plus simple
# que de faire le retournement inverse.
perm = p0
cont = False
return dist_min, nb_perm, perm
dist, nb_perm, perm = ameliore_tour_renversement(villes)
print("nb perm", nb_perm)
dessine_tour(villes, perm);
nb perm 25
Il n'y a plus de croisements, ce qui est l'effet recherché.
On pourrait combiner ces deux fonctions pour améliorer l'algorithme qui resterait sans doute très long pour un grand nombre de villes. On pourrait initialiser l'algorithme avec une permutation moins aléatoire pour accélérer la convergence. Pour ce faire, on regroupe les deux villes les plus proches, puis de proche en proche...
from scipy.spatial.distance import cdist
def build_permutation(villes):
pairs = cdist(villes, villes)
max_dist = pairs.ravel().max()
for i in range(villes.shape[0]):
pairs[i, i] = max_dist
arg = numpy.argmin(pairs, axis=1)
arg_dist = [(pairs[i, arg[i]], i, arg[i]) for i in range(villes.shape[0])]
mn = min(arg_dist)
perm = list(mn[1:])
pairs[perm[0], :] = max_dist
pairs[:, perm[0]] = max_dist
while len(perm) < villes.shape[0]:
last = perm[-1]
arg = numpy.argmin(pairs[last:last+1])
perm.append(arg)
pairs[perm[-2], :] = max_dist
pairs[:, perm[-2]] = max_dist
return perm
perm = build_permutation(villes)
dessine_tour(villes, perm);
Pas si mal... Il reste un croisement. On applique la fonction de la question précédente.
dist, nb_perm, perm = ameliore_tour_renversement(villes, perm)
print("nb perm", nb_perm)
dessine_tour(villes, perm);
nb perm 3
Ce n'est pas nécessairement le meilleur chemin mais ça va plus vite.