Projet apprentissage de règles

1.1.1. Gestion de projet

1.1.2. Programmation

1.1.3. Algorithmique

1.1.4. Outils pour les interfaces

1.6.1. Deux phases

1.6.2. Personnalisation des exercices

1.8.1. Machines virtuelles

1. Pour remmina
   
   • choisir rdp (remote desktop protocol)
   • nouveau profil de connexion
     • Name : votre choix
     • Group : isima
     • Protocol : doit déjà être rempli avec RDP
     • Server : vm-etu-login où login est à remplacer par votre login
     • Password : vous le mettez ou non…
     • Domain : local.isima.fr
     • … si besoin, remplissez les option de votre choix …
     • Resolution : use client resolution
     • Save !!!
   • sur l’écran principal, dans les préférences (CTRL p), dans l’onglet RDP (tout en bas), cocher ’use client keyboard mapping’ pour conserver votre configuration du clavier. Parfois, cela ne suffit pas (???), il faut alors rechercher dans la liste qui précède cette case à cocher un clavier approprié.
2. Précautions
   

   Cette machine virtuelle n’est pas ’garantie’, elle peut être effacée, remplacée, modifiée à tout moment. Il est par conséquent important que vos document soient présents dans un endroit fiable, par exemple le répertoire ’shared’.

   Une astuce pour disposer aisément de vos fichiers de config si vous utilisez plusieurs machines, est de les placer dans le répertoire ’shared’, et de placer un un lien symbolique vers ces fichiers. Par exemple, pour récupérer une configuration emacs placée dans ’shared’ :

     ln -s "~/shared/.emacs.d" "~/.emacs.d"
   

   Évidemment, les risques de perdre beaucoup de votre travail sont quasi nuls, même si votre ordinateur personnel est capturé par des aliens, car il vous est obligatoire de faire des commits et des pushs très régulièrement.

   Dans l’éventualité ou le répertoire ’shared’ ne serait pas monté, la commande kinit permet parfois de résoudre le problème (essayer au moins trois fois).

1.8.2. Machines personnelles

2.9.1. Chargement d’une image

  #include <SDL2/SDL_image.h>               // Nécessaire pour la fonction IMG_Load
                                            // Penser au flag -lsdl2_image à la compilation
  //...

SDL_Texture* load_texture_from_image(char  *  file_image_name, SDL_Window *window, SDL_Renderer *renderer ){
    SDL_Surface *my_image = NULL;           // Variable de passage
    SDL_Texture* my_texture = NULL;         // La texture

    my_image = IMG_Load(file_image_name);   // Chargement de l'image dans la surface
                                            // image=SDL_LoadBMP(file_image_name); fonction standard de la SDL, 
                                            // uniquement possible si l'image est au format bmp */
    if (my_image == NULL) end_sdl(0, "Chargement de l'image impossible", window, renderer);
   
    my_texture = SDL_CreateTextureFromSurface(renderer, my_image); // Chargement de l'image de la surface vers la texture
    SDL_FreeSurface(my_image);                                     // la SDL_Surface ne sert que comme élément transitoire 
    if (my_texture == NULL) end_sdl(0, "Echec de la transformation de la surface en texture", window, renderer);

    return my_texture;
  }

  //...
  IMG_Quit()                                // Si on charge une librairie SDL, il faut penser à la décharger   

#include <SDL2/SDL_image.h>
// ...
  SDL_Texture *my_texture; 
  my_texture = IMG_LoadTexture(renderer,"./img/Maze.png");
  if (my_texture == NULL) end_sdl(0, "Echec du chargement de l'image dans la texture", window, renderer);
//...
  IMG_Quit() 

   SDL_DestroyTexture(my_texture);

2.9.2. Affichage d’une texture sur la totalité de la fenêtre

  void play_with_texture_1(SDL_Texture *my_texture, SDL_Window *window,
               SDL_Renderer *renderer) {
    SDL_Rect 
        source = {0},                         // Rectangle définissant la zone de la texture à récupérer
        window_dimensions = {0},              // Rectangle définissant la fenêtre, on n'utilisera que largeur et hauteur
        destination = {0};                    // Rectangle définissant où la zone_source doit être déposée dans le renderer

    SDL_GetWindowSize(
    window, &window_dimensions.w,
    &window_dimensions.h);                    // Récupération des dimensions de la fenêtre
    SDL_QueryTexture(my_texture, NULL, NULL,
             &source.w, &source.h);       // Récupération des dimensions de l'image

    destination = window_dimensions;              // On fixe les dimensions de l'affichage à  celles de la fenêtre

    /* On veut afficher la texture de façon à ce que l'image occupe la totalité de la fenêtre */

    SDL_RenderCopy(renderer, my_texture,
           &source,
           &destination);                 // Création de l'élément à afficher
    SDL_RenderPresent(renderer);                  // Affichage
    SDL_Delay(2000);                              // Pause en ms

    SDL_RenderClear(renderer);                    // Effacer la fenêtre
  }

2.9.3. Affichage d’une partie d’une texture à un endroit choisi

  void play_with_texture_2(SDL_Texture* my_texture,
                  SDL_Window* window,
                  SDL_Renderer* renderer) {
       SDL_Rect 
         source = {0},                      // Rectangle définissant la zone de la texture à récupérer
         window_dimensions = {0},           // Rectangle définissant la fenêtre, on n'utilisera que largeur et hauteur
         destination = {0};                 // Rectangle définissant où la zone_source doit être déposée dans le renderer

       SDL_GetWindowSize(
       window, &window_dimensions.w,
       &window_dimensions.h);               // Récupération des dimensions de la fenêtre
       SDL_QueryTexture(my_texture, NULL, NULL,
            &source.w, &source.h);  // Récupération des dimensions de l'image

       float zoom = 1.5;                        // Facteur de zoom à appliquer    
       destination.w = source.w * zoom;         // La destination est un zoom de la source
       destination.h = source.h * zoom;         // La destination est un zoom de la source
       destination.x =
     (window_dimensions.w - destination.w) /2;     // La destination est au milieu de la largeur de la fenêtre
       destination.y =
       (window_dimensions.h - destination.h) / 2;  // La destination est au milieu de la hauteur de la fenêtre

       SDL_RenderCopy(renderer, my_texture,     // Préparation de l'affichage  
              &source,
              &destination);            
       SDL_RenderPresent(renderer);             
       SDL_Delay(1000);                         

       SDL_RenderClear(renderer);               // Effacer la fenêtre
     }

