Foreword

In February 2003 I published an article Getting Darwinian Evolution to Work [1] suggesting that a hierarchical or 'layered' evolution process would be effective for the Darwinian evolution of computer software. In that article a hierarchical, 'interpretative' system was suggested, but I mentioned that an alternative system - a 'compilative' one - could be more efficient and that a later article would explore this.

This article will discuss the idea of a 'compilative' architecture in hierarchical evolution. Some concepts from the first article will be used. To avoid making it absolutely necessary to read the first article, some parts of it will be repeated here, so that this article can be read by itself; however any readers who are particularly interested in the concept may wish to read the first article at http://www.paul-almond.com/GettingDarwinianEvolutionToWork.htm.

Introduction

This article suggests that current methods of implementing Darwinian evolution on computers have severe limitations and proposes improvements to the way in which it is done.

It is suggested that the 'evolvability' associated with data that has some meaning is a characteristic of the particular interpretation which gives that data its meaning so that evolvability is mainly a characteristic of the interpretation rather than the data: some interpretations will lead to high evolvability and useful progress by evolution algorithms while others will lead to low evolvability with little useful progress.

In a previous article the idea of a hierarchical system of machines was used, each layer in this system acting as an interpreter for the next layer by controlling its state transitions. It was proposed that each layer of software should be evolved successively to produce an interpreter with high 'evolvability' and that the utility of the particular data on a given layer should be evaluated, following mutation in an evolutionary process, by assessing the degree of progress observed in a large number of secondary evolution processes, each of which uses a different evaluation function, performed on the data in a next layer machine.

The method proposed in the first article involved evolving each layer to act as an interpreter for the layer above it. It is expected that the degree of sophistication with which each layer does this will increase as more layers are added, as the evolution process that generates each layer 'benefits' from the evolvability that has already been attained in lower layers.

This article will propose a 'compilative', hierarchical method that is equivalent to this and that will achieve the same outcome with greater efficiency.

Problems with Existing Genetic Methods

As my previous article stated, existing genetic algorithm techniques have not generated software of substantial complexity.

It seems intuitively apparent to me that mutating symbols in a computer program is unlikely to result in a complex system in any reasonable time; however, it seems that mutation of the ACTG symbols in biological genetic codes can lead to evolution of complex systems. Why is there this difference between our computer systems and biological systems?

I suggest that the main issue here is one of interpretation. Any data that is mutated is effectively a sequence of symbols that is subjected to interpretation. In the case of a high level computer program the symbols are the computer program and it is subject to interpretation by the rules of the computer language being used (provided by a language interpreter or compiler). In the case of DNA the sequence of As, Cs, Ts and Gs is interpreted by the underlying biochemistry which provides a 'machine architecture'.

The underlying architecture is needed to provide the sequence of symbols that is being mutated with its meaning. As an example, the sequence of symbols in the DNA that codes for construction of an organism only encodes for an organism when interpreted by the underlying biochemistry: without this it is just an arbitrary sequence of symbols.

I now make this suggestion:

The likelihood of a mutation on a sequence of symbols having a positive effect is determined by:

• The current complexity of the system described by the sequence of symbols.
• The architecture that is interpreting the sequence of symbols.

I suggest that this makes the interpretative architecture the most important influence on how quickly evolution of a sequence of symbols can progress and that most architectures devised by humans will only give any useful rate of evolution for systems of quite low complexity, the evolution process effectively grinding to a halt when a certain level of complexity is reached. (See figure 1)

We could perhaps imagine an interpretative architecture designed to allow rapid evolution of the sequence of symbols that it interprets, but it is difficult to imagine actually designing such a thing.

Evolution in biological systems, however, seems to produce complex systems. How does it do this? I suggest that the answer lies in the biochemistry that interprets the DNA: it must be a particular interpretative architecture that allows evolvability.

If we need an interpretative architecture that allows evolvability of the data that it interprets then we seem to have a problem here - how does such an interpretative architecture get there in the first place? Clearly, it must have evolved. This may seem to be a paradox: how can we have an interpretative architecture that allows evolvability to evolve when we need it in the first place to allow evolution?

I suggest that the answer is that evolution is not a process that is totally allowed or prohibited by the interpretative architecture, but instead that different architectures allow different degrees of evolution and that the architecture effectively imposes an upper limit on the complexity of the systems that can be evolved with it. The interpretative architecture in biochemistry is less complex than some of the systems that use it to evolve, so can actually evolve within the context of a cruder interpretative architecture that does not allow as much evolvability.

Here is what I think has happened in biological evolution:

A multi-layered system of interpretative architectures has evolved.

