Solving the Magic Square with Genetic Algorithms: population score converges fast, but never reaches the goal?

Question

The desire to learn more about GA has sparkled again, and instead of reading a lot and doing nothing, I've decided to start the other way around: pick a problem and try to solve it.

I've picked the Magic Square problem. For encoding the chromosomes I am using Permutation Encoding, and the following methods for Mutation() and NewChild(parent1, parent2, pivot) .

My selection algorithm is a bit weird, and is adapted from examples found on the Internet.

The score is calculated based on the square of the difference of the sum of rows/columns/diagonals and the magic constant, like this.

What I've noticed is that it converges very fast, and stops improving once it reaches a score of 1..7 (less is better).

I am seeing this as: it reaches a local optimum, a potential well, if you can call it that way, and won't jump over the near-by hill because the mutations are not different enough?

I've tried changing the mutation rate 5 - 80%, leaving an elite group of 10-20% in the chromosome population, changing the population size from 16-32 chromosomes, but no luck.

What am I doing wrong? What improvements can I use to make the population score converge to zero?

If required, I can post the full source code, if someone finds it useful or would like to play with it.

Update: Here is what the convergence rate looks like for a cube of size 5, with a crossover rate of 60% and a mutation rate of 10%:

Answer 1

In cases like this I've used subpopulations with good results. You basically run the algorithm n times and pick the best individuals of each run. With these you form an initial population (rather than initializing randomly as in a usual run) and run the ga again. The starting individuals in this last run are usually suboptimal in different ways and since all of them have more or less the same fitness they tend to pull each other out of their local minima when they get combined. Here it is also a good idea to use elitism in order to not lose the already evolved individuals to easily.

Answer 2

There are no hard and fast answers for this, but I would advise reducing your elitism to no more than 5% and increasing your population size. I don't quite understand how your getPermutation() call is working to select potential candidates but I would also increase the size of your tournament (lines 8-16 in your selection algorithm) as you increase population size. If you're getting stuck in local optima it means either your mutation function isn't jumping far enough or you don't have enough diversity in your population to begin with.

Hope that helps, good luck!