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/

Potomac

Follow me: ai-contest.com/profile.php?user_id=4017 – Potomac

Current settings: Population: 100, Mutate rate: 2%, Mate rate: 20% – Potomac

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!

Idiopathy

Higher population, a lower mutate rate and 14 hours of computation gave good results, but I still had to hand tune two constants. It gave me 200 rating points! – Potomac

Bias: larger mutation if larger constant value, correct. But the uncertainty of the value is higher as well, and the relative change of the mutation is the same (less than 25%). I don't think it matters. – Potomac

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.

Grof

GAUL seems a bit huge for the problem at hand. My current genetic engine is 110 lines of Python code. I did enjoy your suggestions and links, thanks. – Potomac

To stay in search space: I do not check it, if a constant value is out of bounce, the game "organism" will send illegal commands and it will consequently die. – Potomac

Ok Then you may consider Lamarck (reevaluation of all individuals) – Penland

In Lamarck genetics the individual passes on some of the characteristics it has acquired during its lifetime. How do this apply to game playing, the "contants" do not change during the game? – Potomac

You could do a drift ( change a number to something close ) and then look if it's a good adaptation. – Penland