The bottom level of this system is the basic laws of physics. At the start there is nothing to do the interpreting except the laws of physics. Systems evolve that are interpreted by these laws. The laws of physics have not been designed with evolvability in mind and the process of evolution is extremely slow with an effective upper limit on the sophistication of the systems that it can produce in any reasonable time.

This is inadequate for producing anything like complex animals or even bacteria, but this is not what evolves. Although complex systems are not available, what can evolve is a second layer of interpretative architecture that is slightly better at allowing evolution to occur with the data that it interprets than the laws of physics. Evolution of data that is interpreted by this second layer now proceeds more rapidly and has a higher upper limit on complexity than is allowed by evolution within the context of the basic laws of physics. It still does not have a very rapid rate of evolution or a very high upper limit on complexity because limits were imposed by the context of the laws of physics in which it evolved, but it does not have to be very good. All it needs to be is better for evolution than the laws of physics. It can now be used to evolve a third layer of interpretation that is too complex to have evolved within the context of the laws of physics. This third layer of interpretation can now be used to evolve a fourth layer of interpretation that is too complex to have evolved within the context of the laws of physics or the second interpretative layer.

This process continues, with successive layers of interpretative architecture evolving. Each time a new interpretative layer is added the rate of evolution and the upper limit on complexity both increase. The evolution process itself is evolving and highly complex organisms can ultimately be produced.

We need to use a process like this to evolve sophisticated computer software. The method that was previously proposed used a layered architecture very similar to what has just been described. A 'compilative' method of achieving the same result will be presented, but first we will look at why we need it.

The Need for a Compilative Method

If we used a layered process as described above then each layer would serve as an interpreter for the next layer and would be used to provide the interpretation for the evolution of this layer. This is the approach that was proposed in the previous article. A disadvantage of this sort of method is that as the number of layers increases, each layer having to interpret the layer beneath it, the amount of processing needed to support the final layer also increases, potentially causing a lot of inefficiency.

This method would involve a lot of secondary evolution processes and if each one is running inefficiently substantial computing resources and/or time will be required. This problem can be addressed by using a compilative method.

The Basic Idea of a Compilative Method

With a compilative method we will use the idea of layers as described above, but the building of a new layer will involve the construction of a new compiler which will stay close to the fundamental machine language.

One way of thinking of this is that the compiler used for each 'layer' will imply all the previous layers in its construction, but none of these layers will be explicitly required to support the compiled code that it produces, allowing us to have the benefits of a hierarchical system without the inefficiencies.

The idea is that we produce some simple language compiler and use it to evolve a next generation compiler. We start with a number of random programs, each of which can be input into the compiler and used to obtain 'compiled' code. For each of these programs we run a large number of secondary evolution experiments, each with a different fitness function, to determine how quickly evolution tends to proceed when we use the new program as the compiler We use the programs that seem to allow the fastest evolution as the next generation of compilers and discard the others. We then repeat the process: the 'next layer' of compilers is now available and is used to do the compiling in experiments to evolve a later generation of compilers to replace it, each new compiler being tested according to how quickly evolution occurs when it provides the language.

The above description makes no mention of anything analogous to sexual combination of genetic information. A real process would be very likely to use this, but this article is about the hierarchical aspects of a possible method, rather than its sexual aspects so it will ignore the role of sexual combination.

Machine Architecture for a Compilative, Layered Evolution Method

A system to implement a compilative method would require the following components:

Fundamental language - this is the most basic language used in the system and would be a low level language. It need not necessarily resemble any common type of machine code - in fact, it is likely to be more basic than this. It could be the rules for a very basic universal Turing machine.

Symbol array - an array of symbols similar to a Turing machine tape. The array is a one dimensional list of symbols. Each symbol can be considered to be a value from 0 to n, where the value of n is dependent on the design. A symbol array has no implicit meaning: this is dependent on what interprets it. As an example, a symbol array could be regarded as the instruction tape for a Turing machine, but this would only be relevant when a Turing machine interpreted it.

Fundamental interpreter - a device used to interpret a symbol array according to the rules of the fundamental language. The array of symbols is regarded as a computer program expressed in the fundamental language and an output is produced.

Symbol machine - the main computational device used. It is controlled by the command array in a fundamental interpreter, accepts an input array as an input and produces an output array.

Command array - this is a symbol array which is interpreted by the fundamental interpreter and regarded as a low level program in the fundamental language. The command array controls a symbol machine in the same way that a CPU (central processing unit) microchip controls a conventional computer. The command array tells the symbol machine what output to make.

Input array - a symbol array that acts as an input to a symbol machine. The input array provides the input on which the command array acts.

Output array - a symbol array which is produced as a symbol machine's output.

It should be apparent that this sort of architecture corresponds to what we generally understand computers to do in a very basic way. To summarise what is going on:

