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.
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.
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 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 :
| 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.
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é.
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 :