«Arti cial Chemistries—A Review Peter Dittrich Jens Ziegler Wolfgang Banzhaf University of Dortmund Department of Computer Science Systems Analysis ...»
Arti cial Chemistries—A Review Peter Dittrich
University of Dortmund
Department of Computer Science
This article review s the growing body of scienti c
work in arti cial chemistry. First, common motivations and http://ls11-www.cs.uni-dortmund.de
fundamental concepts are introduced. Second, current email@example.com research activities are discussed along three application firstname.lastname@example.org dimensions: modeling, information processing, and email@example.com optimization. Finally, common phenomena among the different systems are summarized. It is argued here that arti cial chemistries are “the right stuff” for the study of prebiotic and biochemical evolution, and they provide a productive framework for questions regarding the origin and Keywords evolution of organizations in general. Furthermore, arti cial complex systems, evolution, selforganization, emergence, molecuchemistries have a broad application range of practical lar simulation, origin of life, chemproblems, as shown in this review.
ical computing Information should be generated from information just as organisms from organisms. The pieces should fertilize each other, they should be crossed over, they should be mutated, that is, varied to a small degree, but also to a larger degree by radical changes not known in genetics. This could perhaps happen in some vessels where reactions between “information-carrying molecules” take place, molecules that carry information in a similar way as chromosomes carry the features of organisms.1 Stanislaw Lem, Summa Technologiae, 1964 1 Arti cial Life and Arti cial Chemistry One of the main driving forces of science is the quest for understanding the origin and nature of life. For centuries, this quest has caused scientists to collect and systematically describe the diversity of life found everywhere around us. Over many years an impressive collection of data about the processes of life has been amassed. Biology as a traditional life science has sorted and classi ed the data, and—in the course of a century—has made considerable inroads into the understanding of certain aspects of life. The informational perspective, however, has not been the center of interest in biological attempts to approach the issue of life’s essence. Arti cial life (AL) research, on the other hand, abstracts from speci c examples of living processes and tries to integrate different approaches into one interdisciplinary attempt to extract the rst principles of life. The working hypothesis of AL research is that biotic phenomena can be modeled by using complex systems of many interacting components. The complex system approach toward an explanation of life employs emergence as a central concept. Emergence is used to deduce global properties of a system from the local interactions between its subsystems. These local interactions may follow simple effective rules that cause global behavior of the system to emerge, but cannot be predicted 1 Translated by the authors from the German edition, 1976, Insel Verlag: Frankfurt am Main
by simply analyzing the subsystems and their components. In other words, a system has certain properties not due to the properties of its constituents, but due to their organization and their mutual function in the whole.
If we tentatively accept the hypothesis that properties of a system’s components are not the main part of the description of that system’s organization, we come to the conclusion that natural systems such as organisms or social structures, though consisting of truly different matter and components, might follow the same organizational principles. This fundamental idea characterizes many AL approaches. Under this view living organisms are alive not because of the properties of their constituents but because of their organization.
The theory of evolution, formulated by Darwin, has caused a storm of controversy, challenging both scienti c and popular beliefs about the appearance of life on earth.
Up to this day the Darwinian revolution has not been realized in its extent, nor is it accepted by most of our contemporaries. The principle of random variation and competitive selection that Darwin discovered is a powerful means for understanding the progress of evolution. It seems to be valid also on the level of replicating molecules, and can be observed in higher-level systems (even social or cultural systems).
What has been left open, however, by the theory of evolution are questions relating to the origin of evolutionary units: How do the prerequisites come into being, that is, the entities that are varied and selected? How did qualitatively new evolutionary mechanisms emerge, such as sexual recombination, regulation of mutation rates, or the genetic code?
Abstract models that should be able to explain the origin of evolutionary systems would allow us to investigate the theoretical conditions for the origin and evolution of life. This is one of the fundamental goals of the AL sub eld of arti cial chemistry (AC) research. By abstracting from natural molecular processes, AC tries to investigate the dynamics of these complex systems. AC deals with combinatorial elements that change or maintain themselves, and especially with systems that are able to construct new components. AC thus deals with forms of organization, self-maintenance, selfconstruction, and with the conditions for those structures to arise. We would like to argue that arti cial chemistries are “the right stuff” to study when trying to uncover the basic mechanisms of life, and more generally, the origin and evolution of organizations.
The spectrum of AC research is broad. Its application may be considered along three main dimensions: (a) modeling, (b) information processing, and (c) optimization.
Along the axis of modeling are several examples of arti cial chemistry modeling systems in different domains. They range from the above-mentioned biological or evolutionary systems to social systems or models of parallel processing. The metaphor of colliding molecules is their common relation to chemistry.
In the area of information processing the computational properties of chemical systems are investigated and exploited. Many instances of chemical processes in nature can be interpreted as performing computations. For example, chemical reaction networks control the movement of bacteria, other chemical processes control the growth of neurons during the development of a brain, and the immune system can also be regarded as a chemical information processing system. The area of information processing can be subdivided again into two parts: (a) real chemical computing and (b) arti cial chemical computing. The former deals with real chemistry and tries to use real molecules in order to compute. The latter applies the chemical metaphor as a design paradigm for new hardware and software architectures.
In the area of optimization arti cial chemical systems help to nd solutions of “dif cult,” mostly combinatorial problems. This application domain is closely related to the eld of evolutionary computing because many evolutionary algorithms can be seen as arti cial chemical systems.
226 Arti cial Life Volume 7, Number 3 P. Dittrich et al. Arti cial Chemistries—A Review This article is organized as follows: First it outlines the common motivation for formulating ACs. Then it gives a structured overview of different approaches by means of common and distinctive features (Section 2.1). The following section (Section 2.2) gives a short tutorial on ACs, introducing two illustrative examples. Section 2.3 is devoted to a systematic attempt to classify the different AC approaches. A basis of discriminative features is given, according to which the consecutive lineup in section 3 is structured. The next section (Section 4) gives an overview of projects that make use of some properties of AC in applications. Section 5 deals with observed phenomena common to several approaches and tries to summarize their results. The closing part (Section 6) gives an outlook of future directions and challenges in the area.
2 Basic Concepts This section gives an introduction to the basic concepts of arti cial chemistries. Two descriptive examples follow, which should demonstrate concrete implementations. Finally, we try to structure the characteristics of ACs.
2.1 What is an Arti cial Chemistry?
Let us start with a broad de nition: An arti cial chemistry is a man-made system that is similar to a real chemical system. This de nition has been kept as general as possible so as not to exclude any relevant work. When we now become more precise in describing the structure of an arti cial chemistry we should keep in mind that not all AC approaches can be subsumed under the following conceptual framework.
More formally, an arti cial chemistry can be de ned by a triple ( S, R, A ), where S is the set of all possible molecules, R is a set of collision rules representing the interaction among the molecules, and A is an algorithm describing the reaction vessel or domain and how the rules are applied to the molecules inside the vessel. Both the set of molecules S and the set of reaction rules R can be de ned explicitly or implicitly (e.g., by an algorithm or mathematical expression). This will be illustrated by two examples in Section 2.2 and discussed in more detail in Section 2.3.
2.1.1 The Set of Molecules S The set of molecules S D fs1,..., si,..., sn g, where n might be in nite, describes all valid molecules that may appear in an AC. A vast variety of molecule de nitions can be found in different approaches. For example, molecules may be abstract symbols , character sequences [9, 51, 77, 95], lambda-expressions , binary strings [12, 43, 134], numbers [17, 44], hierarchical tree data structures [21, 22, 99], combinators , or proofs [30, 55]. A molecule’s representation is often referred to as its structure and is set in contrast to its function, which is given by the reaction rules R. The description of valid molecules and their structure is usually the rst step in the de nition of an AC. This step is analogous to the part of chemistry that describes what kind of atomic con gurations form stable molecules and how these molecules appear.
A reaction rule determines the n components (objects, molecules) on the left-hand side that can react and subsequently be replaced by the m components on the right-hand
side. n may be called the order of the reaction.2 Note that the “ C ” sign is not an operator here, but only separates the components on either side.
A rule is applicable only if certain conditions are ful lled. The major condition is that all of the left-hand side components must be available. This condition can be broadened easily to include other parameters such as neighborhood, rate constants, probability of a reaction, or energy consumption. In such a case a reaction rule would contain additional information or further parameters. Whether or not these additional predicates are taken into consideration depends on the objectives of the AC. If it is meant to simulate real chemistry as accurately as possible, it is necessary to integrate these parameters into the simulation system. If the goal is to build an abstract model, many of these parameters can be omitted.
2.1.3 Reactor Algorithm A—Dynamics An algorithm determines how the set R of rules is applied to a collection of molecules P, called reactor, soup, reaction vessel, or population.3 Note that P cannot be identical to S since some molecules might be present in many exemplars, others not at all.
Algorithm A depends on the representation of P. In the simplest case, without a spatial structure in P, the population can be represented explicitly as a multiset or implicitly as a concentration vector.
We shall now summarize the methods by which the dynamics of a reaction vessel (which usually contains a huge number of molecules) can be modeled and simulated.
The approaches can be characterized roughly by whether each molecule is treated explicitly or all molecules of one type are represented by a number, their frequency, or concentration.