Genetic Algorithm doesn't terminate

9frazz

Hi! I was doing some research on Genetic Algorithms and found the YouTube channel "The Coding Train" and watched his videos on genetic algorithms. While trying out his code, I realised the program was not ending even though the termination condition has been met. Could someone please help fix the code? I apologise for the wall of code but I have attempted to change the code in an attempt to get it to work properly but I can't seem to do it (I attempted to end the code by changing if (population.finished()) { to if (answer == target) { but there was no difference). So I included all the code that was provided in case the problem was in another class.

Main class:

PFont f;
String target;
int popmax;
float mutationRate;
Population population;

void setup() {
  size(800, 200);
  f = createFont("Courier", 32, true);
  target = "To be or not to be.";
  popmax = 150;
  mutationRate = 0.01;

  // Create a populationation with a target phrase, mutation rate, and populationation max
  population = new Population(target, mutationRate, popmax);
}

void draw() {
  // Generate mating pool
  population.naturalSelection();
  //Create next generation
  population.generate();
  // Calculate fitness
  population.calcFitness();
  displayInfo();

  // If we found the target phrase, stop
  if (population.finished()) {
    println(millis()/1000.0);
    noLoop();
  }
}

void displayInfo() {
  background(255);
  // Display current status of populationation
  String answer = population.getBest();
  textFont(f);
  textAlign(LEFT);
  fill(0);


  textSize(16);
  text("Best phrase:",20,30);
  textSize(32);
  text(answer, 20, 75);

  textSize(12);
  text("total generations: " + population.getGenerations(), 20, 140);
  text("average fitness: " + nf(population.getAverageFitness(), 0, 2), 20, 155);
  text("total populationation: " + popmax, 20, 170);
  text("mutation rate: " + int(mutationRate * 100) + "%", 20, 185);

  textSize(10);
  text("All phrases:\n" + population.allPhrases(), 650, 10);
}

Population: class Population {

  float mutationRate;           // Mutation rate
  DNA[] population;             // Array to hold the current population
  ArrayList<DNA> matingPool;    // ArrayList which we will use for our "mating pool"
  String target;                // Target phrase
  int generations;              // Number of generations
  boolean finished;             // Are we finished evolving?
int perfectScore;

  Population(String p, float m, int num) {
    target = p;
    mutationRate = m;
    population = new DNA[num];
    for (int i = 0; i < population.length; i++) {
      population[i] = new DNA(target.length());
    }
    calcFitness();
    matingPool = new ArrayList<DNA>();
    finished = false;
    generations = 0;

    perfectScore = int(pow(2,target.length()));
  }

  // Fill our fitness array with a value for every member of the population
  void calcFitness() {
    for (int i = 0; i < population.length; i++) {
      population[i].fitness(target);
    }
  }

  // Generate a mating pool
  void naturalSelection() {
    // Clear the ArrayList
    matingPool.clear();

    float maxFitness = 0;
    for (int i = 0; i < population.length; i++) {
      if (population[i].fitness > maxFitness) {
        maxFitness = population[i].fitness;
      }
    }

    // Based on fitness, each member will get added to the mating pool a certain number of times
    // a higher fitness = more entries to mating pool = more likely to be picked as a parent
    // a lower fitness = fewer entries to mating pool = less likely to be picked as a parent
    for (int i = 0; i < population.length; i++) {

      float fitness = map(population[i].fitness,0,maxFitness,0,1);
      int n = int(fitness * 100);  // Arbitrary multiplier, we can also use monte carlo method
      for (int j = 0; j < n; j++) {              // and pick two random numbers
        matingPool.add(population[i]);
      }
    }
  }

  // Create a new generation
  void generate() {
    // Refill the population with children from the mating pool
    for (int i = 0; i < population.length; i++) {
      int a = int(random(matingPool.size()));
      int b = int(random(matingPool.size()));
      DNA partnerA = matingPool.get(a);
      DNA partnerB = matingPool.get(b);
      DNA child = partnerA.crossover(partnerB);
      child.mutate(mutationRate);
      population[i] = child;
    }
    generations++;
  }


  // Compute the current "most fit" member of the population
  String getBest() {
    float worldrecord = 0.0f;
    int index = 0;
    for (int i = 0; i < population.length; i++) {
      if (population[i].fitness > worldrecord) {
        index = i;
        worldrecord = population[i].fitness;
      }
    }

    if (worldrecord == perfectScore ) finished = true;
    return population[index].getPhrase();
  }

  boolean finished() {
    return finished;
  }

  int getGenerations() {
    return generations;
  }

  // Compute average fitness for the population
  float getAverageFitness() {
    float total = 0;
    for (int i = 0; i < population.length; i++) {
      total += population[i].fitness;
    }
    return total / (population.length);
  }

  String allPhrases() {
    String everything = "";

    int displayLimit = min(population.length,50);


    for (int i = 0; i < displayLimit; i++) {
      everything += population[i].getPhrase() + "\n";
    }
    return everything;
  }
}

DNA class DNA {

      // The genetic sequence
      char[] genes;

      float fitness;

      // Constructor (makes a random DNA)
      DNA(int num) {
        genes = new char[num];
        for (int i = 0; i < genes.length; i++) {
          genes[i] = (char) random(32,128);  // Pick from range of chars
        }
      }

      // Converts character array to a String
      String getPhrase() {
        return new String(genes);
      }

      // Fitness function (returns floating point % of "correct" characters)
      void fitness (String target) {
         int score = 0;
         for (int i = 0; i < genes.length; i++) {
            if (genes[i] == target.charAt(i)) {
              score++;
            }
         }
         fitness = (float)score / (float)target.length();
      }

      // Crossover
      DNA crossover(DNA partner) {
        // A new child
        DNA child = new DNA(genes.length);

        int midpoint = int(random(genes.length)); // Pick a midpoint

        // Half from one, half from the other
        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;
      }

      // Based on a mutation probability, picks a new random character
      void mutate(float mutationRate) {
        for (int i = 0; i < genes.length; i++) {
          if (random(1) < mutationRate) {
            genes[i] = (char) random(32,128);
          }
        }
      }
    }