A Theoretical and Empirical Analysis of ∝ -ary Landscapes for Genetic Algorithms

• Author(s) / Creator(s)

  • Lichtner, Jonathan

• Technical report TR97-04. Genetic algorithms (GAs) are probabilistic search algorithms that are loosely based on biological evolution. Analyzing genetic algorithms has proven difficult, for a variety of reasons, but a landscape paradigm that rigorously models the search of GAs has become increasingly popular in their analysis. So far much of this analysis concerns binary representations, where each member of the population is a binary string. In this thesis we consider using ∝-ary representations - using strings where each character can be one of ∝ characters - and conduct a theoretical and empirical study of the resulting ∝-ary landscapes. In terms of theory, we discuss the types of landscape graphs produced by various ∝-ary crossover and ∝-ary mutation operators. We relate these landscapes to a common class of graphs, the ∝-ary hypercubes. We then generalize a binary mutation-crossover isomorphism to higher alphabets and use this isomorphism to show that ∝-ary crossover can simulate ∝-ary mutation. Since crossover can simulate mutation, crossover must be at least as powerful as mutation, in the sense of computational power. Because this ∝-ary mutation-crossover isomorphism is closely related to an ∝-ary Gray code, extending our simulation to hyper orders'' is a generalization of iterating the landscape's representation (and thus the landscape) using this ∝-ary Gray code. If we repeatedly apply this Gray code, the landscapes will eventually cycle. We prove a theorem on the maximum number of landscapes produced when this Gray code is iterated. We explore the long path problem for ∝-ary mutation and ∝-ary crossover. We construct exponentially long distance-preserving paths for ∝-ary mutation, improving on a previous method. We also construct exponentially long distance-preserving paths for crossover between two complementary binary strings, and discuss the problem of creating long distance-preserving paths for populations greater than two. In Chapter 7, we create the schizophrenic function, a function designed to discriminate between mutation and crossover. This function has two optima classes, and is constructed in such a way that mutation should find one optimum, crossover the other. Empirical tests show that the schizophrenic function is a useful but imperfect tool. More importantly, these tests offer insight into how crossover works. Finally, we show how to generate an ∝-ary Gray code efficiently in sequence (constant amortized time per codeword). We generalize this Gray code tomultary'' strings, and generalize our algorithm to generate this code in constant amortized time per codeword. | TRID-ID TR97-04

• Date created

  1997

• Subjects / Keywords

  • ∝-ary landscapes
  • Genetic Algorithms

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3G44HX3V

• License

  Attribution 3.0 International