My last blog post showed how the computer can evolve a car, which though exciting, is not particularly useful. Put any 10 year old to work on the same problem, you can rest assured that they will be able to quickly create a strong, fast, and reliable car much quicker than the genetic algorithm will achieve.

a 10 year old is better than a computer

However, a genetic algorithm’s great strength is not in solving the simple problems. The car, for example, only has a few parameters. You have four circles, each with an X & Y location, and a radius. You have 6 springs, each with a stiffness value. That makes a total of 4*3+6 = 18 parameters. Easy enough for most people to handle.

For a computer, the task is not so easy. It has to represent the solution as a long string of 0s and 1s (DNA for the car). If you assign a byte to each parameter, at 8 bits per byte, that is 8 bits / parameter * 18 parameters = 144 bits (0s and 1s). The computer has to come up with the 144 bit number that best represents the car, and it has to do that randomly.

When we consider the number of possible cars you can create using just those 18 parameters, the prospect for a computer can be quite daunting.

the computer has a LOT of possibilities to choose from

The first solution is obviously a DNA of all 0’s. (0000000000000…). The second is 1000000000…, then 0100000000…, then 11000000…. and on and on. It turns out that the number of possibilities is 2^n, where n is the length of your DNA strand. For the 2D car, that’s 2^144, or 22,300,745,198,530,623,141,535,718,272,648,361,505,980,416 possibilities! (thank you Wolfram Alpha).

The computer is a dumb, dumb machine, and it lacks the intuition of a human. It has to mindlessly bounce around, trying solutions and randomly mutating what it gets as it painstakingly inches closer to a better solution. However, it has evolution on its side. That, well, and speed.

Because of natural selection, mutation, and the fact that a modern day processor can crunch numbers like there is no tomorrow, it can quickly plow through test after test, slowly whittling down the possibilities until it gets a good one. Also, because it is random, is cannot, and does not, ignore all the possibilities, even funky ones a human might overlook.

So you can beat a computer at 2D cars, but a genetic algorithm is really good at tackling problems which a human cannot easily perform. Inspired by a post, greg wrote his own. Seeing how cool it was, I had to follow suit.

The problem presented is as follows. You have to create an image of some predetermined picture. For Roger Alsing and Greg it was the Mona Lisa. For me, it was Mario. However, you can’t just paint it, or even copy it pixel by pixel. No, you have to render it using a stack of shapes. 300 squares of any rgb color, opacity, size, and color should do it.

Evolution of a Mario image comprised of 100 squares

No human (to my knowledge) can do this like a computer can. Plus, It is only the tip of the iceberg if you are willing to take a closer look.

For this problem each square is represented by 7 variables: X,Y, side length, color (R, G & B), and opacity. You have 100 squares. That makes 8 bits / variable * 7 variables * 100 squares = 5600 bits. The number of possibilities is 5.86*10^1685. That number is so large, the number of atoms in the universe (approx 1*10^80) is an insignificant speck. If, for each atom in the universe, you had another universe with the same number of atoms, then counted all the atoms in all of the universes and did this 21 times, you would start getting close. The computer sorts through this gaping eternity of possibilities and finds one which works pretty darn well.

But that wasn’t hard enough.

Evolution of a Mario image comprised of 300 triangles

Here we have Mario made of 300 triangles, considerably increasing the problem’s difficulty (while increasing the potential for a better match). Here we have 3 X,Y coordinates, color (R, G & B), and opacity, making 9 variables. That makes 21600 bits, and 1.76*10^6502 possibilities. Unbelievable.

Genetic algorithms are mindless searching methods looking through a massive (mindbogglingly so) set of possible solutions to come up with something that works well.

And here we were, proud of our 2D cars.

That is why genetic algorithms are so amazing, and why evolution itself is so amazing.