ALGORITHMES GÉNÉTIQUES SIMPLES


Définitions
Un exemple

















































Définitions

         Reproduction
         Croisement
         Mutation


         Nous appelerons "algorithme génétique simple" un algorithme génétique de base ne faisant appel qu´aux trois opérateurs de reproduction, de croisement et de mutation, et qui cherche à optimiser une certaine fonction f (appelée fonction d´adaptation). Les individus sont representés par des chaînes de bits de même dimension, et une population de tels individus a été initialisée aléatoirement.

Reproduction

         Chaque chaîne est copiée avec une probabilité proportionnelle à son adaptation, ce qui revient à donner aux individus les mieux adaptés de meilleures chances de survie et donc de participer à la génération suivante (simulation de la sélection naturelle). Pour cela on créé une roue de loterie "biaisée" sur laquelle chaque secteur représentant un individu a une ouverture proportionnelle à son adaptation. Il suffit alors de faire tourner la roue pour tirer aléatoirement des individus sur lesquels seront ensuite executés d´autres opérateurs génétiques. Par exemple soient une population de 4 chaînes {A,B,C,D}, le tableau suivant donne leur adaptation ai, le total de leur adaptation t=a1 + a2 + a3 + a4 et leur probabilités respectives pi=ai / t:

  Numéro   Chaine   a = Adaptation   Probabilité = a / t
  1   (0,1,1,0,1)   169   0.144444
  2   (1,1,0,0,0)   576   0.492308
  3   (0,1,0,0,0)   64   0.054701
  4   (1,0,0,1,1)   361   0.308547
     Total   1170   1.0


(voir figure 2-1).


Figure 2-1: Reproduction


Croisement

         Les individus choisis par la reproduction sont d´abord appariés. Sur chaque paire de chaîne de bits, est effectué un croisement (ou A)cross-over consistant à choisir aléatoirement un point k de coupure (k étant compris entre 0 et n-2, avec n=longueur des chaînes). Deux nouvelles chaînes sont créées en échangeant les bits de [k+1,n-1]. Par exemple soient les chaînes:
         A = (0,1,1,0,1) et
         B = (1,1,0,0,0)
         On a n = 5, supposons qu´on a tiré k = 2, on obtient les deux nouvelles chaînes de la génération suivante:
         A´ = (0,1,1,0,0) et
         B´ = (1,1,0,0,1)
         (voir figure 2-2).


Figure 2-2: Cross-over


Mutation

         Pour éviter que les croisements ne fassent perdre irrémédiablement des configurations intéressantes, l´opérateur de mutation bruite les chaînes, avec une faible probabilité: Un bit, choisi aléatoirement, est remplacé par 1 s´il vaut 0 et, inversement, remplacé par 0 s´il vaut 1. La fréquence de mutation est de l´ordre de 1/1000.

Un exemple

         Ce paragraphe s´inspire de [GOLDBERG 1991].


         Optimisation d´une fonction simple
         Codage et fonction d´évaluation
         Population initiale
         Reproduction
         Croisement
         Mutation
         Remarque

Optimisation d´une fonction simple

         Soit la fonction f(x) = x 2 définie sur l´intervalle entier I = [0,31].
         L´étude analytique de son maximum est évidente: f est continue et dérivable, on a:
         f´(x) = 2 * x
         qui est positive sur I, donc f est croissante et son maximum est f(31) = 961. Mais expliquons, sur cet exemple simple, comment un algorithme génétique peut travailler en ne faisant aucune hypothèse sur la fonction f.

Codage et fonction d´évaluation

         D´après ce que nous avons dit en 1-3-3-4 nous devons d´abord trouver un codage indépendant du problème, choisons par exemple la représentation binaire de la variable x codée sur 5 bits, ce qui suffit à représenter les nombres compris entre
         0 et 31 = 2 5 - 1:

  x   Écriture en base 2   code(x)
  0   0*16 + 0*8 + 0*4 + 0*2 + 0*1   (0,0,0,0,0)
  1   0*16 + 0*8 + 0*4 + 0*2 + 1*1   (0,0,0,0,1)
  2   0*16 + 0*8 + 0*4 + 1*2 + 0*1   (0,0,0,1,0)
  3   0*16 + 0*8 + 0*4 + 1*2 + 1*1   (0,0,0,1,1)
  4   0*16 + 0*8 + 1*4 + 0*2 + 0*1   (0,0,1,0,0)
  5   0*16 + 0*8 + 1*4 + 0*2 + 1*1   (0,0,1,0,1)
  ...   ...   ...
  31   1* 16 + 1* 8 + 1* 4 + 1* 2 + 1*1   (1,1,1,1,1)



         La fonction à optimiser est f = x 2, choisissons la comme fonction d´adaptation. Ainsi l´adaptation de A = (0,0,0,1,1) est f(3) = 9.

Population initiale

         Tirons aléatoirement par exemple 4 chaînes binaires de 5 éléments:
         A1 = (0,1,1,0,1)
         A2 = (1,1,0,0,0)
         A3 = (0,1,0,0,0)
         A4 = (1,0,0,1,1)

Reproduction

Le tableau suivant donne:
         les chaînes de la population
         leur valeur décimale x
         leur adaptation f(x)
         la somme des adaptations s = somme des f(x)
         La moyenne de la population m = s / 4
         la probabilité de reproduction p = f(x) / s
         le nombre attendu de tirages sur la roue de loterie biaisée:
                  na = f / m
         et un exemple ne de nombre obtenu:

  Numéro   Chaine   x   f(x) = x2   p = f(x) / s   na = f / m   ne
  1   (0,1,1,0,1)   13   169   0.14   0.58   1
  2   (1,1,0,0,0)   24   576   0.49   1.97   2
  3   (0,1,0,0,0)   8   64   0.06   0.22   0
  4   (1,0,0,1,1)   19   361   0.31   1.23   1
             Somme                     1170   1.0   4.0   4.0
             Moyenne                     293   0.25   1.0   1.0
             Maximum                     576   0.49   1.97   2.0


Croisement

         Le tableau suivant donne un exemple de croisements sur 4 individus appariés, d´où la nouvelle population et les nouvelles adaptations.

  Croisement   Numéro de la chaîne séléctionnée   Lieu de croisement   Nouvelle population   x   f(x) = x2
  (0,1,1,0      1)   2   4   (0,1,1,0,0)   12   144
  (1,1,0,0      0)   1   4   (1,1,0,0,1)   25   625
  (1,1      0,0,0)   4   2   (1,1,0,1,1)   27   729
  (1,0      0,1,1)   3   2   (1,0,0,0,0)   16   256
  Somme                                             1754
  Moyenne               439
  Maximum               729


On constate que la somme a augmenté: de 1170 a 1754, de même la moyenne de 293 a 439 et le maximum de 576 a 729.

Mutation

         Dans cette simulation on a négligé le rôle des mutations.

Remarque

         Dans cet exemple particulier il est évident que les chaînes commençant par un 1 (ou plus généralement celles dont les bits de poids faibles sont occupés par des 1) sont plus performantes. On peut se poser la question de savoir si l´observation de certaines similitudes entre les chaînes ne pourrait pas aider à orienter la recherche. C´est ce que nous ferons dans le chapitre suivant en étudiant les schèmes.