2.9.4. Créer une première animation

  void play_with_texture_3(SDL_Texture* my_texture,
               SDL_Window* window,
               SDL_Renderer* renderer) {
    SDL_Rect 
      source = {0},                             // Rectangle définissant la zone de la texture à récupérer
      window_dimensions = {0},                  // Rectangle définissant la fenêtre, on n'utilisera que largeur et hauteur
      destination = {0};                        // Rectangle définissant où la zone_source doit être déposée dans le renderer
                                
    SDL_GetWindowSize(                      
    window, &window_dimensions.w,               
    &window_dimensions.h);                      // Récupération des dimensions de la fenêtre
    SDL_QueryTexture(my_texture, NULL, NULL,         
                     &source.w,                 
             &source.h);                    // Récupération des dimensions de l'image
                                
    /* On décide de déplacer dans la fenêtre         cette image */
    float zoom = 0.25;                              // Facteur de zoom entre l'image source et l'image affichée
                                
    int nb_it = 200;                                // Nombre d'images de l'animation
    destination.w = source.w * zoom;                // On applique le zoom sur la largeur
    destination.h = source.h * zoom;                // On applique le zoom sur la hauteur
    destination.x =                     
    (window_dimensions.w - destination.w) / 2;  // On centre en largeur
    float h = window_dimensions.h - destination.h;  // hauteur du déplacement à effectuer

    for (int i = 0; i < nb_it; ++i) {
      destination.y =
      h * (1 - exp(-5.0 * i / nb_it) / 2 *
               (1 + cos(10.0 * i / nb_it * 2 *
                M_PI)));            // hauteur en fonction du numéro d'image

      SDL_RenderClear(renderer);                    // Effacer l'image précédente

      SDL_SetTextureAlphaMod(my_texture,(1.0-1.0*i/nb_it)*255);      // L'opacité va passer de 255 à 0 au fil de l'animation
      SDL_RenderCopy(renderer, my_texture, &source, &destination);   // Préparation de l'affichage
      SDL_RenderPresent(renderer);                  // Affichage de la nouvelle image
      SDL_Delay(30);                                // Pause en ms
    }                               
    SDL_RenderClear(renderer);                      // Effacer la fenêtre une fois le travail terminé
  }

2.9.5. Et si on veut animer un ’sprite’ ?

  void play_with_texture_4(SDL_Texture* my_texture,
               SDL_Window* window,
               SDL_Renderer* renderer) {
     SDL_Rect 
           source = {0},                    // Rectangle définissant la zone totale de la planche
           window_dimensions = {0},         // Rectangle définissant la fenêtre, on n'utilisera que largeur et hauteur
           destination = {0},               // Rectangle définissant où la zone_source doit être déposée dans le renderer
           state = {0};                     // Rectangle de la vignette en cours dans la planche 

     SDL_GetWindowSize(window,              // Récupération des dimensions de la fenêtre
               &window_dimensions.w,
               &window_dimensions.h);
     SDL_QueryTexture(my_texture,           // Récupération des dimensions de l'image
              NULL, NULL,
              &source.w, &source.h);

     /* Mais pourquoi prendre la totalité de l'image, on peut n'en afficher qu'un morceau, et changer de morceau :-) */

     int nb_images = 8;                     // Il y a 8 vignette dans la ligne de l'image qui nous intéresse
     float zoom = 2;                        // zoom, car ces images sont un peu petites
     int offset_x = source.w / nb_images,   // La largeur d'une vignette de l'image, marche car la planche est bien réglée
         offset_y = source.h / 4;           // La hauteur d'une vignette de l'image, marche car la planche est bien réglée
       

     state.x = 0 ;                          // La première vignette est en début de ligne
     state.y = 3 * offset_y;                // On s'intéresse à la 4ème ligne, le bonhomme qui court
     state.w = offset_x;                    // Largeur de la vignette
     state.h = offset_y;                    // Hauteur de la vignette

     destination.w = offset_x * zoom;       // Largeur du sprite à l'écran
     destination.h = offset_y * zoom;       // Hauteur du sprite à l'écran

     destination.y =                        // La course se fait en milieu d'écran (en vertical)
       (window_dimensions.h - destination.h) /2;

     int speed = 9;
     for (int x = 0; x < window_dimensions.w - destination.w; x += speed) {
       destination.x = x;                   // Position en x pour l'affichage du sprite
       state.x += offset_x;                 // On passe à la vignette suivante dans l'image
       state.x %= source.w;                 // La vignette qui suit celle de fin de ligne est
                        // celle de début de ligne

       SDL_RenderClear(renderer);           // Effacer l'image précédente avant de dessiner la nouvelle
       SDL_RenderCopy(renderer, my_texture, // Préparation de l'affichage
              &state,
              &destination);  
       SDL_RenderPresent(renderer);         // Affichage
       SDL_Delay(80);                       // Pause en ms
     }
     SDL_RenderClear(renderer);             // Effacer la fenêtre avant de rendre la main
       }

2.9.6. Et le fond ?

    void play_with_texture_5(SDL_Texture *bg_texture,
                 SDL_Texture *my_texture,
                 SDL_Window *window,
                 SDL_Renderer *renderer) {
    SDL_Rect
      source = {0},                             // Rectangle définissant la zone de la texture à récupérer
      window_dimensions = {0},                  // Rectangle définissant la fenêtre, on  n'utilisera que largeur et hauteur
      destination = {0};                        // Rectangle définissant où la zone_source doit être déposée dans le renderer

    SDL_GetWindowSize(window,                   // Récupération des dimensions de la fenêtre
              &window_dimensions.w, 
              &window_dimensions.h); 
    SDL_QueryTexture(my_texture, NULL, NULL,    // Récupération des dimensions de l'image
             &source.w, &source.h); 

    int nb_images = 40;                         //  Il y a 8 vignette dans la ligne qui nous intéresse
    int nb_images_animation = 1 * nb_images;    // 
    float zoom = 2;                             // zoom, car ces images sont un peu petites
    int offset_x = source.w / 4,                // La largeur d'une vignette de l'image
    offset_y = source.h / 5;                // La hauteur d'une vignette de l'image
    SDL_Rect state[40];                         // Tableau qui stocke les vignettes dans le bon ordre pour l'animation

    /* construction des différents rectangles autour de chacune des vignettes de la planche */
    int i = 0;                                   
    for (int y = 0; y < source.h ; y += offset_y) {
      for (int x = 0; x < source.w; x += offset_x) {
    state[i].x = x;
    state[i].y = y;
    state[i].w = offset_x;
    state[i].h = offset_y;
    ++i;
      }
    }
                                                // ivaut 20 en sortie de boucle
    state[15]  = state[14]                      // on fabrique des images 14 et 15 en reprenant la 13  
              = state[13];                      // donc state[13 à 15] ont la même image, le monstre ne bouge pas   

    for(; i< nb_images ; ++i){                  // reprise du début de l'animation en sens inverse  
      state[i] = state[39-i];                   // 20 == 19 ; 21 == 18 ; ... 39 == 0  
    }

    destination.w = offset_x * zoom;            // Largeur du sprite à l'écran
    destination.h = offset_y * zoom;            // Hauteur du sprite à l'écran
    destination.x = window_dimensions.w * 0.75; // Position en x pour l'affichage du sprite
    destination.y = window_dimensions.h * 0.7;  // Position en y pour l'affichage du sprite

    i = 0;
    for (int cpt = 0; cpt < nb_images_amination ; ++cpt) {
      play_with_texture_1_1(bg_texture,         // identique à play_with_texture_1, où on a enlevé l'affichage et la pause
                window, renderer); 
      SDL_RenderCopy(renderer,                  // Préparation de l'affichage
             my_texture, &state[i], &destination);
      i = (i + 1) % nb_images;                  // Passage à l'image suivante, le modulo car l'animation est cyclique 
      SDL_RenderPresent(renderer);              // Affichage
      SDL_Delay(100);                           // Pause en ms
    }
    SDL_RenderClear(renderer);                  // Effacer la fenêtre avant de rendre la main
  }

