IsdinvalLaisser un commentaire sur Algorithme génétique, première approche

Algorithme génétique, première approche

Dans ce post, nous allons nous intéresser aux algorithmes génétiques, en travaillant sur l’exemple suivant : Retrouver une phrase/un String à partir d’une population initiale qui subit une sélection, et une reproduction.


I°) Pseudo-code

Le pseudo-code utilisé est le suivant :

  1. Initialiser la population :
    • Créer une population ayant un génome généré aléatoirement.
  2. Selection :
    • Evaluer la justesse de chaque élément de la population, puis construire une mating pool.
  3. Reproduction :
    1. Prendre deux parents,
    2. Réaliser un cross-over du génome afin de créer un fil en combinant le génome de ces deux parents,
    3. Réaliser une mutation du génome de l’enfant suivant une certaine probabilité (1%, 0.1%, …)
    4. Rajouter l’enfant à la nouvelle population
  4. Remplacer l’ancienne population avec la nouvelle population, puis reprendre à l’étape n°1.


II°) Résultats

L’objectif est d’obtenir une interface de ce genre :

Résultat final

On y retrouve plusieurs parties :

  • L’objectif à atteindre, dans ce cas là, la célébré citation « Science sans conscience n’est que ruine de l’âme ».
  • Le meilleur element de chaque population.
  • Quelques informations telles que la génération actuelle, la justesse moyenne, ainsi que la justesse max.
  • Une interface utilisateur pour régler le nombre d’élément dans la population totale, ainsi que le taux de mutation. Enfin un bouton Play/Pause et un bouton Reset.
https://youtu.be/BskYcLow7vM


III°) Code

Ce code est décomposé en deux parties : la partie maître, et la partie génome qui regroupe l’ensemble des méthodes pour la justesse, le crossover entre deux membres, pour la mutation, …

La méthode de fitness permet de compter le nombre de bon caracteres entre la phrase objectif et le meilleur element de chaque population.

La méthode de crossover permet de créer un fils en mélangeant le génome des deux parents. Pour cela on utilise la technique du point milieu flottant. Par exemple, si le parent n°1 est « NOUS » et le parent n°2 est « FLUO », alors les possibles enfants sont : NLUO, NOUO, NOUO, FOUS, FLUS, FLUS,…

La méthode de mutation permet de changer un caractère de façon aléatoire : ça donne une chance sur 1% par exemple de changer un caractère par un autre.

La classe DNA pour construire le génome de la population est la suivante : 

class DNA {
  // **************************************************************
  //                         PARAMETERS
  // **************************************************************
  char[] genes;
  float fitness;


  // **************************************************************
  //                        CONSTRUCTOR
  // **************************************************************
  DNA() {
    genes = new char[target.length()];
    for (int i=0; i < genes.length; i++) {
      genes[i] = (char) random(32, 128);
    }
  }


  // **************************************************************
  //                         FUNCTIONS
  // **************************************************************
  // Give a score to the member of the population
  void fitness() {
    int score = 0;
    for (int i=0; i < genes.length; i++) {
      if (genes[i] == target.charAt(i)) {
        score++;
      }
    }
    fitness = (float)score/target.length();
  }

  // Crossover between two member of the population
  DNA crossover(DNA partner) {
    DNA child = new DNA();
    int midpoint = int(random(genes.length));
    for (int i = 0; i < genes.length; i++) {
      if (i > midpoint) child.genes[i] = genes[i];
      else              child.genes[i] = partner.genes[i];
    }
    return child;
  }

  // Mutation given the mutationRate
  void mutate(float mutationRate) {
    for (int i = 0; i < genes.length; i++) {
      if (random(1) < mutationRate) {
        genes[i] = (char) random(32, 128);
      }
    }
  }
  
  // Convert to String - PHENOTYPE
  String getPhrase() {
  return new String(genes);
  }
  

}

La partie maître est la suivante, elle regroupe l’utilisation du génome de chaque membre, et l’interface utilisateur. 

//https://natureofcode.com/book/chapter-9-the-evolution-of-code/ //<>//
// ============================================================================
//                                 PSEUDO-CODE
// ============================================================================
/*
  Step n°1 : Initialize Population
 --> Create a population of elements, each with randomly generated DNA.
 
 Step n°2 : Selection
 --> Evaluate the fitness of each element of the population and 
 build a mating pool.
 
 Step n°3 : Reproduction
 --> Pick two parents with probability according to relative fitness.
 --> Crossover — create a “child” by combining the DNA of these two parents.
 --> Mutation — mutate the child’s DNA based on a given probability.
 --> Add the new child to a new population.
 
 Step n°4 : Replace the old population with the new population and return to Step 2.
 */


// ============================================================================
//                                 PARAMETERS
// ============================================================================
import controlP5.*;

