MJB1@phoenix.cambridge.ac.uk (01/20/89)
There has been some recent discussion of these. However, I am not familiar with the work which is being described. Could someone give a list of the relevant references. Than you. Martin Bishop.
offutt@caen.engin.umich.edu (daniel m offutt) (01/20/89)
Here are a few references on Genetic Algorithms.
=========================================================================
Last modified 1-19-89.
What follows is a short annotated bibliography of papers on genetic
algorithms for those who do not yet know much about genetic
algorithms, but would like to learn enough to start applying them to
practical function opimization problems in which they are interested.
It is not necessary to read anything listed below in order to start
using a GA-based optimization package. But there are mistakes that
can be avoided by knowing something about the theory of genetic search
and the structure of the algorithm.
For example, flipping switches in a GA package to turn off
"crossover", or to turn up the "point mutation rate" yeilds something
that is neither an efficient optimization technique nor a genetic
algorithm. Some of the articles below were chosen to give the
reader a background that can help him avoid these and other mistakes.
I also included some articles to supply evidence that GA's work well
as function optimizers on many types of surfaces.
If your goal is to get some results optimizing your favorite
functions, it is important to know whether a GA package you obtain
from someone is a (1) traditional GA, (2) a somewhat speculative and
possibly-risky variation on a traditional GA, or (3) an algorithm that
is not a genetic algorithm at all, whatever its inventor may have
named it. Researchers sometimes accidentally misclassify their type
(2) or (3) algorithm into class (1). The articles below should
help the reader get a feeling for what a "traditional" genetic
algorithm is.
----------------------------------------------------------------------------
De Jong, K.,
``Adaptive System Design: A Genetic Approach.''
IEEE Transactions on Systems, Man and Cybernetics, vol. SMC-10,
no. 9, pp. 566-574.
(1980).
This is a very good first paper to read on genetic algorithms.
----------------------------------------------------------------------------
Holland, John H.,
in "Progress in Theoretical Biology", volume 4,
edited by R. Rosen and F. M. Snell, 1976, pages 263-293.
This is a very good first paper to read on genetic search theory.
It covers some of the more important theoretical results discussed
in "Adaptation in Natural and Artificial Systems" (see below).
----------------------------------------------------------------------------
Grefenstette, J. J.,
``Optimization of Control Parameters for Genetic Algorithms,''
IEEE Transactions on Systems, Man and Cybernetics. SMC-16, 1
(Jan-Feb 1986), 122-128.
(1986).
Genetic algorithms have parameters such as population size, crossover
rate, mutation rate and selection strategy, whose optimal settings are
not known. This paper describes the use of a genetic algorithm to
find better settings for these parameters -- an interesting
application of a genetic algorithm to optimize genetic algorithms
themselves. The paper is useful for forming an image of a space of
"orthodox" or "traditional" genetic algorithms. That is, variations
on genetic algorithms that would not generally be considered
speculative. One can infer from this paper a few rules of thumb about
GA parameter settings that can destroy the effectiveness of a GA. The
five test functions described in this paper are a standard (and
unfortunately small) set that has been used by many genetic
algorithmists to make comparisons between different GA's, and between
GA's and other optimization techniques.
----------------------------------------------------------------------------
Holland, John H.,
Adaptation in Natural and Artificial Systems.
Ann Arbor: University of Michigan Press,
(1975).
chapters four, five and six
This is the classic work on genetic algorithms. The book is written
on the assumption that the reader has a familiarity with probability
and combinatorics at the level of a first course in finite
mathematical structures. Chapters four, five, six and seven cover the
essential theory of genetic search. Understanding this theory can
help one avoid making "improvements" to a genetic algorithm that
actually reduce or destroy its effectiveness as a function optimizer.
See especially the two-armed bandit theorem and its k-arm
generalization in chapter five, and the discussion in section 6.2:
"Generalized Genetic Operators--Crossing Over". Theorem 6.2.3, the
"schema theorem", may be the most important result in Genetic Search
Theory..
----------------------------------------------------------------------------
Schaffer, J. D. and Morishima, A.,
``An Adaptive Crossover Distribution Mechanism for Genetic Algorithms.''
Proceedings of the Second International Conference on Genetic Algorithms,
pp. 82-89.
Hillsdale, NJ: Lawrence Earlbaum Associates.
365 Broadway, Hillsdale, NJ 07642, (201) 666-4110
(1987).
Shaffer, J. David and Morishima, Amy.,
``Adaptive Knowledge Representation: A Content Sensitive Recombination
Mechanism for Genetic Algorithms.''
Philips Laboratories - Briarcliff Document No. MS-87-088.
(1987).
These two papers describe one of the few variations on a traditional
GA that *may* actually outperform it. GAPC performed "as well or
better than a traditional GA" on the set of five test functions
described above, according to the authors. This is a result of
practical interest if it generalizes to functions ouside of the small
suite of test functions. It may be possible to get a some idea how
well GAPC would perform on a given optimization problem by considering
the results on these five test functions.
----------------------------------------------------------------------------
Smith, S. F.,
``A Learning System Based on Genetic Adaptive Algorithms.''
PhD Thesis, Dept. of Computer Science, University of Pittsburgh.
(1980).
Smith used a GA to search a ~4000-dimensional space of programs
encoded as production systems. This is interesting both for the
presumably highly nonlinear search space involved, and its very high
dimensionality. The best program found in this search space competed
with overwhelming success against a fairly famous machine learning
program that did not employ a GA.
----------------------------------------------------------------------------
De Jong, K.,
``On Using Genetic Algorithms to search Program Spaces.''
Proceedings of the Second International Conference on Genetic
Algorithms, pp. 82-89. Hillsdale, NJ: Lawrence Earlbaum Associates,
365 Broadway, Hillsdale, NJ 07642, (201) 666-4110
(1987).
De Jong is one of the GA community's best internal critics, maybe even
the only outspoken critic within the community itself. He is more
willing than anyone else to speak out against flaky modifications of
genetic algorithm mis-labled a "genetic algorithm" by their creator.
This paper perhaps captures some of that sort of useful skepticism.
----------------------------------------------------------------------------
Coombs, Suzan, and Davis, Lawrence,
``Genetic Algorithms and Communications Link Speed Design: Constraints and
Operators.
Proceedings of the Second International Conference on Genetic
Algorithms, pp. 257-260. Hillsdale, NJ: Lawrence Earlbaum Associates,
365 Broadway, Hillsdale, NJ 07642, (201) 666-4110
(1987).
I include this paper in the list for one reason: It is the first
report I am aware of a major dollar savings attributed to the used of
a genetic algorithm. The authors report a savings of about $140,000.
----------------------------------------------------------------------------
Goldberg, David,
Genetic Algorithms in Search Optimization and Machine Learning.
Addison-Wesley.
1988.
This is a very recent introductory book on genetic algorithms written
by one of Holland's former students.
====================================================================
Dan Offutt offutt@caen.engin.umich.edu