Genetic Algorithm - convergence

Question

I have a few questions about my genetic algorithm and GAs overall.

I have created a GA that when given points to a curve it tries to figure out what function produced this curve.

An example is the following Points

{{-2, 4},{-1, 1},{0, 0},{1, 1},{2, 4}}

Function

x^2

Sometimes I will give it points that will never produce a function, or will sometimes produce a function. It can even depend on how deep the initial trees are.

Some questions:

• Why does the tree depth matter in trying to evaluate the points and produce a satisfactory function?
• Why do I sometimes get a premature convergence and the GA never breaks out if the cycle?
• What can I do to prevent a premature convergence?
• What about annealing? How can I use it?

Can you take a quick look at my code and tell me if anything is obviously wrong with it? (This is test code, I need to do some code clean up.)

https://github.com/kevkid/GeneticAlgorithmTest

Source: http://www.gp-field-guide.org.uk/

EDIT: Looks like Thomas's suggestions worked well I get very fast results, and less premature convergence. I feel like increasing the Gene pool gives better results, but i am not exactly sure if it is actually getting better over every generation or if the fact that it is random allows it to find a correct solution.

EDIT 2: Following Thomas's suggestions I was able to get it work properly, seems like I had an issue with getting survivors, and expanding my gene pool. Also I recently added constants to my GA test if anyone else wants to look at it.

Answer 1

I don't have the time to dig into your code but I'll try to answer from what I remember on GAs:

Sometimes I will give it points that will never produce a function, or will sometimes produce a function. It can even depend on how deep the initial trees are.

I'm not sure what's the question here but if you need a result you could try and select the function that provides the least distance to the given points (could be sum, mean, number of points etc. depending on your needs).

Why does the tree depth matter in trying to evaluate the points and produce a satisfactory function?

I'm not sure what tree depth you mean but it could affect two things:

• accuracy: i.e. the higher the depth the more accurate the solution might be or the more possibilities for mutations are given
• performance: depending on what tree you mean a higher depth might increase performance (allowing for more educated guesses on the function) or decrease it (requiring more solutions to be generated and compared).

Why do I sometimes get a premature convergence and the GA never breaks out if the cycle?

That might be due to too little mutations. If you have a set of solutions that all converge around a local optimimum only slight mutations might not move the resulting solutions far enough from that local optimum in order to break out.

What can I do to prevent a premature convergence?

You could allow for bigger mutations, e.g. when solutions start to converge. Alternatively you could throw entirely new solutions into the mix (think of is as "immigration").

What about annealing? How can I use it?

Annealing could be used to gradually improve your solutions once they start to converge on a certain point/optimum, i.e. you'd improve the solutions in a more controlled way than "random" mutations.

You can also use it to break out of a local optimum depending on how those are distributed. As an example, you could use your GA until solutions start to converge, then use annealing and/or larger mutations and/or completely new solutions (you could generate several sets of solutions with different approaches and compare them at the end), create your new population and if the convergence is broken, start a new iteration with the GA. If the solutions still converge at the same optimum then you could stop since no bigger improvement is to be expected.

Besides all that, heuristic algorithms may still hit a local optimum but that's the tradeoff they provide: performance vs. accuracy.

Answer 2

In order to avoid premature convergence you can also use multiple-subpopulations. Each sub-population will evolve independently. At the end of each generation you can exchange some individuals between subpopulations.

I did an implementation with multiple-subpopulations for a Genetic Programming variant: http://www.mepx.org/source_code.html