• fullscreen
  • DNA.pde
  • Population.pde
  • my_first_GA_02.pde
  • class DNA {
      char[] genes = new char[8];
      String dna;
      float fitness;      // Raw fitness measure
      float fitnessN;     // Normalized fitness measure
      float mutationRate;
      float x; 
      float y;
      String s;
      char c; 
      char d;
    
      // Constructor for a random gene sequence
      DNA(){
        // Generate a genotype 
        // in this case, a hexadecimal string interpretable as a color.
        // The first two characters determine the transparency
        genes[0] = 'F';
        genes[1] = 'F';
        int i = 2;
        while(i < 8){      
          int n = int(random(32, 90));  // The other characters are picked at random
          if(((n >= 48) && (n <= 57)) || ((n >= 65) && (n <= 70))){  // but must be valid hexadecimal characters
            genes[i] = (char) n;
            i++;
          } 
        }
        dna = new String(genes);
      }
    
      // Constructor for a child gene sequence
      DNA(char[] newdna, float m){
        mutationRate = m;
    
        // Mutate according to given probability
        for (int i = 2; i < newdna.length; i++) {  // Iteration through the genotype, ignores the transparency characters
          if (random(1) < m) {
            boolean b = false;  // This switch indicates a valid mutation
            while(b == false){      
              int n = int(random(48, 90));                               // Random character,
              if(((n >= 48) && (n <= 57)) || ((n >= 65) && (n <= 70))){  // which must be a valid hexadecimal character
                newdna[i] = (char) n;  // Mutated character in the gene sequence
                b = true;              // Switch is on when a valid character has been found
              } 
            }
          }
        }
    
        dna = new String(newdna);
      }
    
      void display(float x, float y){
        noStroke();
        fill(0);
        rectMode(CENTER);
        rect(x+2, y+2, 28, 28);      // Shadow
        color c = color(unhex(dna));
        fill(c);
        rect(x, y, 28, 28);          // Marker
        fill(0);
        textFont(font);
        textAlign(CENTER, CENTER);
        text(dna.charAt(2), x-4, y-9);
        text(dna.charAt(3), x+4, y-9);
        text(dna.charAt(4), x-4, y);
        text(dna.charAt(5), x+4, y);
        text(dna.charAt(6), x-4, y+9);
        text(dna.charAt(7), x+4, y+9);
      }
    }
    
    
    
    
    class Population {
    
      ArrayList population;   // Array to hold the current population
      DNA solution;
    
      String target;    // Target for evolution
      int popSize;        // Number of individuals
      boolean end;        // Switch for further evolution
      ArrayList genePool = new ArrayList();  // Dynamic array to store a "mating pool"
      float mutationRate = 0.01;  // The probability of any genotype mutating
      int generations;
      float fRaw;        // Raw measure of fitness
      float fMax;        // Highest fitness measure in a generation
      float fBest;       // Highest fitness measure so far
      int diversity;     // Index of diversity in the gene pool
    
      Population(String t, int pS){
        target = t;
        popSize = pS;
    
        // Create an initial population
        population = new ArrayList();
        for(int i = 0; i < popSize; i++){
          population.add(new DNA());    // The first generation has random genotypes (see DNA constructors)
        }    
        solution = new DNA();
        generations = 0;
      }
    
      // Function: evaluate every individual's fitness
      void evaluateFitness(){
        // Assign a fitness measure to each individual
        for(int i = 0; i < population.size(); i++){
          DNA individual = (DNA) population.get(i);    // Cast the object type (necessary with ArrayList)
          individual.fitnessN = fitnessN(individual.dna, t);  // Refer to fitness functions
          individual.fitness = fitness(individual.dna, t);
    
          if(individual.fitness == 1){
            end = true;
            solution = individual;
          }
          //println(individual.dna + " Fitness: " + individual.fitness);
        }
      }
    
      // Function: select genotypes into a mating pool according to their fitness
      // This function follows the "fitness proportionate selection" a.k.a. "roulette wheel" method
      void select(){
        // Calculate each individual's mating chances
        for(int i = 0; i < population.size(); i++){
          DNA individual = (DNA) population.get(i);
          int chances = ceil(individual.fitness * 100);  
          for(int j = 0; j < chances; j++){  // Number of ocurrences in the gene pool is proportional to fitness
            genePool.add(individual);
          }
        }  
      }
    
      // Function: Create a new generation
      void generate(){
        population = new ArrayList();
        while(population.size() < popSize){
          population.add(mate()[0]);  // Call to the mate() function creates two children
          population.add(mate()[1]);
        }
        
        // Draw the individuals to the screen
        for(int j = 0; j < population.size(); j++){
          DNA individual = (DNA) population.get(j);
          float x = random(width);   // Horizontal position is random
          float y = map(fitness(individual.dna, t), 0, 1, 464, 30);  // Vertical position according to fitness
          individual.display(x, y);
          individual.x = x;
          individual.y = y;
        }
        genePool.clear();  // Empty the gene pool
        generations++;
      }
    
      // Function: combine two DNA sequences
      DNA[] mate(){
    
        diversity = 1;     // Reset gene diversity index
        char[] child1 = new char[8];
        char[] child2 = new char[8];
        DNA parent1 = new DNA();  // Placeholders for parents
        DNA parent2 = new DNA();
    
        //String dna1 = new String();  // Parent identifiers
        //String dna2 = new String();
    
        // Test the gene pool for diversity
        for(int i = 1; i < genePool.size(); i++){
          DNA genotype = (DNA) genePool.get(i);  // With ArrayList, the type must be cast before calling the item
          DNA previous = (DNA) genePool.get(i-1);
          String d = previous.dna;
          if(genotype.dna.equals(d) == false){
            diversity++;  // Count the number of different genotypes
          }
        }
        if(diversity > 1){
          int s = genePool.size();
          for(int i = 0; i < s; i++){
            int p1 = int(random(genePool.size()));
            int p2 = int(random(genePool.size()));
            parent1 = (DNA) genePool.get(p1);  // Parents are genotypes retrieved from the gene pool
            parent2 = (DNA) genePool.get(p2);
            // Prevent mating two equal genotypes
            if(parent1.dna.equals(parent2.dna) == false){
              // Crossover
              // Start by picking a random position in the gene sequence for splicing of parent genes
              // The first two characters (transparency value) are ignored
              int crossover = int(random(3, parent1.dna.length()));
              for(int j = 0; j < parent1.dna.length(); j++){
                if(j < crossover){                      // To the left of the crossover position,
                  child1[j] = parent1.dna.charAt(j);    // clone parent1's genes for child1
                  child2[j] = parent2.dna.charAt(j);    // and parent2's genes for child2
                }
                else{                                   // To the right of the crossover position,
                  child1[j] = parent2.dna.charAt(j);    // clone parent2's genes for child1
                  child2[j] = parent1.dna.charAt(j);    // and parent2's genes for child2
                }
              }
              //dna1 = parent1.dna;
              //dna2 = parent2.dna;
            }
          }
        }
        // If there is no diversity in the gene pool, clone a parent
        else{
          //println("No diversity in the gene pool!");
          for(int i = 0; i < child1.length; i++){
            child1[i] = parent1.dna.charAt(i);  // A clone of the parent, which might mutate
            child2[i] = parent2.dna.charAt(i);
          }
        }
        stroke(255, 36);
        strokeWeight(2);
        line(parent1.x, parent1.y, parent2.x, parent2.y);  // Shows which individuals are mating
    
        DNA[] children = new DNA[2];
        children[0] = new DNA(child1, mutationRate);
        children[1] = new DNA(child2, mutationRate);
        // Display parent's DNA
        //println(dnachild1.dna + " Parent 1: " + dna1 + " Parent 2: " + dna2);
    
        return children;
      }
    
      // Fitness functions:
      // Three functions calculate three measures of fitness:
      // 1: Raw fitness, the percentage of characters in the genotype that match the target string
      // 2: Scaled fitness, maintains the proportionality of fitness measures irrespective of target length
      // 3: Normalized fitness, rescales the values for selection calculations
    
      // Function: calculate "raw" fitness
      float fitness(String dna, String target){
        float fRaw = 0;
        int score = 0;
        fMax = 0;
        // Check the genotype for matches with the target string,
        // character by character
        for (int i = 2; i < dna.length(); i++) {  // Transparency characters left out
          if (dna.charAt(i) == target.charAt(i)) {
            score++;
          }
          fRaw = float(score) / float((target.length())-2);  // The percentage of characters that match the target string, excluding the transparency characters
          // Record new highest fitness scores, if any
          if(fRaw > fMax){ 
            fMax = fRaw;
          }
          if(fRaw > fBest){ 
            fBest = fRaw;
          }
        }
        return fRaw;
      }
    
      // Function: calculate scaled fitness
      // -- not essencial for further calculations
      float fitnessS(String dna, String target){
        float f = fitness(dna, t);
        //float fS = pow(2, f);  // Exponential scaling
        //float fS = 2*f;        // Linear scaling
        float fS = f;            // No scaling
        //println(fS);
        return fS;
      }
    
      // Function: calculate normalized fitness
      float fitnessN(String dna, String target){
        float fN;
        float fS;
        float fPopScale = 0;
        // Calculate the scaled fitness measure for the given genotype
        float fScale = fitnessS(dna, t);
        // Calculate the scaled fitness measure for the entire population
        for(int i = 0; i < population.size(); i++){
          DNA individual = (DNA) population.get(i);
          fS = fitnessS(individual.dna, t);
          fPopScale += fS;
        }
        // Normalize the fitness measure for the given genotype
        // in relation to the entire population
        // The fitness measures for all genotypes will add up to 1
        fN = fScale / fPopScale;  
        return fN;
      }
    }
    
    
    /*
    my_first_GA
     
     A simple implementation of a simple genetic algorithm
     with reference to: 
     Daniel Shiffman, http://www.shiffman.net/teaching/nature/ga/
     G.W. Flake, "The Computational Beauty of Nature", http://mitpress.mit.edu/books/FLAOH/cbnhtml/home.html
     
     version 2:
     * New display and interactivity
     * Crossover method according to Flake, generates two children per selected pair of parents
     * Population array is dynamic
     
     by João Bravo da Costa
     4 November 2009
     */
    
    Population p;
    
    PFont font;
    PFont info;
    PFont italic;
    
    // The target is a hexadecimal string translatable into a color
    // format: FF (total opacity) + six hexadecimal characters
    String t = "FF8392BA";  
    
    int populationSize = 17;
    boolean restart = false;
    
    color field; 
    color dark; 
    color c;
    
    void setup(){
      font = loadFont("LucidaConsole-9.vlw");
      info = loadFont("Georgia-Bold-14.vlw");
      italic = loadFont("Georgia-BoldItalic-12.vlw");
      colorMode(RGB, 255, 255, 255);
      field = unhex(t);
      dark = 102;
      c = 153;
    
      size(800, 800);
      smooth();
      // Initialize a population with random gene sequences  
      p = new Population(t, populationSize);
      background(dark);
      panel();
    }
    
    void draw(){
      frameRate(12); 
      // Repeat until the target is reached:
      if((p.end == false) || (restart == true)){
        noStroke();
        fill(field, 42);
        rectMode(CORNER);
        rect(0, 0, width, 494);
        // 1. Selection:
        // Evaluate every individual's fitness
        p.evaluateFitness();
        // Select genes according to their fitness and place them into a mating pool
        p.select();
        // 2. Reproduction:
        // Pick pairs of parents from the mating pool
        // Combine their genes into a third gene sequence (a child)
        p.generate();
        // Replace the population (parents) with the new generation (children)
        displayInfo();
      } 
      else {
        noLoop();
        noStroke();
        fill(field);
        rect(0, 0, width, 494);
        p.solution.display(p.solution.x, p.solution.y);
      }
    }
    
    // Pressing the mouse button will restart the program
    void mousePressed(){
      t = hex(get(mouseX, mouseY));
      field = unhex(t);
      background(dark);
      panel();
      p = new Population(t, populationSize);  // New population with random genes
      p.end = false;  // Evolution switch reset
      loop();         // Cycle restarted
    }
    
    // Function: display evolution statistics
    void displayInfo(){
      if(p.end == false){
        noStroke();
        colorMode(RGB, 255, 255, 255);
        fill(dark);
        rectMode(CORNER);
        rect(0, 494, 306, 270);
        fill(c);
        textFont(info);
        textAlign(RIGHT);
        text("Number of generations: " + p.generations, 306, 556);
        text(p.diversity + " genotypes / " + p.popSize + " individuals", 306, 586);
        text("Mutation rate: " + int(p.mutationRate * 100) + "%", 306, 616);
        text("Best fitness in generation: " + nf(p.fMax, 1, 3), 306, 646);
        text("Best fitness yet: " + nf(p.fBest, 1, 3), 306, 676);    
        //println(p.generations + " generations. " + "Best fitness: " + p.fMax + " this generation." + p.fBest + " so far.");
      }
      else if(restart == false){
        noStroke();
        fill(dark);
        rectMode(CORNER);
        rect(0, 560, 306, 200);  // Hides text lines
        //println(p.generations + " generations. " + "Solution: " + p.solution.dna + "  " + p.solution.fitness);
      }
    }
    
    // Function: draw static text and a range of colors to choose from
    void panel(){
      colorMode(RGB, 255, 255, 255);
      noStroke();
      fill(dark);
      rect(0, 494, width, 378);
      fill(c);
      textFont(italic);
      textAlign(CENTER);
      text("Click anywhere on the screen to pick a color and restart.", 553, height-42);
      textSize(30);
      text("Color evolution", 553, 650);
      pushMatrix();
      translate(0, height-28);
      colorMode(HSB, width, 100, 100);
      for(int i = 0; i < width; i++){
        for(int j = 0; j < 28; j++){
          stroke(i, 30, 70);
          point(i, j);
        }
      }
      popMatrix();
    }
    

    code

    tweaks (0)

    about this sketch

    This sketch is running as Java applet, exported from Processing.

    license

    advertisement

    Joao Bravo da Costa

    Color Evolution

    Add to Faves Me Likey@! 8
    You must login/register to add this sketch to your favorites.

    A population of color tablets mate, reproduce, and evolve until they generate a tablet with the background color.

    The tablets display the genetic codes (hexadecimal strings) which determine their colors. Each tablet's position on the screen indicates its evolutionary fitness (higher is fitter). The white lines connect two mating tablets; they were selected for their fitness and will produce offspring with a combination of both parents' genes.

    Click to restart the process with a new color.

    A simple implementation of a simple genetic algorithm with reference to Daniel Shiffman and G.W.

    uncertainT
    24 Jul 2011
    This is amazing, beautiful!
    You need to login/register to comment.