Algorithme génétique - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en un temps (Le temps est un concept développé par l'être humain pour appréhender le...) raisonnable. Les algorithmes génétiques utilisent la notion de sélection naturelle (En biologie, la sélection naturelle est l'un des mécanismes qui guident l'évolution...) et l'appliquent à une population de solutions potentielles au problème donné. La solution est approchée par « bonds » successifs, comme dans une procédure de séparation et évaluation (Un algorithme par séparation et évaluation, également appelé selon le terme anglo-saxon branch...), à ceci près que ce sont des formules qui sont recherchées et non plus directement des valeurs.

Les origines

L'utilisation d'algorithmes génétiques, dans la résolution de problèmes, est à l'origine le fruit (En botanique, le fruit est l'organe végétal protégeant la graine....) des recherches de John Holland et de ses collègues et élèves de l'Université (Une université est un établissement d'enseignement supérieur dont l'objectif est la...) du Michigan qui ont, dès 1960, travaillé sur ce sujet. La nouveauté introduite par ce groupe de chercheurs a été la prise en compte de l'opérateur (Le mot opérateur est employé dans les domaines :) d'enjambement en complément des mutations. Et c'est cet opérateur qui permet le plus souvent de se rapprocher de l'optimum d'une fonction en combinant les gènes contenus dans les différents individus de la population. Le premier aboutissement de ces recherches a été la publication en 1975 de Adaptation in Natural and Artificial System.

Cas d'utilisation

Les conditions du problème

Comme cela a été dit plus haut, les algorithmes génétiques peuvent être une bonne solution pour résoudre un problème. Néanmoins, leur utilisation doit être conditionnée par certaines caractéristiques du problème.

Les caractéristiques à prendre en compte sont les suivantes :

  • Le temps de calcul de la fonction fitness doit être raisonnablement court. En effet, celle ci sera évaluée de nombreuses fois.
  • Nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) de solutions important : les performances des algorithmes génétiques par rapport aux algorithmes classiques sont plus marquées lorsque les espaces de recherches sont importants. En effet, pour un espace dont la taille est faible, il peut être plus sûr de parcourir cet espace de manière exhaustive afin d'obtenir la solution optimale en un temps qui restera somme toute correct. Au contraire, utiliser un algorithme génétique (Les algorithmes génétiques appartiennent à la famille des algorithmes...) engendrera le risque d'obtenir une solution non optimale (voir Limites) en un temps qui restera sensiblement identique.
  • Pas d'algorithme déterministe adapté et raisonnable.
  • Lorsque l'on préfère avoir une solution relativement bonne rapidement plutôt qu'avoir la solution optimale en une durée indéfinie. C'est ainsi que les algorithmes génétiques sont utilisés pour la programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent...) de machines qui doivent être très réactives aux conditions environnantes.

Exemples d'applications

Applications dans la recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue...)

