Fonctionnement des algorithmes génétiques

Cours approche multi-agents pour la reconnaissance du cancer du sein, tutoriel & guide de travaux pratiques en pdf.

Objectif des algorithmes génétiques

Les algorithmes génétiques sont des algorithmes d’exploration développés à l’origine par J. Holland et son équipe au sein de l’université du Michigan [35] sont fondés sur la sélection naturelle et la génétique. Ils utilisent les principes de la survie des structures les mieux adaptées, les échanges d’informations pseudo-aléatoires. Ils reposent de manière intensive sur le hasard mais ne sont pas purement aléatoires.

Fonctionnement des algorithmes génétiques

Les AGs fonctionnent avec une population regroupant un ensemble d‟individus (chromosomes). Pour chaque individu on attribue une valeur calculée par la fonction d‟adaptation ou fitness.
En pratique, à partir d‟une population, des chromosomes sont générés d‟une façon aléatoire lors de l‟initialisation. Pour définir la taille de la population, des travaux ont mentionné que cette taille varie d‟un problème à un autre.
Dans chaque cycle d‟opérations génétiques, une nouvelle population appelée génération est créé à partir des chromosomes de la population courante. Pour cela certains chromosomes appelés „parents‟ sont sélectionnés afin d‟élaborer les opérations génétiques. Les gènes de ces parents sont mixés et recombinés pour la production d‟autres chromosomes appelés „enfants‟ constituant la nouvelle génération.
Les étapes de l‟AG sont répétées durant t cycles, l‟arrêt de l‟algorithme est fixé d‟après un critère d’arrêt. On peut avoir plusieurs critères d‟arrêt :
Le nombre de génération fixé initialement a été atteint.
La valeur de la fonction d‟adaptation a atteint une valeur fixée a priori.
L‟absence d‟évolution de la valeur de la fonction d‟adaptation des individus d‟une population à une autre.
Les chromosomes ont atteint un certain degré d‟homogénéité.
Figure III.11 schéma de principe d‟un algorithme génétique
Globalement l‟algorithme est basé sur :
– Une représentation chromosomique des solutions du problème.
– Une méthode pour créer une population initiale de solutions.
– Une fonction d‟évaluation (fitness) pour classer les solutions en fonction de leurs aptitudes.
– Des opérateurs génétiques qui définissent la manière dont les caractéristiques génétiques des parents sont transmis aux descendants (enfants).
– Les valeurs des paramètres utilisés par l‟AG.

Codage et opérateurs d’un algorithme génétique

Trois opérateurs caractérisent les algorithmes génétiques et rappellent l‟origine de ces méthodes, ils vont permettre à la population d‟évoluer, par la création d‟individus nouveaux construits à l‟aide des individus anciens. Plus précisément, on prélève, dans certains individus de la population courante, une partie de leurs caractéristiques en choisissant certaines parties des chromosomes qui les représentent ; puis on recombine ces différentes parties pour constituer les individus de la nouvelle population :
La phase de sélection indique dans quelles configurations de la population courante on va prélever des morceaux de chromosomes ; la phase de croisement prélève ces morceaux de chromosomes et les recombine pour former les configurations de la population suivante.
La phase de mutation s‟applique à la nouvelle population en changeant éventuellement certains gènes de certains chromosomes obtenus à la fin de la phase de croisement. Une succession des trois opérations de sélection, de croisement et de mutation constitue une génération, et les algorithmes génétiques consistent donc à faire évoluer une population initiale pendant un certain nombre de générations, nombre déterminé par l‟utilisateur.

Le codage

Une méthode évolutionnaire, spécifiquement basée sur un algorithme génétique nécessite une représentation des individus qui sont les solutions du problème que l‟on cherche à résoudre Dans la plupart des représentations chaque gène correspond à un attribut qui représente une variable de l‟espace de recherche. Chaque variable, associée à une caractéristique de l‟espace peut prendre certaines valeurs (discrètes ou continues) .une représentation simple, souvent utilisées en algorithme génétique, adapte le principe de gènes binaire exprimant la présence ou l‟absence de la caractéristique associée .dans de telle représentation, chaque individu est représenté par une chaine de longueur généralement fixe
Aujourd‟hui, il est unanimement admis qu‟il faut considérer 2 espaces : l‟espace ou est posé le problème, sur lequel on peut calculer la fonction objectif ou espace phénotypique, et l‟espace ou travaillent les opérateurs génétiques ou espace génotypique
Le codage est le passage du phénotype ou génotype, un bon codage est celui qui favorise la fonction des briques élémentaires qui seront recombinée par l‟opérateur de croisement.
Il y a deux principaux types de codage utilisables, et on peut passer de l’un à l’autre relativement facilement :
Codage binaire : Chaque gène dispose du même alphabet binaire {0, 1}, C‟est le plus utilisé et celui qui a été employé lors de la première application des algorithmes génétiques.
Figure III.12 Exemple de codage binaire
Le codage par permutations de valeurs entières : Le gène est codé par une valeur entière dans un ensemble de cardinalité égale au nombre de gènes, cela peut-être utile notamment dans le cas où l’on recherche le maximum d’une fonction réelle. Exemples :
Figure III.13 Exemple de codage par permutation

Initialisation de la population

cette étape consiste à initialiser une population avec une méthode complètement aléatoire, la population se compose d‟un ensemble d‟individus (points dans l‟espace de recherche),solution possible du problème.
Un individu, appelé généralement chromosomes est constitué de gènes de chaines de bits codés souvent en binaire „0-1‟,a chaque individu on attribue une fonction performance évaluant le mérite de cet individu en tant que solution possible du problème la population évolue en une succession de générations en respectant le principe que les individus les plus adaptés (en terme de valeurs de la fonction performance)survivent et se reproduisent

Principe de sélection

Cet opérateur est chargé de définir quels seront les individus de P qui vont être dupliqués dans la nouvelle population P’ et vont servir de parents (application de l’opérateur de croisement). Soit n le nombre d’individus de P, on doit en sélectionner n/2 (l’opérateur de croisement nous permet de repasser à n individus).
Cet opérateur est peut-être le plus important puisqu‟il permet aux individus d‟une population de survivre, de se reproduire ou de mourir. En règle générale, la probabilité de survie d‟un individu sera directement reliée à son efficacité relative au sein de la population. Il existe différentes méthodes de sélection :
• La méthode de la « loterie biaisée » (roulette wheel) de GoldBerg,
• La sélection par tournois,