anonymous ftp site cs.ucl.ac.uk directory genetic/papers

W.Langdon@cs.ucl.ac.uk . 10 June 1996

This directory contains (at your own risk):

Paper on Evolving Data Structures with Genetic Programming
Paper on Pareto Optimality, Population Partitioning, Price's theorem and GP
Summary of directing crossover locations in a multi-tree GP, as used with list data structures
Paper on Scheduling Maintenance of an Eletricity Network
Summary of Kauffman's NK landscapes inconjuction with Genetic Algorithms
Summary of seeding GA populations
T. G. W. Gordon MSc Thesis on Scheduling maintenance of electrical power transmission networks
Bibliographies of Genetic Programming and the Application of Genetic Algorithms to Production Scheduling, have been move to genetic/biblio

Evolving Data Structures with Genetic Programming

Presented at ICGA-95 (dvi 4 graphs missing) 12 pages.

ABSTRACT

Genetic programming (GP) is a subclass of genetic algorithms (GAs), in which evolving programs are directly represented in the chromosome as trees. Recently it has been shown that programs which explicitly use directly addressable memory can be generated using GP.

It is established good software engineering practice to ensure that programs use memory via abstract data structures such as stacks, queues and lists. These provide an interface between the program and memory, freeing the program of memory management details which are left to the data structures to implement. The main result presented herein is that GP can automatically generate stacks and queues.

Typically abstract data structures support multiple operations, such as put and get. We show that GP can simultaneously evolve all the operations of a data structure by implementing each such operation with its own independent program tree. That is, the chromosome consists of a fixed number of independent program trees. Moreover, crossover only mixes genetic material of program trees that implement the same operation. Program trees interact with each other only via shared memory and shared ``Automatically Defined Functions'' (ADFs).

ADFs, ``pass by reference'' when calling them, Pareto selection, ``good software engineering practice'' and partitioning the genetic population into ``demes'' where also investigated whilst evolving the queue in order to improve the GP solutions.

Code is available. Bibliographic details.

Presentation slides (18 pages)

Scheduling Planned Maintenance of the National Grid

published by Springer-Verlag in Evolutionary Computing

Version presented at the AISB Workshop on Evolutionary Computation, 3-4 April 1995 (dvi no graphs) 15 pages.

ABSTRACT

National Grid Plc is responsible for the maintenance of the high voltage electricity transmission network in England and Wales. It must plan maintenance so as to minimize costs taking into account:

location and size of demand,
generator capacities and availabilities,
electricity carrying capacity of the remainder of the network, i.e. that part not undergoing maintenance.

This complex optimization and scheduling problem is currently performed manually by National Grid's Planning Engineers. Computerized viability checks are performed on the schedules they produce. National Grid's Technology and Science Laboratories and UCL aim to generate low cost schedules using Genetic Algorithms. It is hoped this will aid the Planning Engineers.

This paper reports work in progress. So far:

A four node test problem has been identified
A fitness function has been devised
To date work has concentrated upon devising a representation based upon ``Greedy'' Optimizers.
The best of these has been incorporated in the QGAME genetic algorithm programming environment and optimal solutions have been readily found.

We are now considering how to scale up. The computational complexity of the best of the greedy optimizers is a concern. Our plans are to consider alternative approaches (such as expansive coding and Genetic Programming) before moving on to a significant section of the whole of the National Grid (South Wales has been suggested as a suitable example of intermediate size).

Code is available Bibliographic details.

Presentation slides (27 pages)

Pareto Optimality, Population Partitioning, Price's theorem and Genetic Programming

Accepted for presentation at the AAAI Fall 1995 Symposium on Genetic Programming however it was withdrawn due to pressure of time. This document is as it was submitted, 11 pages.

ABSTRACT

A description of a use of Pareto optimality in genetic programming is given and an analogy with Genetic Algorithm fitness niches is drawn. Techniques to either spread the population across many pareto optimal fitness values or to reduce the spread are described. It is speculated that a wide spread may not aid Genetic Programming. It is suggested that this might give useful insight into many GPs whose fitness is composed of several sub-objectives.

The successful use of demic populations in GP leads to speculation that smaller evolutionary steps might aid GP in the long run.

An example is given where Price's covariance theorem helped when designing a GP fitness function.

Bibliographic details.

Chapter in Advances in Genetic Programming 2

In progress, 4 pages

Slides for presentation at the ICGA-95 GP workshop, 8 pages.

Summary of NK landscapes and GAs

An extended version of the summary that was posted to the Genetic Algorithms Digest on 12 November 1994. I would welcome comments.

ga-nk-summary.txt 300 lines

Summary of Seeding Population GAs

A version of the summary that was posted to the Genetic Algorithms Digest March 1995. I would welcome comments.

ga-seed.txt 150 lines

Electrical Network Maintenance Schedule Optimisation Using Genetic Algorithm

tar file contains postscript files forming T. G. W. Gordon's MSc thesis in Information Technology at University College London, 1995.

The GA uses a timetabling approach to generate maintenance plans for two demonstration networks devised by the National Grid Company plc. The first four-node problem is a small highly constrained network whilst the second is based upon a real-world network, the South Wales region of the National Grid.

The timetabling approach is contrasted with earlier work on these problems using a permuation GA in combination with a "Greedy Scheduler"

gordon.tar.gz ~100 pages