Figure 2.1: An evolutionary system. Entities evolve through a process of variation acting upon their representation.
Evolution is a process that leads to change. In particular domains, the term evolution is used to refer to specific processes of change. In the study of social development, for instance, evolution is used to describe the development of societies. In mathematics, evolution is an iterative process which finds the root of a number. Stellar evolution, in astronomy, is the process of star formation. Software evolution, in software engineering, is the change in functionality over the lifetime of a software system. Biological evolution is the change in genetic constitution of a population of organisms over time.
Even in Darwin's era, there was nothing new about the idea of evolution. Evolution has been acting, and could easily be seen to be acting, in myriad systems since the dawn of history. The thing that shocked Victorian people was the idea that biological populations, too, were subject to evolution and therefore not entirely shaped by the will of God - or, to take the `theory of evolution' [Darwin, 1859] to its ultimate conclusion, formed entirely by a process of selection acting upon essentially random variation.
This chapter has several objectives. First, to introduce the properties of a range of example evolutionary systems. Second, to present commonalities that exist between the properties of these systems and establish a general view of evolutionary systems. Third, to develop a standard taxonomy and terminology of evolutionary systems.
Above all, the aim of this chapter is to demonstrate that it is possible to introduce the key concepts of evolution without having to talk about biological evolution: and, in this way, show that ideas concerning evolution have relevance to a broader range of domains than biology alone.
The simplest evolutionary systems consist of a single entity undergoing change. A good example is a geographical landscape. In an abstract sense, a geographical landscape is a three-dimensional shape. This shape was formed, or evolved, by natural processes such as rain, wind, frost and earthquakes introducing change within the conformation of the rocks that make up the landscape. In essence, the eventual shape was decided by the action of these natural processes of variation upon the properties of the constituent rocks: a product of both the kind of change introduced by the natural processes and the kind of change permitted by the rocks. Different rocks react to natural processes in different ways and, consequently, lead to different landscapes. For instance, chalk can be dissolved by water, sand is easily shaped by wind, and certain rocks (such as granite) are particularly prone to frost shattering.
This example illustrates the three basic elements of an evolutionary system - the entity being evolved, its representation, and the mechanisms of variation. In this case, the entity is the shape of a geographical landscape, the representation is the constituent rocks, and the mechanisms of variation are natural environmental processes. It also illustrates how the evolutionary change of an entity is a result of the mechanisms of variation acting upon its representation, a pattern which is illustrated in figure 2.1.
Figure 2.1: An evolutionary system. Entities evolve through a process of variation acting upon their representation.
Another example of this pattern is software evolution [Lehman and Parr, 1976]. Here, the entity being evolved is a software system. Its representation is the way in which the software is implemented - for example: the granularity of the language it is written in, its internal structure of decomposition, its choice of data structures and algorithms. The mechanism of variation is the programmer or programmers responsible for maintaining and updating the code. Again, it is the action of the mechanism of variation (the programmers) upon the representation (the implementation) that decides how the software system evolves.
However, this example has a significant difference to the previous example: evolution is directed. In geographical landscapes, evolution is the consequence of rocks annealing to environmental processes. There is no external pressure for the system to evolve in any particular direction. In software systems, on the other hand, evolution in the direction of increased functionality is the objective of the programmers who modify the implementation. Consequently, programmers introduce variation that they believe will increase the functionality of the software system. This directed variation leads to directed evolution.
Evolvability [Conrad, 1990,Kirschner and Gerhart, 1998,Nehaniv, 2003] is a measure of an evolutionary system's ability to evolve in an appropriate direction. To re-iterate a point made earlier, the evolution of an entity is a consequence of the mechanisms of variation inducing change within the entity's representation: a result of both the mechanisms of variation's ability to express change and the representation's ability to accept change. Accordingly, the evolvability of an evolutionary system is a function of both the evolvability accorded by the entity's representation and the evolvability accorded by the mechanisms of variation.
In the context of the software evolution example, this entails that the degree to which the evolution of a software system can be directed is a function of not only the programmers' ability to conduct appropriate change but also the implementation's capacity to accept appropriate change. This is not to say that any programmer could not make an appropriate change to the functionality of any existing software system given enough time and energy, but rather that certain approaches to implementation (those which accord greater evolvability) accept these changes more easily than others and that certain forms of code maintenance (those which accord greater evolvability) generate these changes more easily than others.
In this example, the evolvability accorded by an implementation could be measured by the number of lines of code which have to be added or changed in order to produce the desired functionality. An implementation accords evolvability if it is designed in such a way that a minor change in functionality can be achieved with a minor change in its code. An implementation does not accord evolvability if a minor change in functionality can only be achieved through a major re-write of its code. This principle is widely recognised within software engineering where programmers are encouraged to write code in such a way that functionality can be adapted with minimal code change. Mechanisms to achieve this include abstraction, which achieves robustness through functional redundancy; modularisation, which limits the propagation of code changes; and re-use, which removes the need to duplicate changes.
An interesting property of software systems (which is also true of biological systems) is that these architectural mechanisms are recorded within the code of the implementation alongside the code which implements the software's functionality. Consequently, when programmers modify code they are targeting both functional and architectural components of the representation. Therefore, for programmers who maintain software to do so in a way that accords evolvability, they must make appropriate changes to both functional and architectural components of the representation. Again (although to a lesser degree) this principle is recognised within software engineering and programmers are encouraged to modify code in a way that both implements the required changes in functionality and preserves, or improves, the evolvability accorded by the implementation. Mechanisms such as code re-factoring exist to help programmers achieve this.
When talking about evolution, it is often useful to visualise the evolutionary process as movement within an abstract space of all possible conformations of the evolving entity or its representation. It is also conventional, though not always appropriate, to organise these spaces so that neighbouring points represent entities that differ by an amount equivalent to the change introduced by a single variation event; although since there are often multiple sources of variation, this is usually only meaningful if a separate space is envisaged for each source of variation. Nevertheless, such spaces are useful for measuring the evolvability of an evolutionary system since, by measuring the distance between the locations of different entities, it can be seen how much effort will be required to evolve one entity into another.
Within some evolutionary systems it is convenient to assign values of worth to each possible conformation of an evolving entity. For example, within a software system undergoing evolution, each possible version of the software can be given a value that reflects how likely it is to sell within the software marketplace. For such evolutionary systems it is useful to extend the notion of evolutionary space by giving each point a value which reflects its worth: in effect, adding another dimension. Since points close together within the evolutionary space refer to similar entities with typically similar values of worth, this augmented space tends to have what looks like a continuous hyper-surface in the value dimension with peaks in regions of high value entities and valleys in regions of low value entities. In analogy to this appearance, these spaces are often referred to as landscapes [Conrad, 1979,Jones, 1995].
Evolution is often described as a search process. Nevertheless, for most evolutionary systems evolution does not lead to behaviours which would be normally be thought of as search (although you could describe evolution as searching for the natural biases caused by an entity's representation and mechanisms of variation). However, certain evolutionary systems do carry out search behaviours and often this search can be described as directed movement within an evolutionary landscape: moving from a location corresponding to a low valued solution to a location corresponding to a high valued solution.
Sometimes when the representation of an entity experiences variation, the entity itself does not change. This is called neutral evolution [Kimura, 1983]. It occurs when there is a one-to-many mapping between entity and representation: such that a single entity can be described by many representations. Neutral evolution is the result of variation switching between members of this set of equivalent representations.
Returning to the real-world example of a software system, a typical neutral evolution event would involve turning a piece of code into a function and replacing its original occurrence with a call to this function, a technique called re-factoring. This structural change does not affect the functionality of the software and so, from an external perspective, the change appears neutral. This example also illustrates the potential benefit of neutral evolution. The structural change has not improved the functionality of the software but it has improved the evolvability accorded by the representation - since future code additions will be able to use this re-factored code with a single function call.
A sequence of neutral variation events constitutes a neutral walk [Huynen et al., 1996]. Within a directed evolutionary system, appropriate neutral walks can be very useful: taking the representation from a state of poor evolvability to a state of high evolvability, and giving the system access to future evolutionary paths which were not readily accessible using the original representation. Within evolutionary landscapes, areas of neutrality can be seen as plateaus and ravines connecting entities of equal value. Whilst this is a special case of neutrality (since entities of equal value aren't necessarily equal in other respects) it allows visualisation of potential neutral walks within the landscape and, in particular, can indicate which neutral walks lead from low-lying areas (containing solutions of low value) to areas of more mountainous terrain (containing solutions of high value).
Figure 2.2: Evolution of a group of entities. Groups evolve as processes of variation act upon their entities.
Consider a group of evolving entities. Over the course of time, the entities within the group evolve. This may cause the collective properties of the group to change: causing, in effect, an evolutionary process at the group level. This process of group evolution, shown in figure 2.2, obeys the same pattern as the evolution of individual entities (shown in figure 2.1) whereby evolution occurs as a consequence of mechanisms of variation acting upon a representation - but in this case, the representation is the entities that comprise the group.
As an example, consider a group of software systems, each of which has limited functionality. Over time, the developers of the software systems will modify their implementations in order to improve their functionality. Consequently, the level of functionality of the group will appear to evolve in a positive direction. If there is a tendency for developers to develop certain kinds of functionality, perhaps in response to market demands, then the type of functionality of the group will appear to evolve in a particular direction. If developers choose their objectives non-deterministically, then the functionality of the group will tend to become increasingly diverse. The evolution of these collective properties is a result of variation acting upon the entities within the group.
Exchange of information - or more generally, interaction - between members of a group can alter the dynamics of the group-level evolutionary process. This is of particular interest within groups undergoing directed evolution, where the direction (and speed) of evolution is highly dependent upon the nature of interaction between members of the group.
Co-operative evolution occurs when entities within a group share information about how to increase their value. Co-operation works via mechanisms of variation which attempt to identify valuable components of entities and copy these components into other entities. The effect of co-operative evolution is to improve the collective search capacity of the group above that of a group of non-interacting evolving entities. Figure 2.3 shows a simple example of co-operative evolution.
Figure 2.3: Evolving Teacups. Co-operative interactions during evolution.
Effective co-operative evolution depends upon a number of factors. One of these is the ability of variation mechanisms to identify which components of which entities are particularly valuable. Another is the ability of an entity's representation to accept components copied from other entities. Again, effective evolution depends upon both the mechanisms of variation's ability to express appropriate change and the ability of an entity's representation to accept appropriate change. For example, the co-operative evolution of a group of software systems depends both upon the programmers' ability to recognise which components of which software systems lead to useful functionality, and the capacity of the software systems' implementations to augment code copied from other software systems without requiring additional re-writing or re-structuring.
The complement of co-operative evolution is competitive evolution. In a group undergoing competitive evolution, entities only remain in the group if they are able to compete effectively against the other entities in the group. As a consequence, the average ability of entities to compete will tend to increase over time as those entities which compete poorly are removed. Competition may occur either as a result of competitive interactions within the group or as a result of some external selective mechanism. In a software marketplace, for example, competition between software systems is determined by customer preferences. Those which are preferred by customers will survive and continue to be evolved; those which are not preferred by customers may be discontinued and removed from the marketplace. Accordingly, the average quality of software systems will tend to increase over time.
Evolution is a process which leads to change within an entity or group of entities over a period of time. Evolution results from some process or processes of variation acting upon the representation of an entity or group of entities. Importantly, an entity can undergo a certain evolutionary change if and only if this change is possible as a result of processes of change acting upon the entity's representation. Evolvability is the capacity for an evolutionary system to evolve in a particular direction; and is determined by the nature of the entity, by the flexibility of the entity's representation, and by the ability of the variation operators to induce appropriate change. Directed evolution, which can lead to evolution carrying out a process of search, can be encouraged within groups of entities through both co-operative and competitive mechanisms.
The interest of the scientific and engineering communities in developing a unified view
of evolution is a recent phenomenon [Nehaniv, 2003]. Nevertheless, there is
considerable commonality between the evolutionary processes which occur in different
kinds of system: and a growing view that lessons learnt from one evolutionary domain
can be applied within other evolutionary domains. The issue of evolvability is
particularly relevant; since an understanding of evolvability is essential in
understanding how best to design and represent artefacts - such as software systems
and engineered products - which are subject to a process of change over time.
Evolvability is also of paramount importance within evolutionary computation systems.
In the past, the choices of representation within evolutionary computation have been
somewhat arbitrary from an evolvability perspective. Typically an evolutionary
computation practitioner will use the form of representation which is most natural or
most common for a given entity; without thinking about whether or not it is evolvable.
In part this is due to a lack of understanding regarding what is and what is not
evolvable. This thesis presents a biologically motivated approach to the development of
an evolvable representation for evolutionary computation: an approach motivated by the
relatively large amount of information concerning evolvability which may be mined from
biological systems. However, this is not the only approach, and it is conceivable that
other, perhaps equally fruitful approaches, could be developed by looking at how
evolution occurs in a much broader range of both natural and artificial systems.