Introduction to Endogenous Evolution

Walter de Back
Virtual Life lab
Depts. of Philosophy &
Information and Computing sciences
Utrecht University

Also available as pdf document

Introduction

Evolutionary computing (EC) is a collection of computational methods that are inspired on natural selection in the organic world. These methods are rapidly gaining recognition among engineers as a technique for optimization and adaptive control. Evolutionary computation is also more and more frequently used to evolve controllers for autonomous robots. In robotics, automated adaptation to the environment is a useful tool, because of the enormous complexity of real-world and robot controllers.

Although EC provides a very useful tool for engineering purposes, the standard methods and algorithms are no accurate model of natural selection. To study the dynamics of natural selection, or the involvement of natural selection in the evolution of some (intelligent) behaviour, the model has to be implemented more accurately.
One key difference of normal EC methods and natural selection is that in the former the selection criteria are predefined by the human operator in a fitness function, and in the biological case the criteria are introduced by the (social) environment and dependent on the individuals own behaviour.
In other words, in standard evolutionary computation selection is exogenous (generated from outside, the human operator) and in nature selection is endogenous (from inside, the individual perspective). The latter is modeled in evolutionary robotics and especially artificial life simulations.

This paper provides a short introduction to endogenous evolution and its use in some alife simulations.

Standard Evolutionary Computation

The human brain is, as all readers will agree upon, a wonderful device. The process that created the human brain, natural evolution, must be equally wonderful - if not more so. All living organisms are vivid examples of its ability and power to yield enormously complex and adaptive systems.

The field of synthsizing the principles of natural selection for engineering tasks, called Evolutionary Computing (or Evolutionary Algorithms) started in the 1960s with the work of Ingo Rechenberg in Germany, John Holland and L.J. Fogel in the US. All these researchers developed slightly different algorithms. Holland's breed is called Genetic Algorithms (GAs), Fogel developed Evolutionary Programming (EP), and Rechenberg's method is called Evolutionary Strategies (ESs). Although these methods differ in their algorithmic implementation and applications, all of them share a basic evolution-based process:

1. In Evolutionary Computing, a population of possible solutions is randomly generated.
2. Each of the possible solutions is (tested and) evaluated and assigned a fitness value based on a predefined fitness function. The fitness function is used to determine the ‘goodness’ of a solution.
3. A number of individuals are selected to be parents based on their fitness value. The 'genes' of the parents are recombined through cross-over and mutation to yield children. The population of these children is the new generation that is (tested and) evaluated.
4. This process is repeated iteratively until some predefined fitness value is achieved, otherwise, if it doesn't reach this value, the process is halted at a predefined number of generations.

Selection mechanisms

After fitness values are assigned to the individuals (the possible solutions), some of them are selected to reproduce. This selection process can be conducted through several mechanisms. Here, we discuss the most frequently used.

- In, Roulette wheel selection, the chance for an individual to reproduce is proportional to its normalized fitness value. (To be normalized here means that the total of all fitness values adds to 1.) It is therefore also known as proportional selection. The analogy with an roulette wheel is as follows: spin a roulette wheel and choose the individual where the wheel stops. The better ones have greater chance, since their piece of the wheel is larger.
- In rank selection, the propability of individuals being selected for reproduction is based on their rank in the relative fitness, rather than their actual fitness.
- When tournament selection is used, two or more individuals are randomly chosen and compared with each other. The one that 'wins the tournament' with its fitness value is selected for reproduction.

There are some extra options that are often applied to selection processes. One of these is elitism, meaning that the best individuals are automatically copied to the next generation (without recombination!).
Finally, there is a distinction between generational and steady-state selection. The former produces an entirely new population each evolutionary cycle. The latter preserves most of the population, only replacing a small proportion of the population with new individuals, the offspring.

The operators: crossover and mutation

In step 3, we saw that the parents' genes are recombined to yield children that are slightly different from their parents. The operations that do this are cross-over and mutation, after their biological counterparts.

The crossover operation needs two genotypes (genetical strings). It cuts each string in two (or several) parts, leaving four parts. Then, it sticks one part A of the first string to part B of the other string, and the other way around, as shown in the figure below.

The two strings at the bottom are two children, although it is possible to yield just one child, or more than two by iteratively applying this process.
Crossover is designed to combine partial solutions into complete ones with high fitness. This leads to fast convergence while maintaining a good chance of reaching the global optimum.

Mutation makes only a small change in the genotype. The most frequently used version of mutation, is the so-called 'bitflip' (shown below). In this process, a '1' in th genotype is changed into a '0'. Although this a relatively small random change, this can lead to major changes in the phenotype (or actual solution)!

It is important to note that although mutation is relatively small random change, it can lead to major changes in the phenotype (the actual solution)!

Evolutionary robotics

Before turning to the final essential ingredient of EC, the fitness function, here we look at the application of EC to autonomous robotics.
Autonomous robots are mobile robots with several sensors (e.g. sonar, IR, camera, etc.), and some motor devices (e.g. wheels). These robots are designed to be able to move around in a real-world environment (e.g. an office) autonomously, i.e. without human intervention. The controller of the robot (its 'brain') must therefore be able to somehow convert sensor readings into motor commands.

