Comment by antirez | Hacker News Reader

Comment by antirez | Hacker News Reader

It looks like it no longer does much progresses after some time. Many years ago I wrote one of those stuff, just a few days after the famous 2008 blog post doing the same (http://rogeralsing.com/2008/12/07/genetic-programming-evolut...). However after some time I switched the code to use simulated annealing, and it performed better. I'm running it for a few minutes against the Monalisa image to see what happens. Btw I had a plan to release the code after some cleanup, maybe tonight is the right moment after 6 years of this code hanging on my HD.

EDIT: after 6 minutes (64 shapes) -> http://imgur.com/gyZCjBD

EDIT2: after ~15 minutes -> http://imgur.com/5XMU8vH

Now trying using just triangles, again with 64 shapes, I remember it was much better than when using circles for most images.

EDIT3: Oh, much better now, after 6 minutes (64 triangles) -> http://imgur.com/x9E9TmK

EDIT4: 10 minutes more and she got a nose: http://imgur.com/bX8UTIQ

EDIT5: Code released! https://news.ycombinator.com/item?id=8710418

I took a course on this stuff in uni, it was so fantastically fun to play with.

Simulated annealing has less cachet than GAs (and other evolution-inspired approaches) but tends to perform well enough on lots of problems that you might as well skip GAs.

I haven't dug much on the linked GA, but it looks like it converges too quickly. That's a classic problem (exploration vs exploitation, aka coverage vs convergence) in optimisation problems. The problem I practiced on was Ackley's Function[1]. Even in 2 dimensions it's really good at tripping up algorithms that converge too eagerly.

Some GA methods actually make the parameters of the system part of the genome, but as I recall it doesn't make a huge difference overall. Fun to think about though.

Mind you, the No Free Lunch Theorem means that there's a place for everyone in the heuristic computing tent. And simple random sampling (monte carlo method) and/or graphing can be very helpful for looking for the contours of a solution space. There's still room for humans too.

[1] https://github.com/jchester/ruby-ackley-genetic-algorithm

Totally agree one reason why it converges so fast is because independent solutions are unlikely to produce a better offspring when crossed, so basically my feeling is that it ends with a very similar population and most of the evolution happens just because of the mutations... that's why I eventually switched to SA. Another funny thing is when the improvement you get because of the algorithm is not compensated by the drop in performance: working with just a set of triangles that fit the cache can be a true boost.

Ah, good point about crossing. Each individual actually faces enormous local selection pressure, so once a given triangle converges closely enough, offspring just aren't going to be selected upon crossover with a (possibly very different) neighbour.

So actually I think this demonstrates a kind speciation in a very sharply divided landscape. It'd probably work better on simple images with smooth gradients and the like.

> That's a classic problem (exploration vs exploitation, aka coverage vs convergence) in optimisation problems.

The nicest approach to exploration/exploitation I've seen for simulated annealing is to run two searches side-by-side. Their relative "temperatures" (ie. probability of accepting a worse solution) depends on their relative fitness: if both are the same fitness, both have the same temperature; if one has higher fitness than the other, its temperature lowers (so it can "focus" on that high-fitness region) whilst the other's temperature raises (so it can "spread out" to find higher-fitness regions).

Also, regarding the No Free Lunch Theorems, I don't give them much thought since they don't take the computational complexity of the problem into account. They say that every search algorithm, when averaged over all problems, achieves total performance that's the same as random search. The real world doesn't contain all problems; in particular, we care more about (computationally) simple problems than unrealisitically-complex ones. Worrying about NFL for search is like worrying about adversaries with infinite computing power in crypto; yes your algorithm will be weak against such an attacker, but it's unrealistic to care about.

For me the two lessons of the No Free Lunch Theorem are:

1. Stop trying to prove that your solution is the "best overall"

2. Hooray, we can pick and choose our tools.

Excellent observation! In this video, Dr Christos Papadimitriou lays out a compelling argument for why genetic algorithms are poor at optimizing individual fitness when compared to simulated annealing. The video is about asexual vs sexual evolution and how it connects to multiplicative update/weighted majorty type algorithms. https://www.youtube.com/watch?v=cWv-s6KuDlM

Gets to ~97% in the first few minutes and then takes a long time hunting for very small gains. I was hoping to see more dramatic improvement after the first couple of minutes as well, but I was amused by the thought that followed after my evolving image failed to look successively more like a Mondrian.

We were told early in public school that we share 98% (or some such very high number percent) of our DNA with our simian relatives. I always was amazed at how just small a section of the genome was responsible for such amazing diversity among primates, or even mammals in general.

Seeing the wild differences that result in these images when you're given 3% of leeway between generations really helps me appreciate the vast number of individuals in our species!

Reply on news.ycombinator.com