2.9.7. Gestion de la parallaxe

2.9.8. Résultat

2.9.9. Travail à réaliser : une animation

3.1.1. Créer un cache pour limiter le évaluations

    typedef struct{
      bool_t updated;
      configuration_t configuration;
      float evaluation;
    } configurationEvaluated_t;

3.2.1. Problème

3.2.2. Formalisation

3.2.3. Travail à réaliser

1. Génération d’un graphe connexe aléatoire
   

   Un algorithme possible qui ne génère pas une distribution uniforme sur l’ensemble des graphes connexes, mais qui est suffisant (voire plus intéressant) par rapport à notre objectif car il va permettre de régler aisément la densité du graphe. Il n’est pas évident que ce code soit particulièrement efficace, mais comme il n’est pas exécuté fréquemment, il n’est pas nécessaire de chercher à tout prix la vitesse d’exécution.

   • Choisir un entier N, les sommets du graphes sont alors \(\{0, 1, ..., N-1\}\),
   • Phase 1 : création d’un arbre binaire couvrant du futur graphe (c’est cette phase ui permet de garantir que le graphe résultat sera connexe) La fonction python qui suit génère un arbre binaire sous forme d’une matrice d’adjacence, avec l’idée suivante :
     • prendre la liste des sommets, le premier sommet sera la racine,
     • couper ce qui reste en deux (gauche/droite), la partie gauche permettra de fabriquer le sous-arbre de gauche, la partie droite le sous-arbre de droite.

   import random
   def genere(matrice, bas, haut):
       if bas < haut:
           k = random.randint(bas+1, haut)
           matrice[bas][bas+1] = 1
           matrice[bas+1][bas] = 1
           if k+1 <= haut:
               matrice[bas][k+1] = 1
               matrice[k+1][bas] = 1
           genere(matrice,bas+1, k)
           genere(matrice, k+1, haut)
   
   random.seed(42)
   matrice = [[0]*N for _ in range(N)]
   genere(matrice, 0, N-1)
   return matrice
   

   0	1	0	1	0	0	0	0	0	0
   1	0	1	0	0	0	0	0	0	0
   0	1	0	0	0	0	0	0	0	0
   1	0	0	0	1	0	0	0	0	0
   0	0	0	1	0	1	0	0	1	0
   0	0	0	0	1	0	1	1	0	0
   0	0	0	0	0	1	0	0	0	0
   0	0	0	0	0	1	0	0	0	0
   0	0	0	0	1	0	0	0	0	1
   0	0	0	0	0	0	0	0	1	0

   Ce que l’on interprète graphiquement par :

   

   • Ajouter des arêtes au graphe de façon aléatoire. En fonction de la valeur de \(p\) choisie dans l’algorithme suivant, on obtiendra un graphe plus ou moins dense:
     • \(p=0 \longrightarrow\) l’arbre obtenu précédemment sans altération,
     • \(p=1 \longrightarrow\) graphe complet,
     • sur le graphique qui suit : \(p=0.1\)

   import random
   
   def genereGraphe(matrice, p):
       N = len(matrice)
       for i in range(N):
         for j in range(i+1, N):
           if random.random()<p:
               matrice[i][j] = 1
               matrice[i][j] = 1
   
   random.seed(42)
   genereGraphe(matrice, p)
   return matrice
   

   0	1	1	1	0	0	0	0	1	0
   1	0	1	0	0	1	0	0	0	0
   0	1	0	0	0	1	0	0	0	0
   1	0	0	0	1	0	1	1	0	0
   0	0	0	1	0	1	0	0	1	0
   0	0	0	0	1	0	1	1	0	0
   0	0	0	0	0	1	0	0	0	1
   0	0	0	0	0	1	0	0	0	0
   0	0	0	0	1	0	0	0	0	1
   0	0	0	0	0	0	0	0	1	0

   qui a pour représentation graphique :

   

2. Positionnement du graphe dans le plan
   

   Pour obtenir un graphe positionné dans le plan:

   • choisir les coordonnées de tous les nœuds dans l’espace image,
   • appliquer l’algorithme précédent pour choisir quelles sont les arêtes qui existent,
   • calculer les distances euclidiennes qui serviront de valuations aux arcs.

3.2.4. Recherche d’un chemin particulier

3.2.5. Se ramener à un cas classique

3.3.1. Méthode exhaustive

3.3.2. Recherche locale

1. Un exemple : une phrase auto-référente
   

   

   Figure 11 : Un livre à l’origine de beaucoup de vocations en IA, avec des problèmes d’autoréférence

   Le problème ici est de déterminer les valeurs des variable entières dans \([1..12]\) de \(a_0\), …, \(a_9\), de façon à rendre la phrase vraie.

   Cette phrase contient :
       - \(a_0\) chiffres 0,
       - \(a_1\) chiffres 1,
       - \(a_2\) chiffres 2,
       - \(a_3\) chiffres 3,
       - …
       - \(a_9\) chiffres 9.
   

   Si la famille de transformations est ’choisir une des lignes et modifier une la valeur du \(a_i\) de la ligne’, et la fonction objectif (que l’on minimise ici) est le nombre de \(a_i\) incorrects, alors la fonction objectif semble extrêmement chaotique… Est-ce vraiment le cas ? Pour le savoir on code une résolution avec une méthode gloutonne exhaustive, et on examine le résultat.

