Algorithme génétique
Présentation
À propos de ce site
Ce site a été réalisé dans le cadre des exposés logiciels, systèmes et réseaux, encadrés et dirigés par M. Dominique REVUZ.
Il fait suite à l'exposé "Algorithme Génétique", présenté le 30 Janvier 2014 par Thomas LE ROUX, étudiant en 3ème année de formation d'Ingénieur en Informatique et Réseaux à l'école d'ingénieurs Esipe-Marne-la-Vallée.
La présentation de cet exposé est disponible ici.
Introduction
Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes.
Leur but est d'obtenir une approximation de la solution à un problème NP-complet par un mécanisme d'optimisation.
Les algorithmes génétiques utilisent la notion de sélection naturelle développée au XIXe siècle par Darwin et l'appliquent à une population de solutions potentielles au problème donné.
Présentation
Pourquoi avons-nous besoin de tels algorithmes ?
Certains problèmes sont trop complexes pour que l'on puisse proposer un algorithme, ou lorsqu'il n'y a aucune méthode exacte pour les résoudre, d'une modélisation délicate et/ou confuse où la solution au problème est inconnue. Ou alors un algorithme tolérant aux variations de données, susceptible de s'adapter à une nouvelle situation, pour qu'il évolue.
Par exemple, comment effectuer le déplacement d'un robot ? Comment faire réagir ce robot suite à une bousculade, une perte d'équilibre ? Comment adapter le comportement du robot face au danger ?
Les algorithmes génétiques propose une solution à ces questions.
Ces algorithmes sont aussi un excellent support au domaine du Machine Learning, qui est un champ d'étude de l'intelligence artificiel. Ceux-ci peuvent être utilisés pour optimiser un réseau de neurones, notamment en entraînant le réseau par l'utilisation de nouvelles informations dans les connexions synaptiques, améliorant ainsi la topologie du réseau pour obtenir une règle d'apprentissage optimale : C'est ce qu'on appelle la neuroevolution.
Un exemple d'application utilisant la neuroevolution est un robot marchant sur deux jambes. Il est très difficile de le faire marcher : Un programme générique ne marchera pas, et si on réussit, celui-ci risque de ne plus fonctionner si le centre d'équilibre change légèrement suite à un défaut de fabrication ou un changement de composant/fournisseur.
Au lieu de supporter ce chagrin inévitable, nous pouvons utiliser les algorithmes génétiques et les réseaux de neurones afin d'enseigner au robot comment apprendre à marcher plutôt que d'enseigner au robot comment marcher.
Les algorithmes génétiques peuvent également être utilisés pour optimiser des systèmes reposant sur la logique floue, en effectuant la génération et/ou l'optimisation des règles ou des opérateurs dans ces systèmes.
Liste des domaines d'applications
On retrouve les algorithmes génétiques dans différents domaines d’applications, notamment en Bioinformatique, Phylogénie, Économie, Sciences numériques, Robotiques, Industries, Mathématique, Physique et Chimie.