Genetic algorithms and Irrlicht

[Iaro]

This is a small program that uses genetic algorithms to find the local maximums of the Rastrigin function. The algorithm was initially written in visual basic, but I was curious how it would look in 3D, so it was rewritten in C, and uses Irrlicht for the rendering.

Each billboard simulates an individual in a population. Each individual can have a variable number of chromosomes. At each step the current population is evaluated, and a new population is constructed from the old one after applying genetic operators. The algorithm stops after a certain number of generations. You can play with the parameters by modifying the values in the param.txt file, but please keep in mind that for some settings the calculations take a lot of time. For example it takes a very long time to calculate 100 generations for 3000 individuals with 4 chromosomes each.

Download link

Keys:
Q - exit
arrow keys + mouse - movement
G - generate the initial population
C - step-by-step generation drawing - the billboard positions are updated after each generation.
T - billboard positions are updated only after the last generation.
Only press C or T after you have generated the initial population.

Some screenshots:

The initial population.


The result after 100 generations


A smaller scaling factor


To see if the algorithm also finds the global minimum, the Y position was scaled. Some columns start higher than others, but I still can't tell for sure if it indeed finds the minimum.

[JP]

Very nice! I did genetic algorithms at Uni, though i never actually programmed them, let alone did a visual representation of the process. Interesting stuff!

[BlindSide]

Who needs Matlab when you have Irrlicht.

(Just kidding!)

[rogerborg]

Very nice! I did genetic algorithms at Uni, though i never actually programmed them, let alone did a visual representation of the process. Interesting stuff!

Me too! Then I went to a GA conference, and asked one of the speakers that since the genome model doesn't really map closely on to many problem domains, and that it's a random process anyway, had he done real world tests on the efficiency of just randomly generating candidates (and using the fitness function to remember the single best one) versus the cost involved in doing all the selection and breeding?

You've never seen a nerd so outraged that someone would ask him if he could prove that the Emperor was wearing clothes. Ah, one of my happiest moments.

[cdrwolfe]

Very nice! I did genetic algorithms at Uni, though i never actually programmed them, let alone did a visual representation of the process. Interesting stuff!

Me too! Then I went to a GA conference, and asked one of the speakers that since the genome model doesn't really map closely on to many problem domains, and that it's a random process anyway, had he done real world tests on the efficiency of just randomly generating candidates (and using the fitness function to remember the single best one) versus the cost involved in doing all the selection and breeding?

You've never seen a nerd so outraged that someone would ask him if he could prove that the Emperor was wearing clothes. Ah, one of my happiest moments.

Probably because it would be a waste of time to just randomly create a set population of solutions and check there fitness in the hope you manage to find the optimal one

Also even though it is on the whole 'random' it is also heavily weighted to fitter solutions.

Regards Wolfe

[rogerborg]

Probably because it would be a waste of time to just randomly create a set population of solutions and check there fitness in the hope you manage to find the optimal one

Tested that hypothesis, have you?

First, GA techniques are useful when there's no single recognisable "optimal" solution, since if you could recognise it as such, the definition of it would provide the solution. There's only "good enough" solutions, as recognised by your fitness function. The issues are: how good a solution can you find in the time that you have available; or, alternatively, how long does it take to find an acceptable solution.

The GA method should trend towards better solutions, but doing GA selection and breeding is a computationally expensive method of producing new candidate solutions - especially when you have to resort to skulduggery to escape from local minima - compared to randomly generating many new solutions.

Consider that maintaining a "population of solutions" isn't necessary. You just create a single random solution, using the same algorithm that you'd use to create your initial population - which had better be capable of creating solutions that contain the genes for a "good enough" candidate, or you're wasting your time either way - then test it against your fitness function. Repeat, remembering the best one. Stop when the solution is good enough, or you run out of time.

Run that algorithm in parallel against a GA breeding population, and see which one produces an acceptable solution faster, or a better solution when you run out of CPU cycles.

Which method wins will be heavily dependent on the problem domain, how fit a solution you need, how much time you have to find it, and good old (psuedo)random chance. But discarding the possibility that an acceptable solution can be found more efficiently (in CPU cycles) with a relatively simple random search than with a computationally expensive GA is Faith Based Design.

If that's unpalatable for GA True Believers, then you can compromise and at least spend some cycles pruning retards out of your initial population before starting the GA running. That's a method which I have just this second decided to call "Spartan Seeding". You read it here first.

[cdrwolfe]

Oh i never said or ment that GAs will always lead to the Optimal solution, generally as you say they give good to average soltuions in good to average time.

But if you have an extremely large search space it is nice to have a guide .

And as you say it is dependent on the problem domain, and also to be honest i've always gone in fitness evaluations rather then CPU cycles as a means for testing efficiency.

If you look at somethng like bitmax on a string of length 10, where you try and increase the number of 1's on the string there are 1024 possible solutions.

Only one solution is correct so if my probability is correct which it probably isn't thats a 1 in 1024 chance or 0.097656% chance of getting a correct solution each random generation of an individual.

Now a simple GA, has to select, alter, choose and then replace to get new solutions, which is no doubt considerably longer then just randomly generating a solution.

It would be interesting to see which is quicker, no doubt the simple random generator can pump out more solutions faster and probably though i don't rightly know find the solution quicker.

That's a method which I have just this second decided to call "Spartan Seeding". You read it here first.

I think it's called selective pressure, Darwin has you beat .

Regards Wolfe

[gogo]

I could not open zip. Give me MS-zip or rar.

[Iaro]

In rar format.