Population becomes stale - Genetic Algorithm

Question

I'm building a simple "Hello, World!" genetic algorithm for learning purposes. My population is a group of random strings. Through mutation and crossover the strings evolve to be "Hello, World!". For some reason my population will sit at a fitness score and seemingly never evolve. Other times, my population will reach the target genes, "Hello, World". I'm using random selection and one point crossover. Although, this also happens when I use tournament and roulette wheel selection.

Question:
Why is my population becoming stale and not reaching the target genes even though I am diversifying the population through mutation? Is it because of the random nature of the genetic algorithm or a mistake in my code?

E.g.
Every chromosome in the population will end up having the genes "HellV, Wor`dL". Even after 10,000 generations the genes are the same. Other times, the genes reach the target genes "Hello, World!" after ~33 generations.

Note: The code below works as expected when using Java. When using Java, the population always achieves the target genes. Also, I just started learning C++ today so it's highly possible there is a flaw in my code that I'm just not seeing.

Population Size: 333
Elitism: true
Elitism Percentage: 25%
Mutation Probability: 20%
Crossover Probability: 95%
Selection Type: Random
Crossover Type: One Point

EDIT: I've removed the code from this post and instead added a link to my github due to the fact that it is several hundred lines of code.

Genetic Algorithm - C++

Are these free functions using globals or are they members of a class? One of the most common problems when moving from Java to C++ is how C++ copies objects in places where Java passes around a reference. — molbdnilo
That should not compile in any language - wtf are you asking ? (would like to down-vote up-voters) — user2249683
Can you provide a minimal, complete, and verifiable example? What is GAChromosome? Where is stuff defined? — Barry
@molbdnilo, They are using members of a class. I've added the majority of my code because it's hard to pin point where to problem could be stemming from. Although, I would think it's from either mutation or crossover. — Jonathan
@Barry, I've provided the header and implementation file for GAChromosome. As for a minimal, complete, verifiable example it's hard to without posting the majority of my code, which is now in my question. I apologize if it's too much. — Jonathan

Jonathan Jonathan · Accepted Answer · 2015-07-01T00:32:14

Thanks to @molbdnilo's comment I was able to solve my problem.

It turns out that it was because of how C++ copies objects, which explains why this code worked in Java and not C++.

As stated by @molbdnilo:

One of the most common problems when moving from Java to C++ is how C++ copies objects in places where Java passes around a reference.

To fix my issue I change the following method declarations:

1. int calculateFitness(GAChromosome chromosome); ---> int calculateFitness(GAChromosome const &chromosome);
In this method declaration I tell the compiler that I want to pass the chromosome by reference rather than by value, using &, and make it a constant, using const. Doing this prevents the chromosome from being copied and altered.

2. void mutate(GAChromosome chromosome); ---> void mutate(GAChromosome &chromosome);
In this method declaration I tell the compiler that I want to pass the chromosome by reference rather than by value, using &. Doing this prevents the chromosome from being copied. Since the previous method declaration did not specify that the chromosome was being passed by reference a copy was being made, altered, and then thrown out after the method reached the end of scope. Ultimately, the changes were never made.

3. std::pair<GAChromosome, GAChromosome> onePointCrossover(GAChromosome chromosomeA, GAChromosome chromosomeB); ---> std::pair<GAChromosome, GAChromosome> onePointCrossover(GAChromosome const &chromosomeA, GAChromosome const &chromosomeB);
In this method declaration I tell the compiler that I want to pass the chromosome by reference rather than by value, using &, and make it a constant, using const. Doing this prevents the chromosome from being copied and altered.

In conclusion, the problem stemmed from the way the chromosome was being passed to the mutate method. The chromosome was being passed by value rather than by reference causing the chromosome to be copied and changes being thrown out when the mutate method reached the end of scope.

Population becomes stale - Genetic Algorithm

1 Answers