Date of Award

Spring 5-23-2021

Document Type

Honors Thesis

Department

Computer Science

First Advisor

Grant Braught

Language

English

Abstract

Genetic Algorithms (GAs) are a branch of search algorithms popularly used due to their ability to find near optimal solutions in reasonable amounts of time. The algorithm itself stems from the Darwinian Theory of natural evolution. Within the GA, much research has been done to discover ways by which its performance can be improved. One direction of research aims at replacing the randomly generated numbers used in creating the initial population/solution, crossover, and mutation with a chaotic mapping. In addition, other papers report on ways that evolution can improve performance by self-adapting the mutation and crossover operators over time. In this paper, the distribution of values generated by chaotic maps are investigated to explain the performance differences between the Chaos Genetic Algorithm (CGA) and the standard Genetic Algorithm. Of particular interest is the use of the chaotic map parameter values used in the CGA’s mutation that produce explorative or exploitative distributions of values. We propose the hypothesis that it is these distributions of values used for mutations, rather than the chaotic properties of the maps used, that explains differences in performance. A model and set of experiments that investigates this hypothesis are proposed and carried out. The same model is used to investigate the possibility of self-adaptation of chaotic map parameters. iv Based on the results of the investigation of the chaotic map distributions, the distributions of mutation sizes can indeed explain the behavior of the CGA relative to the GA. In addition, experiments show that self-adaptation of the chaotic map parameter is possible and consistent with the observed effects of mutation size distributions.

COinS