Algorithmes génétiques, Fourmis#
Les algorithmes génétiques ne sont pas ou peu enseignés à l’ENSAE. Chaque sujet est l’occasion de découvrir des algorithmes. Chaque sujet considère un problème simple et un algorithme d’optimisation génétique décrit par un document.
Optimisation à partir d’algorithmes génétiques#
La plupart des algorithmes d’optimisation reposent sur le gradient. La plus classique est de se promener le long de la courbe à optimisation dans le long de la pente la plus forte : dans le sens du gradient s’il faut maximier, dans le sens opposé s’il faut minimiser. Lorsque celui-ci n’est pas nul, la direction de cette pente est indiquée par le gradient. Mais cela suppose évidemment que la fonction à optimiser soit dérivable. Il arrive que la fonction ne soit pas dérivable où tout simplement que le problème d’optimisation soit combinatoire.
L’objectif de ce projet est de comparer un algorithme d’optimisation linéaire sous contrainte et un algorithme génétique appliqué à des problèmes au même problème. On s’intéressera à la convergence des deux algorithmes lorsque la dimension de l’espace des observations croît.
Problème du sac-à-dos et algorithmes génétiques#
Le problème du sac-à-dos est un problème d’optimisation discrète linéaire avec contrainte. Il peut être vu comme un problème d”optimisation combinatoire. Comment remplir un sac-à-dos avec des objets de volumes différents en perdant le moins d’espace possible ? L’objectif de ce projet est d’implémentation un algorithme de résolution de tels problèmes à partir d’algorithme génétiques.
On étudiera la convergence et le coût des algorithmes en fonction de la dimension du problème.
Problème du voyageur de commerce et algorithme génétique#
Le problème du voyageur de commerce est un problème d’optimisation discrète très connu. Il consiste à parcourir tous les sommets d’un graphe en minimisant la distance pour les parcourir. Ici encore, il s’agit de résoudre ce problème à l’aide d’algorithme génétique.
On étudiera la convergence et le coût des algorithmes en fonction de la dimension du problème.
Colonie de fourmis et plus court chemin#
On dispose un trésor dans une pièce contenant de nombreux obstacles, à l’autre bout, une colonie de fourmis. Au gré de leurs explorations, ces fourmis vont trouver puis raccourcir le plus court chemin de leurs fourmilières au trésor.
L’aspect visuel est souvent utile lorsqu’on veut vérifier que l’algorithme fonctionne et converge convenablement. Toutefois, il est rarement possible d’implémenter cette interface et d’étudier en détail les algorithmes. Le ou les élèves devront faire un choix entre ces deux directions.
Direction 1 : les fourmis, une colonie, un trésor, des phéromones et une interface visuelle.
- Direction 2un problème plus classique d’optimisation du plus court chemin dans un graphe,
on comparera avec un algortihme de Djisktra, puis on s’intéressera aux propriétés de l’algorithme lorsque le nombre de sommets augmentent (le réseau routier belge, français, américain, européen…)
Recherche de motifs#
Pas encore bien défini mais inspiré de :