2. Expérimentation
   
   • Une situation est représentée par une liste de 10 éléments, en position \(i\) se trouve une valeur de \(a_i\),

   • la fonction printL affiche la phrase au format de l’exemple ci-dessus,

     def printL(L):
         print("Cette phrase contient :")
         for i, v in enumerate(L):
             print("\t-", v, "chiffres", i)
     

   • les fonctions energy1 et energy2 sont des fonctions d’évaluation, elles valent toutes les deux 0 lorsqu’une solution est trouvée (et sont strictement positives partout ailleurs), energy1 semble plus précise que energy2 (mais cela ne signifie pas qu’elle est meilleure),

     def energy1(L):
         nbErrors = 0
         tabCount = [1] * 10
         for v in L:
             for c in str(v):
                 tabCount[int(c)] += 1
     
         for v, c in zip(L, tabCount):
             nbErrors += abs(v - c)
         return nbErrors
     
     def energy2(L):
         nbErrors = 0
         tabCount = [1] * 10
         for v in L:
             for c in str(v):
                 tabCount[int(c)] += 1
     
         for v, c in zip(L, tabCount):
             nbErrors += v != c
         return nbErrors
     

   • les fonction generateState servent à définir les voisinages, en indiquant vers quel état il est possible de transiter à l’itération suivante:
     • generateState1 : choisit un des \(a_i\) et lui assigne une valeur aléatoire,
     • generateState2 : choisit un des \(a_i\),
       • avec une probabilité de 1% lui assigne une valeur aléatoire
       • avec une probabilité de 99% lui assigne une valeur v qui est la somme d’une valeur aléatoire dans \([-2..2]\) et de la valeur qui est celle que l’on aimerait mettre pour corriger la phrase au mieux (on compte combien il y a actuellement de \(i\) sans compter ceux qui sont dans \(a_i\)).
     • generateState3 : choisit aléatoirement un des \(a_i\) et essaie toutes les valeurs possibles, renvoie celui qui minimise l’erreur,
     • generateState4 : essaie pour chacun des \(a_i\) depuis la valeur -1 à la valeur +1 et conserve la meilleure ; à moins que l’on soit sur les bords du domaine, le nombre de possibilités testées ici est \(3^{10} = 59049\)
     • generateState5 : essaie toutes les possibilités sur une variable ; attention, cette fonction devra être encapsulée pour définir quelle variable doit être optimisée.

   def generateState1(L):
       M = list(L)
       M[random.randint(0, 9)] = random.randint(1, 12)
       return M
   
   def generateState2(L, bord = 2):
       M = list(L)
       pos = random.randint(0, 9)
       if random.random() < 0.01:
           a = random.randint(1, 12)
       else:
           a = 1
           for v in L:
               a += str(v).count(str(pos))
               a -= str(pos).count(str(pos))
               M[pos] = min(12, max(0, a + random.randint(-bord, bord)))
       return M
   
   def generateState3(L, energy):
       M = list(L)
       bestM = list(M)
       bestE=energy(M)
       pos = random.randint(0, 9)
       for i in range(1,13):
           M[pos] = i
           E= energy(M)
           if E<bestE:
               bestE = E
               bestM = list(M)
       return M
   
   def generateState4(L, energy, bord = 1):
       bestE = energy(L)
       bestL = list(L)
       def positionI(L,i):
           nonlocal bestE
           nonlocal bestL
           for v in range(max(1,L[i]-bord), 1+min(12,L[i]+bord)):
               L[i] = v
               E = energy(L)
               if E < bestE:
                   bestE = E
                   bestL = list(L)
               if i<9:
                   positionI(L,i+1)
   
       positionI(L,0)
       return bestL
   
   def generateState5(state, pos, energy):
       state[pos] = 1
       bestValue = 1
       state[pos] = bestValue
       bestEnergy = energy(state)
       for value in range(2, 12 + 1):
           state[pos] = value
           E = energy(state)
           if E < bestEnergy:
               bestValue = value
               bestEnergy = E
       state[pos] = bestValue
   

   Il ne reste alors plus qu’à tester et comparer les différentes méthode sur ce problème, car malheureusement on ne pourra pas en conclure sur ce qui se passe sur un autre problème, car comme maintenant vous devez vous en douter, le choix des transformations (déterministe/ stochastique, taille du voisinage,…) ont énormément d’influence sur le résultat et sont dépendants de la structure du problème.