The design of such controllers is a very difficult task. This is mainly because their behaviour is an emergent property if the of their interaction with the environment. Movements of the robot imply difrferent sensor readings, which in turn influence the movements. The robot and its environment can be described as a dynamical system because the sensory state of the robot at any given time is a function of both the environment and of the robots previous movements.

To allow robots to exhibit some level of flexibility in their behaviour (like animals), research in autonomous robotics have turned to adaptive neural networks to serve as controllers. These networks have to be trained. For this, their are several possibilities. A very interesting one, from both an engineering perspective and a biological perspective, is to apply EC to neural robot controllers. This is known as evolutionary robotics (ER).

The basic idea behind ER is simple. Again, an initial population of genotypes is randomly generated, but now each genotype codes for a robot controller. Each controller is tested on a robot and its performance evaluated (according to the fitness function). Selection, crossover and mutation together make up the new population (exactly as described above). This population is thus a new collection of neural robot controllers.

The evolutionary cycle (shown in the figure above) halts when the resulting behaviour of an individual meets a desired fitness. Typical tasks that are evolved in this fashion are collision avoidance, moving towards a point, and navigating through a maze.

Note that ER combines several techniques that resemble behaviour in natural creatures. First of all, these systems are embodied: it is a physical system subject to physical forces such as gravity, friction, inertia, etc. Second, they are situated: they are embedded in a world, and each of the robots' movement changes its own sensory perspective on the world. In other words, there is a sensorymotor loop. Third, these systems are (typically) controlled by neural networks, inspired upon the neural control systems of animals. Fourth, these systems are subject to artificial evolution.

Fitness functions

An important part of the standard exogenous reproduction methods in EC remains undiscussed: the fitness function. The result and dynamics of an evolutionary run depends highly on the form and contents of this function, since this function evaluates the performance of individuals, upon which the selection mechanism operates, that in turn determines the genetical (solution) pool that enables evolutionary innovation.
In the case of EC, evaluation of the individuals it is often conducted directly upon the possible solution. In ER, however, evaluation is done on the basis of the performance of the robot with a controller that is specified in the genotype.

Fitness functions for evolutionary robotics consist of several components, variables and constraints, that rate the performance with respect to the desired behaviour. These are difficult to choose, however, since the behaviour of the evolved by the robot is not known in advance. Indeed, one can say that the degree of knowledge one has about the structure of the desired behaviour is reserve proportional with the need for artificial evolution.
One problem that one has to taken into account in particular is that if the researcher set the constraint too strong, individuals in the initial generation may receive fitness values near zero, and hence, evolution cannot 'take off'. This is known as the bootstrap problem.

Fitness space

Fitness functions play a major role in the evolvability of a system and is thus of major importance in standard evolutionary runs.
The figure above represents the fitness space (Floreano, Nolfi, 2000) that can be used to describe and compare fitness functions. In this fitness space, a fitness function scores high along the following dimensions, if...

Functional - Behavioural: ... it rewards an individual based on its performance, rather than on internal functional modes.

External - Internal: ... variables in the fitness function are based on parameters that are available to the robot itself.

Explicit - Implicit: ... it has little (or no) components.

The sphere in the upper-right corner indicates the goal of adaptive self-organisation. In this area, robots are rewarded only on the basis of their actual performance (behaviour), all the components in the fitness function are available to the control system of the robot, and the fitness function consists of very little components.

Note that the latter dimension is has decicive impact. If the fitness function is ultimately implicit, i.e. it has no components, the other two dimensions are in fact useless.

The quest for open-ended evolution

Now, we are in a position to appreciate the open-ended nature of evolution. Natural evolution is ultimately implicit. Fitness functions with no components are used, or rather, no fitness functions are used. Evolution is thus not guided towards optimizing some parameters.

This kind of evolutionary system, as observed in nature, has the power to conitnue to create novel individuals or, as is sometimes said, individuals of increasing complexity.
How, for example, can a simple process of imperfect (recombinatory) reproduction produce wonderfully complex systems as human brains out of mere single cell organisms? This is a fascinating question, and still very little is understood about this capacity of natural evolution, although the process itself is rather well-understood. In the field of artificial life, being a cooperation of biologists, complexity theorists and computer scientists, these kind of questions are examined.

Some measurements are proposed (Bedau et al., 1998) to analyse a system's open-ended capabilities. These measurements classify a system into three classes: adaptive evolutionary activity is (class 1) absent , (class 2) bounded, or (class 3) unbounded.
These classes are defined using three statistics: diversity, new evolutionary activity, and mean cumulative evolutionary activity. These statistics are compared with a 'shadow' sun of the system, in which random-selection is used.
This classification method is however still being challenged, and does not seem to be fullproof. It has been indicated that some simulations exhibit class 3 adaptive evolutionary activity, without generating novel types of individuals (let alone of increasing complexity).

Artificial Life simulations

In artificial life, computer simulations are constructed and used to learn about the open-ended capacities of evolution. Below are some well-known examples of such simulations. Each of these are designed to model at a different level of complexity (genes, individuals, social).