// Genetic algorithm main parameters
float mutationRate = 0.001; // 0.001
int totalPopulation = 30000; //30 000
int totalGenerations;
DNA[] population;
ArrayList<DNA> matingPool;
String target1 = "To be, or not to be: that is the question";
String target2 = "Science sans conscience n est que ruine de l ame";
String target = target2;
String bestPhrase;
boolean end_GA = false;

// Display parameters
int textSize = 20;
float[] fitness_value = new float[totalPopulation];
float moyenne_fitness;
float max_fitness;
float max_index_fitness = 0;

// GUI Main parameters
ControlP5 cp5;
Accordion accordion;
PFont pfont;
ControlFont font ;
float play = 0;
boolean play_b = false;
float reset = 0;
boolean reset_b = false;




// ============================================================================
//                                     SETUP
// ============================================================================
void setup() {
  //size(400, 480);
  fullScreen();
  frameRate(30);
  population = new DNA[totalPopulation];
  gui(textSize, 15*textSize);

  pfont = createFont("Georgia", 12, true); // use true/false for smooth/no-smooth



  // **************************************************************
  //               STEP n°1 : Initialize population
  // **************************************************************
  // Initializing each member of the population
  for (int i=0; i < population.length; i++) {
    population[i] = new DNA();
  }
}


// ============================================================================
//                                     DRAW
// ============================================================================
void draw() {
  background(255);

  totalPopulation = (int)cp5.getController("Population").getValue();
  mutationRate = cp5.getController("Mutation rate (%)").getValue()/100;
  // paused = 0 : paused == false
  // paused = 1 : paused == true
  play = cp5.getController("Play").getValue();
  if (play == 0) play_b = true;
  if (play == 1) play_b = false;

  reset = cp5.getController("Reset").getValue();
  if (reset == 0) reset_b = false;
  if (reset == 1) reset_b = true;


  if (reset_b) {
    reset();
  }

  if (!play_b) {
    if (end_GA == false) {
      // **************************************************************
      //                     STEP n°2 : SELECTION
      // **************************************************************
      // 2-1 : Give a score to each member of the population
      for (int i=0; i < population.length; i++) {
        population[i].fitness();
      }

      // Get the average fitness of the population
      for (int i = 0; i < population.length; i++) {
        fitness_value[i] = population[i].fitness;
      }
      for (int i = 0; i < fitness_value.length; i++) {
        moyenne_fitness = moyenne_fitness + fitness_value[i];
      }
      moyenne_fitness /= fitness_value.length;

      // Get the max index of fitness from a member of the pulation
      // Then get the bestPhrase
      max_fitness = getMax(fitness_value);
      max_index_fitness = getMaxIndex(fitness_value);

      bestPhrase = population[(int)max_index_fitness].getPhrase();
      //println("bestPhrase = " + bestPhrase);

      // End loop : fitness == 1 means a perfect match between current 
      //phrase and target.
      for (int i = 0; i < population.length; i++) {
        if (population[i].fitness == 1) {
          println("DONE!");
          end_GA = true;
          //noLoop();
        }
      }


      // 2-2 : Add each member to the mating pool
      // Wheel of forturne technique
      matingPool = new ArrayList<DNA>();
      for (int i=0; i < population.length; i++) {
        int n = int(population[i].fitness*100);
        for (int j=0; j < n; j++) {
          matingPool.add(population[i]);
        }
      }

      // **************************************************************
      //                     STEP n°3 : REPRODUCTION
      // **************************************************************
      for (int i = 0; i < population.length; i++) {
        // Get two random indices from the mating pool
        int a = int(random(0, matingPool.size()));
        int b = int(random(0, matingPool.size()));
        // Use these indices to retrieve an actual DNA instance from the
        // mating pool.
        DNA partnerA = matingPool.get(a);
        DNA partnerB = matingPool.get(b);

        // 3-1 : Crossover
        DNA child = partnerA.crossover(partnerB);
        // 3-2 : Mutation
        child.mutate(mutationRate);
        population[i] = child;
        if (population[i].getPhrase() == target) println("DONE MMM");
      }

      totalGenerations++;
    }
  }

  // **************************************************************
  //                   STEP n°4 : DISPLAY RESULTS
  // **************************************************************
  textFont(pfont);
  textSize(20);
  stroke(0);
  fill(0xffff0000);
  text("Goal phrase : ", 20, 2*textSize);

  fill(0);
  textSize(15);
  text(target, 20, 3*textSize);

  fill(0xffff0000);
  textSize(20);
  text("Best phrase : ", 20, 6*textSize);

  fill(0);
  textSize(15);
  if (bestPhrase != null) {
    text(bestPhrase, 20, 7*textSize);
  }

  fill(0xffff0000);
  textSize(20);
  text("Some interesting stuff : ", 20, 10*textSize);

  fill(0);
  textSize(15);
  text("Total generations : " + totalGenerations, 20, 11*textSize);
  text("Average fitness : " + nf(100*moyenne_fitness, 0, 1) + " %", 20, 12*textSize);
  text("Max fitness : " + nf(100*max_fitness, 0, 1) + " %", 20, 13*textSize);
}