3. Recuit simulé : une recherche locale où on peut remonter
   

   

   Le recuit simulé est une méthode qui permet de s’attaquer au problème des minimums locaux trop fréquents. Dans cet algorithme la fonction à optimiser (ici minimiser) s’appelle l’énergie du système et les situations sur lesquelles on calcule cette énergie des configurations. Ce vocabulaire est originaire de la métallurgie et de la thermodynamique qui ont été les inspiratrices de cette méthode. Son principe est :

   • partir d’un état quelconque,
   • essayer une transformation sur cet état,
     • si l’état atteint est d’énergie plus faible que l’état actuel, alors il devient le nouvel état courant,
     • si l’état atteint est d’énergie supérieure à l’état actuel, il ne devient le nouvel état qu’avec une certaine probabilité.

   Le passage de configuration en configuration se poursuit indéfiniment, en diminuant au fil du temps la probabilité d’accepter des configurations moins avantageuses.

   La façon la plus classique de déterminer le passage (ou non) d’un état actuel à un nouvel état est la règle de Metropolis :

   • si l’énergie du nouvel état est strictement inférieure à l’énergie de l’état actuel, on accepte la transition (lorsqu’on trouve mieux que ce que l’on a, sans se poser de question, on accepte),
   • sinon, ce n’est qu’avec la probabilité \(p = e^\frac{-\Delta E}{T}\) que l’on accepte la transition vers ce nouvel état (\(\Delta E = E_\text{nouvel état}-E_\text{ancien état}\)). C’est cette possibilité de ’remonter’ qui va permettre de quitter un minimum local.

   Le paramètre \(T\) de la formule s’appelle la température (strictement positif). A haute température, la probabilité d’accepter un état moins bon que celui où l’on était est haute, à basse température elle est infime. Ce paramètre de température va diminuer au fil de l’exécution de l’algorithme, rendant la possibilité d’accepter des transitions défavorables de plus en plus faibles (pour T proche de 0, on est revenu à un algorithme glouton).

   Ce qui rend cet algorithme très intéressant est que sous certaines hypothèses, on garantit qu’avec une probabilité de 1, il converge vers un minimum global de la fonction. Les conditions de validité de cette affirmation sont que :

   • chaque état doit être accessible en un nombre fini d’étapes et ce avec une probabilité non nulle à tout instant de l’algorithme,
   • le nombre d’états doit être au plus dénombrable.

   Le seul souci dans ce théorème est que pour garantir cette propriété, la température doit décroître très lentement. Un théorème de Hajek prouve que si on note \(h^+\) la différence entre l’énergie maximale possible et l’énergie minimale possible que peut atteindre le système, pour toute valeur \(h\geq h^+\), si on choisit comme température à l’itération \(n\) \(T_n = \frac{h}{\log n}\) alors la décroissance est suffisamment lente pour que la propriété soit validée. Malheureusement… cette décroissance est terriblement lente, et n’est en général pas utilisable en pratique. On va donc la faire décroître plus rapidement, ce qui va faire perdre le théorème, et pratiquement, risque d’entraîner une convergence vers un minimum qui n’est pas global (mais que l’on espère d’énergie proche de celle du minimum, sous condition de ne pas faire descendre la température trop vite). Il existe plusieurs plans de recuit (c’est le nom que l’on donne à la méthode choisie pour réaliser la baisse de la température). On peut :

   • diminuer la température à chaque itération,
   • conserver la même température sur un pallier, et lorsqu’une certaine condition est vérifiée (par exemple : « il y a eu au moins 10 changements d’état ou on a essayé 1000 configurations ») diminuer la température pour passer au pallier suivant.

   Pour diminuer la température, deux méthodes sont fréquemment utilisées :

   • décroissance linéaire : \(T_{n} = \frac{A}{B+n}\) où \(A > 0\) et \(B \geq 0\) sont des constantes (à trouver par expérimentation),
   • décroissance géométrique \(T_{n+1} = \alpha \times T_n\) avec \(0<\alpha <1\) et \(\alpha\) très proche de 1 (0.999 par exemple, mais à régler par expérimentation, et évidemment plus petit si on utilise des palliers que si on n’en utilise pas).
   1. Astuce
      

      Parfois, l’algorithme s’égare dans des zones peu pertinentes (la température est descendue trop vite, et il va être difficile de quitter la zone dans laquelle l’état actuel se trouve). Pour remédier à cela on peut :

      • diminuer moins vite la température (solution simple, mais qui parfois est très coûteuse en temps de calcul),
      • relancer plusieurs fois l’algorithme, en stockant les meilleurs résultats, et en les choisissant comme graine de départ que l’on peut utiliser lorsque l’algorithme se ’perd’.
   2. Phrases autoréférentes et recuit
      

      Le code suivant permet d’obtenir des solutions au problèmes présenté précédemment des phrases auto référentes:

      • en entrée :
        • l’état actuel,
        • la température,
        • la fonction d’énegie.
      • en sortie :
        • le nouvel état
        • un booléen valant True si et seulement si la transition a été acceptée

      def generateStateSimulatedAnnealing(state, T, energy):
          E = energy(state)
          newState = generateState(state) # can use any generateState
          E_newState = energy(newState)
          if E_newState < E:
              return newState, True, E_newState
          else:
              deltaE = E_newState - E
              p = exp(-deltaE / T)
              if random.random() < p:
                  return newState, True, E_newState
              else:
                  return state, False
      

      Cette fonction va être appelée, avec la température qui va décroître au fil des itérations. Ici, le programme de recuit met en place des paliers : la température est constante sur un palier, on change de palier si on y est resté assez longtemps, ou si on a déjà accepté beaucoup de transitions.

      def simulatedAnnealing(initialTemperature = 30, stageLength = 1000, nbAcceptations = 100, energy = energy1 ):
          T = initialTemperature # This value of 30 comes from the estimation of the difference between high and low energies with energy1
          state = [random.randint(0, 13) for _ in range(10)]
      
          nbAccepts = 0
          i = 0
          while True: #infinite loop, maybe it would be fine to leave it one day and obtain results :D
              state, accepted = generateStateSimulatedAnnealing(state, T, energy1)
              nbAccepts += accepted # adds 0 or 1 depending of the boolean value
              if nbAccepts == nbAcceptations or i % stageLength == 0:
                  print(state)
                  print("\tItération :", i, "\tTempérature :", T, "\tEnergie :", energy(state))
                  nbAccepts = 0
                  T = T * 0.9994
              i += 1
      

4. Méthode tabou
   

   

   Figure 12 : La méthode tabou : interdire les états que l’on vient vient juste d’explorer

   La méthode tabou est un algorithme de recherche locale, qui comme le recuit simulé vise à autoriser à transiter de temps en temps vers des états de moindre intéret. Il utilise une file d’états de taille fixe \(K\) qui contient à tout instant la liste des \(K\) états dernièrement visités. A chaque itération de l’algorithme :

   • si tous les états accessibles sont dans la file des tabous, il en choisit un au hasard (normalement cette situation est extrêmement rare, voire ne se produit jamais, et si elle se produit on peut préférer relancer l’algorithme complètement),
   • sinon, le nouvel état est:
     • le meilleur de tous les états qui ne sont pas dans la file des tabous (choix 1),
     • le premier état que l’on trouve qui est meilleur que l’état actuel (et qui n’est pas tabou), ou le meilleur état qui n’est pas tabou.

   Par conséquent, si le meilleur état accessible n’est pas bon… il est tout de même le meilleur et il est donc accédé.

   Une des difficultés de cette méthode est de configurer la taille de la liste des tabous:

   • si elle est trop courte, il n’est pas possible de remonter pendant longtemps (en particulier plus on élève la dimension, plus il y a de sentiers et de façons de descendre dans une vallée locale), et donc quitter un minimum local large est impossible,
   • si elle est trop longue, il n’y a pas de possibilité d’essayer de petites variations qui permettraient de découvrir un petit chemin qui mène à un bon minimum.

   On se rend compte que la longueur de la liste des tabous devrait dépendre de :

   • la forme de la fonction d’évaluation au voisinage du point courant : plus elle est plate, plus la liste est longue
   • du moment de l’algorithme : lorsqu’on cherche une bonne zone, on privilégie une liste de tabous longue ; lorsqu’on cherche à améliorer au mieux une solution (et donc qu’on a déjà choisi la zone) on préférerait utiliser une liste de tabous plus courte.

   On peut améliorer les résultats de la méthode tabou en s’inspirant de l’idée de tabou, en introduisant des tabous moins rigides qui défavorisent des configurations qui ne semblent pas prometteuses:

   • cette zone a déjà été très explorée
   • ce type de solutions a peu de chances d’aboutir à de bons résultats (pour des raisons logiques, ou parce que statistiquement depuis le début de l’exécution ce type de solution n’a mené à aucune solution de qualité)
   • …

   Ce type de tabous, plus difficiles à mettre en œuvre, permettent d’obtenir des comportements faisant intervenir une guidance à moyen ou à long terme. On peut en particulier :

   • favoriser les endroits / motifs qui ont étés les plus fructueux jusqu’ici : on réalise aux bons endroits une intensification des recherches,
   • favoriser la diversification : si certaines zones n’ont jamais été approchées, il peut être intéressant de se téléporter dans l’une d’entre elles plutôt que de rester dans des zonees très connues.

   On peut alors remarquer qu’en étendant cette notion de tabou, le recuit simulé devient alors un cas particulier de la recherche tabou, les états tabous devenant en fait ’tabous avec une certaine probabilité’.

   Le code suivant illustre la méthode la plus simple de recherche tabou, qui n’utilise que la version originale : la liste des derniers états sont totalement tabous.

   • La première version converge vers un minimum local rarement pertinent (à peu près indépendamment de la longueur de tabus) et n’est pas très efficace,
   • la seconde converge bien, mais n’a pas vraiment besoin de la méthode tabou, il suffit de la relancer quelques fois pour avoir une solution, avec une liste de tabous ne contenant que la position actuelle (K=1).

   Sur ce problème, cette méthode ne semble guère pertinente, mais cela ne la remet pas en cause pour autant sur d’autres problèmes.

   def generateState4Tabu(state, tabus, energy, bord=1):
       bestStates = []
       bestE = 1000  # infinity
       tabus[0][tabus[1]] = list(state)
       tabus[1] = (tabus[1] + 1) % len(tabus[0])
   
       def positionI(state, i):
           nonlocal bestE
           nonlocal bestStates
           left = max(1, state[i] - bord)
           right = min(12, state[i] + bord)
           L = []
           for v in range(left, right + 1):
               state[i] = v
               if state not in tabus[0]:
                   E = energy(state)
                   if E == bestE:
                       bestStates.append(list(state))
                   elif E < bestE:
                       bestE = E
                       bestStates = [list(state)]
               if i < 9:
                   positionI(state, i + 1)
   
       positionI(state, 0)
       if len(bestStates) == 0:
           print("Pas d'état accessible à cause des tabous")
           bestState = [random.randint(1, 12) for _ in range(10)]
       else:
           bestState = random.choice(bestStates)
       return bestState
   
   
   def generateState7Tabu(state, tabus, energy, bord=1):
       bestStates = []
       bestE = 1000  # infinity
       tabus[0][tabus[1]] = list(state)
       tabus[1] = (tabus[1] + 1) % len(tabus[0])
   
       def bestInPos(state, i):
           nonlocal bestE
           nonlocal bestStates
           for v in range(1, 13):
               state[i] = v
               if state not in tabus[0]:
                   E = energy(state)
                   if E == bestE:
                       bestStates.append(list(state))
                   elif E < bestE:
                       bestE = E
                       bestStates = [list(state)]
   
       def bestPos(state):
           tabCount = [1] * 10
           for v in state:
               for c in str(v):
                   tabCount[int(c)] += 1
   
           nbErrors = -1
           pos = []
           for (i, (v, c)) in enumerate(zip(state, tabCount)):
               if abs(v - c) > nbErrors:
                   nbErrors = abs(v - c)
                   pos = [i]
               elif abs(v - c) == nbErrors:
                   pos.append(i)
   
           return random.choice(pos)
   
       bestInPos(state, bestPos(state))
       if len(bestStates) == 0:
           print("Pas d'état accessible à cause des tabous")
           bestState = [random.randint(1, 12) for _ in range(10)]
       else:
           bestState = random.choice(bestStates)
       return bestState
   
   
   
   def tabu(K=10, energy=energy1):
       state = [random.randint(1, 12) for _ in range(10)]
       tabuQueue = [[None] * K, 0] # queue of size K : the first element is the list of tabus, the second element the position of the nest insertion
       cpt = 0
       mini = 1000 # infinity
       found = set() # will countain the different solutions (E = 0)
       while True:  # cpt < 10:
           state = generateState7Tabu(state, tabuQueue, energy1, 1) # this functin or the other
           E = energy1(state)
           if E < mini:
               mini = E
               print(state, end="\t<<< ")
               print("Itération :", cpt, "\tEnergie :", E)
           elif E == 0:
               found.add(str(state))
               print("Trouvé :", state)
               print(found)
               tabuQueue = [[None] * K, 0]
               state = [random.randint(1, 12) for _ in range(10)]
               print(state)
           elif cpt % 100000 == 0: #just to have something on screen from time to time
               print(state, end="\t--- ")
               print(tabuQueue[0])
               print("Itération :", cpt, "\tEnergie :", E)
           cpt += 1
   
   

