Searchscapes and Genetic Algorithms

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