// ============================================================================
//                                     FUNCTIONS
// ============================================================================
// Reset
void reset() {
  totalGenerations = 0;
  moyenne_fitness = 0;
  max_fitness = 0;
  end_GA = false;
  // Initializing each member of the population
  for (int i=0; i < population.length; i++) {
    population[i] = new DNA();
  }

  //while (!matingPool.isEmpty()) {
  //  matingPool.remove(matingPool.get(0));
  //}

  // Get the average fitness of the population
  for (int i = 0; i < population.length; i++) {
    fitness_value[i] = population[i].fitness;
  }
}

// Method for getting the minimum value
float getMax(float[] inputArray) { 
  float maxValue = inputArray[0]; 
  for (int i=1; i<inputArray.length; i++) { 
    if (inputArray[i] > maxValue) { 
      maxValue = inputArray[i];
    }
  } 
  return maxValue;
} 

// Method for getting the minimum value
float getMaxIndex(float[] inputArray) { 
  float maxValue = inputArray[0]; 
  float maxIndex = 0;
  for (int i=1; i<inputArray.length; i++) { 
    if (inputArray[i] > maxValue) { 
      maxValue = inputArray[i]; 
      maxIndex = i;
    }
  } 
  return maxIndex;
} 

void gui(float posX, float posY) {
  // Init ControlP5
  cp5 = new ControlP5(this);
  cp5.setColorForeground(color(230, 90));
  cp5.setColorBackground(0xff660000);
  cp5.setColorActive(0xffff0000);


  // ********************************************************************
  //                     GROUPE 1 : Create some controllers
  //                    RadioButton x1, slider x2, button x1
  // ********************************************************************

  // Init Groupe 1
  Group g1 = cp5.addGroup("Main parameters")
    .setBackgroundColor(color(0, 64))
    .setBackgroundHeight(150)
    .setBarHeight(17);




  // Init sliders, radioButton and button
  cp5.addSlider("Population")
    .setPosition(10, 20)
    .setSize(100, 20)
    .setRange(100, 50000)
    .setValue(1000)
    .moveTo(g1);

  cp5.addSlider("Mutation rate (%)")
    .setPosition(10, 50)
    .setSize(100, 20)
    .setRange(0.0001*100, 0.01*100)
    .setValue(0.0001*100)
    .moveTo(g1);

  cp5.addRadioButton("PlayButton")
    .setPosition(75, 90)
    .setItemWidth(10)
    .setItemHeight(10)
    .addItem("Play", 0)
    .setColorLabel(color(255))
    .activate(2)
    .moveTo(g1);

  cp5.addRadioButton("ResetButton")
    .setPosition(75, 120)
    .setItemWidth(10)
    .setItemHeight(10)
    .addItem("Reset", 0)
    .setColorLabel(color(255))
    .activate(2)
    .moveTo(g1);

  //// ********************************************************************
  ////    Groupe1 : Load and apply the font and captionlabels's content 
  //// ********************************************************************
  pfont = createFont("Georgia", 12, true); // use true/false for smooth/no-smooth
  font = new ControlFont(pfont, 12);
  cp5.setFont(font);

  // ********************************************************************
  //                               Accordion : 
  //                                 Groupe1
  // ********************************************************************
  // create a new accordion
  // add g1 to the accordion.
  accordion = cp5.addAccordion("acc")
    .setPosition(posX, posY)
    .setWidth(255)
    .addItem(g1);

  // ********************************************************************
  //                               ShortCuts: 
  // ********************************************************************
  cp5.mapKeyFor(new ControlKey() {
    public void keyEvent() {
      accordion.open(0, 1, 2);
    }
  }
  , 'o');
  cp5.mapKeyFor(new ControlKey() {
    public void keyEvent() {
      accordion.close(0, 1, 2);
    }
  }
  , 'c');
  cp5.mapKeyFor(new ControlKey() {
    public void keyEvent() {
      accordion.setWidth(300);
    }
  }
  , '1');
  cp5.mapKeyFor(new ControlKey() {
    public void keyEvent() {
      accordion.setPosition(0, 0);
      accordion.setItemHeight(190);
    }
  }
  , '2'); 
  cp5.mapKeyFor(new ControlKey() {
    public void keyEvent() {
      accordion.setCollapseMode(ControlP5.ALL);
    }
  }
  , '3');
  cp5.mapKeyFor(new ControlKey() {
    public void keyEvent() {
      accordion.setCollapseMode(ControlP5.SINGLE);
    }
  }
  , '4');



  accordion.open(0);
  accordion.setCollapseMode(Accordion.SINGLE);
}

Laisser un commentaire

Concevoir un site comme celui-ci avec WordPress.com
Commencer
search previous next tag category expand menu location phone mail time cart zoom edit close