3.3.3. Méthodes constructives

1. Méthodes gloutonnes
   

   Ces méthodes sont souvent utilisées pour initialiser un autre algorithme en fournissant un point de départ qui n’est pas trop mauvais. Comme ce sont des méthodes qui font le ’meilleur’ choix par rapport à un critère donné sans jamais remettre en cause les choix précédents, elles sont généralement très peu coûteuses ; si de plus l’heuristique choisie pour décider ce qui est le mieux est assez pertinente, on peut obtenir des solutions qui, au moins sur les instances simples, sont assez proches de l’optimum.

   Dans le cas du voyageur de commerce, une heuristique gloutonne assez simple consiste à choisir comme prochaine ville du circuit la ville la plus proche qui ne fait pas encore partie de la tournée, et quand toutes les villes ont été incorporées, revenir au point de départ.

   Tout se passe très bien dans ce premier cas avec un coût total de 35 qui est effectivement l’optimum :

   • départ de a
   • le plus proche est b
   • puis c
   • puis d
   • et finalement a

   

   Mais sur celui qui suit, assez similaire, le coût total est 37 alors que le meilleur coût est 36 (acdba) :

   • départ de a
   • le plus proche est b
   • puis c
   • puis d
   • et finalement a

   

2. Colonies de fourmis
   

   

   Figure 13 : Est-ce vraiment le meilleur chemin ?

   1. Idée originelle
      

      L’observation de fourmis a permis de remarquer que lorsqu’elles trouvent une source de nourriture, elles partagent l’information avec le reste de la fourmilière ou les fourmis proches. Afin de la rapporter à la fourmilière, le trajet suivi par les fourmis s’améliore. Il y a émergence d’une intelligence collective qui a optimisé le circuit. Pour obtenir ce résultat, les fourmis vont laisser des traces, appelées phéromones (sortes d’hormones) sur les chemins qu’elles empruntent. Examinons comment un mécanisme local très simple va permettre de faire émerger une solution globale de qualité.

      On s’intéresse à la situation représentée par le graphe suivant où les valuations des arrêtes représentent les temps de parcours.

      

      Une fourmi part de la fourmilière, à chaque intersection elle choisit au hasard l’arc qu’elle parcourt, en déposant à chaque déplacement un peu de phéromones. Un fois le miel découvert elle revient à la fourmilière en déposant le long du chemin des phéromones. Une autre fourmi arrive, quand elle doit choisir un arc, elle choisit chaque arc avec un hasard légèrement biaisé par la présence de phéromones qui l’attirent. une fois arrivée au miel, elle repart en déposant des phéromones sur son chemin du retour.

      On se place dans la situation où :

      • les chemins ACB et AB sont au départ équiprobables,
      • à chaque date de temps, 1 fourmi emprunte BA et 1 fourmi emprunte BCA.

      Après 10 minutes, 9 fourmis sont arrivées en A et ont déposé des phéromones sur le trajet AB, aucune n’est encore arrivée par BCA, le chemin le plus court est plus renforcé que l’autre, et le phénomène va s’auto-entretenir, et renforcer de plus en plus le chemin le plus court.

      Si malgré cela (le hasard n’a pas bien fait les choses…), le plein régime arrive, il y a alors autant de fourmis qui arrivent par chacun des deux chemins par unité de temps, mais comme les phéromones sont volatiles, et le temps plus long pour parcourir BCA, il y a donc plus de phéromones restantes sur le trajet BA que sur le trajet BCA, le phénomène s’auto-amplifiant, le chemin AB deviendra alors de plus en plus prépondérant.

   2. Adaptation à l’informatique
      

      La métaheuristique des colonies de fourmis est une méthode constructive qui va relancer plusieurs fois la construction, et essayer d’extraire des informations statistiques des constructions précédemment réalisées. Le point de départ est une heuristique gloutonne qui va être améliorée afin de tenir compte des réussites et des échecs des constructions précédentes.

      Chaque fourmi va construire une solution. La colonie complète part à la recherche d’une solution :

      • Après avoir trouvé sa solution, chaque fourmi indique sur tout le trajet qu’elle a suivi sa satisfaction par des phéromones qu’elle dépose sur chacun des choix qu’elle a effectué, ces phéromones sont d’autant plus puissantes qu’elle est satisfaite de sa solution.
      • La nuit passe, une partie des phéromones s’évapore.
      • Le lendemain chaque fourmi repart, mais lorsqu’elle effectue un choix, elle va prendre en compte son a priori (la méthode gloutonne), et la quantité de phéromones sur chacun des choix. Une fois qu’elle aura construit sa solution, elle reviendra comme son aînée déposer une quantité de phéromones proportionnelle à sa satisfaction sur chacun des choix qu’elle a effectué.

      Au fil des jours, les choix qui produisent les meilleurs résultats vont amasser des phéromones, et il va y avoir émergence des meilleures constructions…

   3. Application de l’idée aux phrases auto-référentes
      
      • apriori a pour entrée un état et une position et renvoie la liste des évaluations obtenues en parcourant toutes les valeurs possibles en position pos, les autres variables étant inchangées.

      def apriori(state,pos):
          qualities =[1000]*12
          save = state[pos]
          for v in range(1,13):
              state[pos] = v
              qualities[v-1] = energy1(state)
          state[pos] = save
          return qualities
      

      • f calcule \(x,n\longrightarrow\frac{1}{x^n}\). Plus \(n\) est grand, plus les petites différences sont amplifiées. Pour n très grand, seule la plus grande valeur est prise en compte, pour n proche de 0, les valurs n’ont plus aucune importance.

      def f(x, power):
          return 1/(x**power)
      

      • construction part d’un état peu favorable fixé, choisit un ordre aléatoire (si on décommente la ligne) pour parcourir les variables et va mettre à jour en prenant en compte deux considérations qui vont définir l’intérêt de chaque choix :

        • la qualité estimée par la fonction apriori,
        • la quantité de phéromone sur chacune des alternatives.

        Une fois l’intérêt calculé, le choix de l’action est obtenu par un tirage aléatoire privilégiant les alternatives de plus grand intéret. Comme on veut essayer de restreindre les descentes dans des minimums locaux peu profonds, on essaie de garder une probabilité proche de pmin pour les alternatives qui ont très peu de phéromones, et au maximum de pmax pour celles qui sont trop représentées (attention, avec le calcul proposé, on ne garanti ni pmin, ni pmax, mais on n’en est pas loin).

      def construction(pheromones, alpha, power, pmin, pmax):
          order = list(range(10))
          #random.shuffle(order)
          state = [3]*10 # arbitrary state, just a state that is not a good starting point, so it is not too easy
          for pos in order:
              qualities = apriori(state, pos)
              interest = [f(qualities[i-1]+1, power) +  alpha *pheromones[pos][i-1] for i in range(1,13)]
              total = sum(interest)
              interest = [max(min(i/total, pmax), pmin) for i in interest]
              total = sum(interest)
              cumulative = [ ]
              p = random.random()
              cumulative = 0
              i = 0
              while p > cumulative:
                  cumulative += interest[i] /total
                  i+=1
              state[pos] = i
          return state
      

      • antColony va gérer les vagues successives de fourmis.

        • 0 < beta < 1 règle la vitesse de disparition des phéromones, plus ce paramètre grandit, plus les phéromones sont volatiles.
        • alpha, power, pmin et pmax sont des paramètres pour les appels des fonctions précédentes

        Au départ il n’y a pas de phéromones, puis par vagues de 100 fourmis, elles explorent le territoire (construction de leur state). Une fois toutes les fourmis passées, mise à jour des phéromones pour la vague suivante.

      def antColony(alpha = 100, beta = 0.1, power = 2, pmin =0.03, pmax=0.5):
          pheromones = [[0 for _ in range(1,13)] for __ in range(10) ]
          total = 0
          cpt =0
          while True:
              newPheromones = [[0 for _ in range(1,13)] for __ in range(10) ]
              bestE = 10000
              for ant in range(100):
                state = construction(pheromones, alpha, power, pmin, pmax)
                E = energy1(state)
                if E==0:
                  print(cpt, "**************************************************************", state)
                else:
                 if E <bestE:
                     bestE = E
                 for i in range(10):
                     newPheromones[i][state[i]-1] += f(E, power)
      
              pheromones = [[beta * newPheromones[i][j-1]/200+ (1-beta)* pheromones[i][j-1] for j in range(1,13) ] for i in range(10)]
              total += bestE
              cpt +=1
              if cpt%10==0:print(int(total/cpt*100)/100,"\t", bestE,"    ", state)
      

   4. Application au voyageur de commerce
      

      L’idée est exactement la même, mais cette fois les formules qui vont assez bien qui permettent de bien gérer les phéromones sont très étudiées et la page wikipedia peut être un bon point de départ documentaire. C’est l’exemple traité dans quasiment la totalité des cours d’introduction à cette méthaheuristique et vous n’aurez normalement aucune difficulté à trouver des sources qui vous conviennent.

