Each member, simply by exchanging information with its nearest
neighbors, unwittingly contributes to the commonweal. From simple,
shortsighted, generally selfish actions, a transcendent global behavior
emerges.
Hoping to understand on a very basic level how such patterns of
cooperation arise, scientists based at the Santa Fe Institute in New Mexico
have stripped the problem to its bones: studying how the simplest imaginable
cells -- appearing as squares on a computer screen -- can interact to
generate surprisingly complex, coordinated behavior.
''There are these incredible pictures in which ants are all trying to get
from one tree to another tree,'' said Dr. Melanie Mitchell, a member of the
project along with her Santa Fe colleague, Dr. James Crutchfield, and Dr.
Rajarshi Das, who recently moved to the I.B.M. Thomas J. Watson Research
Center in Hawthorne, N.Y. ''They build a bridge with their bodies and other
ants can climb across. It's quite amazing. Our motivation is to understand
phenomena like that: how information processing and communication takes
places in these distributed systems with no central control.''
Viewed even more broadly, the goal is a deeper understanding of how
pattern emerges in nature and the universe. ''If I look out at the world, I
see a lot of structure and regularity there,'' said Dr. Crutchfield. ''Where
does that order come from?''
The tool for this research is a computer program called a cellular
automaton. An automaton is a device, made of mechanical or electronic
components, or in this case computer software, that operates autonomously,
almost as though it were alive.
The classic example of this artificial life was invented in 1970 by the
British mathematician John Horton Conway. In the Game of Life, a grid of
cells, like a luminous piece of graph paper, is projected onto the screen of
a computer monitor. Some of the squares are randomly colored black. These
are called ''live'' cells; blank ones are ''dead.'' At every tick of the
clock, each cell in the grid examines only cells adjacent to it (including
the four diagonals). Then it refers to a list of simple rules and responds
accordingly: A live cell with one or no neighbors dies from isolation, a
live cell with four or more neighbors dies of overpopulation, a live cell
with two or three neighbors survives. Finally, a dead cell with three
neighbors comes to life.
Tick by tick a dazzling array of lifelike patterns unfolds, merging,
dissolving, oscillating. Like the cells of a slime mold or the ants in an
anthill, the cells of the cellular automaton trade information only with
their immediate neighbors, but they link up into complex structures that
sprawl across the screen. (There are several places on the Web to play Life,
including www.bitstorm.org/gameoflife).
While the Game of Life is played on a two-dimensional array, like a
checkerboard, the Santa Fe Institute scientists have made their cellular
automata (called C.A.'s for short) even simpler, each consisting of only a
single row of black and white cells. At each tick of the clock, each cell
refers to its three closest neighbors on the left and right. Then according
to a table of rules, it turns on or off. The next generation of cells then
appears in the row underneath. Generation after generation unscrolls from
the top of the screen to the bottom like a roll in a player piano.
Depending on the rules and the initial configuration, different kinds of
patterns unfold. Some C.A.'s quickly freeze up into boring routine, churning
out all black or all white forever. Others cycle through the same pattern
over and over. And still others generate a seemingly endless variety of
intricate structures that seem to hover on the brink between complexity and
randomness.
In their own research, the Santa Fe scientists set out to make a C.A.
that, regardless of the initial configuration, would always settle into a
repeating pattern with a black row alternating with a white row, blinking on
and off eternally. Starting with any randomly chosen pattern of black and
white cells, the system would converge after several hundred ticks of the
clock, into this precise lockstep pattern, reminiscent of the way, perhaps,
the cells in a heart coordinate their random firings into a steady rhythmic
beat.
One way to accomplish this task would be for a godlike human programmer,
like the inventor of the Game of Life, to design a clever set of rules,
imposing them from the top down. Dr. Crutchfield, Dr. Mitchell and Dr. Das
set a more ambitious goal: to see if they could get the rules for a blinking
automaton to evolve, from the bottom up, more as they would in nature.
Through evolution, the cells in a heart develop the ability to beat together
cooperatively; the ants in the anthill to build a bridge. In a
computer-simulated Darwinian struggle, the cells in the cellular automaton
would evolve the ability to form synchronized blinking patterns.
By studying the crisp lines of the simple simulated system, the
researchers of the EvCA project (short for ''evolving cellular automata'')
hope to throw light on how individuals in nature develop this ability to
exchange information and coordinate their behavior, carrying out tasks in
ways that never would have occurred to an engineer.
''The research shows how sneaky nature can be in the ways it finds to
solve problems,'' said Dr. Andy Clark, a philosopher at Washington
University in St. Louis. The solutions that emerge, he noted, are ''quite
different from our armchair design -- often messier-looking on the surface,
yet deeply efficient underneath.''
Like animal breeders, the experimenters started with 100 untrained
C.A.'s, each governed by a set of randomly generated rules. Each C.A. was
then seeded with a random configuration of black and white squares and left
to churn away. After each had been tested on 100 of these initial patterns,
the fittest C.A.'s -- those that came closest, after 300 clock ticks, to
settling into the blinking cycle -- were then pulled from the pool, the
others allowed to die.
The survivors then were allowed to ''have sex'' with one another. Their
rules, expressed as a string of 1's and 0's, can be thought of as the
genetic message -- the chromosome that determines how the C.A. behaves. By
exchanging chunks of this code, like amoebas fusing and swapping DNA, the
winners of the old generation gave birth to a new one. In a further
imitation of natural variation, the chromosomes were also subject to random
mutation, a 1 might become a 0 or vice versa, like a molecule zapped by a
cosmic ray.
Then, using this second generation, the experiment was run again. The
fittest survivors were culled out and bred and the third generation was put
to the test.
''We'd just leave the algorithm cooking on our workstations over night,''
Dr. Crutchfield said. ''Then we'd come back in the morning and see what they
were doing.''
After 100 generations, C.A.'s almost always emerged that knew the
blinking task.
At this point the human overseers had no idea why the solutions that
evolution had stumbled upon worked so well. ''Unraveling this problem,'' Dr.
Das said, ''was the most fascinating aspect of this work.''
For example, if a cell saw that the three cells to the left of it were
black, then it might decide to turn black at the next tick. But what if the
cells to the right of it were all white? And it would have no way of knowing
what distant cells far down the row were doing. What if, imitating its
neighbors, a cell turned black only to find that they, using different
criteria, decided to turn white? There was no higher intelligence looking
down and seeing the whole picture, coordinating the flow.
In another experiment, the scientists bred C.A.'s to perform what is
called the density classification problem. Starting with a random row of
cells, the C.A. would compute the relative number of black and white cells.
If most of the cells in the initial row were white, then the C.A. would
ideally converge to a state where it churned out nothing but white rows. And
if there were more black than white cells, it would eventually churn out all
black rows.
Again, the problem was understanding how the fittest survivors were
performing this computation. The answer was hidden somewhere in the long row
of 1's and 0's representing the rule table -- the digital chromosome that
had evolved. But analyzing a C.A. on that level would be like trying to
understand an animal's psychology by scrutinizing the precise details of its
DNA sequence. Or, the scientists wrote, it would be like trying to explain
how a pocket calculator computes square roots by examining the flow of the
charges though its silicon circuits.
To figure out why a C.A. worked the way it did, the scientists needed to
step back and take a bird's eye view. As they studied the grids of cells
churned out by the program, they noticed that they were typically grouped
into large rectangular and triangular regions. Some were solid black, some
solid white and some checkerboard.
The breakthrough came when they concentrated not on the regions
themselves but on the boundary lines between them. Viewed at a higher level
of abstraction, these began to resemble tracks of colliding particles like
one sees in photographs from physics experiments.
''This is something we didn't anticipate,'' Dr. Crutchfield said. ''In a
sense we were being artificial particle physicists.''
It was a surprising change of metaphor. Drawing on earlier work Dr.
Crutchfield had done at the University of California at Berkeley with Dr.
James Hanson, now with the I.B.M. Watson Research Center, the scientists
classified these ''artificial particles'' according to various
characteristics like the nature of the regions they separated and how fast
they propagated across the screen. The result was a mathematical language
that explained a C.A.'s behavior in terms of particles colliding and trading
information.
This new depth of understanding is the most exciting thing about the
work, said Dr. Mitchell Resnick, a computer scientist at the Media Lab at
the Massachusetts Institute of Technology. Much research on cellular
automata and artificial evolution ''borders on magic,'' he said. Researchers
breed programs by trial and error and, voila, something interesting emerges.
But they are left baffled by how their creations compute.
''The Santa Fe team has helped bring rigor and insight to this field,''
he said. ''They identify a set of patterns that help explain how and why the
evolutionary algorithm works. Their approach is the classic scientific
approach: develop new representations that enable you to see a clear picture
where others had seen only noise.''
Changing metaphors again, the researchers are pondering whether the
patterns that emerge in their simulation bear something in common with those
that emerge inside the brain. Neurons exchanging electrochemical signals
with their immediate neighbors somehow give rise to grand thoughts and
mental images representing things in the outside world.
''The brain does not have a single center to evaluate or coordinate
computations,'' Dr. Das said. ''Yet it is able to bind together many
parallel computations to produce coherent perception and action. I think our
approach can bring a fresh perspective to study this problem.''
Like cells in the Game of Science, the researchers gather and trade
information on the Internet, the telephone and in face-to-face
conversations, never entirely sure of the greater pattern that might unfold.
