Projet académique · L2 MIDL
Metropolis–Hastings & problème du voyageur de commerce
Projet mêlant une étude théorique des chaînes de Markov et de l'algorithme de Metropolis–Hastings, et une implémentation en Python appliquée au problème du voyageur de commerce (TSP).
Metropolis–Hastings & TSP
Projet MIDL
Objectifs du projet
Ce projet a été réalisé dans le cadre du cours “Projet de la licence de Mathématiques” du parcours MIDL. Il comporte deux volets complémentaires : un rapport théorique, et un ensemble de scripts Python illustrant l'algorithme.
La partie théorique introduit les notions de base des chaînes de Markov (matrices de transition, classes de communication, récurrence, ergodicité, mesures invariantes) avant de construire et d'analyser l'algorithme de Metropolis–Hastings.
Contenu et contributions
Étude théorique
- Rappel des propriétés des chaînes de Markov sur un espace d'états fini.
- Construction de l'algorithme de Metropolis–Hastings avec une distribution cible donnée et une loi de proposition.
- Preuve de la réversibilité et de la convergence vers la distribution invariante sous certaines conditions.
Implémentation Python
- Échantillonnage depuis différentes distributions cibles (gaussiennes, mélanges, lois discrètes).
- Application au problème du voyageur de commerce : exploration de l'espace des permutations via Metropolis–Hastings.
- Visualisation de l'évolution de la longueur de la tournée et du comportement de la chaîne.
Ressources
- Rapport PDF détaillant l'ensemble de la partie théorique.
- Scripts Python pour l'algorithme générique et pour le cas du TSP.
- Exemples d'expériences numériques documentées dans le dépôt.
Le dépôt GitHub présente la structure du projet, les instructions d'exécution et les différents cas de test utilisés pour illustrer le comportement de l'algorithme.