3.3.4. Algorithmes génétiques

1. Présentation générale
   

   Les algorithmes génétiques sont des métaheuristiques manipulant des groupes de configurations que l’on appelle population. Le principe général est le suivant:

   1. Créer la population initiale.
   2. Sélection des individus de la population qui deviendront des parents.
   3. Ces parents ont des enfants qui constitueront la génération suivante.
   4. Faire vivre et évoluer ces enfants.
   5. Repartir au point 2 avec cette nouvelle génération.
2. Créer la population initiale
   

   On crée un ensemble de situations, soit en les tirant au hasard, soit en essayant de les répartir dans l’espace de recherche afin d’essayer d’avoir des chances que certains d’entre eux soient ne soient pas trop éloignés d’un optimum local de qualité.

3. Sélection des individus qui deviendront des parents
   

   Il existe plusieurs méthodes, celles qui reviennent le plus souvent sont :

   • Conservation des individus possédant les meilleures évaluations : va souvent permettre une convergence rapide, au risque d’une diversité amoindrie et donc un risque de ne converger que vers un optimum de faible qualité.
   • Probabilité qu’un individu soit choisi comme parent proportionnelle à sa qualité. On réalise autant de tirages que l’on désire de parents, et à chaque tirage, la probabilité qu’un individu soit choisie est le rapport entre sa qualité et la somme des qualités des participants. On peut ou non enlever un individu une fois qu’il a été élu (si on ne l’enlève pas, il pourra alors apparaître plusieurs fois dans la liste des parents)
   • Compétition par tournoi : On choisit la taille des équipes \(N\). On choisit au hasard \(N\) individus, et on conserve celui possédant la meilleure évaluation parmi les \(N\). Encore une fois, un individu qui a été élu peut ou non être retiré de la liste des participants. On réitère le processus jusqu’à avoir choisi le nombre désiré de parents. Cette méthode donne souvent des résultats assez satisfaisants, le paramètre \(N\) permettant de régler le niveau d’élitisme que l’on désire (dans le cas extrême où \(N\) est la taille de la population, on ne choisit que les meilleurs, avec \(N = 1\), c’est un tirage aléatoire équiprobable ; avec \(N\) assez grand on choisit comme parents les champions des pays, avec \(N\) petit on choisit comme parents les champions de village).

   • La sélection par distanciation : on définit une distance sur l’ensemble des configurations, et on va choisir en priorité des individus qui sont les plus éloignés possibles de façon à maximiser la diversité de la population. Cette approche est intéressante mais elle peut rapidement devenir assez coûteuse en temps de calcul. Un algorithme approché permettant d’envisager cette méthode est le suivant :

     1. Distribuer de façon aléatoire les individus dans deux ensembles \(A\) et \(B\) (chaque individu a une chance sur deux d’être affecté aux ensembles \(A\) et \(B\)).
     2. Pour chaque couple \(x\in A\), \(y\in B\), calculer la distance de \(x\) à \(y\).
     3. Décider d’une distance de coupe, et pour chaque distance calculée inférieure à cette distance de coupe, supprimer l’individu de l’ensemble \(A\)

     Ce processus peut être itéré si on le désire, chaque passe ayant un coût de l’ordre de \(O(\text{nb_individus}^2)\). Cette forme de sélection utilisée de façon hybride ou pure devient particulièrement pertinente lorsque le temps d’évaluation de la fonction objectif devient important, et dans son coût devient proportionnellement moins élevé.

   • Ces méthodes sont mélangeables et il n’est pas rare de conserver les meilleurs puis de compléter la liste des parents par des tournois.
