Abstract
Computers that ``program themselves''; science fact or
fiction? Genetic Programming uses novel optimisation
techniques to ``evolve'' simple programs; mimicking the
way humans construct programs by progressively
re-writing them. Trial programs are repeatedly modified
in the search for ``better/fitter'' solutions. The
underlying basis is Genetic Algorithms (GAs).
Genetic Algorithms, pioneered by Holland, Goldberg and
others, are evolutionary search techniques inspired by
natural selection (i.e\ survival of the fittest). GAs
work with a ``population'' of trial solutions to a
problem, frequently encoded as strings, and repeatedly
select the ``fitter'' solutions, attempting to evolve
better ones. The power of GAs is being demonstrated for
an increasing range of applications; financial,
imaging, VLSI circuit layout, gas pipeline control and
production scheduling. But one of the most intriguing
uses of GAs - driven by Koza - is automatic program
generation.
Genetic Programming applies GAs to a ``population'' of
programs - typically encoded as tree-structures. Trial
programs are evaluated against a ``fitness function''
and the best solutions selected for modification and
re-evaluation. This modification-evaluation cycle is
repeated until a ``correct'' program is produced. GP
has demonstrated its potential by evolving simple
programs for medical signal filters, classifying news
stories, performing optical character recognition, and
for target identification.
This paper surveys the exciting field of Genetic
Programming. As a basis it reviews Genetic Algorithms
and automatic program generation. Next it introduces
Genetic Programming, describing its history and
describing the technique via a worked example in C.
Then using a taxonomy that divides GP researchs into
theory/techniques and applications, it surveys recent
work from both of these perspectives.
Extensive bibliographies, glossaries and a resource
list are included as appendices.
Users
Please
log in to take part in the discussion (add own reviews or comments).