W. B. Langdon
While software systems are almost universal, almost all can be characterised as both hand made and inflexible. A major cost to commerce and drain on human resources is the manual effort required to implement even apparently trivial changes. Thus software maintenance is expensive and time consuming, leading to application backlogs and user dissatisfaction. This proposal addresses both consumption of human resources and inflexibility of software systems by investigating the automatic production of computer programs that can learn, i.e. that can adapt.
There are a number of techniques that provide computers with limited adaptation. Some claim inspiration from physical or biological systems (Simulated Annealing, Neural Networks and evolutionary computation techniques such as Genetic Algorithms (GAs)). Indeed the application of GAs to variable length programs (genetic programming (GP)) enables computers to solve problems without being explicitly programmed.
While GP has demonstrated its potential by evolving programs for many applications, most of these programs contain code only and cannot themselves adapt to changing circumstances.
This project will demonstrate that it is feasible to automatically produce programs with simple learning abilities using evolutionary computation techniques. The experiments will seek to show that programs which learn knowledge can re-apply that knowledge in other circumstances. Finally we will show learnt knowledge as well as evolved code can be passed between generations by allowing parents in one generation to teach their offspring.
There are a number of optimisation or learning techniques inspired by natural evolution (Evolutionsstragies [Back et al. 1991,Back and Hoffmeister1994], Evolutionary Programming [Fogel1994] and Genetic Algorithms GAs [Holland1992,Mitchell1996]). GAs concentrate upon representing individuals within an evolving population by their genetic make up. The genes of new individuals are inherited from the ``fitter'' individuals in the population. GAs introduce variation principly by making random changes to the chromosomes (mutations) and sexually combining genetic material from two parents. (Other genetic operations, e.g. inversion, may also be used). GAs can be directly applied to computer programs, represented either linearly [Nordin1994,Perkis1994], as graphs [Teller and Veloso1996,Poli1997] or as trees. This has become known as genetic programming (GP) [Koza1992].
GP has demonstrated its potential by evolving programs for medical signal filters [Oakley1994], modelling complex chemical reactions [Bettenhausen et al. 1995], performing optical character recognition [Andre1994], designing electronic circuits [Koza et al. 1996], and for target identification [Tackett1993].
Where problems are known in advance, it may be feasible to code their solution in advance, however where problems are dynamic the solution needs to adapt or learn. The evolution of species to changes in their environment, e.g. colder winters, can be thought of as ``genetic learning''. Genetic learning can adapt to changes which occur over a number of generations but not to faster changes. In addition to genetic learning, many species evolved the ability to respond in much shorter time intervals. Such learned responses are not stored by changing the individuals' genetic makeup but by remembering.
In GP we control the rate at which new generations are formed so genetic learning may be feasible for some dynamic problems. However in this project we seek to show that life time learning, based on the use of memory, can be advantageous for GP. While there is increasing interest in using memory within GP, most GP research continues to concentrate upon the evolution of memory-less programs ([Langdon1998] contains a survey of the use of memory within GP).
While an individual's memory gives it the ability to learn rapidly, it has the disadvantage that its contents and all that has been learnt is lost to the species when the individual dies. Where an individual's experience is unique to it then this does not matter, but some of what it has learnt may be useful to other members of the species. Teaching provides a way of passing information from one individual to another. It has some advantages over genetic learning, for example it may be quicker, knowledge can be passed without repeating the experience which caused it to be learnt in the first place (which may have been dangerous) and knowledge can be passed to other individuals as well as to direct descendants.
This project seeks to show, in the case of computer programs teaching mechanisms which pass data to other programs (which implies communication and use of memory) can be advantageous (i.e. reduce time and computer resources) compared to genetic learning.
This section proposes an experimental approach to the problem of the emergence of learning based upon the evolution of computer programs.
The test problem uses a sequence of integers which is not easy to represent using a program (this can be verified by comparison with [Sloane and Plouffe1995]). Fitness testing is split into two parts, training and testing. When training the test individual is given both the sequence number and the number itself. In the testing stage, only the sequence number is given and the individual has to respond with the actual number.
The first experiment will demonstrate GP can automatically evolve programs which memorise sequences of integers. This is expected to be straightforward [Langdon1995] but gives an opportunity to test and bed-in the system.
Higher fitness can be obtained in the first part of testing (the training phase) if the correct answer is obtained from the teacher, i.e. before the individual is shown the answer. In these experiments the teacher will be one of the individual's parents. The program being tested will be provided with both procedural and shared memory interfaces to its teacher. The GP system will evolve to make appropriate use of these interfaces. At this stage there will be no penalty on the teacher for time it spends teaching.
Later we repeat the experiment but with parts of the test sequence omitted so alternate generations encounter parts of it which the intermediate generation does not. The evolved programs can solved the test problem if each generation passes on knowledge, i.e. teaching its offspring, even if it does not encounter the specific part of the test sequence.
The second set experiments are similar experiments to the first, but the problem is made more complex so simple memorisation is insufficient. Instead the input will be complex but contain redundancy which will be relatively easy to decode using values stored in memory but difficult to decode using program code only. In the second (testing) phase the individual will be presented with test cases it did not see in the first phase but which do belong to patterns it was shown.
In the teaching experiments, we will look for evidence that data pertaining to ``patterns'' rather than actual answers is being imparted to the individual from its parent.
In these experiments we seek to show automatically produced programs can do two things; firstly learn more complicated data patterns and redundancy, and secondly that abstract learnt data can be used in novel ways.
In the first experiments the GP will be taught board position scores for a 3 by 3 game such as naughts and crosses [Juille and Pollack1996,Rosin and Belew1995] using the two phase (train and test) approach used above. The testing phase will require the evolved programs to recognise and exploit the basic symmetries of the game. Again the parent will be expected to teach its offspring.
In the second group of experiments fitness testing will be extended to include playing the game. An opponent using the taught board scores (i.e. a mini-max strategy with zero look ahead) will be used. These experiments will seek to show the evolved program can re-use data it has already learnt.
The inflexibility of current computer systems and the manual effort required to update them, even to make the most trivial of changes, is a major cost to commerce. This proposal addresses both issues by investigating the automatic production, using a model of Darwinian natural evolution, of computer programs that can learn, i.e. that can adapt.
It should be feasible to conduct the above experiments using the resources available. It is anticipated that they will succeed in demonstrating both the feasibility of incorporating learning and teaching within evolutionary computation.