Algorithme génétique - Définition

Schéma récapitulatif

1. Population de base générée aléatoirement

   n chaînes de caractères ou de bits.

   1 chaîne correspond à 1 chromosome.

2. Évaluation

   à chaque chaîne, une note correspondant à son adaptation au problème.

3. Sélection

   tirage au sort de n/2 couples de chaînes sur une roue biaisée.

   Chaque chaîne a une probabilité d’être tirée proportionnelle à son adaptation au problème.

   Optimisation possible : si l’individu le plus adapté n’a pas été sélectionné, il est copié d’office dans la génération intermédiaire à la place d’un individu choisi aléatoirement.

4. Croisement et mutation

   Chaque couple donne 2 chaînes filles.

   • Enjambement. Probabilité : 70%. Emplacement de l'enjambement choisi aléatoirement.

     Exemple :

     Chaînes parents : A : 00110100  ; B : 01010010

     Chaînes filles : A’ : 00010010  ; B’ : 01110100

     Croisement en 2 points plus efficace.

   • Mutations des chaînes filles. Probabilité : de 0,1 à 1%.

     Inversion d’un bit au hasard ou remplacement au hasard d’un caractère par un autre.

     Probabilité fixe ou évolutive (auto-adaptation).

     On peut prendre probabilité = 1/nombre de bits.

Les algorithmes génétiques reprennent la théorie de Darwin : sélection naturelle de variations individuelles : les individus les plus adaptés (the fittest) tendent à survivre plus longtemps et à se reproduire plus aisément.

Amélioration de la population très rapide au début (recherche globale) ; de plus en plus lente à mesure que le temps passe (recherche locale).

Convergence : la valeur moyenne de la fonction d’adaptation a tendance à se rapprocher de celle de l’individu le plus adapté : uniformisation croissante de la population.

Le temps de calcul des algorithmes génétiques croît en nln(n), n étant le nombre de variables.

Les limites

• Le temps de calcul : par rapport à d'autres métaheuristiques, ils nécessitent de nombreux calculs, en particulier au niveau de la fonction d'évaluation.
• Ils sont le plus souvent difficiles à mettre en œuvre : des paramètres comme la taille de la population ou le taux de mutation sont parfois difficiles à déterminer. Or le succès de l'évolution en dépend et plusieurs essais sont donc nécessaires, ce qui limite encore l'efficacité de l'algorithme. En outre, choisir une bonne fonction d'évaluation est aussi critique. Celle-ci doit prendre en compte les bons paramètres du problème. Elle doit donc être choisie avec soin.
• Il faut aussi noter l'impossibilité d'être assuré, même après un nombre important de générations, que la solution trouvée soit la meilleure. On peut seulement être sûr que l'on s'est approché de la solution optimale (pour les paramètres et la fonction d'évaluation choisie), sans la certitude de l'avoir atteinte.
• Un autre problème important est celui des optima locaux. En effet, lorsqu'une population évolue, il se peut que certains individus qui à un instant occupent une place importante au sein de cette population deviennent majoritaires. À ce moment, il se peut que la population converge vers cet individu et s'écarte ainsi d'individus plus intéressants mais trop éloignés de l'individu vers lequel on converge. Pour vaincre ce problème, il existe différentes méthodes comme l'ajout de quelques individus générés aléatoirement à chaque génération, des méthodes de sélection différentes de la méthode classique ...