2D Optimiser
Optimisation algorithms demonstrated by redrawing famous pictures.
Live Demo
Choose an image to optimise.
Upload your own image.
Approximating the Mona Lisa with mathematics
Description
Optimisation algorithms find solutions to problems that are impossible to solve any other way. They are a last-resort, because they are very slow and and the results are often not very good.
The demonstration on this page solves a trivial problem, the hard way: to re-create a picture, using only coloured triangles(or circles, or letters!).
The computer starts off with a random selection of triangles, then moves them around one by one until it has the best copy it can make. You can watch this happening above, as the computer draws each triangle over the picture to see how it fits, then moves it and tries again.
The demonstration switches between three modes. The "hill climber" algorithm shifts each triangle slightly, to see if the new position is better. The simulated anneal shakes the picture and knocks all the triangles out of place, in the hope that they might end up somwhere better.The "extremal" algorithm finds any triangles which have disappeared and moves them to a random position.
Background
In 2008, Roger Alsing posted his code to draw the Mona Lisa using Genetic Evolution techniques. This project is a continuation of his idea, with different techniques. I use triangles instead of random polygons, and I use a different optimisation technique. Despite this, or perhaps because of it, I get a pleasant abstracted picture.
I use a hill climber. The hill climber examines nearby positions in the solution space, and picks the one that gives the greatest improvement to the picture. You can see this process in the picture above, as each corner of the triangle moves around to find a better fit. Hill climbers are easy to understand and implement, but they have a drawback - they get stuck on a local maxima, resulting in a picture that is only half done. For instance, a triangle might work better on the other side of the picture, but there is no way for it to jump all the way across.
To fix this, I added a round of extremal optimisation in between each round of hill-climbing. The extremal algorithm finds the triangles that are definitely in the wrong place, and randomly moves them to a new part of the picture. This catches triangles that the hill-climber has made invisible, sometimes by making them into thin lines, sometimes by turning them completely transparent. Randomising the values allows a triangle to escape from this position.
Finally, I added a simulated annealing algorithm, which shakes the picture and knocks all the triangles out of place, in the hope that they might end up somwhere better.
The original program uses genetic algorithms to adjust the polygons, and according to the author's report, the genetic algorithm converges faster than this hill climber. This is what we would normally expect. Hill climbers tend to converge slowly, but are easier to understand.