n8443916@unicorn.cc.wwu.edu (John Gossman) (02/07/91)
Chris Langton requested other CA-like ideas people are experimenting with, so here goes: I've been playing with a very simple A-life, mainly to study Genetic algorithms for learning. Basically the board is a square, wrap-around lattice upon which random quantities of food are scattered in chunks. One square may have 10 units, another 3, another 0 with only about 1 in 3 having any food. The creatures consist of a stomach that is initially filled with 8 (or so) units of food, a hunger that causes them to consume one unit of food each turn, and a large gene. Basically, each creature each turn makes a binary number based on how many cells in its 9-cell (including the one it is on) have any food in them. Thus there are 512 combinations (2^9) of how food lies in its neighborhood. The creature indexes its gene with this number and finds a number telling it to move to one of the 9 cells in its neighborhood. If it lands on a cell with food, it consumes one. If it doesn't it consumes one from its stomach until its stomach is empty, then it dies. The simulation drops 20 creatures onto the board randomly, and keeps track of their average survival time, then breeds together the 5 or 10 most successful ones in multiple ways. Note that these genes are initially COMPLETELY random, and new random creatures are added in every generation. Initially, with their random gene strategies, most die very quickly (9-10 turns). Within only 5 or 10 generations this improves to 14-15 turns, and then continues slowly upwards. I have noted that the life-time seems to reach plateaus for 100s of generations, then jump up suddenly, usually at the same key points (24 -> 30, 34 -> 42), offering support for Gould's puncuated equilibrium theory of evolution. Finally, the creatures turned out to be smarter than I. Given 20 creatures and the amount of food initially in their environment, I estimated a maximum average survival time ~50 turns. However, while watching my experiments I found them surviving 60-65 turns after awhile. After investigating my code, I discovered the creatures were exploiting a "bug" in their universe. If they moved off food, onto a blank square, they neither consumed a unit on that square, nor in their stomachs. Thus by bouncing back and forth onto and off of a square with food, they can survive 2 turns on one food unit!! Anyway, another very simple variation on A-life, using merely an array of initially random numbers for "brains". I was surprised by the rapid pace of evolution. My next try is for more interaction beteen the creatures. // *************************************************************** // John Gossman SoftSource (206)676-0999 Phone WWU Math Dept. My employer stands behind all my opinions, except in public. // ************************************************************** //
cgl@t13.lanl.GOV (Chris Langton) (02/07/91)
John Gossman describes observing punctuated equilibria in the course of the evolution of his CA system. David Hiebeler correctly cautions that observing this phenomenon in CA systems alone does not really constitute much support for PE in biological evolution. However, this phenomenon is being seen in many different artificial evolving systems, when people take care to record what happens along the evolutionary path, instead of just noting that ``fitter-critters'' result at the end of the process. Indeed, many of the papers submitted for the proceedings of the most recent workshop on Artificial Life note this phenomenon. Thus, is appears that punctuated equilibrium behavior may well be ``generic'' for evolutionary processes. These punctuation events are often accompanied by population crashes and ``species'' crashes. This is important, because it suggests that extinction events on many different scales can occur due to the natural dynamics of the evolutionary process alone, without having to evoke catastrophes like asteroid impacts. This is one of the better illustrations of the way in which Artificial Life can contribute to theoretical biology. By viewing evolutionary processes (and other biological processes) as dynamical systems, identifying what class of dynamical systems they are (if possible), charting out the different regimes of dynamical behavior that such systems exhibit under different parameter settings and with different initial conditions, and even by altering the rules of the dynamical system (for instance by allowing Lamarckian inheritance), we can derive universal principles from an *ensemble* of examples, rather than trying to derive universals from the *single* examples that nature has given us of most biological processes. Viewing the evolutionary process as a dynamical system allows one to make an analogy between punctuated equilibrium dynamics and what is known as ``intermittency'' in dynamical systems. Intermittency is a generic behavior for many dynamical systems near a phase-transition between periodic and chaotic behavior. Thus, the fact that evolutionary processes exhibit dynamical intermittency suggests that evolution naturally brings populations to some sort of phase-transition. This has a number of interesting implications which I won't go into here, but suffice it to say that the love affair between dynamical systems theory and biology is only just beginning. Cheers! Chris Langton Complex Systems Group MS B213, Theoretical Division Phone: 505-667-9471 Los Alamos National Laboratory Email: cgl@t13.lanl.gov Los Alamos, New Mexico, USA 87545
hiebeler@think.com (Dave Hiebeler) (02/08/91)
John Gossman (n8443916@unicorn.cc.wwu.edu) wrote: > [description of simulation] > I have noted that the life-time seems to reach plateaus for 100s of > generations, then jump up suddenly, usually at the same key points (24 > -> 30, 34 -> 42), offering support for Gould's puncuated equilibrium > theory of evolution. This offers support for a theory of punctuated equilibrium in a CA-like system -- I think it is too simple to offer much evidence for this phenomena as it may exist in the carbon-based biological world. However, if many different kinds of models/simulations exhibit behavior like this, then it could indicate that the phenomenon is fairly common, and perhaps should be expected in biological systems as well. > Finally, the creatures turned out to be smarter than I. Given > 20 creatures and the amount of food initially in their environment, I > estimated a maximum average survival time ~50 turns. However, while > watching my experiments I found them surviving 60-65 turns after awhile. > After investigating my code, I discovered the creatures were exploiting > a "bug" in their universe. This is actually fairly common, from what I've heard. Many people doing A-Life or CA-like simulations with evolution often find that the systems learn to exploit bugs in the system. I sometimes wonder if humanity itself is nothing more than a bug in "The System". :-) -- Dave Hiebeler | Internet: hiebeler@think.com Thinking Machines Corporation | Phone: (617) 234-4070 (work) 245 First Street | "Off we go, into the wilds you ponder." Cambridge, MA 02142 USA |
pollack@dendrite.cis.ohio-state.edu (Jordan B Pollack) (02/09/91)
> Indeed, many of the papers submitted for the proceedings of the most >recent workshop on Artificial Life note this phenomenon. Thus, is >appears that punctuated equilibrium behavior may well be ``generic'' >for evolutionary processes. The principles underlying punctuated equilibria may also be generic for other kinds of search and problem-solving. Certain kinds of connectionist learning curves jump through discrete levels of improvement. In my connectionist model of language induction to appear in NIPS 3, a sequential parity learner undergoes a phase transition which corresponds to the initial discovery of the xor "trick", which is rapidly exploited (in some sort of arms race) by back propagation. Human learning of mathematical concepts, gestalt recognition of distorted objects, and insight problem-solving (the AHA phenomena) also seem to be punctuated by phase transitions, where there no progress until right before the problem is solved. The idea of a pre-adaptive change leading to a massive reorganization of population elements seems to analogically apply. >These punctuation events are often accompanied by population crashes and >``species'' crashes. This is important, because it suggests that extinction>events on many different scales can occur due to the natural dynamics of >the evolutionary process alone, without having to evoke catastrophes like >asteroid impacts. Ive thought about that too, the idea that the asteroids and ET's and continental breaks and are just truly random noise added to the species bifurcation diagram. I even dallied with the idea of collecting the best dating evidence on the time frame of species introduction to see if it follows a classic period-double. The initial result looked promising: the first 5/6 of the time, there were single cellular creatures, then a long period of 2-cell creatures, then the first explosion of multicellular types. We are in a period of rapid species collapse due to humans (merging) with every other creature's niche. I'm sure there is a nobel prize in here somewhere :) -- Jordan Pollack Assistant Professor CIS Dept/OSU Laboratory for AI Research 2036 Neil Ave Email: pollack@cis.ohio-state.edu Columbus, OH 43210 Fax/Phone: (614) 292-4890