Image Evolution

Ten days ago... No, wait. That's something else.

Eight days ago, I stumbled onto Genetic Programming: Evolution of Mona Lisa. I thought it was pretty awesome. Today, I stumbled upon this simulation of the same idea you can run in your browser. Doesn't work in IE, but I really hope anyone reading this isn't using IE (any version) as your default browser anyway. Right now, mine is at 1,077/17,000. That means out of 17,000 “mutations” 1,077 have been an improvement over the previous best fit. I just hit 90% fit. Which looks like 005874.jpg on the example shots from the original post. That leads me to believe the offline version is a bit more efficient than the online version, since it's taken about 3 times the number of mutations to get there. But that's to be expected.

I think the ability to watch it develop over time in your own browser hammers home the idea a bit better than the static example provided in the first post from Roger Alsing. But I think there's still room for improvement. For one thing, Roger's program makes it look like it would take almost 1,000,000 generations to get a decent replication of the low res detail of the Mona Lisa he used as his example. That's a necessary abstraction to get this kind of simulation to run on a computer. In real evolution, each generation produces several nodes, each with their own mutations. The node tree would fork out to very huge, very quickly, due to exponential growth.

But applying survival of the fittest to the tree structure would get us to the best fit much more quickly. The version that runs in a browser addresses this somewhat with the x/y display. I'm currently at 91.10% with 1238/23000. On average so far, it's taken about 18.5 generations to find a better fit. If we could fork that into a node tree, even a simple node tree of 2 child nodes per parent node, we'd hit the first improvement in about 5 generations. Actually, we'd almost hit the first 2 improvements in 5 generations. After 5 more generations, we'd be hitting quantum leaps where over 2,000 mutations are tried. And that number doubles every generation.

Ok, I'm proving to not be a strong enough math geek to really get these thoughts out of my head in a way that makes sense. But the way these programs are running is a bit like selection sort whereas the node tree approach is more like heap sort. In another browser tab, I just hit ~94% fit after ~ 50,000 mutations (but only 1900 improvements). Selection sort has an efficiency rating of n². So if it's taken ~50,000 steps to reach ~94%, that means n is about 224. Heap sort runs at n(log n), so to reach ~94% using that method would only take about 527 steps rather than ~50,000. That's a closer fit to the number of true, natural generations it would take to get the same sort of results through evolution.

A better approach to visualizing this sort of thing would allow for multiple source images and create a node tree instead of using the linear approach. The multiple source images would allow for a simulation of speciesization. The node tree would be less of an abstraction from the natural processes (although still astronomically simplified in comparison) and give a more natural indication of true “generations” required to reach a goal. Ideally, the number of descendant nodes would depend on past history of improvements. So “blood lines” that have produced a high number of improvements in the past would be more fruitful. Those with poor histories would get fewer chances, and eventually die out. There would also need to be a threshold after which a given line is only compared to the source image it seems to be naturally drifting towards. This would simulate the migration into more specialized environments over time. It would also cut down on the processing power required to make it all run, but such a system would experience exponential growth and would quickly overrun any processor or pile of RAM currently available. As abstract as such a program would still be, it would require hardware we won't see until quantum computing becomes a reality.