Optimal population size, mutate rate and mate rate in genetic algorithm

Question

I have written a game playing program for a competition, which relies on some 16 floating point "constants". Changing a constant can and will have dramatic impact on playing style and success rate.

I have also written a simple genetic algorithm to generate the optimal values for the constants. However the algorithm does not generate "optimal" constants.

The likely reasons:

• The algorithm has errors (for the time being rule this out!)
• The population is to small
• The mutate rate is to high
• The mate rate could be better

The algorithm goes like this:

• First the initial population is created
• Initial constants for each member are assigned (based on my bias multiplied with a random factor between 0.75 and 1.25)
• For each generation members of the population are paired for a game match
• The winner is cloned twice, if draw both are cloned once
• The cloning mutates one gene if random() is less than mutate rate
• Mutation multiplies a random constant with a random factor between 0.75 and 1.25
• At fixed intervals, dependent on mate rate, the members are paired and genes are mixed

My current settings:

• Population: 40 (to low)
• Mutate rate 0.10 (10%)
• Mate rate 0.20 (every 5 generations)

What would be better values for population size, mutate rate and mate rate?

Guesses are welcome, exact values are not expected! Also, if you have insights with similar genetic algorithms, you will like to share, please do so.

P.S.: The game playing competition in question, if anyone is interested: http://ai-contest.com/

Answer 1

Your mutation size strikes me as surprisingly high. There's also a bit of bias inherent in it - the larger the current value is, the larger the mutation will be.

You might consider

1. Having a (much!) smaller mutation
2. Giving the mutation a fixed range
3. Distributing your mutation sizes differently - e.g. you could use a normal distribution with a mean of 1.

R.A. Fisher once compared the mutation size to focusing a microscope. If you change the focus, you might be going in the right direction, or the wrong direction. However, if you're fairly close to the optimum and turn it a lot - either you'll go in the wrong direction, or you'll overshoot the target. So a more subtle tweak is generally better!

Answer 2

Use GAUL framework, it's really easy so you could extract your objective function to plug it to GAUL. If you have a multi-core machine, then you would want to use omp (openMP ) when compiling to parallelize your evaluations( that I assume are time consumming ). This way you can have a bigger population size. http://gaul.sourceforge.net/

Normally they use High crossover and low mutation. Since you want creativity i suggest you High mutation and low crossover.http://games.slashdot.org/story/10/11/02/0211249/Developing-emStarCraft-2em-Build-Orders-With-Genetic-Algorithms?from=rss

Be really carefull in your mutation function to stay in your space search ( inside 0.75, 1.25 ). Use GAUL random function such as random_double( min, max ). They are really well designed. Build your own mutation function. Make sure parents dies !

Then you may want combine this with a simplex (Nelder-Mead), included in GAUL, because genetic programming with low crossover will find a non optimal solution.