Wednesday, December 10, 2008

Genetic Algorithms and Mona Lisa

Genetic Algorithms try to apply evolution mechanisms to find solutions to hard problems (typically, where no "proper" solution is known and where the search area is large).

Roger Alsing posted a couple of days ago an extremely cool article showing the convergence of 50 polygons to represent the Mona Lisa, using a random approach.

That was too cool to not try to implement it :)

The screenshot shows a rendering of the Mona Lisa using 50 polygons (16 points each), after 40818 total iterations, with 4577 elected states; the middle image is the original (i.e. the target) and the right image the difference between the current polygon-based image and the target (i.e. a representation of the fitness function).
Underneath was an earlier attempt using ovals instead of polygons.

Now, to be more exact, Roger Alsing's algo is more a hill climber algorithm or possibly a simulated annealing algorithm than a good example of a genetic algorithm; it should be interesting to actually implement a proper genetic algorithm approach (i.e. a population > 1) and see how the convergence rate compares... combining polygons and ovals might also result into interesting things.