Les algorithmes génétiques: théorie et applications

Résumé

Les algorithmes génétiques (GAs) sont des méthodes de résolution méta-heuristiques pour les problèmes d'optimisation combinatoire, dont le fonctionnement est inspiré du processus d'évolution décrit par Darwin. L'idée générale est de faire la comparaison entre les solutions admissibles du problème d'optimisation et un ensemble d'individus évoluant dans un monde abstrait, dans lequel leur adaptabilité est décrite par la fonction objectif, de telle manière à ce que plus la fonction objectif est grande et plus les individus sont "adaptés" à leur environnement. Dès lors, en partant d'une population initiale donnée et en simulant un processus d'évolution basé sur l'alternance d'opérateurs de variations, permettant d'explorer l'espace des solutions admissibles, et d'un opérateur de sélection, permettant de ne garder que les meilleurs individus (i.e. ayant la plus grande fitness), les algorithmes génétiques permettent d'obtenir au fil des générations un ensemble d'individus de plus en plus "adaptés à leur environnement", et donc par construction ayant une valeur objective de plus en plus proche de la solution optimale. Le but de ce mémoire est de donner un aperçu du fonctionnement général des GAs. Une première partie du mémoire est consacrée à l'introduction de la structure générale des GAs, avec les spécifications les plus courantes pour les opérateurs de variation et de sélection , ainsi qu'une justification théorique de leur utilisation (chapitre 3). La deuxième partie du mémoire est consacrée à l'application des GAs sur certains problèmes d'optimisation combinatoire. Nous étudions par exemple le problème de stratégie optimale d'un robot dont la tâche est de nettoyer une surface recouverte de canettes vides (connu sous le nom de "Robby, the Soda-Can-Collecting Robot", chapitre 4). Nous considérons également l'optimisation robuste des expériences par évènements dans le cadre de l'imagerie par résonance magnétique fonctionnelle (réalisé dans le cadre du stage de Master 2)

la date de réponse	24 juin 2011
langue originale	Français
Superviseur	Timoteo Carletti (Promoteur), Bertrand Hespel (Jury), Jean-Paul LECLERCQ (Jury) & Anne Lemaitre (Jury)