[ ERCB Home |
New |
Feature |
Brief |
DDJ |
Letters |
Links
]
Adaptation, Emergent Computation, and Artificial Life
Review by Ray Valdes
Copyright (C) Dr. Dobb's Journal, March, 1993
The computer industry is so fast moving that many products have a shelf
life not much longer than last night's guacamole. It's therefore a salutary
experience to encounter books that won't be outdated by this season's Comdex.
In the preface to the new 1992 edition of his classic work on Adaptation
in Natural and Artificial Systems, John Holland writes, "When this
book was originally published [in 1975, after seven years of writing], I
was very optimistic, envisioning extensive reviews and a kind of 'best seller'
in the realm of monographs. Alas! That did not happen." What did happen
is that the book sold a hundred or so copies a year, steadily, through the
early 1980s, until an explosion of interest occurred in the middle of that
decade.
The area that John Holland pioneered with this book--that of genetic algorithms--is
now extensively covered by a whole raft of books and publications, including
five sets of conference proceedings. This area is of more than academic
interest, if recent articles in the business press are any indication. For
example, Business Week ran a special section on "The New Rocket Science"
(11/2/92) describing how financial trading on Wall Street is being transformed
by software technologies such as genetic algorithms, neural nets, and chaos
theory.
You don't need to read Holland's book to work with genetic algorithms. You
can simply find a good introduction, such as Richard Spillman's "Genetic
Algorithms" in the February 1993 issue of DDJ, get the sample code,
and start working (or playing) immediately. If you have access to the Internet,
there are public-domain tools such as Genitor and GATool that let you build
systems easily.
The value of Holland's book is the carefully written, lucid exposition of
his formal theory of adaptive systems. Genetic algorithms are but one aspect
of this mathematical theory. Holland begins by defining a general framework
that can rigorously describe a wide range of adaptive systems. He illustrates
its power by applying it to cases in genetics, economics, game theory, searching
and pattern recognition, control theory, and physiology. The examples are
not discussed in elaborate detail, but enough to make the connection:
Searches occur as the principal element in most problem-solving
and goal-attainment attempts, from maze-running through resource allocation
to very complicated planning situations in business, government, and research.
Games and searches have much in common and, from one viewpoint, a game is
just a search (perturbed by opponents) in which the object is to find a
winning position. The complementary viewpoint is that a search is just a
game in which the moves are the transformations (choices, inferences) permissible
in carrying out the search.
Likewise, evolutionary processes in nature can be seen as a sophisticated
search over a fitness landscape to ultimately arrive at life forms that
are optimally matched to their environment. If you've read the articles
mentioned earlier, this will come as no news. One critical point, however,
is ignored by much of the press coverage, including many technical articles.
This critical point is fully elaborated on in Chapters 5, 6, and 7, which
constitute the heart of the book. Holland explains, with full mathematical
rigor, why genetic algorithms work as well as they do. You need a good background
in probability, combinatorics, and system theory to follow his reasoning.
His proof relies on the central-limit theorem and the theorem of large deviations--subjects
sufficiently abstruse that I had to struggle to keep up. Nevertheless, I
understood enough to grasp the essential idea behind genetic algorithms,
which is that evolution is not a glorified random search, but one that is
highly efficient because of the genetic operators of crossover and inversion.
Sexless evolution--evolution by mutation alone--is slow and uninteresting,
not much better than an exhaustive enumeration of all possibilities. But
when all three genetic operators (crossover, inversion, and mutation) are
present, the result is a system in which the number of better-than-average
solutions increases exponentially to arrive at a solution close to optimal.
The movement through the large search space follows a rapid trajectory because
of what Holland calls "implicit parallelism": When one individual
is being evaluated by the fitness function, many different comparisons are
being made, because the members of the current population form a compact
representation of a much larger candidate set, which includes much historical
information. Unlike mutation alone, the full genetic algorithm contains,
at the beginning of any cycle, the retained performance of past members
of the population. Holland's analysis does not stop there. Not only does
he create an entire field of research with one book, he also lays the groundwork
for its most penetrating criticism. He realizes that the main shortcoming
of genetic algorithms is the total dependence on how the attributes of a
problem are represented and the way in which those attributes are evaluated.
If you consider attributes to be data, then you can consider the way in
which the attributes are represented and evaluated to be analogous to code.
Holland's insight that carries us beyond the realm of genetic algorithms
is to allow the code to evolve along with the data. To this end, he develops
a "language of algorithms" that is amenable to transformation
by genetic operators. This path eventually leads to Holland's recent work
on "classifier systems," explained in Chapter 10. In the 1992
edition of the book, Chapter 10 is entirely new, and provides a very good
summary of Holland's recent work with the Santa Fe Institute (SFI).
It's quite possible that history will regard SFI as one of the most important
scientific developments in the late 20th century. In Holland's words, it's
basically a "collection of Nobel Laureates, MacArthur Fellows, Old
and Young Turks, and bright young postdocs" dedicated to the study
of complex adaptive systems. The systems have
...a crucial role in a wide range of human activities... Economies,
ecologies, immune systems, developing embryos, and the brain are all examples
of complex adaptive systems. Despite surface dissimilarities, all complex
adaptive systems exhibit a common kernel of similarities and difficulties.
[They all] involve large numbers of parts undergoing a kaleidoscopic array
of simultaneous non-linear interactions. Because of the non-linear interactions,
the behavior of the whole is not, even to an approximation, a simple sum
of the behaviors of its parts.
Two other recent books provide a glimpse into the activities of this intriguing
and diverse group. The first is Emergent Computation, edited by Stephanie
Forrest. Although this book is not an official SFI publication, it includes
contributions by many of the key people at SFI, including John Holland.
The second is Artificial Life II (AL2) published in mid-1992 as part
of an SFI series for Addison-Wesley. AL2 consists of the proceedings
of a 1990 conference at SFI; it follows an earlier volume on a similar conference
in 1988. As discussed further on, artificial life and emergent computation
are two overlapping fields of research. Together, these two books contain
over 60 different papers, bearing titles such as: "Computation at the
Edge of Chaos," "Algorithmic Chemistry," "The Dynamics
of Programmable Matter," and "Interactions between Learning and
Evolution."
Stephanie Forrest introduces the basic idea of emergent computation: "to
explore computational models in which the behavior of the entire system
is in some sense more than the sum of its parts." The traditional approach
to computing focuses on building systems that conduct specific tasks precisely
planned in advance. By contrast, the physical and biological sciences readily
accept the idea that interactions among simple deterministic systems can
produce not-quite-predictable, but interesting and complex, global behaviors.
The premise of emergent computation is that, "...interesting and useful
computation systems can be constructed by exploiting interactions among
primitive components, and further, that for some kinds of problems (such
as modeling intelligent behavior) it may be the only feasible method."
Compare emergent computation with conventional programming:
The standard approach to programming language design minimizes
the potential for emergent computation. The notation or syntax used to express
computer programs is for the most part context free. Roughly, this means
that legal programs are required to be written in such a way that the legality
(whether or not the program is syntactically correct) of any one part of
the program can be determined independently of the other parts. While this
is a very powerful property (among other things, it makes it possible to
build efficient compilers) emergent computations are almost certainly not
context-free since they arise from interactions among components.
Instead of trying to minimize side effects that lead to inadvertent interactions,
such as bashing a global variable, emergent computation is "primarily
computation by side effect." In other words, please set aside all the
careful efforts over the past few decades toward making the programming
process more controllable and predictable--the hallowed precepts of information
hiding, encapsulation, layered abstraction, and modularization--and revel
instead in the unbridled chaos of natural growth processes. If this sounds
a bit New Age and Californian, it's probably because some of it is. Some
of the key figures in emergent computation and artificial life came from
the hippie-ish Dynamical Systems Collective in Santa Cruz, so vividly depicted
in James Gleick's bestseller Chaos.
Nevertheless, there is serious, rigorous, world-class science here, along
with exuberant speculation and inspired creativity. Included with the paper
by John Holland are papers by his students and coworkers. Stephanie Forrest,
one of his PhD students, has a paper on the subject of classifier systems.
John Koza, another PhD student, has a paper entitled, "Genetic Evolution
and Co-Evolution of Computer Programs." After competing his studies
in the '70s, Koza went on to make a fortune doing traditional computing
during the early '80s, then became a venture capitalist, and has now returned
to the unfettered study of genetic algorithms.
I don't have anywhere near the space to describe the articles in these two
volumes, but if you ever get the feeling you haven't encountered anything
really new lately, thumb through either one of these books, and that notion
will be dispelled immediately. The subject of artificial life (AL) deserves
a whole review in itself. One definition of the field of AL is that it seeks
to model and understand natural living processes in the same way that artificial
intelligence (AI) seeks to model natural intelligence. The field of AL overlaps
with emergent computation in the same way that AI overlaps with symbolic
programming.
In the remainder of this review, I'll briefly highlight some of the articles
that struck my fancy.
Thomas Ray's "An Approach to the Synthesis of Life," in AL2,
provides a technical description of his work that has recently been touted
in the popular press, such as the New York Times. Ray takes the most literal
approach possible to implementing genetic algorithms, by implementing a
virtual world inside the computer where self-replicating programs compete
to survive. The precious resources are CPU time and memory space, and organisms
evolve strategies to exploit one another. CPU time is analogous to life-giving
energy, and memory is analogous to inhabited territory. The inhabitants
of this territory (or "primordial soup") are small, machine-language
creations that are a result of mutation from the one original program written
by Ray. In stark contrast with the work of John Holland, Ray provides little
theory or mathematical framework. Ray spent 16 years in the Central American
jungle as a biologist, and is content to let his empiricism stand (or fall)
on its own.
The results of his experiments are enchanting: Over a time scale of thousands
of generations, "biodiversity" appears, parasites evolve, hosts
evolve immunity to parasites, and parasites circumvent the immunity. (Parasites
are creatures that do not contain the complete code for their self-replication;
they rely on other creatures' genomes to reproduce.) Ray's work might not
have the long-term impact of Holland's masterpiece, but his captivating
concepts have made his code a popular choice for ftp-ing on the Internet.
Another gem of a piece is by a different Ray--Alvy Ray Smith. Although Smith
is now well-known for his work in computer graphics and special effects,
his paper in AL2 summarizes Smith's PhD thesis of 20 years ago. The
subject is not computer graphics, but rather a proof of the existence of
non-trivial, self-reproducing machines. The term "nontrivial machine"
refers to a Universal Turing machine capable of processing any computable
function. The theorem that Smith tackles is one proved by John Von Neumann
in 1953, but which originally required a book-length proof. Smith's equivalent
proof fits in two pages. Along the way, he provides the clearest explanation
I've seen of the equivalence between a Turing Machine and a cellular automaton.
In another interesting piece presented in both AL2 and Emergent
Computation, Danny Hillis, founder of Thinking Machines (makers of the
massively parallel Connection Machine), describes his use of "co-evolving
parasites" in addressing the minimal sorting-network problem. A sorting
network is a sorting algorithm that takes a set of inputs and sorts them
using a sequence of comparisons and exchanges of data in a predetermined
order.
Hillis writes, "Finding good networks is a problem of considerable
practical importance, since it bears directly on the construction of optimal
sorting programs, switching circuits, and routing algorithms in interconnection
networks." Hillis uses a genetic algorithm, a pretty sophisticated
one that includes not just mutation and recombination, but also dominant
and recessive genes and competitive mating.
With this algorithm, the system produces a sorting network almost as good
as the one discovered by Donald Knuth in an early study of sorting networks.
To improve on this rather impressive result, Hillis introduces a whole new
population, one which interacts with the original population of networks
in a host-parasite relationship (equivalent to a predator-prey relationship).
In this interaction, hosts (sorting networks) are scored by how well they
sort, while parasites (test cases) are scored by how well they find flaws
in sorting networks. After successive waves of epidemic and immunity (feast
and famine), the result is a 61-exchange sorting network, very close to
the best known, and better than Knuth's.
Adaptation in Natural and Artificial Systems
John H. Holland
MIT Press, 1992
205 pages, $14.95
ISBN 0-262-58111-6
Emergent Computation
Stephanie Forrest, Editor
MIT Press, 1991
452 pages, $32.50
ISBN 0-262-56057-7
Artificial Life II
Chirstopher Langton, Charles Taylor, Doyne Farmer, and Steen Rasmussen,
Editors
Addison-Wesley, 1992
854 pages, $34.50
ISBN 0-201-52571-2
Electronic Review of Computer Books
Created 5/1/96 / Last modified 6/23/96 / webmaster@ercb.com