Projet académique · L2 MIDL
Hastings—Metropolis & problème du voyageur de commerce
Co-rédaction d'un rapport mathématique de 44 pages en LaTeX, composé d'une étude théorique des chaînes de Markov et d'une implémentation de l'algorithme de Hastings—Metropolis.
Démonstration de multiples résultats / preuves (théorème ergodique, de convergence, etc.) et implémentation Python appliquée au problème du voyageur de commerce (TSP).
Réalisé avec Tony Perottino, Corentin Vaillant et Léo Bernard.
Hastings—Metropolis & TSP
Rédaction d'un rapport mathématique sur les chaînes de Markov & l'algorithme de Hastings—Metropolis et implémentation Python d'une méthode MCMC, appliquée au TSP.
Présentation générale
Les ressources suivantes permettent de consulter le rapport complet et d'exécuter interactivement les implémentations Python du projet.
Contexte du projet
Ce projet a été réalisé dans le cadre de l'UE Projet de la licence de mathématiques de ma double licence.
L'objectif était de comprendre en profondeur une méthode probabiliste importante, l'algorithme de Hastings—Metropolis (une méthode MCMC), puis de l'illustrer sur un problème classique d'optimisation : le problème du voyageur de commerce (TSP).
Le travail comporte donc deux parties complémentaires :
- Une première partie théorique (mathématiques), consacrée aux chaînes de Markov et à la justification de l'algorithme de Hastings—Metropolis,
- Une deuxième partie pratique (informatique), consacrée à son implémentation en Python et à sa mise en pratique sur plusieurs exemples, notamment le TSP sur les 10 plus grandes villes de France.
Présentation générale de Hastings—Metropolis
L'algorithme de Hastings—Metropolis est une méthode d'échantillonnage stochastique : au lieu d'explorer exhaustivement un espace de solutions, on construit progressivement une chaîne de Markov dont le comportement converge vers une distribution cible choisie.
Dans notre projet, on a appliqué Hastings—Metropolis au TSP sur les 10 plus grandes villes de France, en les reliant par leurs distances à vol d'oiseau.
Ici, une solution possible est une permutation de ces 10 villes.
L'idée est alors de parcourir "intelligemment" l'espace des permutations en acceptant ou refusant des modifications aléatoires selon une règle probabiliste favorisant les tournées courtes, sans imposer une recherche exhaustive impossible dès que le nombre de villes augmente.
1. Démarche mathématique
La première partie du rapport introduit les outils nécessaires à la compréhension de l'algorithme. Elle commence par les chaînes de Markov à espace d'états fini, en détaillant notamment les matrices de transition, la représentation sous forme de graphe orienté, les classes de communication, les états récurrents ou transients, les probabilités invariantes et le comportement en temps long.
Ces notions permettent ensuite d'expliquer les raisons pour lesquelles une chaîne de Markov "bien construite" peut produire des échantillons représentatifs d'une distribution cible.
Cette idée est centrale dans les méthodes MCMC (Markov Chain Monte Carlo), dont Hastings—Metropolis fait partie.
La suite du rapport présente alors l'algorithme lui-même : choix d'un état initial, choix d'une loi de proposition, calcul d'un ratio d'acceptation, puis acceptation ou rejet du nouvel état proposé. Notre rapport détaille aussi les arguments mathématiques justifiant que la chaîne obtenue admet bien la distribution cible voulue, sous les hypothèses appropriées.
2. Implémentation en Python
Algorithme générique d'Hastings—Metropolis
La deuxième partie de notre rapport (informatique) commence par une implémentation générique de Hastings—Metropolis.
Le Google Colab que l'on a réalisé nous permet de définir une distribution cible discrète et une matrice de proposition, puis de simuler une suite d'états dont l'histogramme se rapproche progressivement de la distribution visée.
Plusieurs exemples de distributions sont testés afin de vérifier expérimentalement le comportement de l'algorithme : loi binomiale, loi de Poisson, loi uniforme, loi géométrique et distribution discrète quelconque.
Application au voyageur de commerce
Dans notre rapport, on a également choisi d'appliquer Hastings—Metropolis au problème du voyageur de commerce, sur une tournée de 20 villes placées aléatoirement, puis sur les 10 plus grandes villes de France (représentées par leurs coordonnées).
Une tournée est représentée par une permutation des villes.
À chaque itération, l'algorithme propose une nouvelle tournée en échangeant aléatoirement deux villes, puis accepte ou refuse cette nouvelle tournée en fonction de sa longueur totale.
La distribution cible utilisée favorise les tournées courtes : plus une tournée est longue, moins elle est probable.
Le paramètre beta nous permet de contrôler la sélectivité de cette préférence.
Notre Google Colab compare alors le comportement de l'algorithme selon le nombre d'itérations et selon différentes valeurs de beta.
Pour finir, différentes visualisations permettent d'observer l'amélioration progressive des tournées obtenues :
- Exemples aléatoires sur un ensemble de 20 villes générées,
- Cas concret avec les 10 plus grandes villes de France,
- Puis expérience de plus grande taille pour analyser l'évolution de la meilleure distance rencontrée au fil des itérations.