For those of you who are interested in evolution / GP.
Here is a small app that I made to reverse engineer blackboxed formulas.
The application is fed with a “problem domain”
The problem domain consists of multiple cases, like this:
When X is 1 and Y is 2 I want the result to be 3
When X is 3 and Y is 5 I want the result to be 8
When X is 10 and Y is 10 I want the result to be 20
That was a very simple problem.
And the formula to solve the problem would be (X+Y).
Ofcourse the problems aren’t described in english, it’s code. but this is the idea behind it anyway.
Once the application is fed with a problem domain, it will create a population of “formulas”
Each formula have its own DNA, the DNA in this case is the various functions, constants and variables.
Each formula in the population will be fed with the data from each problem case and then evaluated.
Depending on how close to the goal the result is, the better the error level is.
Once each problem case have been evaluated by a formula, all the error levels per case will be summed up.
The summed error level is then used to decide what formulas are allowed to survive and breed.
(There is also a bit of crossover going on between formulas, but I won’t get into that now.)
So how fancy stuff can this application solve?
Well, here are some examples:
Problem data and result is shown on the pictures.
And no, it does not care if the result is pretty, it just strives to find a working formula.
ofcourse this could be altered so that once the solution is found, it continues to evolve and promote shorter formulas.
Complex solution, the application generated a formula to convert decimal 0-15 into binary representation:
After some optimization of the final formula it came up with this:
((((int)(((((100 * ((int)(-8) & (int)(x))) - (-23 * ((int)(-4) & (int)(x)))) + x) - 2)) | (int)(7)) + 1) + x)
Not the prettiest formula in the world, but it does what it is supposed to..
Also consider that the extensive use of “(int)” is not really generated by the application,
Its my ToString implementation of binary operators that add those.
If we remove all the extra clutter which is really only part of the visual representation, we would end up with this:
(((100 * (-8 & x) - (-23 * (-4 & x)) + x) - 2) | 7) + 1 + x;
I find it quite interesting to see how evolution solves the problem, it’s far from how a human would have solved it.
Evolution also have a habit to cheat, and very much so.
Eg, if I allow the application to use the XOR binary operator, it sometimes finds XOR patterns that can be applied to the problem cases, and thus solving the problem, but not the way you might have wanted it to..
Anyway, for those interested:
The application source code (C# 2) can be downloaded here:
Genious! Simply genious! I just love reading about this kind of stuff! =D
I was thinking about doing this in php the other day just for kicks, but I kind of gave writing something that could generate mathmatical functions (offspring) that was actually valid.
Though.. I guess that wouldn’t be needed, as any function that resolves into an error would get a pretty horrible fitness rating. =P
How do you generate and alter the functions when you create a new generation?
Do you evaluate a whole generation, kill off the stragglers, make a new generation from the winners and repeat? Or do you breed two of the best members of a population, add their offspring and kill off an equal number of members from the bottom of the fitness list?
thanks for the information about genetic programming, I am still learning about the genetic programming and a bit confused about how this program is to generate the initial population? Can you give an explanation to me. thanks in advance.
My best bet is that the initial population is completely random. You could of course shape the initial population yourself if you wanted to try to influence the evolution towards a spesific result, but for the most part, randomness and a large number of individuals rules.