genetic programming

Genetic programming in the cloud

I've been working with genetic programming on and off since the early 90's. I haven't done anything with respect to research, but I have played with GP for various problems. Occasionally I've played with image processing in GP, and recently I've gotten interested in applying GP to the DIY Book Scanner dewarp problem. I don't have a particular direction or plan in mind (otherwise I'd be a Fully-Baked Maker), but I figure I'll start with some basic image processing routines and work up from there.

I use ECJ as my GP engine.

My original forays several years ago into image processing GP involved images of 16x16. I didn't really have a good enough processor or good enough libraries to handle bigger images. Today, I'm using bilevel images of actual pages, scaled down 8x. The resulting images are about 300x400, which is a huge step up from my little 16x16 toy images. Nevertheless, my laptop can process these images in GP well enough.

My first idea was to set up a problem where GP had to find a sequence of operations which would yield the following image: IMG.closeBrick(10, 2) & IMG.dilateBrick(2, 3). The closeBrick(w, h) operation performs a morphological close using a structuring element that is wxh, all hits, and center at w/2, h/2. Similarly, dilateBrick(w, h) performs a morphological dilate using a wxh structuring element, all hits, and center at w/2, h/2. The & operation performs a pixel-by-pixel AND operation.

As primitive functions, I used the following list:

IMG: → img: returns the source image
And: img, img → img: returns the pixel-by-pixel AND of two images
Or: img, img → img: returns the pixel-by-pixel OR of two images
Xor: img, img → img: returns the pixel-by-pixel XOR of two images
Inv: img → img: returns the pixel-by-pixel inverse of an image
Shift: int, int, img → img: shifts an image by a number of pixels
CloseBrick: int, int, img → img: morphologically closes an image with a brick
OpenBrick: int, int, img → img: morphologically opens an image with a brick
ErodeBrick: int, int, img → img: morphologically erodes an image with a brick
DilateBrick: int, int, img → img: morphologically dilates an image with a brick
W: → int: returns the width of the image
H: → int: returns the height of the image
One: → int: returns 1
MinusOne: → int: returns -1
+: int, int → int: adds two integers
-: int, int → int: subtracts two integers
*: int, int → int: multiplies two integers
/: int, int → int: safely divides two integers (returns 1 if divisor is 0)

The integer parameters to the morphological operators are negated if negative, and limited to 0-199. This means if, for example, H,-H are the parameters, the brick will actually be 199,199.

Individuals are scored against 167 images. Each pixel they get wrong adds one to the error count. The result is scaled by the total number of pixels (167x300x400) which doesn't affect the GP algorithm since it's only a scaling factor. Thus, 0% is a perfect score, and 100% is the worst score.

I started a run of 3000 individuals and let it run overnight. About twelve or so hours later, I had gotten 20 generations, and a score of 5%. Looking at the best individuals, it was clear that GP was approaching the answer, but very slowly. There was no way I was going to solve this problem, let alone a dewarping problem, with my laptop.

Then I remembered this thing that was being trumpeted a few months ago: the Amazon Elastic Compute Cloud. I did some research into it, and found that it was surprisingly (and refreshingly) cheap. No cost to sign up, and you pay for virtual compute instances by the hour and storage by the month. Linux compute instances are anywhere from 9 cents per hour up to $2.40 per hour, depending on memory, storage, number of cores, and so on, but I've found that using spot instances, where you bid on instances, you can get the price down by more than half.

The instance I chose was an 8-core 64-bit instance with low memory, for 68 cents per hour, or 25-30 cents per hour spot. I can run the "master" GP program from my laptop, which would store the individuals and perform evolution on them (the fast part), and run "slaves" on the instances (the slow part). With ten instances (for about three bucks an hour) I can run 80 slaves, and so run about 80 times as fast as my laptop. So in a single hour I might be able to get 130 generations or so.

The nice thing about ECJ is that slaves can come up and down while the master runs, and the master will just keep distributing individuals to whatever slaves are up for evaluation. So even if my spot instances die or are terminated, ECJ will still run.

I tried running with a single instance, and after about 40 generations, a little over an hour, GP had solved the problem. The winning individual:

IMG.dilateBrick(1,1).dilateBrick(199,1) &
IMG.dilateBrick(199,2).dilateBrick(199,199).erodeBrick(199,2) &
IMG.closeBrick(199,2) &

Note that dilateBrick(1,1) does nothing. The fact that this individual does the same thing in a different way than the required operation is normal for GP.

Runs with larger images take very long, even in the cloud. I may have to rethink the whole idea. Still, it's an idea, even if half-baked.