3

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?
enter image description here

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%:

enter image description here

false
  • 10,264
  • 13
  • 101
  • 209
Mike Moe
  • 226
  • 2
  • 5
  • I also work on magic square problem using binary encoding, GA always returns the best solution from the define search space. I recommend you to play with cross over & mutation rate as well as genome size because it also effects the correctness of the solution. keep mutation rate of 5%, cross over rate 80-90%, population size 200, generation size 500-800. – Desire Jan 02 '12 at 18:40

2 Answers2

3

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!

Raskolnikov
  • 286
  • 3
  • 13
2

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.

Fortunato
  • 1,360
  • 10
  • 9