int GA_POPSIZE= 300; // GA population size
int GA_MAXITER= 200; // maximum iterations
float GA_ELITRATE= 0.10; // elitism rate
float GA_MUTATION= 0.25; // mutation rate
String [] population = new String[GA_POPSIZE]; // array to hold possible solutions
int [] population_fitness = new int[GA_POPSIZE]; // array to hold the fitness value
String [] buffer = new String[GA_POPSIZE]; // a copy of population
int [] buffer_fitness = new int[GA_POPSIZE]; // a copy of fitness values
int esize = (int)( GA_POPSIZE * GA_ELITRATE); //elitism size
String character = ""; // a dummy String used to create words
int w = 30; //side of the bitmap (30x30)
int tsize = w*w; // the size (length) of the target String
int iter = 0;
void setup(){
  size(200,200);
  // initialize the population: creates a number of randomom Strings
  for(int i=0; i< GA_POPSIZE; i++){
    character = "";
    population_fitness[i] = 0;
    for(int j=0; j< tsize; j++) // for tsize characters
      character += str(int(random(2))); //create a random String
    population[i] = character;
  }
}
void draw(){
  background(255);
  int i=0;
  for(int x=0; x<w*5; x+=5)
    for(int y=0; y<w*5; y+=5){
      if(population[0].charAt(i)=='1'){
        fill(0);
        rect(25+y,25+x,5,5);
      }
      i++;
    }
}
void keyPressed(){
  // calculate fitness
  for(int i=0; i<GA_POPSIZE; i++){
    int k=0;
    int pop_length = population[i].length();
    for(int idx=0; idx<pop_length/2; idx++)
      if(population[i].charAt((idx/15)*30+(idx%15))==
        population[i].charAt((idx/15)*30+(30-idx%15-1)))
        k++;
    population_fitness[i] = (w*w/2) - k;
  }
  // sort them (simple bubble sort)
  for(int i=1; i< GA_POPSIZE; i++)
    for(int j=0; j< GA_POPSIZE-1; j++)
      if( population_fitness[i] < population_fitness[j]){
        //swap values
        int temp = population_fitness[ i];
        population_fitness[i] = population_fitness[j];
        population_fitness[j] = temp;
        String stemp = population[i];
        population[i] = population[j];
        population[j] = stemp;
      }
  // print the best one
  println( (iter++) + " Best fitness: " + population_fitness[0] );
  // mate take half of the population and cross it with the other half
  int spos, i1, i2;
  for (int i=0; i< GA_POPSIZE; i++) {
    i1 = (int)(random(1.) * esize); //random position within the elite population
      i2 = (int)(random(1.) * esize); //random position within the elite population
      spos = (int)(random(1.) * tsize); //random position of character within a String
      buffer[i] = population[i1].substring(0, spos ) +
      population[i2].substring(spos, tsize); //crossover
    // mutate: take a tring and alter one of its characters
    if(random(1.) < GA_MUTATION) { //if chance is 1:mutation rate
      int ipos = (int)(random(1.) * tsize); //select a random character
      character = "";
      for(int j=0; j< tsize; j++)
        if( j== ipos)
          character += str(int(random(2))); //replace a random character in the String
          else
          character += buffer[i].charAt(j);
    }
    buffer[i] = character;
  }//for
  // swap buffers
  for (int i=0; i< GA_POPSIZE; i++) {
    population[i] = buffer[i];
    population_fitness[i] = buffer_fitness[i];
  }
} // key pressed