This was my MSc thesis at Edinburgh University.

Proposal Description


Koza and Rice [1, 2] introduced the idea of subroutines (automatic function definition) to genetic programming. In this the top node has a fixed number of branches, one of which is the main program with the remaining being sub-routines that it can call. This system can suffer because a good subroutine that is not called by its program can be lost.

Moriaty and Miikkulainen introduced the idea of symbiotic evolution to neural networks [3,4]. Here instead of the entire structure of the network as is usually done the individual neurons are evolved. These neurons are then combined either at random [4] or using separately evolving blueprints [3]. The fitness of each neuron is calculated from the fitness of the networks in which it is participating at each generation.

The goal of this project is to bring these two ideas together. Individual functions will be evolved and then brought together only for evaluation in separately evolving programs. This removes some of the constraints on the number and usage of the functions that may be used. It will also dramatically reduce the probability of a good subroutine being wasted by an inefficient parent program, because the subroutines are not explicitly dependent on the calling programs. The biological analogy would be evolving the protein structures and the method of combining this proteins independently.

Issues that could be explored include the value of evolving the programs against generating them randomly, and the speed of convergence compared to conventional ADF systems and genetic programs. Investigation of different rules for the combination of functions could also be explored.

The first step would be the implementation of the system outlined above with the functions evolved at one level and the controlling program at another. This should be compared to the standard ADF systems and genetic algorithms across a number of problems, such as the Sante Fe trail and symbolic regression problems. This will allow an analysis of the effectiveness of the method in comparison to known techniques to be made. If the results of this are promising then the work could be extended by examining applications of the technique to genetic algorithms (rather than programs), where the functions are replaced by chromosome segments that are recombined. Although time would probably not allow for it’s implementation, an extension to artifical life systems could be outlined.
References:

  1. John R. Koza, “Simultaneous Discovery of Reusable Detectors and Subroutines Using Genetic Programming”, Proceedings of the Fifth International Conference on Genetic Algorithms, 1993.
  2. John R. Koza, “Genetic programming II : automatic discovery of reusable programs”, MIT Press, 1994.
  3. David E. Moriaty & Risto Miikkulainen, “Hierarchical Evolution of Neural Networks”, Proceedings of the 1998 IEEE Conference on Evolutionary Computation (ICEC-98).
  4. David E. Moriaty & Risto Miikkulainen, “Efficient Reinforcement Learning through Symbiotic Evolution”, Machine Learning 22, 11-33 (1996).

Final Dissertation

The abstract is

This dissertation presents and investigates a new technique for using sub-routines in genetic programming. The technique differs from previous ideas by having separate populations for programs and functions and evolving the members of each concurrently. It was hoped that this technique will solve problems as successfully as existing methods with the additional advantage of having less structure determined in advance by the experimenter. It was also hoped that the technique would be superior to existing methods at finding generally useful sub-routines. The initial algorithm was found to be better than genetic programming techniques that don't use sub-routines but inferior to Koza's automatically defined functions (ADFs). The reasons behind the performance are analysed and three refinements are investigated. One of these improved the performance but remained inferior to ADFs. The system was found to discover generally useful sub-routines on successful runs.


The final dissertation is available.