A symbol machine is a computer. It contains a fundamental interpreter which is responsible for controlling the symbol machine's state transitions and is analogous to the CPU of a conventional computer. The fundamental interpreter contains the command array, which is a symbol array and provides the software that performs the compilation. This software is run by the fundamental interpreter according to the rules of the fundamental language. The fundamental interpreter accepts an input array - a symbol array - which is input into the symbol machine and produces the output array - another symbol array - as output. (See figure 2)

Use of the Machine Architecture as a Compiler Machine

The architecture just described will be used a compiler machine in a way analogous with the way that conventional compilers, such as those for high level languages such as Pascal or Visual BASIC, are used. For the architecture to be used in this way, each component of the architecture described above will be analogous to part of a compilation system as follows:

The fundamental language is analogous with the low level machine language into which compilation is performed.

The fundamental interpreter is analogous with the CPU (central processing unit) of the computer running the compiler program. Its purpose is to interpret the code that makes up the compiler.

The symbol machine is analogous with a computer running the compiler software.

The command array is analogous with the compilation software - the compiler program itself.

The input array is analogous with the high level source code that is input into a conventional compiler to be compiled.

The output array is analogous with the compiled, low level, machine code program output from a compiler as the 'compiled' or 'executable' version of the high level source program.

To summarise what is going on here:

The symbol machine acts as a compiler. It accepts the input array, which is a symbol array, as the high level source code. The command array - another symbol array - tells the symbol machine how to compile the program represented by the input array: it is the compiler's 'software'. The command array symbols are given their meaning by the fundamental interpreter which 'runs' the compilation program embodied by it according to the rules of the fundamental language. The fundamental interpreter produces the output array - a symbol array - which is a compiler version of the computer program in the input array and is intended to be operated on as low level, executable code by the fundamental language of the interpreter. (See figure 3)

Is there anything special about compiler machines?

It should be noted that the use of a symbol machine as a compiler does not involve modifying it. Any use of a symbol machine could be regarded as compilation, should we choose to interpret it that way.

What makes a symbol machine a compiler machine is our intent when we start it running. The input array provided to a symbol machine is not particularly special when the machine is being used as a compiler: all that makes it different is our intention that the symbols in the array represent a high level, source code program. Likewise, there is nothing special about the output array produced by a compiler machine when compared with the output arrays produced by symbol machines in general. The output array can be used as executable code and operated on by a fundamental interpreter, just like the command array in the compiler, but this can be said of any output array or, in fact, any symbol array. What makes the output from a compiler machine different is our intention to use it as executable code.

How a Hierarchical Evolution Method Will Work with a Compiler Machine

We will now look at how these components will be used to run a hierarchical evolution process. The process would be as follows:

Step 1: We start with a number (p) of compiler machines. Each compiler machine contains a fundamental interpreter with a random command array so that we have a pool of randomly created compilers.

Step 2: We create a large number of copies of the compiler machines in the pool. Each compiler machine is a mutated copy of one of the compiler machines in the pool, meaning that it is a copy of one of the compiler machines in the pool, except that a random change has been made to its command array.

Step 3: Each compiler machine in the pool is tested by running a large number of secondary evolution experiments. Each secondary evolution experiment returns an evolvability score and the fitness function of the compiler is taken as being the average of these results. Each secondary evolution experiment involves its own secondary fitness function - a large number of secondary fitness functions is required - and is as follows:

Step 4: After Step 3 we will have a large number of compiler machines, each with an average score resulting from many tests of the evolvability that that compiler provided in evolution experiments with different fitness functions. These compiler machines will now be used to replace the collection of p compiler machines in the pool. Out of the compiler machines that have just been tested, the p compiler machines which have the highest evolvability scores will become the new pool of compilers. We will now go to Step 2 for the next iteration of the main evolution process.

Using the Process

Each time the evolution process iterates a new generation of compilers is produced. The fitness function for each compiler involves testing its suitability for use in providing the language in which programs are expressed when they are going to subjected to Darwinian evolution. For this reason, the evolvability provided by compilers is expected to gradually increase.

The process would not be continued forever, of course: all that would give us is compilers that are never put to any use apart from the evolution of better compilers. In reality the process would be performed until it was considered that a compiler was available that provided adequate evolvability for the sophistication that was required. This compiler would then be used to enable the evolution of a program serving some more immediate practical purpose. This could actually be done many times, so that once a suitable compiler is considered to exist, it could be used to evolve a very large number of programs for different purposes. This could be used as a justification to support the potentially high costs of the computational resources needed to produce compilers that offer a high level of evolvability.

Positive Feedback

