Introduction
Cet article présente l'application d'un algorithme génétique (AG) pour résoudre une variante simplifiée du problème du voyageur de commerce (TSP) appliqué à la logistique de livraison. L'objectif est de déterminer l'itinéraire le plus court reliant un point de départ à plusieurs destinations, avant de revenir au point initial. Le document aborde les fondements théoriques de l'AG, détaille l'implémentation en Python et analyse les performances de l'approche.
Fondements de la méthode
Modélisation du problème TSP
Le problème TSP classique peut être formulé comme un problème d'optimisation combinatoire. Étant donné un ensemble de N nœuds (points de livraison), l'objectif est de trouver le cycle hamiltonien de coût minimum. L'espace des solutions potentielles est de taille factorielle, rendant une approche exhaustive impraticable pour des instances de taille significative.
Composants centraux de l'algorithme génétique
Représentation des solutions
Chaque solution candidate (chromosome) est encodée sous la forme d'une permutation des identifiants des points de livraison. Cette représentation garantit automatiquement la validité des itinéraires (chaque visite unique).
Fonction d'évaluation (Fitness)
La qualité d'une solution est évaluée par la fonction d'aptitude f, définie comme l'inverse de la distance totale de l'itinéraire :
f(itinéraire) = 1 / Distance_Totale
La distance entre deux points est calculée à l'aide d'une formule adaptée aux coordonnées géographiques.
Sélection par tournoi
Pour sélectionner les parents de la prochaine génération, on utilise une sélection par tournoi. Pour chaque parent à sélectionner, on tire aléatoirement k individus de la population courante (typiquement k=3). L'individu avec la meilleure aptitude parmi ce sous-ensemble est retenu.
Croisement ordonné (OX)
L'opérateur de croisement ordonné (Order Crossover) préserve la structure relative des villes dans les chromosomes parents. Le procédé est le suivant :
- Sélectionner une section aléatoire dans le premier parent.
- Copier cette section dans l'enfant au même emplacement.
- Remplir les positions restantes dans l'enfant avec les villes du second parent, dans leur ordre d'apparition, en omettant celles déjà présentes dans la section copiée.
Mutation par inversion
L'opérateur de mutation introduit de la diversité. Dans l'inversion, deux positions sont choisies aléatoirement et la sous-séquence entre ces positions est inversée. Ce mécanisme permet d'explorer le voisniage de la solution courante.
Implémentation en Python
Chargement des données
import numpy as np
import matplotlib.pyplot as plt
import random
# Configuration pour l'affichage
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
# Définition des points de livraison (nom, longitude, latitude)
points_livraison = {
"Depot": (116.300000, 39.900000),
"A": (116.310000, 39.910000),
"B": (116.305000, 39.895000),
"C": (116.320000, 39.905000),
"D": (116.315000, 39.888000),
"E": (116.295000, 39.902000),
"F": (116.325000, 39.900000),
"G": (116.308000, 39.890000),
"H": (116.312000, 39.885000),
"I": (116.318000, 39.915000),
"J": (116.302000, 39.908000)
}
Classe principale de l'optimiseur
class OptimiseurParAG:
def __init__(self, ensemble_points, taille_pop=200, nb_elite=10, taux_mutation=0.05, iterations=1000):
self.points = ensemble_points
self.taille_pop = taille_pop
self.nb_elite = nb_elite
self.taux_mut = taux_mutation
self.max_gen = iterations
self.liste_villes = list(ensemble_points.keys())[1:]
self.mat_dist = self._calculer_matrice_distances()
Calcul des distances
def _distance_euclidienne(self, coord1, coord2):
"""Calcule la distance entre deux points (approximation plane)."""
delta_long = coord1[0] - coord2[0]
delta_lat = coord1[1] - coord2[1]
return np.sqrt(delta_long**2 + delta_lat**2) * 111320 # Conversion en mètres
def _calculer_matrice_distances(self):
"""Pré-calcule et retourne la matrice des distances entre tous les points."""
noms = list(self.points.keys())
n = len(noms)
mat = np.zeros((n, n))
for i in range(n):
for j in range(n):
mat[i][j] = self._distance_euclidienne(self.points[noms[i]], self.points[noms[j]])
return mat
Initialisation et évaluation
def _creer_population_initiale(self):
"""Génère une population initiale de permutations aléatoires."""
population = []
for _ in range(self.taille_pop):
individu = random.sample(self.liste_villes, len(self.liste_villes))
population.append(individu)
return population
def _evaluer_aptitude(self, chemin):
"""Retourne l'aptitude d'un chemin (inverse de la distance totale)."""
distance_totale = 0.0
point_courant = "Depot"
index_courant = list(self.points.keys()).index(point_courant)
for prochain_point in chemin:
index_suivant = list(self.points.keys()).index(prochain_point)
distance_totale += self.mat_dist[index_courant, index_suivant]
index_courant = index_suivant
distance_totale += self.mat_dist[index_courant, 0] # Retour au dépôt
return 1.0 / distance_totale
Sélection
def _selection_par_tournoi(self, population, k=3):
"""Sélectionne un individu via un tournoi de taille k."""
participants = random.sample(population, k)
meilleur = max(participants, key=lambda ind: self._evaluer_aptitude(ind))
return meilleur
Croisement et mutation
def _croisement_ox(self, parent_a, parent_b):
"""Effectue un croisement ordonné (OX) entre deux parents."""
taille = len(parent_a)
debut, fin = sorted(random.sample(range(taille), 2))
enfant = [None] * taille
enfant[debut:fin+1] = parent_a[debut:fin+1]
villes_a_inserer = [ville for ville in parent_b if ville not in enfant[debut:fin+1]]
pos_courante = 0
for i in range(taille):
if enfant[i] is None:
enfant[i] = villes_a_inserer[pos_courante]
pos_courante += 1
return enfant
def _mutation_par_inversion(self, chemin):
"""Applique une mutation par inversion sur un chemin."""
if random.random() < self.taux_mut:
i, j = sorted(random.sample(range(len(chemin)), 2))
chemin[i:j+1] = chemin[i:j+1][::-1]
return chemin
Boucle évolutionniste
def executer_optimisation(self):
"""Lance l'algorithme génétique sur un nombre défini de générations."""
population = self._creer_population_initiale()
for generation in range(self.max_gen):
# Évaluation et classement
classement = sorted(population, key=lambda p: self._evaluer_aptitude(p), reverse=True)
# Élitisme : conserver les meilleurs
nouvelle_pop = classement[:self.nb_elite]
# Remplir le reste de la population par sélection, croisement et mutation
while len(nouvelle_pop) < self.taille_pop:
parent1 = self._selection_par_tournoi(classement)
parent2 = self._selection_par_tournoi(classement)
descendant = self._croisement_ox(parent1, parent2)
descendant = self._mutation_par_inversion(descendant)
nouvelle_pop.append(descendant)
population = nouvelle_pop
# Retourner le meilleur individu final
meilleur_chemin = max(population, key=lambda p: self._evaluer_aptitude(p))
distance_optimale = 1.0 / self._evaluer_aptitude(meilleur_chemin)
return ["Depot"] + meilleur_chemin + ["Depot"], distance_optimale
Exécution et visualisation
if __name__ == "__main__":
random.seed(42)
np.random.seed(42)
solveur = OptimiseurParAG(points_livraison, taille_pop=150, iterations=600)
itineraire, longueur = solveur.executer_optimisation()
print(f"Longueur optimale trouvée : {longueur:.2f} mètres")
# Préparation des données pour le graphique
longitudes = [points_livraison[pt][0] for pt in itineraire]
latitudes = [points_livraison[pt][1] for pt in itineraire]
# Création du graphique
plt.figure(figsize=(10, 6))
for nom, (lon, lat) in points_livraison.items():
plt.scatter(lon, lat, s=80, zorder=5)
plt.annotate(nom, (lon, lat), textcoords="offset points", xytext=(5,5), ha='left')
plt.plot(longitudes, latitudes, 'b-', linewidth=2, alpha=0.7, label='Itinéraire optimal')
plt.title("Optimisation d'itinéraire de livraison par Algorithme Génétique")
plt.xlabel("Longitude")
plt.ylabel("Latitude")
plt.legend()
plt.grid(True, linestyle='--', alpha=0.5)
plt.tight_layout()
plt.show()