Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
Les algorithmes génétiques (parfois appelés algorithme évolutionnaires) appartiennent à une famille d'algorithmes appelée métaheuristiques dont le but est d'obtenir une solution convenable en un temps correct. Ils sont une
alternative à des algorithmes plus classiques dans les cas où l'on n'a pas de méthode qui permette de résoudre un problème
difficile en un temps correct. Les algorithmes génétiques reprennent, afin de résoudre ces problèmes, certains principes
développés au XIXe siècle par le scientifique Darwin.
| Sommaire |
|
|
L'utilisation, dans la résolution de problèmes, d'algorithmes génétiques est à l'origine le fruit des recherches de John Holland et de ses collègues et élèves de l'université 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 de Crossing over 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.
Les algorithmes génétiques étant basés sur des phénomènes biologiques, il convient de rappeler au préalable quelques termes de génétique.
Les organismes vivants sont tout d'abord constitués de chromosomes qui correspondent en fait à des chaînes d'ADN. L'élément de base de ces chromosomes (le caractère de la chaîne d'ADN) est un allèle. Sur chacun de ces chromosomes, une suite d'allèles constitue une chaîne qui code les fonctionnalités de l'organisme (la couleur des yeux ...). La position d'un allèle sur le chromosome est son locus. L'ensemble des chromosomes correspond au génome de l'individu.
On utilise aussi, dans les algorithmes génétiques, une analogie avec la biologie, qui concerne l'évolution, hypothèse émise par Darwin et qui propose qu'au fil du temps, les gènes conservés au sein d'une population donnée sont ceux qui sont le plus adaptés aux besoins de l'espèce et à son environnement.
La génétique a mis en évidence l'existence de plusieurs opérations au sein d'un organisme donnant lieu au brassage génétique.
Ces opérations interviennent lors de la phase de reproduction lorsque les chromosomes de deux organismes fusionnent.
Ces opérations sont imitées par les algorithmes génétiques afin de faire évoluer les populations de solutions de manière
progressive.
Lors de cette opération, deux chromosomes s'échangent des parties de leurs chaînes, pour donner de nouveaux chromosomes. Ces
crossing-over peuvent être simples ou multiples.
Dans le premier cas, les deux chromosomes se croisent et s'échangent des portions d'ADN en un seul point. Dans le deuxième cas,
il y a plusieurs point de croisement. Pour les algorithmes génétiques, c'est cette opération (le plus souvent sous sa forme
simple) qui est prépondérant. Sa probabilité d'apparition lors d'un croisement entre deux chromosomes est un paramètre de
l'algorithme génétique. En règle générale, on fixe la proportion d'apparition à 0,7.
De façon aléatoire, un gène peut, au sein d'un chromosome être substitué à un autre. De la même manière que pour les crossing-over, on définit ici un taux de mutation lors des changements de population qui est généralement compris entre 0,001 et 0,01. Il est nécessaire de choisir pour ce taux une valeur relativement faible de manière à ne pas tomber dans une recherche aléatoire et conserver le principe de sélection et d'évolution.
Les algorithmes génétiques, afin de permettre la résolution de problèmes, se basent sur les différents principes décrits ci-dessus. De manière globale, on commence avec une population de base qui se compose le plus souvent de chaînes de caractères correspondant chacune à un chromosome. Nous reviendrons par la suite sur les différentes structures de données possibles ( voir Encodage ) mais nous retiendrons pour le moment l'utilisation de l'encodage binaire (ex. : 0100110).
Le contenu de cette population initiale est généré aléatoirement. On attribue à chacunes des solutions une note qui correspond à son adapatation au problème. Ensuite, on effectue une sélection au sein de cette population. Pour chaque individu, la propabilité d'être sélectionné est proportionnelle à son adaptation au problème. Afin de sélectionner un individu, on utilise le principe de la roue de la fortune biaisée. Cette roue est une roue de la fortune classique sur laquelle chaque individu est représenté par une portion proportionnelle à son adaptation. On effectue ensuite des tirages au sort sur cette roue par groupe de deux. Lorsque deux chromosomes ont été sélectionnés, on passe à la phase du crossing-over. On effectue ensuite des mutations sur chaque individu. Ce processus nous fournit une nouvelle population. On réitère le processus un grand nombre de fois de manière à imiter le principe d'évolution, qui ne prend son sens que sur un nombre important de générations. On peut arrêter le proccesus au bout d'un nombre arbitraire de génération ou lorsque qu'une solution possède une note suffisamment satisfaisante.
Considérons par exemple les deux individus suivants dans une population où chaque individu correspond à une chaîne de 8 bits : A = 00110010 et B = 01010100. On ajuste la probabilité du crossing over à 0.7.
| Chromosome | Contenu |
| A | 00:110010 |
| B | 01:010100 |
| A' | 00 010100 |
| B' | 01 110010 |
Supposons ici que le crossing-over ait lieu, on choisit alors aléatoirement la place de ce crossing over (toutes les places ayant la même probablité d'être choisies). En supposant que le crossing-over ait lieu après le deuxième allèle, on obtient A' et B' ( « : » marquant le crossing over sur A et B ). Ensuite, chacun des gènes des fils (ici, chacun des bits des chaînes) est sujet à la mutation. De la même manière que pour les combinaisons, on définit un taux de mutation (très bas, de l'ordre de 0,001 - ici on peut s'attendre à ce que A' et B' restent identiques).
En effectuant ces opérations (sélection de deux individus, crossing-over, mutation), un nombre de fois correspondant à la taille de la population divisée par deux, on se retrouve alors avec une nouvelle population (la première génération) ayant la même taille que la population initiale, et qui contient globalement des solutions plus proches de l'optimum. Le principe des algorithmes génétiques est d'effectuer ces opérations un maximum de fois de façon à augmenter la justesse du résultat.
Il existe plusieurs techniques qui permettent éventuellement d'optimiser ces algorithmes, on trouve par exemple des techniques dans lesquelles on insère à chaque génération quelques individus non issus de la descendance de la génération précédente mais générés aléatoirement. Ainsi, on peut espérer éviter une convergence vers un optimum local.
Pour les algorithmes génétiques, un des facteurs les plus importants, si ce n'est le plus important, est la façon dont sont encodées les solutions (ce que l'on a nommé ici les chromosomes), c'est-à-dire les structures de données qui coderont les gènes.
Ce type d'encodage est certainement le plus utilisé car il présente plusieurs avantages. Son principe est d'encoder la solution selon une chaîne de bits (qui peuvent prendre les valeurs 0 ou 1). Les raisons pour lesquelles ce type d'encodage est le plus utilisé sont tout d'abord historiques. En effet, lors des premiers travaux de Holland, les théories ont été élaborées en se basant sur ce type d'encodage. Et même si la plupart de ces théories peuvent être étendues à des données autres que des chaînes de bits, elles n'ont pas été autant étudiées dans ces contextes. Cependant, l'avantage de ce type d'encodage sur ses concurrents a tendance à être remis en question par les chercheurs actuels qui estiment que les démonstrations d'Holland sur les avantages supposés de cet encodage ne sont pas révélatrices.
La démonstration d'Holland (en 1975) pour prouver la supériorité de ce type d'encodage est la suivante. Il compara deux types de codage pour le même problème. Le premier était composé de peu de types d'allèles mais avec des chromosomes d'une longueur importante (des chaînes de 100 bits par exemple), l'autre était composé de chaînes plus courtes mais contenant plus d'allèles (en sachant que tout autre encodage, pour le même chromosome, aboutira à une chaîne plus courte). Il prouva que le codage sous forme de bits était plus efficace de manière assez simple. En effet, les chaînes de 100 bits permettent d'avoir plus de possibilités de crossing-over. Entre deux chromosomes du premier type, le crossing-over peut avoir lieu à 100 endroits différents contre 30 pour ceux du second type. Le brassage génétique sur lequel repose l'efficacité des algorithmes génétiques sera donc plus important dans le premier cas.
Il existe cependant au moins un coté négatif à ce type de codage qui fait que d'autres existent. En effet, ce codage est souvent peu naturel par rapport à un problème donné (l'évolution des poids d'arcs dans un graphe par exemple est difficile à coder sous la forme d'une chaîne de bits).
Une autre manière d'encoder les chromosomes d'un algorithme génétique est donc l'encodage à l'aide de caractères multiples (par opposition aux bits). Souvent, ce type d'encodage est plus naturel que celui énoncé ci-avant. C'est d'ailleurs celui-ci qui est utilisé dans de nombreux cas poussés d'algorithmes génétiques que nous présenterons par la suite.
Cet encodage utilise une structure arborescente avec une racine de laquelle peuvent être issus un ou plusieurs fils. Un de leurs avantages est qu'ils peuvent être utilisés dans le cas de problèmes où les solutions n'ont pas une taille finie. En principe, des arbres de taille quelconque peuvent être formés par le biais de crossing-over et de mutations.
Le problème de ce type d'encodage est que les arbres résultants sont souvent difficiles à analyser et que l'on peut se retrouver avec des arbres « solutions » dont la taille sera importante alors qu'il existe des solutions plus simples et plus structurées à côté desquelles sera passé l'algorithme. De plus, les performances de ce type d'encodage par apport à des encodages en chaînes n'ont pas encore été comparées ou très peu. En effet, ce type d'expérience ne fait que commencer et les informations sont trop faibles pour se prononcer.
Finalement, le choix du type d'encodage ne peut pas être effectué de manière sûre dans l'état actuelle des connaissances. Selon les chercheurs dans ce domaine, la méthode actuelle à appliquer dans le choix du codage consiste à choisir celui qui semble le plus naturel en fonction du problème à traiter et développer ensuite l'algorithme de traitement.
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. 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'agorithme 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 (40 320 possibilités) mais ensuite, l'augmentation du nombre d'arrêts fait suivre au nombre de possibilités une croissance exponentielle.
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. L'idée de base est de prendre comme fonction d'adaptation d'un chemin sa longueur puis, pour effectuer le croisement de deux chemins, une fois que le locus où doit avoir lieu le crossing-over est sélectionné, on garde les itinéraires des deux chemins jusqu'à ce locus et on place dans le chemin A les villes qui ne sont pas présentes dans la première partie, dans l'ordre où elles apparaissent dans le chemin B. On fait le contraire pour le chemin B.
| Chemin | Codage |
| A | 1234:56789 |
| B | 4163:98257 |
| A' | 1234 69857 |
| B' | 4163 25789 |
Soit un itinéraire qui contient 9 clients, supposons que l'on croise les deux chemins suivants (un chiffre représente un client). Si l'on croise ces deux chemins après le locus 4, on obtient les deux chemins A' et B'.
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 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. Le problème pour lequel motorola a utilisé les algorithmes génétiques concerne les tests des applications. 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 de définition de plans de tests. Ils ont pour cela défini un algorithme où chaque individu correspond à un résultat d'exécution d'un programme (l'enchainement des valeurs passées au programme) et où chaque individu reçoit une valeur qui correspond à son aptitude à passer dans un maximum de parties du code de l'application. Finalement, l'outil 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 entres autres l'aérodynamique où des optimisations sont mises au point à l'aide de ces outils, l'optimisation structurelle, qui consiste à minimiser le poids d'une structure en tenant compte des contraintes de tension admissibles pour les différents éléments, et la recherche d'itinéraires : ces algorithmes ont été utilisés par la NASA pour la mission d'exploration de Mars, dans la gestion des déplacement du robot 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 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é.