The big issue that this is supposed to address is scalability; that is to say, getting the process to work for situations involving substantial complexity, rather than merely evolving simple behaviour. There is an element of positive feedback that assists in this. Each generation of compilers should be more suitable for use in evolution of software - in the sense that it provides more evolvability - than its predecessors. As compilers improve the evolution process becomes faster and capable of generating greater sophistication, but this higher evolvability will be used to make better compilers: the process increases the effect that is driving it and the intention is to use this to try to cause a 'runaway' evolution process which will generate significant complexity.

The key idea here is one of taking manageable steps that put sophisticated systems within range. The first compilers will not provide sufficient evolvability for the production of very sophisticated systems, but they will allow the evolution of more sophisticated compilers which provide more evolvability. The higher evolvability provided by these compilers can be used to evolve more sophisticated compilers, which provide still higher evolvability, that were out of the range of the first generation of compilers. In this way, through a series of stages, high evolvability and sophistication can be accessed.

How a Compiler Machine May Work

A compiler machine, as described here, has to work like a Turing machine. There is, however, the added complication that the fundamental interpreter seems to have to process three instruction tapes (the command array, input array, and output array) at once, so some readers may wonder how this could be done.

There is not much of a problem and various methods are possible: one simple solution could involve the fundamental language effectively being a Turing machine with three different read/write heads. The instruction table would then state what symbols should be placed on each of the three tapes and how the read/write heads should move for every possible permutation of symbols under the read/write heads. This could be a bit unwieldy as it would require the fundamental language to have a very large Turing machine instruction table.

Another approach would be to combine the tapes. The 'tape' containing the command array would have the input array inserted after the command array symbols and another region of the tape would be used for writing of the output array so that it could be read off the tape when the Turing machine halted.

Further approaches could rely on the idea that it is not, strictly speaking, necessary to actually read any data from the output tape, but simply to output it. As an example, the command array and input array could be combined to form a single Turing machine tape and each entry in the Turing machine instruction table could specify outputs of symbols that are to be made, as well as the usual symbol manipulations and read/write head movements that Turing machine instruction tables specify. When the Turing machine halted all the outputs that were made could be taken in sequence as describing the output array.

One issue that may be worth considering is whether or not the Turing machine should be required to halt to complete its creation of the output array. The Turing machines being used here are the product of evolution rather than human design and may behave erratically. It is possible that some may halt when, if they had been allowed to continue processing, they would have continued to output useful data, or that that others may create useful output arrays but never halt, so that these output arrays are never regarded as valid data. It could be that requiring the Turing machine to halt is too 'tight' as a requirement and that some other method of determining the end of processing is more appropriate.

Another issue could be that the system, as described, is better for solving problems which require an output to be produced only once in response to input. This is suitable for allowing the symbol machine system to be used in compilers, but it could present complications if we want to use the system to produce software that continually accepts inputs and gives outputs in real-time situations. One solution, already known to neural network designers, would be to continuously feed part of the system's output back in as input data, effectively making some of the output a memory. Other solutions could involve changes to the way in which the symbol machine works.

Discussion of these issues could be lengthy: however, this article is merely an argument to establish the idea in principle and such technical considerations could come later.

Possible Improvements

This article has focused on compilers that behave like Turing machines and which produce compiled code that can be regarded as Turing machine instruction tapes. This approach was used because it is easy to understand, but the Turing machine paradigm may not be the best. Although, technically, any system that could be used as a compiler would have to be equivalent to a Turing machine, it may be that various systems that resemble the Turing machine architecture less explicitly, and that may provide more robustness, could be more useful. Detailed consideration of such ideas is beyond the scope of this article, but ideas could include:

• using neural networks as compilers. The pattern of neural network connection strengths would be equivalent to the command array and the system would accept inputs into the neural network that would be equivalent to the input array (or high level source code). The network would output symbols that could be used to describe the connection strengths in another network, thereby allowing the neural network to produce another neural network and be usable as a compiler.
• using cellular automata in a similar sort of way.

Conclusion

As with my previous article, this article has made a case that hierarchical evolution will be much more efficient than non-hierarchical evolution. Some sort of 'layering' is involved in which each 'layer' is used to determine the interpretation of the data that will be evolved to produce the next layer. The previous article suggested an approach in which the layers existed explicitly and simultaneously as sequences of symbols, each layer interpreting the next higher layer. This article has suggested an alternative approach in which layers build (or compile) each other rather than interpret each other and that this is equivalent to the system proposed in the previous article, except that it is more efficient.

References

[1] Almond, P. (2003). Getting Darwinian Evolution to Work. Retrieved on 31 October 2004 from http://www.paul-almond.com/GettingDarwinianEvolutionToWork.htm.