ERA

Download the full-sized PDF of A Theoretical and Empirical Analysis of ∝ -ary Landscapes for Genetic AlgorithmsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3G44HX3V

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

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

Descriptions

Author or creator
Lichtner, Jonathan
Additional contributors
Subject/Keyword
Genetic Algorithms
∝-ary landscapes
Type of item
Computing Science Technical Report
Computing science technical report ID
TR97-04
Language
English
Place
Time
Description
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 to ``multary'' strings, and generalize our algorithm to generate this code in constant amortized time per codeword.
Date created
1997
DOI
doi:10.7939/R3G44HX3V
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-29T16:38:56.801+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1303169
Last modified: 2015:10:12 21:21:06-06:00
Filename: TR97-04.pdf
Original checksum: 855ee959c99db57e9792b19610d14c1d
Well formed: true
Valid: true
Page count: 93
Activity of users you follow
User Activity Date