Genetic Algorithms are something I’ve found intriguing for a long time, but I’d never got around to actually implementing one. A recent flurry of blog posts and forum chatter about them – such as this program for evolving the Mona Lisa as a vector image, or this one which breeds vehicles, rekindled my interest. I quickly found a tutorial outlining the basics, and posing a sample problem: given a series of disks in a given area, find the largest disk which fits within the area without overlapping any of the others. I’d been planning to work, as usual, with SAGE, but the graphical nature of this problem gave me an opportunity to dive once again in to processing, which as it happens has recently left beta.

You can play with the results here; for an afternoon’s coding, I’m quite pleased with it as a proof of concept even though it doesn’t always do a fantastic job of solving the problem! As implemented, each run generates a fixed obstacle set of a dozen disks (in black) and an initial population of 25 candidate solutions. The ‘genome’ is 28 bit, split 10/9/9 for x co-ordinate, y co-ordinate and radius. Disks that overlap an obstacle or go off screen are awarded a fitness of zero and painted red; otherwise the fitness function is simply the radius. In line with the tutorial, I pick pairs by roulette selection based on this fitness (so red disks shouldn’t survive into the next generation), breed by crossover at bit 20, and mutate about 1 in 200 bits.

However, for this particular set up the crossover approach doesn’t seem ideal- offspring will inherit almost exactly the co-ordinates of one parent and the radius of the other. This often means large areas of the screen are missed unless a chance mutation moves a disk, which then has to be lucky enough to produce a few offspring in the next generation. It might work better if I generated offspring bit by bit (say, taking bits from each parent a certain percentage of the time), rather than the simple cut currently in use. Fortunately, it shouldn’t be hard to experiment in this way; ideally, I’d build several algorithms into the applet and offer a choice at runtime, as well as control over the assorted variables. If nothing else, it’s teaching me a lot about processing, which I continue to be impressed with.