We are about to switch to a new forum software. Until then we have removed the registration on this forum.
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);
}
}
}
}