Algorithme génétique

Objectif du projet

Découvrir les algorithmes génétiques en les appliquant à un problème concret : trouver la sortie d'un labyrinthe.

Ma démarche

Un algorithme génétique s'inspire de la sélection naturelle : on fait évoluer une population de solutions de génération en génération, en gardant les meilleures et en les faisant se croiser et muter, jusqu'à obtenir une solution satisfaisante.

J'ai choisi le labyrinthe comme terrain d'application, car on peut facilement mesurer la qualité d'un chemin. Je me suis fixé deux étapes : d'abord créer un labyrinthe sur lequel travailler, puis écrire l'algorithme chargé de le résoudre.

Réalisation du projet

• Génération du labyrinthe avec un parcours en profondeur (DFS).
• Résolution par un algorithme génétique.
• Exécution de plusieurs simulations en parallèle pour gagner du temps.

Problèmes rencontrés

• Problème : Une simulation prend beaucoup de temps, car l'algorithme doit évaluer un grand nombre de solutions à chaque génération.

  Solution : Réaliser plusieurs simulations en parallèle.

Ce que j'en retiens

Ce projet m'a permis de comprendre concrètement le principe d'un algorithme génétique et de voir que son coût en calcul peut vite devenir un frein, d'où l'intérêt de la parallélisation.