goldfain@osiris.cso.uiuc.edu (02/03/88)
Would someone do me a favor and post or email a short definition of the term "Genetic Learning Algorithm" or "Genetic Algorithm" ? Thanks. - Mark Goldfain arpa: goldfain@osiris.cso.uiuc.edu
g451252772ea@deneb.ucdavis.edu (0040;0000003980;0;327;142;) (02/06/88)
I offer definitions by (1) aspersion (2) my broad characterization (3) one
of J Holland's shortest canonical characterizations and (4) application.
(1) GA are anything J Holland and/or his students say they are. (But this
_is_ an aspersion on a rich, subtle and creative synthesis of formal systems
and evolutionary dynamics.)
(2) Broadly, GA are an optimization method for complex (multi-peaked, multi-
dimensional, ill-defined) fitness functions. They reliably avoid local
max/min, and the search time is much less than random search would require.
Production rules are employed, but only as mappings from bit-strings (with
wild-cards) to other bit strings, or to system outputs. System inputs are
represented as bitstrings. The rules are used stochastically, and in
parallel (at least conceptually; I understand several folk are doing
implementations, too).
A pretty good context paper for perspective (tho weak on the definition of
GA!) is the Nature review 'New optimization methods from physics and
biology' (9/17/87, pp.215-19). The author discusses neural nets,
simulated annealing, and one example of GA, all applied to the TSP, but
comments that "... a thorough comparason ... _would be_ very interesting"
(my emphasis).
(3) J. Holland, "Genetic algorithms and adaptation", pp. 317-33 in
ADAPTIVE CONTROL OF ILL-DEFINED SYSTEMS, 1984, Ed. O. Selfridge, E. Rissland,
M. A. Arbib. Page 319 has:
"In brief, and very roughly, a genetic algorithm can be looked
upon as a sampling procedure that draws samples from the set C; each
sample drawn has a value, the fitness of the corresponding genotype.
From this point of view the population of individuals at any time t,
call it B(t), is a _set_ of samples drawn from C. The genetic algo-
rithm observes the fitnesses of the individuals in B(t) and uses
this information to generate and test a new set of individuals,
B(t+1). As we will soon see in detail, the genetic algorithm uses
the familiar "reproduction according to fitness" in combination with
crossing over (and other genetic operators) to generate the new
individuals. This process progressively biases the sampling pro-
cedure toward the use of _combinations_ of alleles associated with
above-average fitness. Surprisingly, in a population of size M, the
algorithm effectively exploits some multiple of M^3 combinations in
exploring C. (We shall soon see how this happens.) For populations
of more than a few individuals this number, M^3, is vastly greater
than the total number of alleles in the population. The correspond-
ing speedup in the rate of searching C, a property called _implicit
parallelism_, makes possible very high rates of adaptation. Moreover,
because a genetic algorithm uses a distributed database (the popu-
lation) to generate new samples, it is all but immune to some of the
difficulties -- false peaks, discontinuities, high-dimensionality,
etc. -- that commonly attend complex problems."
Well, _I_ shall soon close here, but first the few examples of applications
that I know of (the situation reminds me of the joke about the two rubes
visiting New York for the first time, getting off the bus with all of
$2.50. What to do? One takes the money, disappears into a drugstore
and reappears having bought a box of Tampax. Quoth he, "With tampax,
you can do _anything_!) Anyway:
o As noted, the TSP is a canonical candidate.
o A student of Holland has implemented a control algorithm for
a gas pipe-line center, which monitors and adaptively controls flow
rates based on cyclic usages and arbitrary, even ephemeral, constraints.
o Of course, some students have done some real (biological) population
genetics studies, which I note are a tad more plausible than the usual
haploid, deterministic equations.
o Byte mag. has run a few articles, e.g. 'Predicting International
Events' and 'A bit-mapped Classifier' (both 10/86).
o Artificial animals are being modelled in artificial worlds. (When
will the Vivarium let some their animated blimps ("fish") be so programmed?)
Finally, I noted above that the production rules take system inputs as
bit-strings. This representation allows for induction, and opens up a
large realm of cognitive science issues, addressed by Holland et al in
their newish book, INDUCTION.
Hope this helps. I really would like to hear about other application
areas; pragmatic issues are still unclear in my mind also, but as apparent,
the GA model has intrinsic appeal.
Ron Goldthwaite / UC Davis, Psychology and Animal Behavior
'Economics is a branch of ethics, pretending to be a science;
ethology is a science, pretending relevance to ethics.'