I have been working on a pet project lately. I've been trying to write a genetic algorithm to solve a simple test problem. In case you don't remember genetic algorithms are search techniques designed to find problem solutions by mimicking natural occurrences from the field of evolutionary biology. They are part of the larger studies of Biological Computing and Artificial Intelligence. Long ago (and I'm not saying how long) I studied these and other algorithms as part of my graduate work in Computer Science.
The basic premise of a genetic algorithm is that you first initialize a search space with potential solutions each represented as some sort of string. In biological speak each string would be a gene. You then follow the space (i.e. the gene pool) through successive generations as some genes die, others strengthen and new genes are created through mutation and crossover. This is all supposed to be the computer representation of natural selection in process. With each generation, the "best" genes are selected and new, hopefully better, genes are created by mutating and combining the good genes. The idea is that, if this process works so well for finding unique biological solutions, why wouldn't it work for computer problems?
The problem I'm trying to solve is purely recreational—I'm trying to write an algorithm that will discover the correct solution to a Rubik's Cube from a random start condition. Some problems are so difficult that a particular approach won't generate a viable solution. I'm so blind on this project that I have no idea if I'll succeed or not. To my thinking, the search space—the pool of potential solutions—is relatively small. And I'm starting with the knowledge of the exact result I want. Generally it's easier to write a search solution when you know in advance what you're trying to find. Have I succeeded? I don't know. I'm spending quite a bit of time early on just figuring out how best to represent my genes and how to manipulate strings in C.
But this does take me back to my study of AI—or, as I like to call it, advanced algorithms. Honestly I miss this kind of work. In some ways the advent of the internet has moved computing ahead by orders of magnitude. What were once disjoint point solutions are now part of the global connected computing landscape. But, in others ways, the internet has actually moved us backward (my opinion). This is especially true as pertains to unique or elegant algorithms. For example, have you ever heard anyone wax rhapsodically about the elegance of HTML embedded in a classic ASP page? No you haven't—because it is anything but elegant. In some cases it's nearly illegible.
But I digress. The point is I'm back at it; using what I remember about genetic algorithms to see if I can answer the age old question, "Can we really get all the red cubes on the same side?" My hope is that success on this test project will open my mind to other ways I can use this technology to solve more meaningful problems and maybe find a solution that I didn't already know before I started. Wish me luck!