LES SCHÈMES


Motifs de similarité
Traitement des schèmes
Dénombrement des schèmes utiles
Hypothèse de la brique élémentaire
Interprétation géometrique de l´espace de recherche

















































Motifs de similarité


         Définitions
       Dénombrement des schèmes
       Dénombrement des schèmes associés à une chaîne
       Effet des opérateurs génétiques sur les schèmes
       Thérème des schèmes (ou théorème fondamental des algorithmes génétiques)

Définitions

         Un schème est un motif de similarité décrivant un sous-ensemble de chaînes avec des similarités à des positions différentes.
         À l´alphabet {0,1} servant à construire les chaînes binaires ajoutons le symbole * qui joue le rôle de "joker" (il peut être remplacé indifféremmant par 0 ou 1). Les schèmes sont alors les chaînes créées à partir de l´alphaber ternaire {0,1,*}. Ainsi à un schème donné correspond toute une classe de chaînes ayant en commun les élément 0 ou 1 du schème.
         Par exemple au schème (*1100) correspondent les deux chaînes (01100) et (11100) qui ont pour ressemblance les 4 bits (numéros 1,2,3 et 4 et qui différent par le bit 0.
         Au schème (*000*) correspondent les 4 chaînes: (00000), (00001), (10000) et (10001) qui ont en commun leurs bits de numéros 1,2 et 3.
         On appelle ordre d´un schème S le nombre de positions instanciées. Par exemple:
         o(0,1,0,*,1) = 4
         o(*,*,*,*,*) = 0
         On appelle longueur utile d´un schème la distance entre la 1ère et la dernière position instanciée. Par exemple:
         u(010*1**) = 4 - 0 = 4
         u(*1*****) = 1 - 1 = 0

Dénombrement des schèmes

         Le nombre de chaînes binaires de longueur 5 construites sur l´alphabet {0,1} est 25 = 32 et le nombre de schèmes construits sur l´alphabet {0,1,*} est 35 = 243. Plus généralement le nombre de chaînes de longueur n construites sur l´alphabet {0,1,...,k} est kn et le nombre de schèmes construits sur l´alphabet étendu {0,1,...,k,*} est (k+1)n.

Dénombrement des schèmes associés à une chaîne

         Soit par exemple la chaîne (1,1,1,1,1), il y a 25 schèmes lui correspondant (obtenus en remplaçant un ou plusieurs éléments de la chaîne par *:
         (1,1,1,1,*)
         (1,1,1,*,1)
         (1,1,1,*,*)
         (1,1,*,1,1)
         (1,1,*,1,*) etc...
         Plus généralement il y a dl schèmes correspondant à une chaîne binaire de longueur l. Une population de n chaînes de longueur l contient entre 2l et n * 2l schèmes (selon la diversité des chaînes: Toutes identiques, différentes ou toutes différentes).

Effet des opérateurs génétiques sur les schèmes

         Soit A(t) = {A1(t),A2(t),...,An(t)} une population de n chaînes à la date t. Supposons que, pour un schème donné H, il y ait m chaînes dérivées de H dans A(t), ce que nous noterons:
         m = m(H,t)
         Lors de la reproduction une chaîne Ai est sélectionnée avec la probabilité:
         pi = fi / s avec:
         fi = adaptation de la chaîne Ai et
         s = somme des adaptations de toutes les chaînes de la population.
         Désignons paf f(H) l´adaptation moyenne des chaînes dérivées de H, on attend, au temps t+1, m(H,t+1) schèmes H:
         m(H,t+1) = m(H,t) * n * f(H) / s
         L´adaptation moyenne f de la population est s / n, donc:
         m(H,t+1) = m(H,t) * f(H) / f
         Les schèmes ayant une adaptation f(H) supérieure à la moyenne f de la population seront davantage copiés, c´est à dire que tous les schèmes d´une population se développent ou dépérissent, en parallèle, en fonction de leur moyenne de schème.
         Supposons que f(H,t+1) = f(H,t) + c * f(H,t), on a:
         m(H,t+1) = m(H,t) * (f(H,t) + c * f(H,t) / f
         m(H,t+1) = m(H,t) * f(H,t) * (1 + c) / f = (1 + c) * m(H,t)
         Ainsi: m(H,1) = (1 + c) * m(H,0) et
         m(H,2) = (1 + c) * m(H,1) = (1 + c)2 * m(H,0)
         Plus généralement: m(H,t) = (1 + c)t * m(H,0)
         Les schèmes au dessus de la moyenne se développent donc exponentionnellement en parallèle.

         Lors d´un croisement un schème survit si la coupure tombe à l´extérieur de sa longueur utile. Par exemple:
         (1***0) est détruit par toute coupure en 1,2 ou 3
         alors que (**01*) n´est détruit que par les coupures 1 et 2.
         Un schème sera plus sûrement détruit s´il a une grande longueur utile et s´il a une petite dimension l, sa probabilité de destruction est donc:
         pd = u(H) / (l - 1)
         Et sa probabilité de survie est: ps = 1 - pd = 1 - u(H) / (l - 1)
         Si le croisement a lieu avec une probabilité pc alors:
         ps >= 1 - pc * u(H) / (l - 1)

         L´effet combiné de la reproduction et du croisement est:
         m(H,t+1) >= (1 - pc * u(H) / (l - 1)) * m(H,t) * f(H) / f
         Les schèmes se développent, ou dépérissent, selon un facteur multiplicatif (croissance ou décroissance exponentielle) et en fonction de leur adaptation (au-dessus ou au-dessous de la moyenne) et de leur longueur utile (petite ou grande).

         En négligeant l´effet des mutations, on en déduit le théorème des schèmes

Thérème des schèmes (ou théorème fondamental des algorithmes génétiques)

Les schèmes de petite longueur utile, d´ordre faible et de performence au-dessus de la moyenne font l´objet d´un nombre de tests exponentiellement croissants au cours des générations successives de la population.


         Pour comprendre l´importance de ce théorème, détaillons l´évolution des schèmes au cours du processus de reproduction en nous appuyant sur l´exemple simple vu au chapitre précédent.

Traitement des schèmes

         Soient H1=1****, H2=*10** et H3=1***0 trois schèmes dont on se propose de suivre l´évolution.
         Reprenons le tableau donnant un exemple de reproduction:

  Numéro   Chaîne   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


         Ainsi que le tableau donnant un exemple de croisement sur 4 individus appariés:

  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 voit que, après la reproduction, trois chaînes ont été produites et qui sont des instances du schème H1:
         (1,1,0,0,1), (1,1,0,1,1) et (1,0,0,0,0)
  Scheme H   Chaîne   f(H)=moyenne d´adaptation
  H1 = 1 * * * * *   2,4   (576+361)/2=469
  H2 = * 1 0 * * *   2,3   (576+64)/2=320
  H3 = 1 * * * * 0   2   576


         Le théorème des schèmes prévoie un nombre de copies (voir 3-1-5):
         nc = m * f(H1) / f
         Or le schème H1 a été utilisé m = 2 fois
         la moyenne du schème H1 est f(H1) = (576+361) / 2 = 469
         et la moyenne de la population est f = 293
         d´ou: nc = 2 * 469 / 293 = 3
         De plus le schème H1 ne peut pas être détruit par un croisement (car il a une longueur utile nulle) et la probabilité de mutation (de l´ordre de 1/1000) est trop faible pour modifier un bit lors des copies. Le nombre de copies donné par le théorème des schèmes est donc 3, ce qui correspond bien au nombre trouvé.

         Étudions la propagation du schème H2=*10**: Il figure deux fois dans la population initiale avec les chaînes (1,1,0,0,0) et (0,1,0,0,0). Après reproduction il y en a deux copies: (1,1,0,0,0) et (1,1,0,0,0).
         Le théorème des schèmes prévoie:
         nc = m * f(H2) / f
         Or m = 2, f(H2) = (576+64) / 2 = 320 et f = 293
         D´où: nc = 2 * 320 / 293 = 2.18          ce qui correspond bien au nombre trouvé.
Après croisement les deux copies sont conservées:
         (1,1,0,0,1) et (1,1,0,1,1).
         Sa longueur utile l = 2 - 1 = 1 est courte, il ne sera rompu qu´ une seule fois sur (5 - l) soit une probabilité de destruction de 0.25, sa probabilité de survie est alors:
         ps = 1 - 0.25 =0 .75
         Le nombre attendu de schèmes H2 après croisement est donc:
         m(H2,t+1) = nc * ps = 2.18 * 0.75 = 1.64
ce qui est proche du nombre 2 effectivement trouvé.
         Étudions de même la propagation du schème H3 = 1***0: Il ne figure qu´une seule fois dans la population initiale avec la chaîne (1,1,0,0,0). Après reproduction il y en a deux exemplaires:
         Le théorème des schèmes prévoie:
         nc = m * f(H3) / f
         Or m = 1, f(H3) = 576 et f = 293
         D´où: nc = 1 * 576 / 293 = 2
         ce qui correspond bien au nombre trouvé.
         La longueur utile de H3 étant grande: l = 4 - 0 = 4 il sera détruit une fois sur (5 - l) soit presque systématiquement, ce qui explique qu´on n´en trouve aucun exemplaire après croisement.

3-3 Dénombrement des schèmes utiles

         On a vu en 3-1-3 que, dans une population de n chaînes binaires de longueur l, il y a entre 2l et n*2l schèmes. Or on vient de voir sur un exemple que les schèmes de grande longueur utile disparaissent plus vite que les autres. D´autre part le théorème des schèmes dit que les schèmes de petite longueur utile, d´ordre faible et de performence au-dessus de la moyenne font l´objet d´un nombre de tests exponentiellement croissants. Holland a montré que ces schèmes efficacement traités sont au nombre de n3 à chaque génération. Il s´agit du parallélisme implicite: À chaque génération la complexité du calcul effectué est proportionnel à la taille n de la population mais il y a n3 schèmes utilement traités en parallèle (sans utilisation de mémoire autre que celle de la population elle-même).

Hypothèse de la brique élémentaire

         Goldberg appelle briques élémentaires les schèmes bien adaptés, de petite longueur utile et d´ordre faible: Ce sont ceux qui sont sélectionnés, recombinés et resélectionnés formant ainsi des chaînes de mieux en mieux adaptées.
         Reprenant l´exemple simple, cherchons à représenter graphiquement certains schèmes. Par exemple des schèmes n´ayant qu´un seul bit instancié couvrent la moitié du domaine avec une fréquence d´oscillation dépendant de la position de ce bit.
         Des schèmes ayant deux bits instanciés couvrent le quart du domaine avec des périodicités qui rappelent les séries de Fourier.


Figure 3-1


Interprétation géométrique de l´espace de recherche

         Soient par exemple une population de chaînes binaires de longueur 3. L´espace de recherche est un espace à 3 dimensions dans lequel les points sont des chaînes (comme 100), des segments représentent des schèmes d´ordre 2 (2 positions instanciées comme *11 ou 10*, des plans représentent des schèmes d´ordre 1 (1 position instanciée comme **0 ou *1*) (voir figure 3-5):


Figure 3-2



         Une population de chaînes de longueur n peut être représentée par un espace de dimension n dans lequel les hyperplans de dimensions p représentent des schèmes d´ordre n-p.