Julian Adams
Department of Biology
University of Michigan.

(extended abstract postscript pdf)

Kenneth J. Arrow
Stanford University.

The agents of the economy (consumers, workers, investors) have to form predictions to guide their actions. They are solving the problem of inventing and selecting rules for belief and action, precisely the basis of the genetic algorithm. But the actions of other individuals are precisely what each individual is trying to predict. Recent research has shown that modelling securities markets as made up coevolving rule structures, each following a genetic algorithm, gives a credible picture.

Rik Belew
Univ. of California, San Diego (UCSD).

Perhaps our best characterizations of what it means for systems to be `complex' are in terms of the various classes of computational complexity. One unfortunate aspect of these definitions is there sensitivity to worst-case problem instances: An algorithm is complex if any of the problems it must solve take a long time.

Those in artificial intelligence have been resigned to ``heuristic'' methods for a long time: sometimes they work, sometimes they don't. Sometimes these heuristics prove themselves very robust; simulated annealling, tabu search, and neural network learning are only some examples. John Holland's Genetic Algorithms represent an important class of heuristics, with the additional virtue that they suggest themselves as models of biological, evolving systems.

For example, co-evolution is believed to be an important dynamic by which interacting biological species can reciprocally drive one another to progressive improvement. It is also possible to use it to cause algorithms to improve one another. The focus of this talk will be a consideration of the co-evolution of populations of heuristics against a ``landscape'' of problem instances.

(full paper postscript gzipped postscript, gzipped pdf)

James Brown

The following perspective comes from my somewhat indirect involvement in trying to make connections between artificial ecology as represented by ECHO and SFI, and the real ecology that I have studied for most of my career. My knowledge of artificial ecologies comes principally from discussions with Peter Hraber and Simon Fraser, from attending the two ECHO conferences, and from some knowledge of the work on GECKO being done by Oz Schmitt at Yale. My overall assessment is that we have a ways to go before ECHO or any comparable, very general artifical ecology will yield valuable insights into real ecology and evolutionary biology. The great attraction of ECHO is its sweeping generality, especially its impressively creative effort to incorporate some essence of both ecology (including resource-consumer dynamics and the fundamental interactions of competition, predation, and mutualism) and evolution (including a resource base for evolutionary information, as well as a "genetic" basis for adaptive evolutionary change through mutation, recombination, and selection). Unfortunately, however, some key principles and ingredients are still needed to produce an ecology that is sufficiently realistic to be useful for tackling basic and applied problems in the discipline. Notable for its absence is any treatment of energy and thermodynamics. In addition, I believe that the coupling of "information" and "metabolism" is inappropriate. Some of the obvious pathologies of ECHO appear to be directly related to these two problems. It is not clear whether these problems can be corrected without designing a fundamentally new system. So far, attempts to modify ECHO to make it more realistic (and here I would include GECKO as well as the work of Hraber and Fraser), have sacrificed much of the elegant generality of the original model, without producing an alternative that has useful ecological applications.

Arthur Burks
Philosophy and Electrical Engineering & Computer Science
University of Michigan

Some have recently suggested that the electronic digital computer arose from Alan Turing's 1936 machine formulation of the arithmetic and recursive logical manipulations that human computers had been carrying out and mathematical logicians had been studying. I will evaluate this thesis from the perspective of one who was involved in the development of the modern electronic computer.

The Atanasoff-Berry Computer (ABC) of 1939-1942 was the first electronic (digital) computer to be built. In addition to accomplishing computation with vacuum tubes, it established the principles of drum memory, binary computing and base conversion, dynamic capacitor memory (the D of DRAM), and vector computing. Atanasoff told my wife Alice and me that neither he nor Berry had ever heard of Turing.

The ABC led directly to the ENIAC (1943-1946), the first general- purpose (digital) electronic computer, designed and built by Eckert, Mauchly, Sharpless, Shaw, myself, and several othgers. These were electrical engineers, and none had sutdied or knew much mathematical logic except me, and I had not heard of Turing.

The ENIAC was followed by the EDVAC, for which von Neumann provided the logical circuit and program language design. Because he did know Turing and his 1936 paper, I will compare von Neumann's logical circuit and program language design of the EDVAC with Turing's state transition table design of his theoretical machines.

I will conclude with a precise definition of the concept of a Universal Electronic Computer that combines Turing's concept of a universal machine with von Neumann's EDVAC program language and his theory of self- reproducing automata.

David M. Cohen
Children's Nutrition Research Center
Baylor College of Medicine
Houston, Texas 77030

Estimation of metabolic flux rates from the isotopic labeling of intermediary metabolites depends on the use of mathematical models. In the use of stable isotopes and nuclear magnetic resonance (NMR) spectroscopy to measure fluxes, arguments based on mathematical models or on heuristic reasoning about the transfer of labeled carbon atoms have been used to substantiate the accuracy of calculations of flux rates during steady state or non-steady state conditions. However, debate and controversy are common. What is needed is a reliable model that can predict the distribution of isotopically labeled atoms among metabolic intermediates, independently of the mathematical methods presently used to interpret experimental data.

We have proposed a syntactic approach to modeling of biochemical fluxes that combines a rule-based description of atomic transfer in chemical reactions with a structurally oriented, stochastic model of chemical kinetics. This approach avoids the use of differential equations to describe the production and disappearance of each molecule. Our computer simulation predicts the concentration of each labeling pattern of each metabolic intermediate of a given pathway (such as [1^1-^13C]glutamate, [1,2-^13C]glutamate, [1,3-^13C]glutamate, etc.), as a function of time and of pathway fluxes. In fact, high resolution NMR spectroscopy can be used to measure these same labeling patterns (called "isotopomers"), providing a good test of theory/simulation and experiment.

(full paper postscript gzipped postscript)

Kenneth De Jong
Computer Science Department
George Mason University
Fairfax, VA
kdejong@gmu.edu

It was in 1969 that I signed up for Holland's Adaptive Systems course and was exposed to his ideas on "reproductive plans" that later evolved into "genetic algorithms". For me these ideas led to a PhD thesis and an interest in evolutionary and adaptive systems that has continued to the present. This span of 30 years in the area provides the background for a discussion of the past, the present, and future of GAs.

(full paper postscript gzipped postscript)

Marc Feldman

Short tandemly repeated DNA offers an extraordinary possibility to study human evolutionary history. There are estimated to be more than 100,000 markers of this kind in the human genome. They are highly polymorphic and have a very high mutation rate, about 0.0006 per gene per generation. We have studied several sets of data on repeated di-, tri-, and tetranucleotides, developing distance measures appropriate for these polymorphisms. Such distance measures translate into estimates of the times of separation of major modern human population groups.

New work shows that the pattern of variability can be used to infer the history of population expansion or contraction. In fact, it is possible to compute the expectations of higher moments of the repeat number distribution and show explicitly how these depend on demographic history. I will discuss two different approaches to such historical demographic inference. The first uses autosomal genes and the second Y-chromosomal polymorphisms. There is a strong signal of population expansion in most parts of the world except America and Oceania, where random genetic drift seems to have had the strongest influence. The methods of statistical analysis are often computationally intensive and raise interesting problems in biocomputing.

Marion R. Finley, Jr.
Graduate Program in Information Management Sciences
Asahi University, Japan
finley@asahi-u.ac.jp

The period in the United States extending from the late 1950's through the end of the 1960's and beginning of the 1970's has sometimes been called the "golden age" of American of American science. This period was characterized by an enormous creative output from the academic sector which, in turn fed the the industrial and military sectors. Indeed, there was a rather cozy and mutually beneficial relationship between these three sectors. The Logic of Computers Group, founded by Arthur W. Burks and John H. Holland perhaps epitomizes the essence of this fascinating period, one that surely will draw the attention of future scholars of the history of science and technology. The free atmosphere of search and intellectual query, of adventure into the unkown and daunting worlds of the computer, the human mind, human language and new mathematical paradigms, created a heady wine indeed for the young and idealistic gradaute student, still unwise in the ways of the world. In this paper, I shall try to attempt to recreate what it was like to have studied and worked in that unique environment created by Burks and Holland. The imprint of that experience on my professional development was profound indeed and I shall review some highlights of my own contributions, humble though they be, all of which owe much to the years spent at the University of Michigan.

(full paper)

A second contribution by Marion Finley et al:
Towards a Theoretical Model of Tele-Learning Using Genetic Algorithms
Marion R. Finley, Haruo Akimaru, Evelyne B. Hansen-Tropper
In the following is given a brief description of a theoretical model of tele-learning in which genetic algorithms may play a key role. (full paper)

Marion Finley's home page is here

Stephanie Forrest and Steven A. Hofmeyr
Department of Computer Science
University of New Mexico
Albuquerque, NM
fsteveah,forrestg@cs.unm.edu

We describe an artificial immune system (AIS) that is distributed, robust, dynamic, diverse and adaptive. It captures many features of the vertebrate immune system and places them in the context of the problem of protecting a network of computers from illegal intrusions. The AIS resembles a classifier system in many important ways. Similarities and differences are discussed.
(full paper: postscript; gzipped postscript )

Andrew M. Gillies
Nonlinear Dynamics Inc.
Ann Arbor, MI.
gillies@nonlineardynamics.com

A recognizer is a computer program for locating objects of known classes within a complex signal. Best known examples include speech recognition and character recognition (OCR) systems, but an argument is made that the techniques apply in a broad spectrum of applications. This paper discusses the recognizer development process. Topics addressed include training sample collection, feature detection, the integration of segmentation and classification, and the use of high-level information in the recognition process. The paper contains two conjectural sections, one about using style information, and another about maintaining diversity in a genetic algorithm. The paper is written in a personal style, as part of a convention honoring the contributions of John Holland to the academic community.

(full paper: postscript; gzipped postscript )

Douglas Hofstadter
Cognitive Science
Indiana University

It's an easy pathway from genetic algorithms to artificial evolution to the evolution of artificial software organisms with superhuman intelligence to the emergence of a race of superior beings who at first adopt us humans for their pets and then, as they continue to evolve and soon leave us in the proverbial dust, see us as boring albatrosses, and dump us. Is this a plausible short-term scenario for humanity and its artificial progeny? Why or why not? Whither humanity, in any case, with the Pandora's box of simulated evolution opened? Are our decades numbered? Have we JHH to thank for ending it all for us?

Keith J. Holyoak and John E. Hummel
Dept. of Psychology
University of California, Los Angeles
holyoak@lifesci.ucla.edu, jhummel@lifesci.ucla.edu

One of the hallmarks of an adaptive system is the use of combinatoric power to construct representations of novel situations from a pool of more elementary elements. In the case of humans and probably other primates, combinatoric representations appear to require the compositional properties of symbol systems. I will argue that the mind is symbolic in a way that requires dynamic variable binding over distributed representations of meaning. Neither PDP-style connectionist models nor traditional symbolic models satisfy these twin requirements. These requirements are met by symbolic connectionism, an approach I will illustrate using the LISA model (Learning and Inference with Schemas and Analogies; Hummel & Holyoak, 1997) of analogical reasoning and relational generalization.

Hummel, J. E., & Holyoak, K. J. (1997) Distributed representations of structure: A theory of analogical access and mapping. Psychological Review, 104, 427-466.

(full paper postscript, gzipped postscript)

John R. Koza
Stanford University

The subtitle of John Holland's pioneering l975 book Adaptation in Natural and Artificial Systems correctly anticipated "applications to ... artificial intelligence." By applying the genetic algorithm to the space of possible computer programs, it has proven possible to automatically create computer programs that or approximately solve, a wide variety of problems. This variation of the genetic algorithm, called genetic programming has been used to solve problems of system identification, classification, control, robotics, optimization, pattern recognition, and design. There are a number of instances where genetic programming has produced a computer program that is competitive with human performance on particular specific problems from the fields of computational molecular biology, mathematical problems of cellular automata and sorting networks, and the synthesis of designs for analog electrical circuits. In particular, genetic programming has been applied to the problem of automatic synthesis of both the topology and sizing of analog electrical circuits, including filters (lowpass, highpass, bandpass, crossover, and comb), amplifiers, computational circuits, time-optimal controller circuits, source identification circuits, temperature-sensing circuits, and a voltage reference circuits. In addition, the advent of rapidly reconfigurable field-programmable gate arrays (FPGAs) and the idea of evolvable hardware opens the possiblity of embodying each individual of the evolving population into hardware for the purpose of accelerating the time-consuming fitness evaluation task of genetic algorithms. In addition, genetic algorithms and genetic programming exploit the increasingly available power of parallel computing and cluster computing in a highly efficient way.

(full paper postscript, gzipped postscript)

Michael S. Landy
Psychology Department and
Center for Neural Science
New York University
New York, NY 10003

Various visual cues provide information about depth and shape in a scene. In this talk, I'll review research on depth cue combination. Using normative considerations, my colleagues and I have developed the ``Modified Weak Fusion'' (MWF) model of cue combination. This model includes a simple, linear cue combination rule (weighted averaging of depth estimates). But, it also raises three key issues for depth cue combination in human vision that lead to apparent nonlinearities and interactions between cues: (1) cue promotion (most cues must be scaled and disambiguated before averaging is a meaningful operation), (2) dynamic weighting of cues (a cue's weight depends on scene content, including the weight of other cues), and (3) robustness of cue combination (a cue's weight may change with the degree of discrepancy of the estimate of depth derived using that cue relative to the estimates from other cues present in the scene). We have perceptual evidence for all of these processes including the linear depth combination rule, cue reweighting with changes in cue reliability, cue reweighting with changes in depth discrepancy between cues, and cue interactions contributing to cue scaling (that is, to an estimate of the viewing distance used to scale velocities or disparities to depth values). Finally, we summarize more recent work concerned with the way in which different cues' a priori biases interact to disambiguate simple 3-D stimuli.

(full paper postscript, gzipped postscript)

John H. Miller, Carter Butts, and David Rode
Carnegie Mellon University

Communication plays a vital role in the organization and operation of biological, computational, economic, and social systems. Agents often base their behavior on the signals they receive from others and also recognize the importance of the signals they send. Here we develop a framework for analyzing the emergence of communication in an adaptive system. The framework enables the study of a system composed of agents who evolve the ability to strategically send and receive communication. While the modeling framework is quite general, we focus here on a specific application, namely the analysis of cooperation in a single-shot Prisoner's Dilemma. We find that, contrary to initial expectations, communication allows the emergence of cooperation in such a system. Moreover, we find a systematic relationship between the processing and language complexity inherent in the communication system and the observed behavior. The approach developed here should open up a variety of phenomena to the systematic exploration of endogenous communication.

(full paper postscript, gzipped postscript)

Dr. Robert G. Reynolds and Xidong Jin
Dept. of Computer Science
431 State Hall
Wayne State University
Detroit, Michigan 48202
Phone: (313)-577-0726
Fax: (313)-577-6868

The key idea behind Cultural Algorithms is to explcitly acquire problem-solving knowledge (beliefs) from the evolving population in the form of schemata and in return apply th at knowledge to guide the search [Reynolds 1993, 1996]. In solving nonlinear constraint optimization problems, the key problem is how to represent and store the knowledge about the constraints. Previously, Chung [1996,1998] used Cultural Algorithms to solve unconstraint optimization problems. There, he used interval schemata proposed by Eshelman and Schaffer [Eshelman 1992] to represent global knowledge about the independent problem parameters. However, in constraint optimization the problem intervals must be modified dependently. In order to solve constraint optimization problems, we need to extend the interval representation to allow for the representation of constraints. In this paper, we define ann-dimensional regional-based schema in terms of belief-cells, which can provide an explicit mechanism to support the acquisition, storage and integration of schematic knowledge about the constraints. In a Cultural Algorithm framework, the belief space can "contain" a set of these schemata, each of them can be used to guide the search of the evolving population. This kind of region-based schemata can be used to guide the optimization search in a direct way by pruning the unfeasible regions and promoting the promising regions. We compared the results of 4 CA configurations that manipulate these schemata for an example problem. An application to a problem in Cultural Evolution is also demonstrated.

(full paper postscript, gzipped postscript)

Richard S. Rosenberg
Department of Computer Science
University of British Columbia
Vancouver, BC Canada V6T 1C8
rosen@cs.ubc.ca

There is no doubt that genetic technology has become an important and controversial technology in contemporary life. Whether it is the Human Genome Project, the cloning of sheep, the genetic modification of food, the linkage of an ever-growing number of diseases to their genetic origins, the public is being told on a regular basis that the basic substance of life can be modified to improve society in a striking manner. The contribution of genetics and evolutionary theory to the development of intelligent systems is not nearly as well advertised or understood. Nevertheless, the implications for society are deep and broad.

Given the intrinsic difficulty of determining the complex interactions involved in the diffusion of technological innovation, it is not surprising that so little effort has been devoted to this enterprise. Furthermore, there is little evidence that findings of potential problems have resulted in a curtailment of specific research and development programs. One encouraging note is that the multi-billion dollar Human Genome Project has allotted 5% to sponsor research on the social implications arising from this massive research program.

It should be recalled that when Arthur Samuel launched his influential research program on learning in computer programs, he was motivated by the desire to employ the results in an economic framework to improve productivity and efficiency. That John Holland was influenced by Samuel's checker player is undeniable and in fact his realization that one form of learning could be substantially accelerated by recasting it into an evolutionary framework has been a powerful guiding principle through the subsequent years. But what about Samuel's original motivation? If the purpose for developing powerful learning and adaptive mechanisms is to improve the functioning of the economy, shouldn't that assumption be evaluated?

More specifically, the following concerns are of considerable interest and therefore merit our attention. Although the relation between work and technology has long been studied and continues to generate considerable interest, the impact of intelligent machines on both the number of jobs and the quality of those jobs, remains a serious issue. The simplistic assumption that replacing humans by intelligent artifacts will necessarily benefit society at large must be continually reevaluated. Clearly, contributing factors must involve concerns of efficiency, the role of work as a component in human self worth, the distribution of wealth generated by advanced technologies, and growing divisions in society resulting from gross inequities in income. Obviously, this paper will provide few definitive answers.

Other issues of interest are the use of intelligent programs in data mining, the analysis of vast amounts of information to determine useful patterns of commercial activities. Such patterns are of considerable value to direct marketers and represent a serious threat to individual privacy. Along this direction as well, there is considerable interest in natural language understanding programs that could be used by filtering and blocking programs on the Internet to restrict access in an intelligent manner to "undesirable" Web sites. Smart vision programs could be used to block access to images that may be too sexually explicit for some tastes. The current interest in controlling and limiting access, as a means to make the Internet a safe place for business, will be aided by the diffusion of intelligent programs that replace inefficient humans in these difficult and time-consuming tasks.

It should be obvious that the benefits of intelligent machines and processes are being emphasized and possible detrimental impacts are being largely ignored. Agreed, but with the vast amounts of money and people engaged in research and development, supported by both private and public funds, surely an investigation of problematic outcomes is in order. John Holland's work is important and could change society in fundamental ways. These potential changes deserve a careful analysis; a beginning is made here as to whether or not technological determinism, reduces the debate to a vacuous exercise.

Michael M. Skolnick,
RPI

Embodied in the concept of implicit parallelism are some fundamental "observations" concerning the limitations of knowledge. Implicit parallelism says that the GA procedure works because there is something it is not telling us, and this something is the allocation of credit to schemata. At the same time, we want to know which schemata are being judged better than others.

This paper will explore some connections between implicit parallelism and various philosophers such as Nietzsche, Wittgenstein, Hebb, James, and Midgely. Philosophical issues from epistemology, ethics, and psychology can be connected to some of the mystery generated by implicit parallelism.

The foremost "mystery" is that of speciation. To make tag-like connections emerge it would seem that credit-allocation would have to be embodied in some (as yet unknown) metric, resulting in equivalence classes formed over the schemata state space. What is inherently implicit must be made explicit? Not being able to penetrate schemata space is why speciation is such a difficult problem and, in some sense, is also a canonical problem - along with object recognition - of the general problem of emergence.

(full paper postscript, pdf)

Oliver G. Selfridge
The Media Lab, MIT

     "The world is all that is the case
     But none, I think, do there embrace."
                "The Marvellous Wittgenstein"

This paper will cover a general discussion of changes and improvement in software. I will focus on some special aspects of the evolutionary process, and propose to extend those techniques and approaches.

The problem To explain, with working examples, how we can speed up evolution from billions of years to billions of, say, microseconds. Can we explain, and perhaps begin to remedy, the difficulty of finding the really new concept?-e.g., the origins of wings, eyes, and mathematics.

The approach Agreements and conflicts wrt evolution: improvements and genetics and the drive for changes and evolution. The trouble with evolution is that it has taken so long. What is the information (in the Shannon sense) that drives evolution? Originally just one bit per organism-or so, for many offspring are presumably altogether contribute more than a single bit. Basically, the generating idea is that the drive of evolution is survival, although there is more than a little circularity in that viewpoint. We propose an approach that considers feedback for each module of the software package as a whole; that is, it is not just survival-though of course, that is important too!-but the continuing improvement of each part. We consider that each module is a control structure, driven by a purpose. Every purpose is then a control, and all of them integrate into a purpose structure, which can be very large indeed. The nature of such a structure and what it requires and implies will be discussed.

(full paper postscript, gzipped postscript)

Charles F. Stevens
The Salk Institute
San Diego, CA

The theory of evolution plays a key role in all thought about biological systems, but the notion of evolution by selection is quite different in character from other important scientific theories. The theory of evolution has been modified and extended over and over as more is learned about biological mechanisms, but even the modern version remains an incomplete account of the evolutionary process. John Holland's formalization of evolution in complex adaptive systems provides a clear framework for evaluating current evolutionary theory in biology.

Tommaso Toffoli
Electrical and Computer Engineering
Boston University
Boston, MA

In spite of their seemingly "obvious" virtue as a search strategy, genetic algorithms have ended up playing only a modest role as design tools in science and engineering. We review the reasons for this apparent failure, and we suggest a more relaxed view of their utility.

(full paper postscript, gzipped postscript)

T. H. Westerdale
Department of Computer Science
Birkbeck College
University of London

A contrived example is used to illustrate how implicit group selection might be used in a Michigan-style classifier system to control freeloading. Each useful group is defined by a short schema, but not all short schemata define useful groups. This preliminary report describes the mechanism by which useful groups combat freeloaders, but it does not address the difficulty of encouraging the spontaneous appearence of useful groups.

(full paper)

Stewart Wilson

Classifier systems have traditionally taken binary strings as inputs, yet in many real problems such as data mining, the inputs have real components. A modified XCS classifier system is described that learns a non-linear real-vector classification task.

(full paper postscript, gzipped postscript)

Bernard P. Zeigler, M. Jamshidi and H. Sarjoughian
Electrical and Computer Engineering
University of Arizona

This short paper outlines research that the Universities of Arizona and New Mexico have initiated in distributed robotics. A basic hypothesis of this research is that intrinsically efficient discrete event abstractions of soft computing paradigms, including neurons and fuzzy rule controllers, will enable cooperative multi-robot systems to overcome severe limitations on on-board processing and communications networking. Specifically, we seek to implement fast reacting agent architectures capable of identifying and deactivating non-self invaders. Implications in general for the tradeoffs between local computation, communication and ability to cooperatively self-organize are discussed.

(full paper-postscript, full paper-pdf, a site with powerpoint slides)

Back to top page for the JHH Festschrift conference.