As mentioned in section 1.4, there are two major research areas in computer science that are strongly inspired by natural evolution and genetics: Artificial Life and Evolutionary Computation. In both areas there exists a body of literature that is already so big that it is impossible to present or even know every idea that has been published until now. This is not something unusual. In nearly all areas of research you have the problem of finding a good compromise between having broad and interdisciplinary knowledge (which is good for getting new ideas) and having complete knowledge about a special subfield (which makes a good expert). This introduction about recent work in Artificial Life and Evolutionary Computation tries to give you an overview with concentration on approaches that are more closely related to the ideas presented in this thesis. In the section about Artificial Life these will mainly be publications about modelling cells and especially multicellularity, as this is the best natural example for the organization of cooperation between many small parts to reach a higher goal. The section about Evolutionary Computation will present some approaches that either use such a cooperation for building problem solutions or evolve solutions that exhibit a cooperative behaviour themselves.
Simulation and modelling of biological processes has a long history in computer science. But until 1987, there was no common name for this field and it was therefore very difficult to find all the literature that had the same objective. Because of these problems, Christopher G. Langton organized the "First workshop on Artificial Life" which gave a name to this branch of science and made scientists of very different areas get aware of the many similarities in their work and visions.
Like there are many different areas of research in biology, there are also many different approaches to Artificial Life. If you have read everything up to this point, you know at least two very important processes of life on earth: Evolution and Gene Regulation. The latter is one of the key conditions for the development of individual creatures from a single egg cell to the fully grown individual. This development is called ontogeny33. As we have seen in sections 1.2.3 and 1.3, the working of these two developmental processes (evolution as the development of a species and ontogeny as the development of an individual member of the species) is very different. Even though some developmental stages of an individual have similarities with evolutionary stages of its species34, the functioning of the development is of a totally different kind. While the driving forces for evolution come from outside (variation and selection are mainly an effect of the environment), ontogeny is mostly an effect of the internal information and interactions, only modified by the environment35.
Evolution is also called phylogeny36. This process is the basis for the whole branch called Evolutionary Computation. Without Darwin's seminal ideas, we would not be able to breed problem solutions. So this is probably by far the most simulated natural mechanism. And the good results of using its workings practically make Evolution be an even better theory. But there are also researchers in Artificial Life that want to find out more about natural phylogeny. Larry Bull has for example examined the initial conditions for the emergence of multicellularity in [Bull, 1997] by comparing the fitness of unicellular and simple multicellular simulated organisms under different conditions.
A wide and frequently covered area of research is morphogenesis or pattern formation. The main question in these areas is: What are the conditions for the development of forms found in nature? As shapes, structure and patterns in nature are usually built of and by many cells that have grown into this form, the researchers working on these questions also have to model multicellularity.
One very popular approach to doing this is to use Cellular Automata (CA). A cellular automaton is a mathematical model of cells and their interactions originally conceived by Stanislas Ulam and John von Neumann and presented by the latter in [von Neumann, 1966]. Von Neumann wrote:
The question we hope to answer ...is: what are the basic principles which underlie the organization of these elementary parts in living organisms?The model is very far away from the natural example, but it is a good basis for studying complex interacting systems in general. Moshe Sipper describes cellular automata in [Sipper, 1997] as
...dynamical systems in which space and time are discrete. A cellular automaton consists of an array of cells, each of which can be in one of a finite number of possible states, updated synchronously in discrete time steps, according to a local, identical interaction rule. The state of a cell at the next time step is determined by the current states of a surrounding neighborhood of cells.Hans Meinhardt for example uses differential equations in [Meinhardt, 1995] for developing many different patterns with striking similarity to patterns found on sea shells and according to [Pfeifer et al., 2000] these can easily be reformulated to cellular automata rules.
Another approach to simulating cells is to construct an Artificial Chemistry. This means that there are rules which determine the reaction of different substances getting into contact and that the substances can diffuse37 into the local environment38. Chikara Furusawa and Kunihiko Kaneko use this method in [Furusawa and Kaneko, 1997] for studying cell differentiation. In [Furusawa and Kaneko, 1998], they simulate multicellular pattern formation with an artificial chemistry and in [Kaneko and Yomo, 2000], Kunihiko Kaneko and Tetsuya Yomo find that differentiation on the basis of the modeled interactions can lead to discrete cell types that are not mixed by recombination. Also Cefn Hoile and Richard Tateson use such a reaction-diffusion system in [Hoile and Tateson, 2000], but with the difference that they use an artificial neural network for producing the reaction output. Hiroaki Kitano and his coworkers present in [Kitano et al., 1997] their Virtual Biology Laboratories, in which they try to simulate all the biochemical processes happening in cells as detailed as possible.
There are also different approaches to modelling gene expression networks which work on the basis of the gene regulation mechanisms introduced in section 1.2.3. Most works concentrate on the interactions without modelling diffusion and spatial dimensions or growth. This means that these simulations only model the processes in single cells. Shoudan Liang et al. use boolean networks in [Liang et al., 1998] for inducing gene regulation models in a single cell from observed data. Sean Luke et al. use gene regulation abstracted from the natural example of Drosophila39 for evolving deterministic finite state automata [Luke et al., 1999]. Thorsten Reil examines in [Reil, 1999] the dynamics of gene expression networks on the basis of template matching in a DNA-like sequence and draws interesting conclusions for artificial and biological ontogeny. Jan T. Kim also introduces a formalism for modelling gene regulation networks which is quite close to the natural example [Kim, 2001]. But they all only model the interactions in one single cell.
Peter Eggenberger uses the same principles of template matching in a DNA-like sequence to model gene regulation networks, but he expands this by adding a spatial dimension to it and by simulating multicellular growth processes. He uses this approach both for pattern formation in [Eggenberger and Dravid, 1999] and for morphogenesis of 3D shapes in [Eggenberger, 1997].
In their important book [Maynard Smith and Szathmáry, 1995] John Maynard Smith and Eörs Szathmáry compare a termite-hill with a well-designed house:
Although the mound resembles a human building in having features ensuring the comfort of its inhabitants, it differs in that not one of its builders had a picture of the completed structure before building started. The structure emerged from the rule-governed behaviour of tens of thousands of interacting workers. In this, the mound resembles a human body rather than a human building. The body is build by the rule-governed actions of millions of cells. Nowhere is there anything resembling a blueprint of the body. At most, the genome is a set of instructions for making a body: it is not a description of a body.
The resemblance between the development of an insect colony and of an organism has led to the concept of a 'superorganism'. The analogy has some value.So according to John Maynard Smith, swarms of ants, termites or bees can in many respects be compared to multicellular organisms. Jesper Hoffmeyer also compares the body of multicellular creatures with animal swarms, only inversely. He writes in [Hoffmeyer, 1997]:
The body can be understood as a swarm of cells and tissues which, unlike the swarms of bees or ants, stick relatively firmly together.There has been quite a lot of work on simulating swarm behaviour by modelling mobile reactive agents40 that interact in a simulated environment. Jean-Louis Deneubourg and Simon Goss found an explanation for the fact that ants find the shortest path between food sources and the nest and prefer nearby located food by simulating their interactive behaviour [Deneubourg and Goss, 1989]. The results have even been used to solve computational problems such as the Traveling Salesman Problem [Colorni et al., 1992]. Craig Reynolds simulated flocking birds [Reynolds, 1987] and Maja Mataric has done a lot of work on constructing socially behaving robots [Mataric, 1995,Mataric, 1997]. More complex agent-based models with agents that have internal states are widely used for all sorts of simulations including economic models, traffic simulations, ecological simulations and simulation games such as SimCity [Hiebeler, 1994]. But the behavioural rules for the individuals are nearly always formulated manually. There are very few attempts to finding good rules by letting them evolve automatically. We will get back to this in the next section.
The use of evolutionary principles for breeding solutions to computational problems instead of solving them analytically already started in the late 1950s with works of R. M. Friedberg [Friedberg, 1958]. But the application and invention of approaches that are still used today started in the 1960s.
The first two important methods were Evolutionary Programming (EP), where finite state automata are being evolved, invented by Lawrence Fogel [Fogel et al., 1965] and Evolutionary Strategies (ES), which are numerical optimizations on the basis of evolutionary principles pioneered by Ingo Rechenberg and Hans-Paul Schwefel [Schwefel, 1965,Rechenberg, 1970]. Evolutionary strategies are together with the next development--Genetic Algorithms--the best known and until now the most widely used Evolutionary Algorithms41 (EA).
Genetic algorithms (GA) were invented by John Holland in the early 1970s [Holland, 1975]. The main difference to evolutionary programming and evolutionary strategies is that the variations are not performed directly on the problem solution. There is a (often binary) representation of the solution which is varied and mapped onto the real solution by some function. The real solution then is tested on the problem to get the fitness of the individual. The used function is called the genotype-phenotype mapping because the representation corresponds to the natural genome (the genotype) and the real problem solution corresponds to the living being (the phenotype) which develops on the basis of the genome. This difference to Evolutionary Strategies is very important because on the one hand, it makes the representation be shorter and more powerful in expressing different solutions, but on the other hand, the differentiation between genotype and phenotype usually makes the search for a good solution less powerful. This happens because depending on the mapping function a small variation of the genotype can lead to a big variation in phenotype and the inverse. In evolutionary strategies, the size of the variational steps is reduced with the solution getting better. This makes it possible to approach the optimum quickly and then find it quite exactly without jumping around it with too big steps. This normally is not possible in genetic algorithms. But not all problem solutions can be represented in real numbers. For many problems it is much easier to use genetic algorithms. William E. Hart et al. examine the possibilities and impacts of developmental mechanisms (including not only the genotype-phenotype mapping but also learning which denotes an adaptive quality that remains in the problem solution) in genetic algorithms in [Hart et al., 1995].
An example for the use of genetic algorithms with cellular automata is described by Moshe Sipper in [Sipper, 1997]. He uses the genetic algorithm technique for evolving good reaction rules for the automaton cells and calls this method Cellular Programming. This is a first approach to breeding behavioural rules for many small units in order to enable them to cooperate for reaching a higher goal. But it is very limited in its usability as well because of the simplicity of cellular automata (uses regularly placed, synchronously updated, reliable units without internal memory and with quite restricted communication) as because of the limitations of the genetic algorithm (compared to Genetic Programming which is introduced later in this section).
Peter Eggenberger used genetic algorithms together with gene regulation processes for evolving artificial neural networks for given problems [Eggenberger, 1996]. Jens C. Astor and Christoph Adami independently describe a similar combination in [Astor and Adami, 1998].
Genetic Programming (GP) is the most recent important new model for evolutionary computation. Even though already Alan Turing thought about breeding computer programs in 1950 [Turing, 1950], it was not really done until John Koza published his important book [Koza, 1992]. Since then, the genetic programming community grows rapidly. The main advantages of GP are the following:
Thomas Haynes et al., who come from Multiagent Systems45 (MAS) research, use strongly typed genetic programming46 in [Haynes et al., 1995] for evolving behavioural strategies for the agents in a multiagent domain. As testing domain they use the predator-prey pursuit problem, which is well known in the MAS research community. Their agents do not communicate and they all follow the same evolved rules. Sean Luke and Lee Spector use a very different and quite interesting approach for evolving teams of agents that follow different rules [Luke and Spector, 1996]. They use Automatically Defined Functions47 and Automatically Defined Macros48 for evolving a whole team of different agents as one GP individual. Every function or macro incorporates the behavioural rules for a different agent.
The disadvantages of all the mentioned approaches are that the resulting behavioural strategies are not very flexible in adapting to dynamic environments, there is no or very limited communication between the acting units, and the resulting agents are either homogeneous [Haynes et al., 1995] or heterogeneous [Luke and Spector, 1996,Sipper, 1997], but cannot change their strategies while cooperating, for example if more agents for a special function are needed. This does not allow for evolving high level multiagent systems49 like the ones that have until now only handcrafted behaviours.
As far as we know, nature uses a different approach. As we have seen in sections 1.2.1 through 1.2.3, all cells contain the same control program, the genome. But nevertheless, there exists a very complex interaction between the cells, which differentiate to many different types and perform very different functions. The basis of this--gene regulation--seems to be a solution to the problem how to evolve a team of many heterogeneous agents. Moreover, this mechanism implies a totally new kind of communication which is powerful even though it is very simple concerning the message structure. The use of gene regulation has many advantages, but we will come back to that later.
This is not the first work that stresses the power and importance of gene regulation for evolutionary computation. Sean Luke, Shugo Hamahashi and Hiroaki Kitano wrote in [Luke et al., 1999]:
While evolutionary computation has drawn some inspiration from modern genetics, by and large the inspiration for this field has been aging Mendelian ideas ...Even Melanie Mitchell's highly-regarded GA text [Mitchell, 1996] introduces biological genes thus: "A chromosome can be conceptually divided into genes--functional blocks of DNA, each of which encodes a particular protein. Very roughly, one can think of a gene as encoding a trait, such as eye color. The different possible 'settings' for a trait (e.g., blue, brown, hazel) are called alleles." This is not how it actually works ...Genes form a complex network of interrelationships and regulation which, when seeded with initial chemical concentrations distributed throughout cells, results in miniature chemical machines ...In the rest of this paper, we begin by describing our work in modelling an interesting area of developmental genetics, gene regulation, which we think has particular utility to many new domains in evolutionary computation.Also Hassan Masum and Franz Oppacher saw the power of gene regulation for evolutionary computation. They wrote in [Masum and Oppacher, 2001]:
We focus particularly on regulatory networks and embryogenesis, as these provide a mechanism that is key in developmental biology and genetics but has not been substantively used to date in EC.Seemingly, these works were not enough to make many researchers take notice of the powerful mechanisms that are yet unexplored. The above cited researchers saw the power for EC, but as they mainly work in Artificial Life research, they seemingly did not continue with the idea and did not yet produce systems capable of using that power for real applications. As we will see in section 2.1.1, my ideas for Object-Oriented Ontogenetic Programming and the use of gene regulation for evolutionary computation also developed out of studies in Artificial Life that modeled these processes and out of the resulting question why nobody uses this powerful mechanism for solving practical problems until now. I hope, that this work at last can make more people recognize the possibilities of gene regulation mechanisms for automatic problem solving and adaptive systems design and that it makes a whole new area of research begin to grow: Evolution of Distributed Intelligence50 (EDI).