Commonly regarded as the first artificial system that exhibited open-ended evolution, is Tierra, by biologist Thomas Ray. The Tierra simulator explores what happens when evolution by natural selection is embedded in the medium of digital computation. Pieces of software compete with each other for CPU time ("energy") and memory ("material resources").
An interesting feature that was observed in Tierra was the emergence of 'parasite' programs that had no reproductiver capacity themselves, but 'parasited' on the reproductive powers of their hosts.
A drawback of Tierra, as a comparative tool for natural evolution, is that its individuals are reproductive pieces of software in a digital abstract environment, not in the least bit like a natural environoment.

Echo is an agent-based simulation tool developed by John Holland to investigate mechanisms which regulate diversity and information-processing in systems comprised of many interacting adaptive agents, or complex adaptive systems (CAS). Echo agents interact via combat, trade and mating and develop strategies to ensure survival in resource-limited environments.
This simulation is a bit more realistic, since its individuals are agents in a (2D) space. Thus, the agents have to move to collect food and mates. However, the environment, as well as the agents, remain abstract entities.

PolyWorld is an artificial life simulator developed by Larry Yeager. It simulates a realistic 3D world in which simulated creatures move around and reproduce sexually, eat food that the world provides, fight, and die. PolyWorld is created to study the emergence/evolution of social behaviour. Flocking and foraging were among the behaviour that emerged.
Although the environment is a simulated physical 3D world, the individuals are in fact agents, in the sense that the individuals have a limited number of predefined behaviours, and an unarticulated body. This is done, because Yeager is primarily interested in the social level of complexity. He is not concerned about how these behaviours are implemented of evolved within the individuals of the population. (And perhaps because the computational power of the computer available to him in 1992 didn't facilitate the simulation of large populations of articulated creatures.)

Endogenous reproduction

All these simulations have something in common. The evolutionary cycle is different from the one used in standard evolutionary computation, as described above. That is, there is no fitness function (or a function with no components). Therefore, there can be no selection mechanism, because there are no fitness values upon which a selection mechanism can select some individuals to reproduce. In other words, reproduction is not exogenous, controlled from outside, but reproduction is endogenous, from inside the individuals.

This requires a view from the individuals. Initially, individuals are created and have a certain energy level. The individuals must collect energy (food) to survive, because every movement costs some amount of energy. When the energy level is (below) zero, the individual dies.
Individuals are able to reproduce (sometimes sexually) when some amount of energy is achieved, or when two individuals are spacially close, or collide.

If an individual is unable to reproduce, because it dies before it has the chance to, or is preoccupied with finding food, it leaves no offspring. Only the genetical material of the individuals that leave offspring, remain in the genepool. It is that simple.

A consequence of this endogenous method is that there have to be groups of individuals in the environment (if reproduction is sexual). Although sometimes steady-state selection is used (to keep a certain amount of individuals in the population), most frequently the population levels are free to allow overcrowding and extinction.
Overcrowding introduces competitiveness if there are a limited food and sexual resources. And (virtual) extinction introduces strong selective power.

The possibilities of simulating natural forces is almost unlimited. One can allow speciation, one can introduce (or evolve) predators or parasites, and even foodchains.

However, endogenous evolution by no means garantees open-ended evolution. As noted before, the requirements for open-endedness are still to be examined.

Framsticks

As an follow-up study of the simulations described above, we propose the 'Virtual Life' project. In this project, we use the Framsticks simulator (Komosinski, Ulatowski, 1997-present).
Framsticks is a versatile artificial life simulator which facilitates standard optimization evolution and 'spontaneous' evolution (akin to endogenous reproduction) of both control system and morphology. In Framsticks, articulated creatures inhabit a simulated physical environment. The creatures consist of several sticks and joints, in potentially all different configurations. The creatures are controlled by neural controllers, consisting of receptor (smell, touch, equilibrium), interneurons (sigmoid, fuzzy, etc.), and motor neurons (rotation and strech). Creatures can be predefined and/or evolved.
The environment can be flat, a block world, or a height field (as shown below). It contains physical charateristics for land and water, such as friction, gravity, inertia, etc.
Framsticks also allows user and developers to define their own experiment definitions.

We have built experiment definitions into Framsticks that allows endogenous sexual reproduction, either from a single atomic structure (one empty stick) or from predefined creatures. It also allows many different co-evolving populations (and thus genepools).

We use Framsticks, extended with the 'Virtual Life' endogenous reproduction scheme, to study the emergence of simple social behaviour (as in PolyWorld), with a focus on the control system of individuals (unlike PolyWorld).

Conclusion

This paper describes standard evolutionary computation and endogenous evolution. The goal of analysing through synthetizing the self-organising and open-endedness of natural evolution, is being approaches by simulation in artificial life. One requirement is the endogenous nature of reproduction, in contrast with exogenous reproduction in standard evolutionary computation.
We propose the 'Virtual Life' platform, built on the Framsticks simulator to study the emergence/evolution of basic social behaviour, with a focus on the control system of individuals.