Searchscapes and Genetic Algorithms
(Click to view)
This research is mostly aimed at trying to better understand how
genetic algorithms search, and in particular the interactions and
relationships between mutation and recombination in Genetic
Algorithms. It started with the development of the GIGA program, which
was intended to violate the underlying assumptions of the Schema
Theorem, while yet remaining a Genetic Algorithm. Basically, this is
accomplished by having the offspring replace their parents in pairs.
One significant feature of this algorithm is that it does not use mutation,
and instead relies solely on crossover operations to generate new
individuals.
Together with the selection and replacement policy
this enforces a type of genetic invariance, in that in each
locus the set of available bits remains always the same. This means
that the population cannot converge in the usual sense.
-
TR92-02: Genetic Invariance: A New Paradigm for Genetic Algorithm Design
-
Joseph Culberson
-
TR92-06: GIGA Program Description and Operation
-
Joseph Culberson
Michael Lewchuk explored a special case in which selection
is also restricted so that no bias towards better individuals is ever
used. The only way in which improvement can be achieved is via
something akin to diffusion. Selection is now restricted to choosing
the pair in the population which are closest to each other in value.
-
TR92-05: Genetic Invariance: A New Approach to Genetic Algorithms
In TR92-02 I observed that there is a simple isomorphism between
the search spaces induced by binary
mutation and by binary crossover on pairs of complementary strings.
In that document this achieved the status of a footnote, with the observation
that this could be used to perhaps convert from easy to hard problems.
I began to realize the significance of this observation
about the time of the following notice.
-
Crossover versus mutation: fueling the debate: TGA versus GIGA.
-
Joseph Culberson
In Stephanie Forrest, Editor, Proceedings of the Fifth
International Conference on Genetic Algorithms, page 632,1993
The following note describes the application of this program to Holland's Royal
Road function. These results indicate
that this view of one of the roles of crossover is
quite compatible with the GIGA approach.
-
Holland's Royal Road and GIGA
- Joseph Culberson
In
Genetic Algorithms Digest Thursday, Aug 26, 1993 Volume 7 : Issue 23
Notions of searchscapes and the use of isomorphism
led to the following paper, wherein the equivalence of the
two operators on trivial populations is used to transform functions
that are
easy/hard for one operator to others that are equally easy/hard for the other.
These are then tested in larger population GAs to gain insight into the role of
crossover in those larger populations.
-
Mutation-Crossover Isomorphisms and the Construction of
Discriminating Functions
-
Joseph Culberson
Evolutionary Computation, 2(3), 279-311, 1994.
Wolpert and Macready's
No Free Lunch Theorems for Search have initiated some
interesting controversy. In the following report I take
a look at the NFL from the viewpoint of adversary arguments,
then discuss the relation of NFL to standard complexity
theory. These adversary arguments originally started in a discussion over coffee
with Gregory Rawlins.
-
On the Futility of Blind Search
- Joseph Culberson, University of Alberta technical report TR96-18.
A followup to the isomorphism paper, joint work with
Jonathan Lichtner,
the next paper looks more closely at landscape analysis, notes some
pitfalls, and extends the isomorphisms to larger alphabets.
It also uses refined notions of adversaries that are less formidable than the
blind search adversary. It hints at some measures of operator graphs that might
be useful to observe when designing any heuristic search.
-
On Searching A-ary
Hypercubes and Related Graphs
-
Joseph Culberson and Jonathan Lichtner
Foundations of Genetic Algorithms IV
August 3-5, 1996. Univ. San Diego
Jonathan Lichtner explored extensions to this analysis,
as well as other insights into GAs.
in random graph problems.
His
thesis can be found here
(ftp://ftp.cs.ualberta.ca/pub/TechReports/1997/TR97-04/)
Gregory Hornby
developed a visualization tool, and studied the correlations of
real valued operators with landscape features.
Joseph Culberson
Aug 8, 1997