Genetic Programming and Data Structures

W. B. Langdon, University College, London, 1996, 350 pages

Chapter 8 Conclusions

The key to successful human produced software is using abstraction to control the complexity of each task in hand. I.e. in each task, being able to use objects without considering in detail how they interact. The objects are abstractions of lower level code or data, which are in turn abstractions of still lower levels. Thus a programmer may use a file while knowing nothing about how to program the disk drive on which it is stored. Indeed the program can continue to work even if the file is moved to another disk drive, even if it is of a different type, even a type which had not been designed when the program was written.

Genetic programming, with its undirected random program creation, would appear to be the anathema of highly organised software engineering. It is an evolutionary technique, using only information in its current population. It does not plan ahead or use a global top-down design but we have already seen, via ADFs and other techniques, it too can gain considerable benefit from functional abstraction.

While GP work to date has concentrated on functional abstraction, we argue that techniques which allow GP to take advantage of data abstraction will be essential to enable it to scale up and tackle large real problems. Chapters 3, 4 and 5 show GP can produce structured data types (stacks, queues and lists). In Chapter 6 we demonstrate GP can use data abstraction, by solving three problems. For the two more complex examples we have shown a stack abstract data type is beneficial. While the first example does not require a stack, a general solution was evolved which used the appropriate data structure. The failure of indexed memory to solve the two more complex problems, is disappointing, but was expected. While it is anticipated that it is possible to evolve solutions to the two problems using indexed memory, e.g. if increased resources are available, the richness of interactions supported by indexed memory allows complex interactions to arise and these complicate the search space making it harder to search. This problem is a general one. The search effort increases rapidly with problem complexity. While other research has shown changes to the representation (e.g. ADFs and more powerful primitives) can help, this work has shown that reducing the complexity of evolved programs through use of data abstraction to control interactions within evolving programs can also be beneficial.

Appendices C and D have demonstrated that both the combination of a GA and hand coded heuristic, and a GP using the same heuristics as seeds in the initial population can produce low cost maintenance schedules for a real world electrical power transmission network.

In many of the problems in this thesis, general scalable solutions have been evolved. This is very encouraging. Perhaps general algorithms are easier for GP to find? It may be argued on the basis of the Minimum Description Length (MDL) principle or Occam's Razor that general programs tend to be shorter than programs which are specific to the test case and fail to generalise . Non-general program may ``memorise'' the tests and need to be longer and more complex to do this. Perhaps solutions occur more frequently in the search space of shorter programs or perhaps GP is less effective at searching for longer programs?

The idea that symbolic regression is compressing the training data into a program, can be inverted. If a required program's size can be estimated, then so too can its information content. This gives a lower bound on the information content of the training data and thus, a lower bound on the size of the training set. This indicates that the volume of training data will need to increase as we try and evolve more ambitious programs. If we continue to test all evolved programs on all the training set then GP machine resource usage will grow at least quadratically with task complexity. However techniques such as co-evolution, soft brood selection and sparse training sets indicate it may not be necessary to exhaustively test every evolved program.

8.1 Recommendations

A number of practical recommendations for GP work can be made. To a large extent the advice in kinnear Advances in GP and GP1 remains sound, however a number of additional suggestions can be made:

GP populations should be closely studied as they evolve. There are several properties that can be easily measure which give indication of problems:
- Frequency of primitives. Recognising when a primitive has been completely lost from the population (or its frequency has fallen to a low level, consistent with the mutation rate) may help to diagnose problems.
- Population variety. If the variety falls below 90% of the population size, this indicates there may be a problem. However a high variety does not indicate all is well. Measuring phenotypic variation (i.e. diversity of behaviour) may also be useful.
Measures should be taken to encourage population diversity. Panmictic steady state populations with tournament selection and reproduction and crossover appear to converge too readily. The above metrics may indicate if this is happening in a particular case. Possible solutions include:
- Removal of the reproduction operator.
- Addition of one or more mutation operators.
- Smaller tournament sizes and/or using uniform random selection to decide which individuals to remove from the population. NB the latter means the selection scheme is no longer elitist. It may be worthwhile forcing it to be elitist.
- Splitting large populations, i.e. above 1000, into semi-isolated demes.
- Using fitness sharing to encourage the formation of many fitness niches.
Use of fitness caches (either when executing an individual or between ancestors and children) can reduce run time and may repay the additional work involved with using them.
Where GP run time is long, periodically save the current state of the run. Should the system crash; the run can be restarted, from part way through rather than the at the start. Care should be taken to save the entire state, so restarting a run does not introduce any unknown variation. The bulk of the state to be saved is the current population. This can be compressed, e.g. using gzip. While compression can add a few percent to run time, reductions in disk space to less than one bit per primitive in the population have been achieved.

8.2 Future work

There are many interesting questions raised by the work in this thesis. There are a number of techniques that have been introduced or which are fairly new to GP which warrant further investigation to further explore their benefits or clarify the best circumstances in which to use them. Examples include:

Multi-objective fitness functions.
Pareto fitness.
Fitness Niches.
Fitness Sharing.
Design of primitive sets and fitness functions (particularly concerning deceptive fitness functions and representations).
Semantic and syntactic restrictions on evolving programs or parts of programs.
Scoping rules.
Reducing run time via caching or inheriting partial fitness information from ancestors.

However the failure of GP to evolve data structures ``on the fly'' is the most important. Aspects that could be investigated include: Is the failure specific to the problems tried, the primitive sets used or insufficient resources dedicated to the task? If the later how much extra resources are required? While these are possible explanations, it is felt that this failure is part of the general difficulty of scaling up GP to solve more complex problems and so its solution would have a direct bearing on the fundamental scaling problem for GP.

The addition of data structures greatly extends the power of genetic programming. GP plus data structures should be evaluated on such problems. The use of stack data structures with other context free languages is an obvious first step.

W.B.Langdon 24 July 2001