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.
Copyright © 1993, Dr. Dobb's Journal