Le problème du voyageur de commerce : Ce problème est un classique d'algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées...). Son sujet concerne les trajets d'un voyageur de commerce. Celui-ci dispose de plusieurs points où s'arrêter et le but de l'algorithme est d'optimiser le trajet de façon à ce que celui-ci soit le plus court possible. Dans le cas où huit points d'arrêts existent, cela est encore possible par énumération (2520 possibilités [pour n arrêts,n supérieur ou égal à 3, il y a (n-1)!/2 chemins possibles) mais ensuite, l'augmentation du nombre d'arrêts fait suivre au nombre de possibilités une croissance exponentielle (En mathématique, en économie et en biologie, on parle d'un phénomène à croissance...).

Par le biais d'algorithmes génétiques, il est possible de trouver des chemins relativement corrects. De plus, ce type de problèmes est assez facile à coder sous forme d'algorithme génétique (La génétique (du grec genno γεννώ = donner naissance) est...). L'idée de base est de prendre comme fonction d'adaptation d'un chemin sa longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus...). Pour effectuer le croisement de deux chemins :

  • On recopie le premier chemin jusqu'à une "cassure (En minéralogie, la cassure désigne l'aspect de la surface d'un minéral qui,...)".
  • On recopie ensuite les villes du second chemin. Si la ville (Une ville est une unité urbaine (un « établissement humain » pour...) est déjà utilisée, on passe à la ville suivante.
Chemin Codage (De façon générale un codage permet de passer d'une représentation des...)
A 1 2 3 4 : 5 6 7 8 9
B 4 1 6 3 : 9 8 2 5 7
fils 1 2 3 4 : 6 9 8 5 7

Soit un itinéraire qui contient 9 clients, on suppose que l'on croise les deux chemins suivants (un chiffre (Un chiffre est un symbole utilisé pour représenter les nombres.) représente un client). On croise ces deux chemins après le locus 4 : on obtient le chemin fils.

En partant de ce principe, de nombreux algorithmes génétiques ont été développés, chacun utilisant différentes variantes afin de se rapprocher le plus possible du maximum dans tous les cas. Il existe d'ailleurs un concours sur internet (Internet est le réseau informatique mondial qui rend accessibles au public des services...) qui propose de développer un algorithme à même de trouver le meilleur chemin sur un problème de voyageur de commerce de 250 villes.

Applications industrielles

Un premier exemple est une réalisation effectuée au sein de l'entreprise Motorola (www.motorola.com/fr). Le problème pour lequel Motorola a utilisé les algorithmes génétiques concerne les tests des applications informatiques. En effet, lors de chaque changement apporté à une application, il convient de retester l'application afin de voir si les modifications apportées n'ont pas eu d'influence négative sur le reste de l'application. Pour cela, la méthode classique est de définir manuellement des plans de test permettant un passage dans toutes les fonctions de l'application. Mais ce type de test nécessite un important travail humain. Le but de Motorola a donc été d'automatiser cette phase (Le mot phase peut avoir plusieurs significations, il employé dans plusieurs domaines et...) de définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la...) de plans de tests. Ils ont pour cela défini un algorithme où chaque individu (Le Wiktionnaire est un projet de dictionnaire libre et gratuit similaire à Wikipédia (tous deux...) correspond à un résultat d'exécution d'un programme (l'enchaînement des valeurs passées au programme) et où chaque individu reçoit une valeur qui correspond à son aptitude à passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques...) dans un maximum de parties du code de l'application. Finalement, l'outil (Un outil est un objet finalisé utilisé par un être vivant dans le but d'augmenter son...) développé permet, à l'aide d'un algorithme génétique, de faire évoluer ces programmes de test pour maximiser les zones testées de façon à ce que lors de modifications apportées à l'application on puisse soumettre celle-ci à des tests efficaces. D'autres domaines industriels utilisent aujourd'hui les algorithmes génétiques. On peut retenir entre autres l'aérodynamique (L'aérodynamique est une branche de la dynamique des fluides qui porte principalement sur la...) où des optimisations sont mises au point (Graphie) à l'aide de ces outils, l'optimisation structurelle, qui consiste à minimiser le poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la...) d'une structure en tenant compte des contraintes de tension (La tension est une force d'extension.) admissibles pour les différents éléments, et la recherche d'itinéraires : ces algorithmes ont été utilisés par la NASA (La National Aeronautics and Space Administration (« Administration nationale de...) pour la mission d'exploration (L'exploration est le fait de chercher avec l'intention de découvrir quelque chose d'inconnu.) de Mars, dans la gestion des déplacements du robot (Un robot est un dispositif mécatronique (alliant mécanique, électronique et...) Pathfinder.

La société Sony les a aussi utilisés dans son robot Aibo. En effet, ce robot a « appris » à marcher dans un dispositif expérimental où son système de commande (Commande : terme utilisé dans de nombreux domaines, généralement il désigne un ordre ou un...) a été soumis à une évolution artificielle. Différents modes de commandes ont été testés, les plus performants ont été croisés et le résultat a été très positif. De génération en génération, le robot s'est redressé, puis a commencé à marcher en chutant souvent et a fini par marcher d'un pas assuré.

Informatique décisionnelle (L’informatique décisionnelle (en anglais : DSS pour Decision Support System ou...)

Les algorithmes génétiques sont mis en œuvre dans certains outils d'informatique (L´informatique - contraction d´information et automatique - est le domaine...) décisionnelle ou de data mining par exemple pour rechercher une solution d'optimum à un problème par mutation des attributs (des variables) de la population étudiée.

Ils sont utilisés par exemple dans une étude d'optimisation d'un réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des...) de points de vente ou d'agences (banque, assurance, ...) pour tenter de répondre aux questions :

  • quelles sont les variables (superficie, effectif, ...) qui expliquent la réussite commerciale de telle ou telle agence ?
  • en modifiant telle variable (En mathématiques et en logique, une variable est représentée par un symbole. Elle...) (mutation) de telle agence améliore-t-on son résultat ?
Page générée en 0.458 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique