In [12]:
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.pylab import rcParams  # pour fixer la taille des graphiques
rcParams['figure.figsize'] = 5,5
In [13]:
N = 50 # nombre de villes
In [14]:
# Configuration Villes aléatoire

villes_alea = np.array(np.random.randn(N,N))  #tableau 2xN dont chaque colonne est une ville
In [15]:
# Configuration Villes en cercle

Xcirc = np.cos((2*np.pi/N)*np.arange(N))
Ycirc = np.sin((2*np.pi/N)*np.arange(N))
villes_cercle = np.array([Xcirc,Ycirc])
In [16]:
# Configuration Villes grille

M = int(round(np.sqrt(N)))
N = M**2
Xgrid = np.array(list(range(M))*M)
Ygrid = []
for j in range(M):
    Ygrid += [j] * M  
Ygrid = np.array(Ygrid)
villes_grille = np.array([Xgrid,Ygrid])
In [17]:
# Vecteur des distances ; villes = tableau 2xN dont chaque colonne représente les coordonnées d'une ville

def distances(villes):
    Dist = []
    for i in range(N):
        ligne_i = []
        for j in range(N):
            ligne_i.append(np.linalg.norm(villes[:,i]-villes[:,j]))
        Dist.append(ligne_i)
    return(Dist)
    
    
# Energie d'une permutation x (= tableau de nombres entre 0 et N-1) de N villes à distance "Dist"

def energie(x,Dist): 
    s = 0
    for i in range(N):
        s += Dist[x[i]][x[i-1]]
    return s


def rho(i,k,beta,x,Dist):  # permutation obtenue de x après inversion complète entre x[i] et x[k]
    EcartEnergie = Dist[x[i-1]][x[k]] + Dist[x[i]][x[(k+1)%N]] - Dist[x[i-1]][x[i]] - Dist[x[k]][x[(k+1)%N]]
    return np.exp(-beta*EcartEnergie) 


def transition(beta,x,Dist):
    (i,k) = np.sort(np.random.choice(N, size=2, replace=False))
    y = x.copy()
    if np.random.rand() < rho(i,k,beta,x,Dist):
        for j in range(i,k+1):
            y[j] = x[k+i-j]
    return y
In [18]:
def RecuitSimule(Nstep,c,villes):
    x = np.random.permutation(N) 
    Dist = distances(villes)
    energies = [energie(x,Dist)]

    for t in range(Nstep):
        x = transition(c*np.log(t+2),x,Dist)
        energies.append(energie(x,Dist))
    return(x,energies)
In [19]:
# Illustration configuration initiale

def PlotConfigInit(villes):
    Xvilles = villes[0]
    Yvilles = villes[1]
    
    x = np.random.permutation(N)
    
    plt.figure()
    plt.plot(Xvilles,Yvilles,"b.")
    X_itineraire = [Xvilles[x[i]] for i in range(N)] + [Xvilles[x[0]]]
    Y_itineraire = [Yvilles[x[i]] for i in range(N)] + [Yvilles[x[0]]]
    plt.plot(X_itineraire,Y_itineraire,"r")
    plt.title("Trajet initial")
    plt.show()
In [20]:
PlotConfigInit(villes_grille)
In [21]:
# Illustration configuration finale

def PlotConfigFinale(Nstep,c,villes):
    Xvilles = villes[0]
    Yvilles = villes[1]
    
    x = RecuitSimule(Nstep,c,villes)[0]
    
    plt.figure()    
    plt.plot(Xvilles,Yvilles,"b.")
    X_itineraire = [Xvilles[x[i]] for i in range(N)] + [Xvilles[x[0]]]
    Y_itineraire = [Yvilles[x[i]] for i in range(N)] + [Yvilles[x[0]]]
    plt.plot(X_itineraire,Y_itineraire,"r")
    plt.title("Trajet final")
    plt.show()
In [25]:
Nstep = int(1e5) 

PlotConfigFinale(Nstep,1,villes_grille)
In [27]:
# Décroissance de l'énergie

Nstep = int(1e5)
villes = villes_grille
c = 1  

Energies = RecuitSimule(Nstep,c,villes)[1]

plt.figure()
plt.plot(range(Nstep+1),Energies)
plt.title("Itérations")
plt.ylim((0,max(Energies)))
plt.show()
In [ ]:
In [ ]: