Why is my genetic algorithm seemingly behaving randomly?

Question

I'm attempting to evolve optimal strategies for the Iterated Prisoner's Dilemma using a basic genetic algorithm (Stochastic Universal Sampling, 1-point crossover, Canonical GA). I've implemented this algorithm in Haskell and recently added chart output. Unfortunately the graphs produced don't fit the expected pattern for this problem so it appears I have a bug.

All graphs of fitnesses I have seen for this problem look something like this:

Other examples can be seen in On Evolving Robust Strategies for Iterated Prisoner's Dilemma, P.J. Darwen and X. Yao (1993) p6-7

However my output looks like this:

If I set mutation rate to 1 I get:

Perhaps suggesting that my selection function is not being quite so random as I had thought as the graph implies a homogeneous population.

My code is in this git repository should you wish to inspect it.

Now for the question: Could any of you suggest what I might be doing wrong in my GA implementation to make the graph look like this?

e.g. I would assume it is unlikely to be the fitness function as I am using the same fitness function for output that it is maximising so even if the fitness function is wrong in some way it will still be maximising that wrong function (though I'm sure I could be wrong here, I'm rather new to genetic algorithms)

I would just like suggestions for which functions to look at, I'm tearing my hair out trying to fix this.

EDIT: Having added some debug code to my combine function it seems that it is always being passed the same individuals (even with mutation set to 1) so presumably selection is going wrong somewhere.

EDIT: Selection was going wrong, but that wasn't causing all the problems, just homogeneity in the population.

Answer 1

You have a function maybeFlip, which will change an allele to its opposite with a given probability. Hence, when the mutation rate is 1, you will just keep flipping all the alleles back and forth between two opposites. This explains the zig-zag pattern seen in your graph.

_{Also, swap is in Data.Tuple :)}