Stochastic hill climbing: Sisyphus pushes an image
This run took around two days, for around 100.000 generations (estimated count, as generations are not in the "usual" generation count system).
The algorithm works as follows. Given an image we want to approximate, for each generation we do:
1. If we can add a triangle, try to add a random triangle MaxSteps times. If the image is closer to the original, go on.
2. Depending on a random factor, either
- Changer: Take one of the given triangles of the actual approximation by a random choice and try to change it to a better one, try to do it for a random number smaller than MaxSteps.
- Pruner: Try to remove one triangle of the set (try for every triangle)
- Mover: Try to move every triangle to every possible position in the triangle list (for every triangle on the list). It starts in random positions in the triangle list, not to bias moving the "underneath" triangles.
- Swapper: Try to swap every pair of triangles. As above, but swapping every two triangles.
I have set also several thresholds. First, I set a maximum number of triangles, and divide it by 20 (for example). Then, divide the initial error by 8 (for example also, but these are quite good numbers) to have a FitStep, and every time the current fit result for the image is smaller than InitialThreshold-Function(FitStep), increase the number of triangles (if smaller than the total maximum). I added this after realizing that most of the first placed triangles were mostly crap, with this method I try to get for each number of triangles, somewhat like the best possible approximation. This part works quite well, the problem is the later addition of triangles, which is not as good. In the previous plot, the green lines show the triangle add thresholds.
After this, I also realized that random changes for all parameters in a triangle were too random for a change, more so when the image was quite close to the original. Thus I added a Jiggler step, which is chosen randomly instead of Changer, which just moves a little the triangle parameters for every triangle (starting from a random triangle in the list, and for a certain number of tries).
I'll post the corrected source soon (it is already in my googlecode repository, but it lacks comments and the most obvious tweaks, and also the shell scripts used to generate the postcard), hope you can wait for it. If you have any suggestions to improve the algorithm, you are really welcome.
C code juicer: detecting copied programming assignments
Cron, diff & wget: Watch changes in a webpage
9 programming books I have read and somewhat liked...
8 reasons for re-inventing the wheel as a programmer
My take on logical mazes: Part 1