Dissertation/Thesis Abstract

On mutation and crossover in the theory of evolutionary algorithms
by Richter, James Neal, Ph.D., Montana State University, 2010, 300; 3403059
Abstract (Summary)

The Evolutionary Algorithm is a population-based metaheuristic optimization algorithm. The EA employs mutation, crossover and selection operators inspired by biological evolution. It is commonly applied to find exact or approximate solutions to combinatorial search and optimization problems.

This dissertation describes a series of theoretical and experimental studies on a variety of evolutionary algorithms and models of those algorithms. The effects of the crossover and mutation operators are analyzed. Multiple examples of deceptive fitness functions are given where the crossover operator is shown or proven to be detrimental to the speedy optimization of a function. While other research monographs have shown the benefits of crossover on various fitness functions, this is one of the few (or only) doing the inverse.

A background literature review is given of both population genetics and evolutionary computation with a focus on results and opinions on the relative merits of crossover and mutation. Next, a family of new fitness functions is introduced and proven to be difficult for crossover to optimize. This is followed by the construction and evaluation of executable theoretical models of EAs in order to explore the effects of parameterized mutation and crossover. These models link the EA to the Metropolis-Hastings algorithm. Dynamical systems analysis is performed on models of EAs to explore their attributes and fixed points. Additional crossover deceptive functions are shown and analyzed to examine the movement of fixed points under changing parameters. Finally, a set of online adaptive parameter experiments with common fitness functions is presented.

Indexing (document details)
Advisor: Paxton, John T., Wright, Alden H.
Commitee: Angryk, Rafal, Gedeon, Tomas, Harkin, Gary, Young, Douglas
School: Montana State University
Department: Computer Science
School Location: United States -- Montana
Source: DAI-B 71/05, Dissertation Abstracts International
Subjects: Mathematics, Computer science
Keywords: Crossover, Evolutionary algorithms, Genetic algorithms, Mutation, Optimization algorithms
Publication Number: 3403059
ISBN: 978-1-109-76076-7
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy