Genetic Algorithms

(This page is not yet available in english. The french version is displayed)

Présentation

Mon année de DEA en Informatique m'a amené à effectuer un stage dans le domaine des algorithmes génétiques. Il a été encadré par Philippe Collard et Manuel Clergue du Laboratoire I3S de l'Université de Nice - Sophia Antipolis.
Le rapport final de ce stage qui est présenté ici est intitulé :  Étude de l'influence de la neutralité sur la dynamique des Algorithmes Génétiques.

Introduction

Les Algorithmes Génétiques (AG) s'inspirent des modèles des processus d'évolution naturelle pour concevoir et implanter des systèmes de résolution de problèmes. Ils simulent l'évolution de solutions potentielles via des variations stochastiques dues à des mécanismes tels que sélection, croisement, mutation ou reproduction.

Exemple de croisement et de mutation
En tant que technique d'optimisation, les AG sont utilisés pour traiter des problèmes combinatoires. Ils entrent en concurrence avec les méta heuristiques classiques : recuit simulé, recherche tabou,... Des résultats récents ont montré que l'on pouvait obtenir de bons, voire même les meilleurs résultats, sur des problèmes industriels par des techniques hybrides basées sur une approche évolutionniste (e.g. allocation de fréquences en téléphonie mobile).

Sujet du stage

Une théorie de l'évolution biologique basée sur le concept de neutralité a été proposée par Kimura. Il suggère que la majorité des changements durant l'évolution résulte d'une dérive aléatoire au niveau des génotypes plutôt que de l'effet de la pression sélective. Ceci suppose d'une part qu'il existe des ensembles de génotypes sélectivement équivalents, et d'autre part que l'on puisse se déplacer dans ces ensembles par mutations sélectivement neutres.

Dans ce contexte l'implication de la neutralité dans le processus évolutionniste d'adaptation peut être expliquée par un phénomène de diffusion dans les réseaux de neutralité. La diffusion augmente les chances qu'une région de l'espace soit trouvée dans laquelle le réseau sélectivement dominant se rapproche d'un réseau mieux adapté.

Le concept de neutralité n'a pas encore été largement exploité dans le domaine des AG. Les travaux sur ce sujet consistent à étudier l'influence d'une neutralité intrinsèque sur la dynamique. Une autre démarche consiste à introduire une neutralité structurée (dite synthétique) dans l'espace de recherche.

Exemple de l'action d'un operateur neutre

Objectif

L'objectif du stage est d'étudier l'influence de la neutralité intrinsèque sur la dynamique d'un algorithme génétique. En particulier, on s'intéressera au rôle de la distribution des réseaux d'iso-fitness, ainsi que celui des opérateurs neutres dans le phénomène de diffusion.

Il est important de préciser que le but de ce stage n'est pas de montrer la supériorité des algorithmes génétiques par rapport à une autre technique d'optimisation mais de montrer que, sous certaines conditions, grâce à une ``bonne'' exploitation de la neutralité, un AG peut mieux converger vers la solution optimale.

On montrerai ainsi qu'un ingénieur souhaitant résoudre un problème à l'aide des AG, pourrait avoir intérêt à exploiter la neutralité afin d'optimiser  la résolution.

Téléchargement

Cliquez sur les icônes suivantes pour visualiser le rapport complet au format PDF ou au format Postscript. Les transparents peuvent être visualisés au format Powerpoint
PDF PS PPT