(Warning! This is a long one!) This is a really intriguing concept. I've often daydreamed about writing something like this, but didn't have the time or expertise to go about attempting an implementation. It's so cool to see others doing this.

What would be really cool with these optimizers is if the stored databases of "patterns" could be shared. In other words, if the optimizer stumbles across a particularly excellent implementation of a particular code goal, it would be uploaded to a central database and cached for reuse and further mutation. People all around the world would be working from, and contributing to, one giant database of randomly discovered optimization techniques.

As a field of study, I also feel like stochastic optimization has a huge potential for improvement over the coming years. Recently, I had the problem of trying to space equally-sized spheres as far apart from each other as I could -- in other words, if I have 361 points that I'm putting in a box, I want the minimum distance between two points to be maximized (this is the fitness function).

My first attempt was to give each point a "charge" and attempt a little electrostatic simulation. This didn't work that well, for various reasons. After stumbling around for a while, I decided to attempt a genetic mutation algorithm. I had never written anything like this before, but I thought it would be fun to give it a go.

Initially, my program randomly placed points in the box. Then, for each point, it finds its nearest neighbor and computes the distance to it. I then take the average of all these distances, so I essentially have the mean nearest neighbor distance. On the next iteration, all points less than this mean value are perturbed. The process is repeated until no random perturbations produce improvement.

This worked alright, but it needed more. I kept modifying my program, but in the process of modifying it, I introduced a bug that somehow actually made the code the converge to a larger minimum distance (which is the goal). Inspecting my code, I realized the source of the "error": in the process of computing the distance between a point and its nearest neighbor, I was setting an initial "minimum" distance, which was supposed to be infinity. As closer distances were found, the infinity was replaced, so eventually it ends up with the closest distance. Well, it turns out that instead of infinity, I had been setting it to something like 10 (for a 100^3 box). So if the nearest neighbor distance was larger than 10, it was still a value of 10 that was contributing to the mean NN distance!

I soon realized that I could also modify the distances that I randomly perturbed the points in each step, and that some values worked better than others. Not only that, but that larger perturbations worked better at the beginning of the convergence, and smaller perturbations worked better toward the end of the convergence. So I created a heuristic that based the next "perturbation distance" on the most recently successful distances.

But this wasn't enough. Eventually as the perturbation distance became smaller, the convergence process would "stall". I found that by temporarily increasing this distance, the system would find new mutation paths that would get the program out of its local optimum and move it forward again. But how frequently do I modify this distance?

The more code I wrote, the more I realized could be changed. There's a ridiculous amount of parameters that could be optimized in my optimizer, and I was just sitting there tweaking them by hand and testing what worked best. The thought occurred to me, why don't I write a program, that writes a program, that optimizes the sphere placing problem? And then, darn, I may have to write a program that even optimizes that one.

Well, I had to get this thing done -- since it was for my research -- so I couldn't go off on a tangent and I had satisfactory results. But the sheer number of techniques to optimize this thing left me highly intrigued, and I will certainly be revisiting my program when I can find time to do so.