4. Construire la génération suivante
   

   Cette partie est celle qui est la plus variable. Cependant deux considérations doivent rester à l’esprit :

   • la spécialisation : dans les zones intéressante, il est utile de raffiner les solutions afin de les améliorer. C’est en général l’opération la plus fréquente. Les opérations les plus fréquemment rencontrées sont :
     • le crossover à deux parents : s’applique aux configurations qui sont des vecteurs. Un point de rupture est tiré au hasard, et un nouvel individu est créé en prenant la partie gauche de la configuration du premier parent, et la partie droite du second. Cette transformation est la plus célèbre et a donné des résultats intéressants. Elle est parfois plus compliquée à mettre en œuvre, car les nouveaux individus ne sont pas toujours valides : dans le cas du voyageur de commerce par exemple, avec des configurations qui sont l’ordre de parcours des villes, cette opération va générer des configurations non valides (2 fois certaines villes, absence d’autres villes) et il sera nécessaire de rectifier les configurations obtenues pour qu’elles soient valides. Dans le cas du voyageur de commerce, on peut choisir de conserver une partie de la liste de parcours du premier parent, et de la compléter par les villes qui n’y sont pas, dans l’ordre dans lequel elles apparaissent dans le parent n°2.
     • le crossover à 3 parents : cette opération est identique à la précédente, mais cette fois il y aura 2 points de rupture, et à gauche on récupère la partie gauche de la configuration du premier parent, au milieu la partie centrale du deuxième, et à droite la partie droite du troisième. Cette opération est préférable à la précédente sur certains problèmes.
   • la diversification : la spécialisation a tendance à converger vers des extremums locaux. La diversification va permettre d’explorer des parties plus importantes de l’espace des configurations.
     • les mutations : une partie plus ou moins importante d’un parent est altérée aléatoirement pour fabriquer le nouvel individu. Plus l’altération est importante, plus le taux de mutation (pourcentage de la nouvelle génération obtenue par mutation) doit en général être faible. Il est à noter que la majeure partie des mutations est défavorable, et que les individus générés par mutation posséderont rarement de bonnes évaluations. Parfois on ajoute à ce mécanisme un temps de survie des mutants de générations en générations afin de laisser la chance aux mutations de porter leurs fruits. Dans le cas du voyageur de commerce, on peut choisir \(k\geq2\) villes et les échanger aléatoirement dans le circuit. Plus \(k\) est grand, plus la force de la mutation est importante.
     • la mutation peut être portée à l’extrême en choisissant simplement d’intégrer des individus générés comme à l’initialisation. La mise en œuvre est alors très simple, mais plus l’algorithme avance, plus ses nouveaux individus sont défavorisés par rapport à ceux ayant subi plusieurs générations d’évolution et ils ont tendance à être éliminés de la population très rapidement.
5. Évolution des enfants
   

   Cette phase n’est présente que dans certaines implémentation, elle correspond à une hybridation de cette métaheuristique avec des recherches locales, on parle alors d’algorithme mémétique . On vise à améliorer les solutions par des algorithmes rapides. Il n’est pas nécessaire de pousser cette optimisation au maximum et on se contente parfois de quelques itérations d’une recherche locale, sans la mener à son terme.

   Attention, cette amélioration peut être contre-productive, par exemple dans le cas où une mutation d’un attribut vient d’être appliquée pour générer un enfant : une recherche locale a des chances assez importantes de supprimer la mutation, car c’est souvent la suite d’opération la plus simple pour ’corriger’ l’individu et améliorer son évaluation. On remplace donc souvent la mutation partielle par l’incorporation de nouveaux individus, qui sont alors passés dans l’algorithme de recherche locale avant d’être incorporés à la population, et après chaque croisement, on applique une recherche locale partielle afin de ’donner une chance’ à ce nouvel individu.

4.3.1. Observations sur le monde

  typedef struct {
      case_t devant, gauche, derrière, droite; // le contenu des 4 cases voisines
      direction4_t direction_predateur;        // dans quelle direction se trouve le prédateur le plus proche
      direction8_t direction_proie;            // dans quelle direction se trouve la proie la plus proche
  } RuleTyped;

4.3.2. les actions

    typedef enum {
        AV, GAUCHE, DROITE, RETOUR
    } direction_relative4_t ;

4.3.3. Les règles

4.3.4. Filtrage des règles

4.3.5. Choix de l’action à réaliser

4.3.6. Réalisation de l’action

8.5.1. Options de compilation

8.5.2. Allocations

8.5.3. Définitions