In early April, I posted my genetic algorithm program, and when it was out, I moved on, taking what I learned about genetic selection based algorithms, and started working on a simple "food seeking" program based on neural networks. The above program is the result. Each moving agent on the screen is an independent neural network, taking in information about its current position, where it is and where the goal is (on a Cartesian plane), running it through a series of "neural" layers, weighing the values of the inputs and producing new values, which in turn go through their own layers, until two values are put out: distances to travel on the x and y axes. This output is fed to the movement control of the agent (the code representing the object on the screen) and the little seeking agent moves in that direction. However, unchanged, the configuration of the network will send the agent in the same direction forever. Things really get fascinating when the agents reproduce. The agents that are heading to the goal at the fastest, most direct pace are given the highest fitness, but every agent is given some fitness value. The higher an agent's fitness, the more likely it will pass on roughly half or more of its "genes". In the last program the genetic information being passed on was binary strings, forty bits in length. This time, actual values between 0 and 1 are used, but the splicing process is the same:
Mate One's weight at [layer2][neuron7][weight2]: .6730 Mate Two's weight at [layer2][neuron7][weight2]: .1094
A splice randomly chosen to occur after second digit yields: .6794. The program randomly chooses who the first and second mate are, so if they were flipped, the new weight would be: .1030. This weight, and all the other new weights (if the splice point is before the first number or after the last, the whole of one mate's old weight is passed on), are given to an offspring network.
Unlike natural selection, the weakest are replaced every time without room for the chance that their betters get destroyed first by unexpected accident (flood, virus, comet, etc..). Based on fitness, the networks are sorted in descending order, and the least fit are replaced by the next generation of offspring. There is still always a chance for these agents to be replaced by their own offspring. On the screen no new objects are created by this process; the old vehicles for the weakest neural networks are taken over by their kin. The one exception is when agents stray too far out of bounds. If an agent wanders away (perhaps rejecting their goal seeking life), it is destroyed and an offspring is created somewhere on the board. The rate of replacement in this case is set to a tenth the size of the whole population, rounded up. Before replacement, though, the offspring go through a mutation roll. In binary, bits marked for mutation simply switched, 0 to 1, 1 to 0. In the interest of keeping mutations from changing too much, mutated digits will only go up or down one integer. This allows for a range of impacts from a single mutation: a mutation on the first digit after a decimal will greatly change the weight (especially if a 9 is increased to a 0) whereas one on the last digit will have nearly unseen change. The selection process was mostly finished a few days ago and I've spent the last few days tweaking the parameters and making the program look a little nicer. Lag from processing too much put a lot of constraints on what I could do, particularly in the process of mating/mutating networks. Allowing the program to lag makes for a poor visual program, so I spent today trying to write more efficient code, but so far I haven't made significant progress. Each network is built as a multidimensional array which, as far as I can figure out, requires an long, irreducible structure:
//for every network, a loop is run for(a=0; a<amountOfNetworks; a++) { //within every network, the user's desired amount of layers are looped for(b=0; b<amountOfLayers; b++) { //each layer has a desired amount of neurons which are looped for(c=0; c<amountOfNeurons; c++) { //and each neuron has the amount of weights equal to the amount of inputs it receives //neurons also have an additional weight that acts as an activation bias //the activation bias weight is subtracted from the combined value of all weights * inputs and the result is the output for(d=0;d<amountOfWeights { //network[a][b][c][d] is assigned or used for something here... }//d }//c }//b }//a
Each amount, the number of networks, layers, and neurons per layer, can be adjusted, but again, lag set an upper limit in this case. The above is actually a simplified version of the code. The first and last layers have to specialized; the first must have an equal amount of weights as the amount of initial inputs (plus one for the activation bias), whereas every middle layer has the same amount of weights: equal to the amount of neurons of the previous layer plus one. The last layer has to have an amount of neurons equal to the amount of final outputs, as each neuron acts as a single output. The result is three separate sets of the code above.
I found that the more layers and neurons I used, the better the program was at performing its task. Few layers and neurons resulted in agents drifting much farther away from their goal before adjusting to a better direction. Often, you'll see the agents headed slightly to one side of the goal, at some point passing it. More layers correlated with a faster "turn around" time for the agents, though I'm still trying to figure out exactly why. Anyway, lag limited my ability to see how far this trend went, and it also set the upper limit to just about four layers (five including output), with nine neurons each. I set the maximum number of networks to 30 on the slider bar at the bottom of the program. That is 9 neurons * 5 weights for the input layer, 9*10 for the next four layers, and 2*10 for the output layer - 425 weights per network time thirty networks. At the set maximum, 12750 weights are created at the start of the program; every twenty five milliseconds they are multiplied against their inputs and produce outputs; every fifty milliseconds (every other tick on the game "clock"), 1275 new weights are created, roughly ten percent of which mutate after they all run through the mutation dice roll. After that, the sorting and replacement is fairly efficient. I had the program running with two hundred networks, ignoring the amount of time the program hung, and saw enough to get the sense that too many networks actually hindered the selection process. One result I've noticed from the way the selection is set up in this program is that a small handful agents making smart moves can alter the course of the whole crowd if the agents are mostly in a group together (something that occurs on its own from the seeking process). If the goal is centered among distributed agents, the whole thing can go haywire. It will always work out, but it is hard to say when this is just because some random mutant baby happens down the right trajectory or if it is truly the result of corrective selective pressure. The pressure system seems to work pretty well though. A good agent can quickly hem in strays or stop the whole crowd rapidly, the most fit sending the whole group careening toward the goal. In this constrained environment, speed often results in slower goal achievement, as the whole group has to adjust for a longer period of time. If the whole group is going in the same direction, their children are going to have approximate trajectories, showing the importance of mutation and the rapid spread of successful mutants. A group, it seems, is best collected, but still spread out enough to allow for a greater cloud of fitness. It may be that I am alone in my excitement about this, but the promise of this sort of program is mind boggling. I do often have a mixed reaction to watching the program: I am amazed that a minimally complex program is able to perform such seemingly intelligent actions, its ability to "learn" built into its code. I am amazed that this sort of thing can be built by a novice programmer (I'm really only five or six programs into using Flash and ActionScript), and that selective pressure and evolutionary concepts work so well in such a simple medium of abstract representation. I am also amazed at how unintelligent the program can be. Earlier in the spring, I made a program that shot homing missiles at wherever the mouse was. With a tenth of the code that I used here, the missiles did a far better job at hitting their goal as fast as possible. This program does things that look almost random. Sometimes an agent, far ahead of the others, with no interference, will nearly reach its goal, only to abruptly backtrack, immediately becoming the least fit (as everyone else is catching up). The result is a flailing agent, moving left and right, adjusting over and over. Though this setting opens the door to strange occurrences, there are definite applications, with more constrained environments, that this sort of program is very useful for that are within my range of ability. I added the semi-transparent circles because, watching the program, I am reminded of videos of microscopic environments. I remember watching an amoeba chase a small, bacteria meal, shifting and turning as it followed.
