🧩 Optimisation de l'agencement de modules dans une forme polygonale

Ce projet implémente une méthode d'optimisation par recuit simulé pour positionner des modules (sous forme de carrés) dans une forme complexe tout en respectant diverses contraintes spatiales et fonctionnelles.

🔍 Objectif

L'objectif est de placer des carrés dans une surface polygonale tout en :

• minimisant la distance entre nœuds connectés,
• évitant les chevauchements,
• respectant les besoins spécifiques des modules (lumière naturelle, proximité, etc.),
• assurant une disposition compacte et lisible.

📐 Fonctionnalités principales

• ✅ Génération d'une forme polygonale complexe.
• ✅ Création d'un graphe de dépendances entre modules.
• ✅ Positionnement intelligent par recuit simulé.
• ✅ Intégration de contraintes personnalisables :
  • Distance minimale entre modules.
  • Groupement (clustering).
  • Lumière naturelle en bordure.
  • Adjacence physique.
  • Alignement sur une grille virtuelle.
  • Interférences d’arêtes.

🔧 Fichiers

• main.py : point d’entrée du programme, définit la forme, le graphe, les contraintes, lance l’optimisation et affiche la meilleure solution.
• optimizer.py : contient toutes les contraintes et l’algorithme de recuit simulé.
• requirements.txt : liste des dépendances Python nécessaires.

📊 Visualisation

Le programme affiche une visualisation des modules placés :

• Chaque carré représente un module.
• Les couleurs indiquent la connectivité.
• Des marqueurs signalent les besoins particuliers :
  • 🟡 Besoin de lumière naturelle.
  • 🔵 Besoin d'adjacence.

▶️ Utilisation

1. Installation des dépendances

pip install -r requirements.txt

2. Exécution

python main.py

3. Résultat

Une ou plusieurs solutions sont testées, et la meilleure est visualisée avec Matplotlib.

🧠 Détails techniques

• Algorithme d’optimisation : Recuit simulé.
• Gestion des contraintes par fonctions de pénalité pondérées.
• Prise en compte de la géométrie réelle grâce à la bibliothèque shapely.

📌 Exemples de contraintes intégrées

• CompactnessConstraint : regroupe les modules.
• NaturalLightConstraint : rapproche les modules du périmètre.
• AdjacencyConstraint : encourage les modules à se toucher.
• EdgeInterferenceConstraint : évite que les arêtes passent par d'autres modules.

📎 Dépendances

• networkx
• shapely
• matplotlib

Voir requirements.txt pour l'installation.

🔥 Recuit simulé : le principe

Le recuit simulé est un algorithme d’optimisation inspiré de la physique, plus précisément du refroidissement des métaux. L’idée est de faire chauffer un métal, puis de le refroidir très lentement pour qu’il atteigne une structure bien ordonnée (donc avec moins d’énergie).

On applique ce principe à la recherche de la meilleure solution possible à un problème complexe, souvent avec beaucoup de variables et de contraintes.

⚙️ Comment ça marche (étapes clés)

1. On démarre avec une solution au hasard.
2. À chaque étape, on modifie légèrement la solution (mutation).
3. Si la nouvelle solution est meilleure → on l’accepte.
4. Si elle est moins bonne → on l’accepte parfois (selon une probabilité liée à la température).
5. On réduit progressivement la température → donc, on devient de plus en plus strict avec les mauvaises solutions.
6. À la fin, on garde la meilleure solution rencontrée.

📊 Le projet

Dans ton code :

• La solution = une configuration des carrés.
• Le coût = somme des distances + pénalités des contraintes.
• Mutation = déplacer un carré (ou plusieurs).
• Température = contrôle le taux d’acceptation de mauvaises solutions.
• Objectif = minimiser le coût global, tout en respectant les contraintes.

✅ Avantages

• Évite de rester bloqué dans une mauvaise solution.
• Fonctionne bien même quand il y a plein de contraintes ou un espace de recherche complexe.

❌ Inconvénients

• Assez lent.
• Sensible aux réglages (température initiale, taux de refroidissement, etc.).
• Ne garantit pas la meilleure solution, mais souvent une très bonne.

Recommandation pour le projet

1. Recuit simulé avec contraintes pondérées (l'algo actuel)

Amélioration possible :

• Meilleur placement initial (ex: algorithme glouton pour init).

• Refroidissement adaptatif selon stagnation.

• Stratégie de réchauffement déjà présente → top.

• Ajouter un voisinage intelligent (ex: nudge, rotation, swap…).

2. Ajout d’un niveau génétique / multi-solution

Générer plusieurs solutions simultanément, les faire évoluer comme dans un algorithme génétique :

• Sélection de la meilleure.

• Mutation croisée de deux “agencements”.

• Réinjection de diversité si stagnation.

Combiner SA + GA :

• GA pour explorer globalement,

• SA pour raffiner localement chaque individu.

3. Bonus : Backtracking intelligent ou CSP + géométrie (dur)

4. S'il faut respecter strictement toutes les contraintes (pas de pondération), transformer le problème en un problème de satisfaction de contraintes géométriques (CSP) — (plus complexe et plus lent).

🧪 Conclusion

👷‍♂️ Court terme : garde le recuit simulé, affine-le.

🚀 Moyen terme : hybride recuit + heuristiques ou GA.

🧠 Long terme / recherche : formulation en CSP géométrique ou intégration de solveurs SMT (type Z3).