evolutionAlgorithm

import java.util.*;

DNA[] population = new DNA[50000];
String target = "Pack my box with five dozen liquor jugs";
DNA winner;

void setup() { //this is a comment
  size(900, 400);

  for (int i = 0; i < population.length; i++) {
    population[i] = new DNA();
    population[i].fitness();
  }

  sortPopulation();
}

void draw() {
  background(0);

  if (winner.fitness < 1.0) {
    sortPopulation();

    ArrayList<DNA> 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]);
      }
    }

    for (int i=0; i < population.length; i++) {
      DNA parentA, parentB;
      while (true) {
        int a = int(random(matingPool.size()));
        int b = int(random(matingPool.size()));

        parentA = matingPool.get(a);
        parentB = matingPool.get(b);

        if (parentA != parentB) break;
      }

      DNA child = parentA.crossover(parentB);
      child.mutate();

      population[i] = child;
      population[i].fitness();
    }
  }

  drawText();
}

void drawText() {
  textSize(30);
  textAlign(LEFT, TOP);
  text(new String(winner.genes), 10, 10);

  textSize(20);
  for (int i = 1; i <= 17; i++) {
    text(new String(population[i].genes), 10, i * 20 + 30);
  }
}
void sortPopulation() {
  Comparator<DNA> c = new Comparator<DNA>() {
    public int compare (DNA a, DNA b) {
      //return int(a.fitness*100 - b.fitness*100);
      if(a.fitness > b.fitness) return 1;
      if (a.fitness < b.fitness) return -1;
      return 0;
    }
  };

  Arrays.sort(population, c);
  population = (DNA[])reverse(population);

  winner = population[0];
}

class DNA {
  char[] genes = new char[target.length()];
  float fitness;
  float mutationRate = 0.015;

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

  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();
    fitness = (score == 0) ? 0 : pow(score, 2) / pow(target.length(), 2) + 0.01;
  }

  DNA crossover(DNA partner) {
    DNA child = new DNA();

    for (int i=0; i < genes.length; i++) {
      float s = random(1);
      if (s < 0.5) child.genes[i] = genes[i];
      else child.genes[i] = partner.genes[i];
    }

    return child;
  }

  void mutate() {
    for (int i=0; i < genes.length; i++) {
      if (random(1) < mutationRate) {
        genes[i] = (char) random(32, 128);
      }
    }
  }
}