For more experiments and code, check out my flash programming blog.
## Tiny Genetic Programming Library in AS3 and C++By Forrest Briggs, March 23, 2008## GP Art DemoImagine there is a population of animals with different patterns on their skin. Members of the population that don't blend in with their environment are eaten by predators, and members of the population with good camoflouge survive and reproduce, passing the genes that encode their skin pattern on to their offspring (possibly with slight mutations). Over time, the population will evolve toward a well-camoflouged skin pattern. In the demo below, each image is like the skin of an animal in an evolving population. When you click on one of the images, you play the role of the predator, and effectively eat all of the other members of the population. The one surviving member reproduces, creating the next generation of the population.Inspired by the Tiny GP Contest, I decided to write my own tiny implementation of standard genetic programming (there are many other kinds of GP, but standard GP usually means GP as presented by John Koza). The demo above uses the TinyGP library to generate random evolving art. Each image above comes from a randomly generated mathematical expression. Mouse over an image to see the expression that generates it. Click on an image to replace the entire population of images with mutations of the image you clicked. Click the randomize button to randomize all of the images. You can download the AS3 source for the tiny gp art demo. ## GP Regression DemoThis next demo requires a slightly more technical explanation. One of the many uses of genetic programming is non-linear regression—finding an equation that fits a set of example input and output data. In this demo there are two fields where you can enter a series of inputs and expected outputs. Click the 'Start New Problem' button, then click the 'Run' button. It will generate some output that looks like this:```
best: (+ x x) depth=2 size=3 fitness=0 evals=100 avgFitness=32.66962
``` Let's look at what this output means piece by piece. The first part, `best: (+ x x)` means that `(+ x x)` is the best expression it found to match the example data. The expression is written in prefix notation, and means the same as x + x or 2x. Notice that the example data we gave it exactly matches the function y=2x or y=x+x. Next, we have `depth=2 size=3` , which describes the size of the best expression it found. After that, `fitness=0` indicates that the error of the best expression with respect to the example data is 0, i.e. it exactly matches. After that, `evals=100` is the number of expressions it has generated and tested so far. In this case, it stopped at 100, even though we told it to run 500 iterations, because it found a solution in the initial random population (which has 100 members). Finally, `avgFitness=32.66962` is the average error of all members of the population.
You can experiment with entering your own example input and output data. Keep a few things in mind: - Remember to press the 'Start New Problem' button before you click the 'Run' button, and whenever you change the example input and output data.
- The input and output data must have the same number of items.
- This demo is configured to make only expressions that use +, -, *, / and the number 1. If you give it data that cannot be modeled by an expression consisting only of these primitives, it will have no hope of finding a perfect match. However, it is not hard to modify the code to add more functions.
## Genetic Programming Implementation DetailsNow that we have seen some demos, lets get down to the technical details of this code. This GP library uses the standard Koza expression tree program representation. It uses the 'grow' algorithm to generate random expressions. Mutation is performed by selecting a random subexpression in an expression tree, and replacing it with a new random expression (which satisfies the maximum tree depth constraint). Crossover (mating) between two expressions is performed by selecting a random subexpression in each parent, then exchanging them (although it only makes on child, not two).In addition to the core code for creating, mutating, mating and evaluating expressions, the library includes a steady-state genetic algorithm with tournament selection, and a worst-out, elitist replacement policy (i.e. when a new child is created, it replaces the worse member of the population, only if it is better). Note that the art demo does not use crossover or the steady-state genetic algorithm; it just uses random expression creation and mutation (which is like a stochastic hill climbing algorithm). ## Implementation in C++I originally wrote the TinyGP library in C++, then ported it to ActionScript 3. You can download the C++ source code for TinyGP. One nice thing about the C++ version is that it is all contained within one file, so it is easy to add to other projects (this wasn't possible in AS3, because each class must be in a file with the same name).Asside from differences in language syntax, the two implementations are algorithmically identical. I timed both implementations running through 1000 iterations, and the C++ implementation is about 10 times faster than the Flash implementation. ## Strongly Typed, Functional Genetic ProgrammingTinyGP is simple as far as genetic programming systems go. If you want to see some really fancy genetic programming, check out my research on strongly typed functional genetic programming with combinator expressions (shameless plug): Genetic Programming Bibliography for Forrest Briggs. It can evolve expressions in a subset of Standard ML, and functions that operate on arbitrary recursive algebraic data types, rather than just numbers. |