Random Recipe

Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !
Take me higher...

March 23, 1999, Tuesday
Science Desk

Mindless Creatures Acting 'Mindfully'

By GEORGE JOHNSON

Oblivious to its fellows, the single-celled creature called the cellular slime mold slithers amoeba-like along the ground, lapping up the nutrients in its path. But when the food supply runs out, it has a biochemical panic attack, frantically sending out molecular signals to other nearby slime molds, which in turn are sending out signals of their own. Guided by these primitive conversations, the individual cells come together to form a multicelled organism, sprouting a stalk and a head of spores that become the seeds of the next generation. When these fall to the ground, the cycle begins anew.

Exotic as it seems, this behavior is just a stark example of one of the most familiar phenomena in the living world: the way individuals, whether cells in a body, plants and animals in an ecosystem, or members of a corporation or society, congregate into complex wholes that take on autonomous existences of their own. There is no need for a central controller orchestrating their movement.


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.



Organizations mentioned in this article:
Santa Fe Institute

Related Terms:
Evolution; Models (Simulations); Computers and Information Systems; Computer Software; Mathematics; Physics; Biology and Biochemistry; Sociology


Copyright 1998 The New York Times Company


Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !