What is Artificial Life?

by Scott Robert Ladd

---

Artificial Life, commonly known as ALife, is the study of theoretical biology, using technology to investigate the properties of living systems. In terms of complexity science, ALife research seeks to synthesize the self-organizing principles underlying life-like behaviors, resulting in a better understanding of natural life and the invention of tools relevant to machine learning and robotics.

Science derives general principles from the comparison of different models, seeking common features in disparate systems -- and biology is limited by circumstance to the examination of a single model of life, as found on Earth and built from carbon-chemistry molecules. When forming a general definition of �life,� biologists have few criteria for separating the properties of �life in general� from those inherent to �life as we know it�. Hence the interest in ALife, which provides examples of �possible life.�

Traditional biology uses a reductionist approach in studying life, breaking organisms into ever-smaller components; in contrast, ALife works up from the bottom, looking for complex behavior to emerge from simple interactions among basic elements. Most aspects of life, from the shape of proteins to the path of evolution, can be interpreted as emergent behaviors. Age-old questions about the origin of life can be answered in terms of self-organization, according to American biologist Stuart Kauffman. Life, it is supposed, originated from chemical interactions in a �primordial soup�; critics of that theory compare the spontaneous origin of life to the construction of an airplane by a tornado in a junkyard. Kauffman�s work, however, strongly asserts that life arose as an inevitable consequence of natural self-organizing principles.

History

The foundations of ALife were laid down by some of the first computer theorists. In the early 1950s, British scientist Alan Turing theorized about a potential relationship between mathematics and biological morphogenesis. His work, exemplified by the theoretical Turing Machine, became a foundation for later investigations into the genetic definitions of shape and pattern. Hungarian-American mathematician John von Neumann, a contemporary of Turing�s, considered the problems inherent in self-replication. He developed the concept of a self-reproducing automata in the late 1940s and early 1950s. This �von Neumann machine� possessed a dual nature: the symbolic description of the automata was distinct from the physical automata machine. Von Neumann�s abstract theory presaged biological reality; in 1953, Francis Crick and James Watson announced their discovery of deoxyribonucleic acid (DNA), the symbolic self-description contained within every living cell.

Prior to the invention of the electronic computer, several attempts were made to simulate living creatures with mechanical devices. In the early 1950s, Grey Walter, a British physiologist and encephalography pioneer, constructed a series of electromechanical tortoises. Walter based his tortoises on behavioral models and his belief that complex behavior was an outgrowth of rich interconnections between simple elements. These were the first truly autonomous robots, showing a variety of movement and search behaviors.

Artificial Life research was generally unfocused until 1987, when Christopher Langton organized the first Artificial Life conference at the Santa Fe Institute (SFI) in New Mexico. More ALife conferences followed, bringing together scientists from many fields and fostering cross-disciplinary communication. ALife research is now firmly established as an important branch of complexity science, involving scientists at universities and institutions world-wide. Active areas of investigation include cellular automata, autonomous agents, and evolutionary algorithms, described in the following sections.

Cellular Automata

A cellular automata (CA) is a matrix of cells, with each cell acting as an independent automaton in reaction to its neighbors� states. A CA is dynamic; starting from an initial condition, each cell evolves according to simple and universal rules. Formally, the characteristics of CA are:

• Parallelism
  Individual cells update simultaneously and synchronously (i.e., at the same time each cycle).
• Locality
  The new state of each cell is determined from its position in the grid and the current states of its adjacent neighbors.
• Homogeneity
  All cells of a given type use the same set of rules for updating their status.

The Game of Life

The most common and popular cellular automata is Life, which imitates a colony of "living" cells. The Life rules were developed by mathematician John Horton Conway of the University of Cambridge (England) in the late 1960s. Conway used dishes to mark �live� cells on the checkered floor of a hallway in his home, seeking a set of rules that promoted interesting pattern changes while avoiding runaway cell �growth.� Calculating new generations by hand and experimenting with variations on his rules, he developed the following three rules:

• The Rule of Birth
  If exactly three "live" cells are adjacent to an empty cell, the empty cell comes to life.
• The Rule of Overpopulation
  When a cell has four or more live neighbors, it dies from overcrowding.
• The Rule of Underpopulation
  Any cell with one or no neighboring cells dies.

Life is a seminal example of Artificial Life: the emergence of complex behavior from simple rules. Embodied in three absolute rules is a pocket universe; patterns form and move, sometimes disappearing, sometimes becoming repetitive. A well-known pattern consists of five cells that create an offset copy of themselves each cycle, giving the appearance of a moving �glider� that diagonally traverses the grid. You can see these patterns in action by exploring the Life rules in my LifeBox applet.

Experimentation with Life�s rules produced a number of interesting patterns, including oscillating �glider guns� that produce a steady stream of gliders. Other patterns change or combine gliders into new streams, mimicking the behavior of electronic �logic gates.� Such elements, when combined, form the basis for a complete computing architecture.

Virtual Ants

Christopher Langton invented a simple, yet intriguing, automata universe in 1986. Langton�s �virtual ant� moves on a plane divided into a grid; there are two types of cells, �black� and �white�. The ant begins in the center square, facing in one of four directions (North, South, East, or West). Movement of the ant is controlled by a simple rule: If the cell to be entered is white, the cell changes to black and the ant turns 90 degrees to the right; if a black cell is found, the color changes to white and the ant turns 90 degrees left. Starting on an all-white grid, the ant will meander around its origin point for about 500 moves until it begins drawing a �highway� leading away at an angle. Following a series of 104 steps, the ant continues drawing the highway pattern until it encounters the edge of the grid.

You can see these actions in the Vants applet. The ant will always start drawing a path, even if the original grid contains a mixture of black and white cells. Slight changes in the ant�s rules give rise to radically different behaviors. Further experiments with Langton�s ants have studied the interaction of multiple ants, which produce cyclic behavior.

Other Automata

Life is the best-known cellular automata, but it is by no means the only one. A cell matrix might have one, two or three dimensions; cells can be square or hexagonal, reacting to the sum of their neighbor�s states or to regions beyond their immediate area. ALife researchers find the limitless variety of CA rules and forms to be fruitful ground for research.

English mathematician Stephan Wolfram, a pioneer in complexity theory, extensively studied one-dimensional automata, where each cell in a line reacts to the states of its two immediate neighbors. The creation of a new generation shifts the previous generation �down� in an image, producing a two-dimensional record of the automata�s changing state. In 1995, Przemyslaw Prusinkiewicz and Deborah Fowler (both of the University of Regina, Saskatchewan, Canada) showed that patterns on certain sea shells can be interpreted in terms of one-dimensional automata.

Automata prove useful in many ways. Lattice gas automatas simulate diffusion in liquids and gases; three-dimensional automatas filter and enhance images created by MRI and PET scans. In image processing, cellular automata rotate pictures, enhance contrast, and produce stereoscopic views. Other practical applications include simulations of dendritic growth, brain activity, and digital circuitry.

Agents and Environments

Autonomous agent is a catch-all term for any artificial system capable of pursuing a goal through independent action in a dynamic environment. A precise definition for �autonomous agent� is problematic, since the term encompasses systems as divergent as independent robots to Internet-searching software. In general, the behavior of an autonomous agent stems from a set of rules governing its actions; simple rules often produce remarkably complex and life-like behaviors, leading to a better understand of the mechanisms behind behaviors.

An agent may be implemented either in computer software or as a programmed device. A program that independently searches or gathers information from a database is one type of autonomous agent; many Internet indexes use �crawler� programs to follow hyperlinks while cataloging web pages. Other terms for software agents are �knowbots� or �softbots,� to distinguish them from physical robotic agents. Mechanical robots are material agents that sense and react to the physical environment.

Boids

Autonomous agents create animated movie and computer �characters� with natural properties. A prominent example of this type of world was developed by Craig Reynolds, an American computer scientist. Reynolds wanted to simulate bird-like flocking behavior in software; naming his creatures �boids�, he based the model of their motion on three rules:

1. Separation
   A boid steers to avoid crowding local flockmates.
2. Alignment
   A boid steers towards the average heading of local flockmates.
3. Cohesion
   A boid steers to move toward the average position of local flockmates.

The boids travel inside the confines of their world, changing direction as defined by Reynold�s rules. You can watch what happens in the applet below: the birds eventually form into a group, matching speed and direction with their flockmates. The Flock applet allows you to change the characteristics of the flock, by changing the number of boids or the constraints on their behavior.

Major motion pictures have used Reynold�s rules to animate flocks of birds and herds of animals; related simulations produce the schooling behavior seen in fish. Additional rules -- to avoid obstacles or predators, for example -- add to the richness of the boids environment.

Swarm

Another Christopher Langton project is Swarm, a configurable software universe for studying multiple interacting agents. The fundamental component is the �swarm�, which contains a collection of agents and a schedule of events. An agent may, in turn, be composed of swarms, allowing a simulation to be constructed from a hierarchy of nested models. The Swarm system is object-oriented, based on reusable components that display, manipulate, analyze, and control experiments.

Langton and his colleagues developed Swarm to provide a standard system for ALife experimentation. Most ALife software is built for a specific purpose; each application is unique, even when two scientists are studying the same phenomena. Comparing the results obtained from unique systems is often complicated by different design choices; in addition, scientists often lack training as computer programmers, leading to ALife software that is poorly engineered. Swarm is the ALife equivalent of standard laboratory equipment, providing a reliable and flexible software environment.

Tierra

Thomas Ray, an American tropical biologist, developed an ALife software system named Tierra. Tierra defines an abstract �virtual� computer for evolvable programs; the machine instructions understood by Tierra can be manipulated by the mechanisms of Darwinian evolution. In a traditional computer, changing a random bit in an instruction often leads to a non-sensical program. A Tierra program, however, remains valid even after mutation, allowing evolutionary algorithms to be applied directly to Tierra software. This system provides an environment for evolving diverse ecological communities of synthetic organisms. Computer processing time is the organisms� �food�; computer memory can best be thought of as �raw material�.

Tierra-based communities provide an experimental environment for testing evolutionary theories. Ray�s experiments have demonstrated the spontaneous development of parasitism, where certain programs reproduce by using the reproductive code and processing of other organisms. Other Tierra experiments investigate coevolution, punctuated equilibrium, evolutionary arms races, and the role of diversity in ecosystems. Extended beyond single computers, the Network Tierra Project evolves �digital organisms� across an inter-connected region of the Internet. By providing Tierra organisms with a broad range of environments, Ray hopes to see a diversification of forms, similar to the Cambrian explosion in natural life.

Physical Agents

The first ALife pioneers were also interested in the development of robots and other physical automata. Using algorithms derived from ALife research, roboticists hope to develop intelligent and adaptable machines. At the Massachusetts Institute of Technology, Rodney Brooks is developing humanoid robots, theorizing that the evolution of human-like behavior and intelligence requires a human-like body. Brooks has also developed prototype robotic space probes, akin to the 1997 NASA Mars Pathfinder Mission, as autonomous agents for the exploration of outer space. Miniature robotic devices, the size of mice or even insects, could provide flexible tools for investigating other planets in the solar system.

In a 1959 lecture, American physicist Richard Feynman suggested that it was possible to manipulate matter atom-by-atom, constructing new materials on a molecular level. His vision became a foundation for nanotechnology, the manufacture of materials and devices by the direct placement and manipulation of atoms. Such constructions are smaller than the tiniest electronic circuit, being measured in nanometers (billionths of a meter). K. Eric Drexler, director of California�s Foresight Institute, promotes atomic-level engineering as the next step in technological development.

The basic building blocks of life -- proteins and enzymes, for example -- can be viewed as simple molecular machines; proponents of nanotechnology plan to manipulate atoms in composing human-designed machines. The most complex creations will use self-assembly to build themselves; in this way, nanotechnology acts like self-organizing biological machinery. Some nanotechnologists hope to construct microscopic medical robots that perform intracellular and genetic surgery; other researchers seek to make �smart materials� that adapt to changing conditions and needs. Worldwide, more than 200 research centers and companies work with nanotechnology.

Evolutionary Algorithms

An evolutionary algorithm is any computer procedure that attempts to solve problems by using the mechanisms found in biological evolution. Building on Charles Darwin�s theory of natural selection through survival of the fittest, computer scientists have developed a variety of algorithms that evolve solutions to problems. Where other areas of ALife seek to discover the fundamental principles of life, evolutionary algorithms attempt to implement biological principles in technology.

Different types of evolutionary algorithms may be used in concert to create an overall application or artificial organism. The boundaries between these techniques are often fuzzy, and definitions may vary from conference to conference and person to person. The salient point is that all of these concepts incorporate some aspect of adaptation and natural selection.

Genetic Algorithms

Computer programs tend to be static -- they begin at one point and proceed to another along a predetermined path. A user presses a button to cause a list of items to be sorted; a transaction occurs and is added to a database. Such deterministic algorithms work best in applications where specific goals must be met within a limited range of conditions. Some problems, however, don't lend themselves to solution by deterministic algorithm; the number of answers may be too large or there may be no clue as to what the best solution is. Optimizing networks, searching large databases, and finding optimal paths often involves networks that cannot be practically examined by deterministic algorithms.

Psychologist and computer scientist John Holland, from the University of Michigan, began developing the concept of a genetic algorithm (or GA) in the late 1960s. A GA creates a set of solutions, testing them against a given problem, and then "breeding" a new set of solutions based on some measure of success. This is how natural evolution takes place; think of a biological species as life's solution to the problem of exploiting a niche. In the case of a genetic algorithm, a solution evolves to solve some specific problem by emulating natural selection.

Computer scientists still debate the precise definition of a genetic algorithm. In the broadest sense, a GA creates a set of solutions that reproduce based on their fitness as solutions to a problem. The process includes these steps:

1. Initialization
   Create an starting population of random solutions (called chromosomes.)
2. Fitness Testing
   Assign each chromosome in the population a fitness value based on its evaluation against the problem.
3. Reproduction
   Chromosomes with higher fitness are most likely to parent new solutions during reproduction. Parent chromosomes combine genes to produce offspring; in some cases, reproduction is asexual, involving a single parent that clones itself. Mutation may make random changes in the child before it is assigned to the next population.
4. Next Generation
   If the optimal solution has been found, the algorithm is finished. Otherwise, the old set of chromosomes is replaced by the newly-generated children. A generation is complete, and the process iterates back to step 2.

That process implements, in an abstract fashion, the concept of survival of the fittest. The reproductive success of a solution is directly tied to the fitness value assigned it during evaluation. In this stochastic process, the least-fit solution has a relatively small chance at reproduction while the most-fit solution may not reproduce at all. The outcome of a genetic algorithm is based on probabilities, just as biological success is grounded in chance. Through natural selection, a genetic algorithm �zeros in� on a solution by constantly refining a population through natural selection.

Consider the Traveling Salesman Problem (TSP), a classic problem in game theory. The theoretical salesman has several cities he must visit; the problem is to order his visits such that he travels the least total distance over the entire journey. Problems such of this type appear in endeavors ranging from the optimization of scheduled delivery routes to the construction of computer networks. A search of all possible pathways is guaranteed to find the right answer -- but a deterministic approach can be impractical when the network in question contains many cities or nodes. The Traveller applet demonstrates how a TSP can be solved using a basic genetic approach.

A genetic algorithm solves a TSP by breeding a set of solutions. Beginning with chromosomes representing a random set of paths, the GA calculates the total distance traveled for each route. Chromosomes mapping the shortest path have the highest chance of reproducing in the next generation, sharing genes with other �good� routes. By combining, testing, and breeding new solutions according to their fitness, the genetic algorithm generates shorter pathways in subsequent generations.

Classifier Systems

Another idea originated by Holland is the classifier system (CFS), which classifies one or more inputs to produce one or more outputs. In the simplest classifier systems, a series of �if this then that� statements determine the relationship between inputs and outputs. More sophisticated CFS application may use a genetic algorithm to adapt its operations to a changing environment or responses to its outputs. A CFS may also evolve rules from a initial set of randomly-generated classifications.

A CFS for securities trading would �watch� stock and bond values, producing recommendations (buy, sell, jump from window) based on its rule-based classification of the data. An evolving classifier system might learn from the buying and selling habits of a stockbroker, refining its outputs to better suit the needs of its user. The first classifier systems were built in the 1970s, based on Holland�s initial ideas. As a part of Artificial Life research, a CFS can be a component of an autonomous agent or other complex artificial organism.

Genetic Programming

In the early 1990s, John Koza, a computer scientist at the Massachusetts Institute of Technology, began applying survival of the fittest to computer programs written in the language LISP. In a technique known as genetic programming, Koza creates random programs that evolve through fitness testing, natural selection, and the exchange of program fragments during breeding. Where a genetic algorithm works with strings of data, a genetic program manipulates descriptions of a process. Unlike a genetic algorithm, a genetic program does not use mutation; the only reproduction operator is crossover, which exchanges subtrees between parents.

A common theoretical application of genetic programming involves artificial �ants�. The initial population is comprised of randomly-generated programs defining the behavior of individual ants. The fitness of a given ant is based on how well it follows a �trail�; the most-fit ants reproduce to create the next generation. The refinement process evolves ants that have learned the characteristics of the trail, following it more closely. Researchers sometimes name common patterns, such as the �Santa Fe Trail� and the �John Muir Trail.�

In a practical sense, genetic programming provides a tool for machine learning and pattern recognition. Craig Reynolds of �boids� fame has investigated how genetic programming can evolve obstacle-avoidance behavior in robots. Graham Spencer developed a genetic programming model for a six-legged robot to walk in a simulated environment; the evolved solutions performed better than hand-coded programs. Other applications apply genetic programming to the development of marketing strategies and optical character recognition systems.

Evolutionary Programming

Evolutionary computing is similar to genetic programming, but defines programs in terms of the finite state machines (FSM) first envisioned by Alan Turing. An FSM contains a number of possible internal states, of which one represents the current state. A finite set of input symbols is mapped to a finite set of output symbols by each state; an input symbol is given to the FSM, which returns an output symbol before making a possible transition to a new state. The figure at right shows a possible 3-state machine with an input alphabet of { 0, 1 } and an output set of {A , B, C }.

Beginning is state 0, the FSM in Figure 1 will map the input string 11010001 to the output string AACBBBBA.

Finite state machines are computationally complete -- meaning that a finite state machine can be constructed to accomplish any programmatic task. While the concept may be simple, FSMs can be powerful software tools due to the possible arrangements of states and symbol sets. For example, it is possible to create more the 400 quadrillion different FSMs using five states and alphabets with only three symbols each.

Programmers construct most finite state machines to accomplish a specific task; evolutionary programming, however, constructs FSMs through natural selection. In the mid-1960�s, Larry Fogel, of the University of California, suggested techniques for doing just that. Fogel defined intelligence as the ability to predict and react to one�s environment; his goal was to find a mechanism for evolving machine intelligence.

Fogel�s finite state machines evolve in much the same way as LISP programs evolve in genetic programming. A set of FSMs is tested against an environment that consists of a series of input symbols; the evolutionary algorithm calculates a fitness value for each FSM based on its performance. The fitness values define relative reproductive chances for the FSM population; offspring are generated by copying a parent FSM and possibly mutating it. The new population then replaces its parents, and the cycle begins again.

Prisoner�s Dilemma

The Prisoner�s Dilemma is a classic problem of game theory used by ALife scientists to investigate population dynamics and the evolution of cooperation. In its basic form, the dilemma involves choices made by two prisoners about to be tried for a mutual crime. Each prisoner has two options: to inform on their partner (defect) or to maintain the other prisoner�s innocence (cooperate). When both prisoners inform on each other, they each receive a mid-length term; if one defects and the other cooperates, the informer earns his freedom while his accomplice receive a harsh sentence; if both remain loyal and cooperate with each other, they each serve a short time in jail. The dilemma is for each prisoner to minimize his sentence, even though he has no knowledge of his partner�s action. In a single instance, the most rational choice is to defect, since this guarantees avoidance of the harshest penalty.

For ALife research, the Iterated Prisoner�s Dilemma (IPD) is more interesting than the one-shot case. The IPD performs a series of contests between two strategies, each strategy choosing its next move based on a history of its opponent�s moves. A strategy might defect in the first game, then cooperate if its opponent defected or defect if the opponent cooperated. Using a round-robin tournament, the IPD tests a population of strategies; the total score for each strategy is calculated as the sum of its performance against all other strategies in a population.

Robert Axelrod, an University of Michigan political scientist, used the IPD to investigate models of cooperation. He found that the most effective strategy was �tit-for-tat� (TFT), which mimicked the last action of its opponent. If the opponent cooperated in the previous game, TFT cooperates; if the opponent defected, TFT defects. Axelrod compared this to the trench warfare of World War I, where both sides avoided attacking the other�s supplies, thus avoiding retaliation against their own rations. Intent on applying his discoveries to Cold War politics, Axelrod sought to understand the mechanisms of cooperation. Since the end of the Cold War, his research has focused on the automatic evolution of altruistic strategies. He and other researchers have developed a visual form of IPD, similar to a cellular automata, showing the spatial dynamics of cooperation. An example of this is shown in the VIPD applet.

Another from of IPD simulates ecological evolution, allowing populations of strategies to coevolve in a competitive environment. Kristian Lindgren, a physicist at the Chalmers University of Technology in Copenhagen, created an artificial IPD ecosystem that exhibited the dynamics of natural evolution. In Lindgren�s simulation, the most effective strategies are most likely to breed in the next generation; mutation allows new strategies to appear. Lindgren discovered that periods of relative stasis are punctuated by intervals of variation and population diversity. While one or two strategies may dominate for a time, the dynamics of the population will suddenly enter a chaotic period when a variety of strategies compete for dominance. Lindgren�s experiment is a primitive analogy to biological evolution, showing mass extinction, adaptive stasis, coevolution, and punctuated equilibrium.

Variants in the IPD include the introduction of misunderstanding (making a mistake about the opponent�s last move), simultaneous contests between three or more strategies, and the option of choosing or rejecting opponents based on past encounters.

Neural Networks

An artificial neural network is a computational structure that imitates the principles embodied in the neural processing of the human brain. In biology, a neuron is one of the impulse-conducting cells (also known as nerve cells) that constitute the brain, spinal column, and nerves. A neuron reacts to chemical signals delivered via its dendrites, �firing� an electrical impulse along its axon. The axon, in turn, connects via synapses to the dendrites of other neurons, passing the signal along and stimulating other neurons to fire.

Complex organisms and human intelligence arise from an intricate web involving billions of interacting neurons. While neurons are five to six times slower than digital circuits, the human brain is more than capable of out-performing the fastest computers. No computer emulation can hope to reach the complexity of the human brain, but useful simulations can be created on a smaller scale. Basic neural networks involve layers of artificial neurons; each layer accepts input and produces output for the next layer in sequence. Essentially, each layer of the network operates as a filter, with the final (or top) layer producing a final result. The output of different neurons can be weighted as to importance or value; a neural network is �trained� by adjusting weights and altering connections between neurons, based on feedback about the network�s performance.

Neural networks imitate the brain's ability to sort out patterns and learn from trial and error, discerning and extracting relationships from data. They have proven most useful in applications of artificial intelligence: expert systems, data analysis, signal processing, computer vision, and artificial intelligence. ALife researchers have studied the evolution and programming of neural networks through evolutionary algorithms.

The first artificial neural network was the Perceptron, constructed by Frank Rosenblatt, of Cornell University, in 1958.

Computer Viruses

A computer virus is a software program that automatically reproduces itself via connected computers. The connection may be by network or through the sharing of software; mechanisms vary from virus to virus. A virus may attach itself to the start-up code on a computer disk, or make itself part of another executable program. A few viruses are merely annoying, but most damage data and cause software failures. A virus may lay dormant inside a system, manifesting only when triggered by a specific condition -- the advent of a specific date, for example. Other viruses can collect information from a computer and transmit it to another location.

Computer viruses, like their biological namesakes, exist at a boundary in definitions, breeding only through infection of a host. A computer virus uses the resources of its host computer to duplicate itself, just as a biological virus employs the metabolism of a cell for reproduction. Some computer viruses react to their environment, �hiding� from detection attempts and avoiding anti-virus protections. While computer viruses do not currently evolve, the potential exists for viruses that include genetic algorithms and other evolutionary techniques.

In 1992, the "Michelangelo" virus generated world-wide headlines. Designed to damage the file systems in PC-compatible computers, the virus was set to activate on March 6^th. While actual occurrences of the virus were far fewer than expected, the incident did raise public awareness of viruses and their potential danger.