Algorithmes génétiques

Comment ca marche ?

Heuristiques

Pourquoi avons nous besoin de tels algorithmes ?

Certains problèmes sont trop complexes pour que l'on puisse proposer un algorithme, d'autres nécessitent que l'algorithme de réponse soit tolérant aux variations des données en entrée. Enfin parfois on souhaite que notre système s'adapte aux nouveaux problèmes qu'il pourra rencontrer, qu'il évolue.

Pour résoudre de tels problèmes on fait appel aux heuristiques, ces algorithmes permettent de trouver une solution à ce genre de problème.

Qu'est ce qu'une heuristique ?

L'idée principale des heuristiques est d'explorer l'espace des solutions possibles en cherchant la moins mauvaise. Les différences entre chacuns d'entre eux étant la manière dont ils vont effectuer cette exploration. En d'autres termes, l'algorithme essai de converger vers une solution qui soit la meilleure possible.

Voici une liste de quelques heuristiques:

• Hill climbers: Gradient descent (Descente de gradient), Annealing (Recuit simulé), Tabu search (Recherche avec tabous).
  
• Evolutionary algorithms: Genetic (Algoritmes génétiques), Ant colony (Fourmilliere), Neurals networks (Réseaux de neurones).
• Constraints algorithms: Local consistency, Hybrid algorithms.

Algorithmes génétiques

Origine : Théorie Darwinienne de l'évolution

L'idée des algorithmes génétiques vient, comme beaucoup d'autres (fourmilière, métallurgie, ...), d'une observation de la vie réelle. Ainsi, le principe de base des AG provient de la théorie de Darwin sur l'évolution des espèces.

Cette théorie est simple, elle se base sur quatre observations :

• Le monde est constitué d'un ensemble toujours croissant d'espèces, dont chaque individu est différent de ses pairs et possède ses propres capacités ou particularités.
• L'environnement de ces espèces est limité (en nourriture, en espace, etc.).
• Le struggle for life ou "combat pour la survie" : dans un environnement limité, la nourriture est rare et il faut soit se battre avec les autres, soit être plus malin pour pouvoir en profiter. Chaque individu de l'espèce fait jouer ses particularités pour acéder aux ressources vitales. Le résultat de ces observations conduit à la sélection naturelle : seuls ceux qui ont pu accéder aux ressources vitales (les plus forts, ou malins, ou rapides...) peuvent réellement survivre, les plus "faibles" ou moins adaptés à leur environnement se voient disparaître.
• L'hérédité d'une génération à la suivante : ce qui a fait la survie de certains individus se retrouve dans la descendance qui peut ainsi profiter de "meilleures" capacités venant de parents différents. On obtient une combinaison de particularités au dessus de la moyenne des individus, et par croisement, on aura des individus de plus en plus adaptés à leur environnement.

AG inspirés de ce paradigme

Etant donné l'origine des algorithmes génétiques, nous retrouverons la terminologie de la biologie, et plus précisément de la génétique (population, individu, chromosome, gène), qui s'est aussi inspiré de la théorie Darwinienne.

Pour la modélisation, le passage de la théorie de Darwin aux AG, le phénomène a tout smiplement été traduit, à partir des quatre observations ci-dessus. Darwin a également identifié des opérateurs qui régissent l'évolution des espèces.

Opérateurs d'évolution

• Sélection : choix des individus les mieux adaptés .
• Croisement : mélange par la reproduction des particularités des individus choisis.
• Mutation : altération aléatoire des particularités d'un individu

Principes

Les AG utilisent la notion de gène. Une gène est un fragment d'information, plus généralement c'est une particularité d'un individu. On a par exemple chez l'être humain le gène de la couleur des yeux qui selon les informations qu'il contient va donner des yeux bleus, verts ou marrons. Le resultat "visible" de l'expression des gènes est ce qu'on appelle le phénotype.

Le génotype est un ensemble de gène, un individu a son génotype qui contient toutes les informations (gènes) permettant de le caractériser.

Le croisement ou crossing over

Le phénomène de croisement dans les AG est une simple adaptation du phénomène génétique, le crossing over. Pour expliquer le crossing over, rappelons d'abord la structure des chromosomes.

Les êtres humains possèdent tous 46 (23 paires) de chromosomes. Ces chromosomes contiennent les gènes qui lorsqu'ils vont s'exprimer donneront le phénotype de l'individu. Dans chaque paire, un chromosome vient de la mère, l'autre du père. Pour transmettre leurs chromosomes, les parents produisent des "gamètes" (cellules qui ont la particularité de ne contenir que 23 chromosomes et pas 46). Lorsque ces gamètes sont créés, les paires sont "mélangées" ce qui va donner un chromosome pouvant contenir des gènes des deux chromosomes de la paire.

Observations de Darwin

L'expression des gènes, le phénotype, conduit à la génération d'un population dont les individus sont tous différents les uns des autres.

Les différences ou particularités de chaque individu vont être décisifs dans le "struggle for life". Ici pour les girafes qui doivent manger des feuilles situées sur des branches hautes, il est clair que plus la girafe a un long cou, plus elle pourra manger abondamment. A chaque génération va donc s'opérer une sélection des mieux adaptés à leur environnement.

De génération en génération ne pourront se reproduire que les individus qui ont survécu grâce à leur particularité avantageuses. En se reproduisant, les gènes qui codent pour ces particularités vont être transmis et, croisés à d'autres gènes, cela va faire évoluer l'espèce à long terme.

Traduction en algorithme

Jusqu'ici, nous sommes restés dans des observations de la nature qui nous ont permis de comprendre un phénomène. Cependant, nous n'avons pas vu en quoi la théorie de l'évolution de Darwin pouvait résoudre des problèmes NP complexes.

Si l'on considère un problème qui comporte plusieurs solutions dont certaines sont meilleures que d'autres, que ces solutions sont composées d'éléments et que l'on peut mélanger ces solutions entre elles, on voit bien le rapprochement avec l'évolution des espèces.

Schématisons le fonctionnement de l'évolution :

Génération Création d’un population aléatoire Evaluation Comparaison des individus On s'arrête si le résultat est satisfaisant Sélection On ne garde que les meilleurs Croisement/Mutation On les fait se reproduire / Évoluer Retour à l’évaluation