Metaheuristic

🧐 Problème des n-reines — Résolution par heuristiques

📌 Description

Ce projet aborde la résolution du problème des n-reines pour un échiquier de taille n × n avec n > 3, à l’aide de deux heuristiques classiques :

1. Hill Climbing (Amélioration continue, version greedy)
2. Recuit simulé (Simulated Annealing)

Chaque reine occupe une case différente par ligne et par colonne, donc les conflits potentiels concernent uniquement les diagonales.

---

⚙️ Langage et environnement

• Langage : Python 3.10+ recommandé
• Environnement : Jupyter Notebook ou tout interpréteur Python compatible

---

📦 Dépendances logicielles

Le projet repose sur les bibliothèques Python suivantes :

pip install numpy matplotlib

• numpy : gestion des tableaux et des permutations
• matplotlib : affichage graphique des échiquiers

---

🧮 Contenu

Le programme implémente deux approches :

1. 🔼 Hill Climbing (greedy)

• Utilise des permutations aléatoires comme états initiaux.
• Explore tous les voisins en échangeant deux colonnes.
• Accepte uniquement un meilleur voisin à chaque itération.
• Peut rester bloqué dans un optimum local (plateau ou colline non globale).

2. 🔥 Recuit simulé

• Commence également par une permutation aléatoire.
• Explore un voisin aléatoire à chaque itération.
• Peut accepter une dégradation temporaire de la solution avec une probabilité dépendant de la "température" simulée.
• Plus robuste face aux optima locaux grâce à cette capacité d’exploration.

---

📟 Rapport et ressenti

Ce travail nous a permis de mieux comprendre le rôle des heuristiques dans la recherche de solutions optimales (ou quasi-optimales) dans des espaces d’états très vastes.

• L’implémentation du hill climbing est simple et rapide, mais peu efficace pour des tailles de plateau plus grandes (n > 10) à cause de son caractère purement avide.
• Le recuit simulé, plus complexe, permet de sortir des optima locaux en acceptant temporairement des solutions moins bonnes, ce qui lui donne un net avantage dans les situations complexes.
• Le choix de voisinage (permutation de deux éléments dans la permutation représentant la solution) est pertinent et conserve l’unicé ligne/colonne.

---

📊 Comparaison des performances

Méthode	Temps / Itérations	Conflits finaux	Sensibilité au point de départ
Hill Climbing	Rapide	1–3 (souvent non nul)	Très sensible (optima locaux fréquents)
Recuit simulé	Modéré	0 (souvent)	Moins sensible (bonne exploration)

🔧 Influence des paramètres

• Hill climbing :

  • Répéter l'algorithme plusieurs fois (Limite) améliore les chances de trouver une solution correcte.
  • Ne gère pas l’aléatoire une fois lancé (pas de retour en arrière possible).

• Recuit simulé :

  • Le paramètre Tlimit (nombre d’itérations) influence fortement la qualité : une valeur trop basse mène à un échouement prématuré.
  • La probabilité d’acceptation des mauvaises solutions diminue avec le temps, simulant un refroidissement naturel.

---

✅ Conclusion

• Le hill climbing est efficace sur de petits échiquiers, mais rapidement limité dès que n augmente.
• Le recuit simulé, bien qu’un peu plus lent, est plus fiable et robuste face aux difficultés dues à la structure du problème.
• Pour des échiquiers de taille moyenne à grande, il est préférable d’utiliser une meta-heuristique comme le recuit simulé.

---

📸 Exemple d’affichage

L’échiquier s’affiche à l’aide de matplotlib, avec :

• ♛ noires : reines sans conflit
• ♛ rouges : reines en conflit

Author

👤 HONGBO Bryan