I've been interested in genetic algorithms and neural networks, but only recently had it occurred to me that I could create them with ActionScript 3.0. The idea and general processes for this program came from a great resource for this sort of stuff www.ai-junkie.com. The example code, however, was written in C++, so beyond the concepts, the code had to be written from scratch.
I threw the interface together pretty quickly once the algorithm functioned, so it isn't the best looking program, nor does it show you what happens when the algorithm runs. I am still really excited. The whole thing is fairly simple, but the result is pretty damn cool to me. When the algorithm runs, ten "chromosomes" of forty binary digits are randomly generated, each set of four digits representing a number, 0-9, or an operator, +, -, *, or /. The chromosomes are decoded and computed in order:
0110 0111 1100 0000 0101 1001 1010 0100 0001 1011
6 7 * 0 5 9 + 4 1 -
The result (in this case, (67 * 59) + 41 = 3994) is compared to the goal (the default is 20), and given a reproductive fitness: the closer a chromosome's value is to the goal, the more opportunities it is given to reproduce. After all ten individual chromosomes are decoded and given a fitness, individuals are randomly selected from the weighted gene pool to produce a new individual made up of a randomly spliced combination of the two parent chromosomes.
0110011111000000010110011010010000011011 parent one 1111000101001101001001001110100010011010 parent two 1111000101001100010110011010010000011011 new child
After the ten old individuals are replaced by new offspring, each chromosome is run through a mutation chance. In this algorithm, the mutation rate is set to .001, so each digit in every chromosome essentially has a one in a thousand chance to be flipped from 0 to 1 or 1 to 0. The mutation rate is low, but depending on where the mutation occurs, it could the result greatly. For example, some binary combinations, 1111, for example, don't represent anything, so they are ignored. A 0111 (7) changing to a 1111 would knock the 7 out of the equation entirely (or the opposite could occur, and a number could appear suddenly). A less drastic change could be something like a 0001 changing to a 0011, flipping a 1 to a 3. This, coupled with reproductive fitness, makes for a pretty successful system. Mutation prevents a whole population from being overrun for too long by a genetically fit, but not fully successful equation (this can be seen if the generations are listed out every time.. an equation the produces 7 instead of 8 is still so close that every individual becomes that equation, effectively removing reproductive variation and any chance of the equation getting closer), while on the other hand, only mutations that increase fitness are likely to be continued to the next generation.
Once the chance for mutations has passed, the ten new individuals are then run through the whole process again. In the end, one of two things occurs: either an individual's value is equal to the goal and the problem is solved, or the algorithm runs out of time and produces the best result available. I've set it run 2000 generations, one every .005 seconds, so it has roughly ten seconds. Some calculations slow the process down (the program can find equations for fractions, for instance, but the whole process crawls as it if it runs into equations that produce long or repeating numbers, so they were removed for now), which results in a longer time before the algorithm gives up.
Running the program a bunch of times yields two common results: either a solution is found, usually very rapidly, or the program gives up after dealing with an approximation of the goal (i.e. 19.925 instead of 20).
For speed and simplicity, I kept the population at ten individuals and assigned a limit that gives only a small window of time for the algorithm to find an equation. If the program had a larger population and more time, I am confident it could find solution at a much greater rate of success. Still, the fact that it works as well as it does is astounding to me. The next step is to implement this sort of algorithm in a neural network!
