To answer this question properly, we should probably first consider the question "what's a GENETIC ALGORITHM?"
The Genetic Algorithm is a model of machine learning which derives its behaviour from a metaphor of the processes of evolution in nature. This is done by the creation within a machine of a population of individals represented by chromosomes, in essence a set of character strings that are analogous to the base-4 chromosomes that we see in our own DNA. The individals in the population then go through a process of evolution.
We should note that evolution (in nature or anywhere else) is not a purposive or directed process. That is, there is no evidence to support the assertion that the goal of evolution is to produce Mankind. Indeed, the processes of nature seem to boil down to different individuals competing for resources in the environment. Some are better than others. Those that are better are more likely to survive and propagate their genetic material.
In nature, we see that the encoding for our genetic information (genome) is done in a way that admits sexual reproduction. Asexual reproduction (such as by budding) typically results in offspring that are genetically identical to the parent. Sexual reproduction allows the creation of genetically radically different offspring that are still of the same general flavour (species).
At the molecular level what occurs (wild oversimplification alert) is that a pair of chromosomes bump into one another, exchange chunks of genetic information and drift apart. This is the "RECOMBINATION" operation, which GA/GPers generally refer to as "CROSSOVER" because of the way that genetic material crosses over from one chromosome to another.
The crossover operation happens in an environment where the selection of who gets to mate is a function of the "FITNESS" of the individual, i.e. how good the individual is at competing in its environment.
Some genetic algorithms use a simple function of the fitness measure to select individuals (probabilistically) to undergo genetic operations such as crossover or REPRODUCTION (the propagation of genetic material unaltered). This is fitness-proportionate selection. Other implementations use a model in which certain randomly selected individuals in a subgroup compete and the fittest is selected. This is called tournament selection and is the form of selection we see in nature when stags rut to vie for the privilege of mating with a herd of hinds. The two processes that most contribute to evolution are crossover and fitness based selection/reproduction.
As it turns out, there are mathematical proofs that indicate that the process of fitness proportionate reproduction is, in fact, near optimal in some senses.
Mutation also plays a role in this process, though it is not the dominant role that is popularly believed to be the process of evolution, i.e. random mutation and survival of the fittest. It cannot be stressed too strongly that the genetic algorithm (as a simulation of a genetic process) is not a "random search" for a solution to a problem (highly fit individual). The genetic algorithm uses stochastic processes, but the result is distinctly non-random (better than random).
Genetic algorithms are used for a number of different application areas. An example of this would be multidimensional optimisation problems in which the character string of the chromosome can be used to encode the values for the different parameters being optimised.
In practice, therfore, we can implement this genetic model of computation by having arrays of bits or characters to represent the chromosomes. Simple bit manipulation operations allow the implementation of crossover, mutation and other operations. Although a substantial amount of research has been performed on variable-length strings and other structures, the majority of work with genetic algorithms is focussed on fixed-length character strings. We should focus on both this aspect of fixed-lengthness and the need to encode the representation of the solution being sought as a character string, since these are crucial aspects that distinguish Genetic Programming, which does not have a fixed length representation and there is typically no encoding of the problem.
When the genetic algorithm is implemented it is usually done in a manner that involves the following cycle: Evaluate the fitness of all of the individuals in the population. Create a new population by performing operations such as crossover, fitness-proportionate reproduction and mutation on the individuals whose fitness has just been measured. Discard the old population and iterate using the new population.
One iteration of this loop is refered to as a GENERATION. There is no theoretical reason for this as an implementation model. Indeed, we do not see this punctuated behaviour in populations in nature as a whole, but it is a convenient implementation model.
The first generation (generation 0) of this process operates on a population of randomly generated individuals. From there on, the genetic operations, in concert with the fitness measure, operate to improve the population.
Genetic Programming is the extension of the genetic model of learning into the space of programs. That is, the objects that constitute the population are not fixed-length character strings that encode possible solutions to the problem at hand, they are programs that, when executed, "are" the candidate solutions to the problem. These programs are expressed in genetic programming as parse trees, rather than as lines of code. Thus, for example, the simple program "a + b * c" would be represented as:
+ / \ a * / \ b cor, to be precise, as suitable data structures linked together to achieve this effect. Because this is a very simple thing to do in the programming language Lisp, many GPers tend to use Lisp. However, this is simply an implementation detail. There are straighforward methods to implement GP using a non-Lisp programming environment.
The programs in the population are composed of elements from the FUNCTION SET and the TERMINAL SET, which are typically fixed sets of symbols selected to be appropriate to the solution of problems in the domain of interest.
In GP the crossover operation is implemented by taking randomly selected subtrees in the individuals (selected according to fitness) and exchanging them.
Genetic programming is a machine learning model which, its adherents would claim, is the most general and flexible around. It has already been applied to a wide variety of problem domains and may well have real-world utility.
Genetic Programming is a comparatively new field, so there isn't a large body of documentation on it. [aside: is anyone prepared to keep an up to date, on-line GP bibliography?] A number of researchers are beginning to publish GP related papers. At least for a while, the best place to start is likely to be one of two sources:
a. "Genetic Programming: On the Programming of Computers by Means of Natural Selection" - by John R. Koza, MIT Press 1992
b. "Genetic Programming - The Movie" - by John R. Koza and James P. Rice, MIT Press 1992.
The movie is probably the cheapest and easiest way to get a quick introduction into the sorts of things that have already been achieved by GP. The book is probably the best way to go about becoming a GPer. An order form for the book and movie can be found below.
Goldberg, David E. 1989. "Genetic Algorithms in Search, Optimization, and Machine Learning." Addison-Wesley. - Mix of theory and practice
Davis, Lawrence. 1991. "Handbook of Genetic Algorithms" Van Nostrand Reinhold. - Mostly practical.
Holland, John H. 1992 "Adaptation in Natural and Artificial Systems." MIT Press - Very theoretical.
Michalewicz, Z. 1992. "Genetic Algorithms + Data Structures = Evolution Programs." Springer-Verlag - Practical
..... suggestions anyone.... ?
I'm new on this mailing list. Can I see an archive of the old messages?
Well this is one of the advantages of the new mail list. Old messages were not readily available via the old one.
"THE GA 30"
Information for Instructors and Prospective Instructors of University Courses on Genetic Algorithms
TITLE: "University Courses on Genetic Algorithms 1995 Edition No. 1 - December, 1995
Compiled by John R. Koza, Computer Science Department, Stanford University
This volume contains lightly-edited information about 30 different university courses on genetic algorithms that are offered by universities around the world. The information was contributed by the instructors of the various courses. This information was solicited by posting "requests for information" during 1995 on electronic mailing lists on genetic algorithms, genetic programming, and other topics related to evolutionary computation. It is hoped this collection will be useful to both instructors of existing courses on genetic algorithms and instructors considering starting up their own course on this subject.
Copies of this volume (ISBN 0-18-195903P8) are available DIRECTLY from Stanford University Bookstore for $9.30 plus $6.00 shipping and handling (in the USA) by calling 415-329-1217 or 800-533-2670 or by writing Stanford Bookstore Stanford University Stanford, California 94305-3079 USA The E-Mail address of the bookstore for e-mail orders is mailorder@bookstore.stanford.edu.
Be sure to mention the ISBN number, exact title, refer to "Custom Publishing" and "CSD 000" when ordering to avoid confusion with course readers, collections of student papers, and other materials associated with my courses at Stanford.
John R. Koza Consulting Professor Computer Science Department Gates Building Stanford University Stanford, California 94305 USA PHONE: 415-941-0336 E-MAIL: Koza@Cs.Stanford.Edu WWW: http://www-cs-faculty.stanford.edu/~koza/
No, there is nothing about GP that requires Lisp, it's just a very convenient language to use. It's also the easiest way to write a GP implementation that is small enough and simple enough to put into the appendices of a book. At present, the most easily available implementation of GP is that shown in the book, so you would require a Common Lisp implementation to use it.
However, William Archibald
Although it is by no means clear that C is faster in this
context, GP can be implemented in C/Pascal/... in a
relatively straighforward manner. Note that (given suitable
type declarations) code generated by a good Lisp compiler is
likely to be just as fast as that generated by a C compiler
unless you are very careful. Lisp, however, carries a
larger price in working set and is less readily available.
The big problem that you have to tackle in coding a C based
version is that there is no garbage collection. This means
that for anything beyond trivial applications there is a big
benefit associated with doing all of your storage allocation
statically and doing careful storage management. There are
lots of ways that one could Cify GP, but here is a simple
scheme:
a) Statically create arrays to represent the individual
programs. There should be one table representing the points
in the tree. This will require a enough bits of width to be
able to represent (max (cardinality function-set)
(cardinality terminal-set)). You need a second table two
bits wide of the same length to encode the four distinct
types of things you bump into in the trees: functions,
pseudo-macros, variable terminals and constant terminals. A
third table is needed with enough bits to encode (reduce #'max
(mapcar #'length (mapcar #'arglist function-set))). These
tables should be sized for the worst-case size of an
individual. (500 points is probably enough to get along
with).
b) If the function set is to be {AND OR NOT} with arg
counts {2 2 1} and the terminal set is to be {D0 D1 D2 D3}
then you need two bits of width in the first table and two
bits for the third (you can strictly get away with 1 because
this function set has no zero arg functions, but it probably
isn't worth it if you're trying to make a general
framework). Now, you make a mapping table that maps {0->AND,
1->OR, 2->NOT} and another that maps {0->D0, 1->D1, 2->D2,
3->D3}.
This all means that you can linearise the parse tree into
the arrays in an efficient manner. You can trivially write
an interpreter which does something of the form:
Obviously it's a bit more complex than this but the idea is
pretty simple. It gets a little harder when you want to
have an arbitrary number of randomly generated constants,
since this can spoil your coding efficiency if you're not
careful.
c) Implement the crossover (and other) genetic operations
so that rather than swapping subtrees it shuffles the values
in the tables up and down and copy the crossed over subtrees
(which are always contiguous in the linearised
representation) from one to the other.
d) A simple resource architecture and a reference counting
scheme that decides what operations are to be performed to
which individuals in the population before any operations
are performed allows you to deallocate all of the
individuals that are not going to contribute to the next
generation. Using the reference counting scheme you can
easily make it the case that you do not need to allocate
enough memory to accomodate 2X the size of the population.
You can always deallocate individuals before you are about
to need to get new ones to put the newly created individuals
into for the next generation.
Yes. See
ftp host cs.ucl.ac.uk/genetic/ftp.io.com/code
Process patents have been issued both for the bucket brigade
algorithm in classifier systems (to John Holland) and for GP
(to John Koza). This FAQ does not attempt to provide legal
advice. However, use of the Lisp code in the book is freely
licensed for academic use. Although those wishing to make
commercial use of any process should obviously consult any
patent holders in question, it is pretty clear that it's not in
anyone's best interests to stifle GA/GP research and/or
development. Commericial licenses much like those used for CAD
software can presumably be obtained for the use of these
processes where necessary.
To have a real understanding of what's going on in terms
of efficiency and what's best to do you'd need to know a
fair bit about Lisp and its implementation and a fair bit
about the application in question, but the argument
breaks down something like this:
- When you do GP you have to execute a large number of
randomly created and/or evolved programs, which are
consequently not known at file-compile time.
- The number of times you execute ANY GIVEN individual
program is (generally) the product of the number of
fitness cases and the number of timesteps over which you
need to simulate. Thus, for a regression problem for a
simple one dimensional space (page 237) you might have
(say) 50 fitness cases, but no simulation and hence 50
evaluations per individual. For a robotics problem like
the box-moving robot (p. 381) there might be 4 fitness
cases and 350 timesteps so there are up to 1400
evaluations per individual (note that individuals that
quiesce are aborted earlier.) The number of effective
evaluations might be increased enormously by having
operators in the function set that cause iteration or by
the doing automatically defined function stuff (chapters
20 and 21), which is not suported in the GP code in the
book, but is not that hard to add.
- There are two obvious ways to execute a program;
interpretting and compiling and funcalling. There are
costs associated with each of these. Interpreting is
slower, but you don't pay the up-front cost of
compilation, which is huge relative to evaluating a
simple expression.
- There are costs in fitness computation other than
simply executing the program itself. This is
demonstrated excellently by problems like the
pursuer-evader game (p423) or the broom balancing problem
(p289), where part of the simulation happens after the
evaluation of the individual, since the program delivers
the value of the control variable, which is then used to
perform the state transitions of the simulation. Since
these computations typically involve complicated uses of
transcendental functions they can often be more expensive
than the execution of the program itself.
Thus, what you're trying to do when you do GP is to
maximise the number of calls to the fitness function per
second. This might be optimised by compiling the
individuals or by interpreting them, or by spending time
on optimising the fitness function. You can only really
know for sure by metering the behaviour of the run and
trying each (your intuition is almost sure to be wrong in
our experience). However, our experience tells us that
interpreting is typically faster for the majority of
problems, particularly those that novice users of the
little GP code in the book are likely to be tackling to
start with. There are also operational issues associated
with compiling the individuals, but we can neglect that
for now.
So, when we say that fast-eval is faster, we're not
comparing it to compilation, we're comparing it to the
interpreter that comes for free with Lisp (eval). The
reason it is typically faster than eval is that eval has
to carry all of the baggage associated with being a
complete Common-Lisp interpreter and fast-eval doesn't.
This baggage includes things like lexical closures, local
variables and functions and macros, none of which are
needed by GP.
In GP there are really only four classes of things that
are processed: constants, like 3.5, variables, like X,
functions, like +, and functions that control their own
argument evaluation, which we call pseudo-macros, such as
IFLTE. All of the complicated implementation-specific
hair in fast-eval is caused by the desire to discriminate
between these classes rapidly at run-time.
All Lisps have highly optimised means to execute things
like consp and symbolp. The only problem comes in trying
to discriminate between the two classes of "internal
points", i.e. functions and pseudo-macros. CL doesn't
provide a specific optimised hook for this and all
implementations represent their functions somewhat
differently, so we have to hunt around for the fastest
way we can on any particular implementation. Note that
some implementations are rather fascist about what you
can legally put in the function cell of a symbol, so this
causes some of the reasons for the non-portability.
Indeed, Lucid tightened up on things between release 4.0
and 4.1 and broke the code in the book. Maybe we'll be
able to get a patch in if there's a second printing.
As far as avoiding the recursion is concerned, this is
not as trivial as it may sound (not necessarily as
desirable as you might think either). If your
sexpression is (say)
(setq my-sexpr '(+ a (* b (- c 42))))
then compiling this to give you
(setq my-compiled-sexpr (compile nil `(lamda () ,my-sexpr)))
will deliver a function that in most implementations will
have open coded the references to the functions +, * and
-. Note that you might want to put type delcarations
into these functions, such as:
(compile `(lambda () (declare (type integer a b c)) ,my-sexpr))
to get optimal code generation.
However, if your sexpression was of the form:
(progn (move-left) (iflte (turn-right) 42 (move-forward) (move-backwards)))
Then you are presented with two problems.
a) The bodies of the functions move-left etc. will probably
not get open coded into the compiled individual. Functions like
move-left are likely to be trivially implemented, i.e. move-left
might consist of nothing more than (decf *x-coord* 1.0) Note that
what one is really trying to avoid is not recursion pre se, but
rather function-call overhead, which is highest for calls to non-
(self/mutually) tail-recursive functions. Thus, failure to
open code functions like move-left results in compilation giving
almost no benefit (you'd like to get ~20X speedup from compilation
in general). Open coding can usually be achieved by proclaiming
the functions in question to be inline, but this does not work
on every implementation and may be suboptimal. You might have to
declare compiler-macros (compiler-optimizers) for the functions
in question to get the right open coding.
b) In the example above there is an instance of a pseudo-macro call
to IFLTE. If it is the case that you always compile your individuals
then you can just define these as real macros. Real macros, however
are incompatible with fast-eval, so you can't use real macros in
interpretted mode. One of the main reasons for using pseudo-macros
and fast-eval is because macro-expansion is very expensive and
undesirable at GP run-time, especially when all you're using them
for is as functions that control their argument evaluation. If you
want to have your cake and eat it, then you'll need to define
compiler macros for each pseudo-macro so that they get open coded
properly. In the GP code that JK and I use we have a hairy and
complex chunk of code that automatically generates pseudo-macros
for our version of fast-eval as well as all of the necessary
compiler optimizer stuff in order to get around all of these
problems.
As you will have spotted, this is not a trivial issue. Any given
problem will have its own specific usage/performance profile and
you'll need to take things on a case by case basis. The code in the
book is intentionally supposed to be as simple as possible and yet
show all of the fundamental principles of GP. For this reason, there
are no type declarations, even though these would doubtless increase
performance. Type declarations would have increased the size of the
code by a fair chunk and would have clouded the issue too much, we
feel. Many compilers have a knob you can tweek that will get it
to advise you of good places to put type declarations that will have
the best effect (try fast-eval first, of course).
Things have moved on a great deal.
Their old code is available via ftp
(see Answer 8)
but you might want to consider new implementations.
For a number of methodological reasons, a tightly defined
answer to this question is too complex to include here.
An expansive coverage is given in chapter 9 of the book.
Having said this, the high order bit of the answer to this
question is an absolute and emphatic "YES". As examples
of this superior to random behaviour are shown in the book
and are well documented in the literature. For example:
13.1 Pete Angeline evolved solutions to the tic-tac-toe
problem with only 200,000 individuals of effort
(population size of 1000 run for 200 generations). In
trying 200,000 random individuals he observed nothing that
even half way played the game. The fitness of the best
randomly generated program was 2.25 compared to a score of
16.5 for the best evolved program. See his paper for
details on the scoring function. This result is still
unpublished and will appear in his dissertation.
Symbolic regression (chapter 10 in the book) is the
process of discovering both the functional form of a
target function and all of its necessary coefficients, or
at least an approximation to these. This is distinct from
other forms of regression such as polynomial regression in
which you are merely trying to find the coefficients of a
polynomial of a prespecified order. In some senses, all
GP problems are symbolic regression problems, but the term
is usually used to apply to finding real-valued functions.
This is very much a "how long is a piece of string"
question. However, GP is a very resource intensive
process and it is probably a good idea to get the fastest
machine that you can (no surprise).
Howard Oakley
Genetic Algorithm (GA) - Model of machine learning that
uses a genetic/evolutionary metaphor. Implementations
typically use fixed-length character strings to represent
their genetic information.
Genetic Programming (GP)- Genetic Algorithms applied to
programs. Genetic Programming is more expressive than
fixed-length character string GAs, though GAs are likely
to be more efficient for some classes of problems.
Recombination - (see crossover)
Crossover - The genetic process by which genetic material
is exchanged between individuals in the population.
Reproduction - The genetic operation which causes an
exact copy of the genetic representation of an
individual to be made in the population.
Generation - An iteration of the measurement of fitness
and the creation of a new population by means of
genetic operations.
Function set - the set of operators used in GP, these
functions label the internal (non-leaf) points of the
parse trees that represent the programs in the
population. An example function set might be {+, -, *}.
Terminal set - the set of terminal (leaf) nodes in the
parse trees representing the programs in the
population. A terminal might be a variable, such as X,
a constant value, such as 42, or a function taking no
arguments, such as (move-north).
7. I would like to use GP with C instead of LISP because C is
usually faster. How does one use GP with C instead of LISP?
In LISP the parse tree is obvious - in C it is not. How does
one eval C programs?
(defun interpret-program (program current-index)
(with-slots (points-of-tree type-of-current-point arg-count-table) program
(case (aref type-of-current-point current-index)
(function
(case (aref arg-count-table current-index)
(0 .....)
(1 (multiple-value-bind (value next-index)
;;; Evaluate single arg for this function.
(interpret-program program (+ 1 current-index))
(values (funcall (aref function-mapping-table
(aref points-of-tree current-index))
value-of-arg)
next-index)))
(2.....)))
(variable-terminal ......)
(....))))
i.e. you step along the program recursively evaluating the
arguments to functions when necessary, always returning both
the value of the subexpression and the index to the point
after the subtree just evaluated.
8. I don't want to have to type in the code in the appendices to
the book. Can I get the source code on-line somewhere?
9. What's all this I hear about patents?
10. I'm not a sophisticated Lisp user and don't understand why
so much apparent effort is spent in the Lisp code in the book
worrying about FAST-EVAL. Can't I just get things to go faster
by compiling my population or some such. This would avoid the
apparent recursion in the FAST-EVAL function.
12. Can I get the code that JK and JR run?
13. Has GP been shown to be better than Random Search?
14. What is Symbolic Regression?
15. I want to GP but I don't know what sort of machine to
run it on. What should I get?
Machine Lisp Test 1 Test 2
(times in seconds, gross)
Mac IIci MCL 2.0 90.59 303.58
Mac IIfx MCL 2.0 81.18 214.96
Mac IIci+Rocket MCL 2.0 34.17 100.77
Mac Quadra 950 MCL 2.0 28.91 100.22
Sun 10/20 Sparc Lucid 4.1 13.06 ???
Sun 10/30 Sparc Lucid 4.1 11.10 29.81
Sun 10/30 Sparc Franz Allegro 6.25 32.48
Sun 4/470 Sparc Franz Allegro 17.19 68.53
Sun IPC Lucid 4.1 29.21 ???
Sun IPC Franz Allegro 14.85 80.86
TI Explorer II TICL 6.1 13.28 143.64
SGI IndigoR3000 AKCL 6.15 259.09 ???
SGI IndigoR3000 Franz Allegro 16.25 80.56
(Franz Allegro CL was V 4.1)
(note that all results are now consistent and correct, following the Lucid
patch)
(times above are gross, including all OS and GC overhead)
More details on systems:
Machine CPU Clock speed OS RAM virtual RAM actual RAM used
(if fixed)
Mac IIci 68030 25 7.0.1 20 12 22
Mac IIfx 68030 40 7.0.1 36 0 30
Mac IIci+Rocket 68040 33 7.0.1 20 0 16
Mac Quadra 950 68040 33 7.0.1 36 0 32
Sun 10/20 Sparc 4.1.3 32 180
Sun 10/30 Sparc 4.1.3 32 180
Sun 4/470 Sparc 33 4.1.1 32
Sun IPC 4.1.3 32 400
TI Explorer II 6.1 16 128
SGI IndigoR3000 MIPS 3000 33 IRIX 4.0.5 48 120
The 'league table' of speed based on the second test is thus:
1 Sun 10/30 & Lucid 1.0 (relative to fastest)
2 Sun 10/30 & Franz Allegro 1.1
3 Sun 4/470 & Franz Allegro 2.3
4 SGI Indigo & Franz Allegro 2.7
5 Sun IPC & Franz Allegro 2.7
6 Macintosh Q950 & MCL 3.4
7 Macintosh IIci+Rocket & MCL 3.4
8 TI Explorer II 4.8
9 Macintosh IIfx & MCL 7.2
10 Macintosh IIci & MCL 10.2
Please send any further results to Howard Oakley
99. Glossary
100. Book order form
---------------------------ORDER FORM----------------------
PHONE: 1-800-356-0343 TOLL-FREE or 617-625-8569
MAIL: The MIT Press, 55 Hayward Street, Cambridge, MA 02142
FAX: 617-625-9080
Please send
____ copies of the book GENETIC PROGRAMMING: ON THE
PROGRAMMING OF COMPUTERS BY MEANS OF NATURAL SELECTION by
John R. Koza (KOZGII) (ISBN 0-262-11170-5) @ $55.00.
____ copies of the one-hour videotape GENETIC PROGRAMMING: THE
MOVIE by John R. Koza and James P. Rice in VHS NTSC format
(KOZGVV) (ISBN 0-262-61084-1) @$34.95
____ copies of the videotape in PAL format (KOZGPV) (ISBN 0-262-
61087-6) @$44.95
____ copies of the videotape in SECAM format (KOZGSV) (ISBN 0-
262-61088-4) @44.95.
Name __________________________________
Address_________________________________
City____________________________________
State_________________Zip________________
Country_________________________________
Phone Number ___________________________
$ _______ Total
$ _______ Shipping and Handling ($3 per item. Outside U.S. and
Canada, add $6 per item for surface rate or $22 per item for airmail)
$ _______ Canada - Add 7% GST
$ _______ Total due MIT Press
__ Payment attached (check payable to The MIT Press in U.S. funds)
__ Please charge to my VISA or MASTERCARD credit card
Number ________________________________
Credit Card Expires _________________________________
Signature ________________________________