Scribd
Importer
33 vues2 pages

Recuit Simule

Le document présente une implémentation de l'algorithme de recuit simulé pour résoudre le problème du voyageur de commerce. Il inclut des fonctions pour calculer la distance totale d'une solution, générer une solution initiale, échanger des villes, et exécuter l'algorithme de recuit simulé avec des paramètres de température. Les données d'entrée comprennent une matrice de distances entre villes et des paramètres pour l'initialisation de l'algorithme.

Transféré par

assili oumaima
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats TXT, PDF, TXT ou lisez en ligne sur Scribd
33 vues2 pages

Recuit Simule

Le document présente une implémentation de l'algorithme de recuit simulé pour résoudre le problème du voyageur de commerce. Il inclut des fonctions pour calculer la distance totale d'une solution, générer une solution initiale, échanger des villes, et exécuter l'algorithme de recuit simulé avec des paramètres de température. Les données d'entrée comprennent une matrice de distances entre villes et des paramètres pour l'initialisation de l'algorithme.

Transféré par

assili oumaima
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats TXT, PDF, TXT ou lisez en ligne sur Scribd

import numpy as np

import random
import math

def calculer_distance_totale(solution, matrice_distances):


distance_totale = 0
for i in range(len(solution) - 1):
distance_totale += matrice_distances[solution[i]][solution[i + 1]]
distance_totale += matrice_distances[solution[-1]][solution[0]]
return distance_totale

def generer_solution_initiale(nombre_villes):
solution = list(range(nombre_villes))
[Link](solution)
return solution

def echanger_villes(solution):
# Échange deux villes dans la solution
i, j = [Link](range(len(solution)), 2)
solution[i], solution[j] = solution[j], solution[i]

def recuit_simule(matrice_distances, temperature_initiale, temperature_finale,


taux_refroidissement):
nombre_villes = len(matrice_distances)
solution_actuelle = generer_solution_initiale(nombre_villes)
distance_actuelle = calculer_distance_totale(solution_actuelle,
matrice_distances)

temperature = temperature_initiale

meilleure_solution = list(solution_actuelle)
meilleure_distance = distance_actuelle

while temperature > temperature_finale:


nouvelle_solution = list(solution_actuelle)
echanger_villes(nouvelle_solution)
distance_nouvelle = calculer_distance_totale(nouvelle_solution,
matrice_distances)

delta_distance = distance_nouvelle - distance_actuelle

if delta_distance < 0 or [Link](0, 1) < [Link](-delta_distance /


temperature):
solution_actuelle = nouvelle_solution
distance_actuelle = distance_nouvelle

if distance_actuelle < meilleure_distance:


meilleure_solution = list(solution_actuelle)
meilleure_distance = distance_actuelle

temperature *= taux_refroidissement

return meilleure_solution, meilleure_distance

# Données d'entrée
matrice_distances = [
[0, 2, 2, 7, 15, 2, 5, 7, 6, 5],
[2, 0, 10, 4, 7, 3, 7, 15, 8, 2],
[2, 10, 0, 1, 4, 3, 3, 4, 2, 3],
[7, 4, 1, 0, 2, 15, 7, 7, 5, 4],
[7, 10, 4, 2, 0, 7, 3, 2, 2, 7],
[2, 3, 3, 7, 7, 0, 1, 7, 2, 10],
[5, 7, 3, 7, 3, 1, 0, 2, 1, 3],
[7, 7, 4, 7, 2, 7, 2, 0, 1, 10],
[6, 8, 2, 5, 2, 2, 1, 1, 0, 15],
[5, 2, 3, 4, 7, 10, 3, 10, 15, 0]
]

temperature_initiale = 1000
temperature_finale = 1
taux_refroidissement = 0.95

meilleure_solution, meilleure_distance = recuit_simule(matrice_distances,


temperature_initiale, temperature_finale, taux_refroidissement)

print("Meilleure solution:", meilleure_solution)


print("Distance minimale:", meilleure_distance)

Vous aimerez peut-être aussi