|Wesley R. Elsberry
Joined: May 2002
My MacBook Pro suffered a mainboard failure some time ago, and I just bit the bullet to get it fixed. That was the development machine for my Avida work. I thought that too much bit rot might have rendered things uncompilable on Linux anymore, but I'm happy to say my initial pessimism was unfounded, and I now have a running Linux executable.
I should note just what I'm talking about here. Back in 2009, I presented a paper with my colleagues at Michigan State University titled, Cockroaches, drunkards, and climbers: Modeling the evolution of simple movement strategies using digital organisms. I'm working toward taking the next steps in this research. To do that, I needed to get my tools up to date. Where I have the computing power now is in an 8-core desktop running Ubuntu Linux, so I was aiming to get my code compiled there. That's happened just this week. I've been running tests to make sure I'm getting results as I did back in 2009. And the newly-compiled system is, I'm pleased to say, showing the evolution of gradient-ascent effective methods just as the runs in 2009 did.
As a recap, I'm using a version of Avida that I extended to permit movement of organisms in the Avida world grid. Avida's normal mode of operation puts an organism in a specific cell in the world grid, and there it stays for its entire life. I wrote Avida CPU instructions for "tumble", "move", and "sense-diff-facing". The "tumble" instruction simply rotates the organism to a new random facing in its grid cell. A facing is always toward another adjacent grid cell, so for an interior grid cell there are eight legal facings, five legal facings on an edge, and three at each corner grid cell. The "move" instruction puts the organism executing it into the cell that it currently faces. (If there is another organism in that cell, they swap cells.) The "sense-diff-facing" instruction puts the difference in the amount of a specified resource between the current grid cell and the faced grid cell into one of the Avida registers. The run is seeded with the default classic Avida organism. This is an organism whose only functionality is to make a copy of itself. None of the codes associated with movement is included in the initial organism. Mutation is the only way those instructions can enter the genome at the outset.
The environment is defined with a positively rewarding resource, with a peak in the resource set off-center in the world grid. This was done so that the peak resource would not be on an edge or diagonal of the world grid.
The run also includes a 2% cost to the organism for each move instruction that it executes.
The updates are set to permit about three Avida instructions to be executed per-organism per-update. The runs go on for two million updates. The total population is capped at 200 Avidians, so the world grid has about 2% of its grid cells filled with Avidians at any time.
During the run, each grid cell has a count of the number of visits it receives from Avidians. I output these visit counts every 5000 updates. I then plot a surface map of the difference in visits between each update and the one prior, which shows in aggregate the movement of the population for 5000 updates. It becomes very clear when a gradient-ascent effective method, or "climber", becomes the dominant class of organism in the population. I have a few plots to show the transition from "drunkard" dominant to "climber" dominant, and from "climber" to a more efficient "climber".
The results show the evolution of a useful algorithm from scratch. Part of what I did in the work at MSU was in collaboration with Jacob Walker to use the evolved organisms as robotic controllers, which we did with both a Roomba Create robot and a Lego Mindstorms robot. We used a point light source to create a "resource peak" that the robot displayed phototropic behavior toward with the "climber" organisms loaded.
This isn't about adjusting weights of some existing model. This is about evolution creating algorithms that did not exist before, based on nothing more than having a resource to exploit, the ability to take a step, to change direction randomly, and to sense differences in the local environment. (Very local, just to the extent of where a move instruction would take the organism were it executed, and only so far as to give a relative difference, not an absolute number.) There's no reward system other than "organisms do better if they go where resources are more abundant". There's nothing in the system to prefer inclusion of the new instructions, and there's actually a cost associated with executing the "move" instruction. And yet, time and again, this system can produce effective methods in the provably optimal class of gradient ascent algorithms.
"You can't teach an old dogma new tricks." - Dorothy Parker