anonymous ftp site cs.ucl.ac.uk directory genetic/papers
W.Langdon@cs.ucl.ac.uk . 12 March 1995
This directory contains (at your own risk):
- Paper on Evolving Data Structures with Genetic Programming
- Paper on Scheduling Maintenance of an Eletricity Network
- A summary of Kauffman's NK landscapes inconjuction with Genetic Algorithms
- 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
Submitted to
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.
Scheduling Planned Maintenance of the National Grid
To be 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).
C code is available by request from W.Langdon@cs.ucl.ac.uk
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