Main content

The Adaptive Memory Feature & the Lamplighter Puzzle

Show full item record

Title: The Adaptive Memory Feature & the Lamplighter Puzzle
Author: Gregor, Connor
Department: Department of Mathematics and Statistics
Program: Mathematics and Statistics
Advisor: Ashlock, DanielWillms, Allan
Abstract: This thesis discusses the adaptive memory feature: a sub-routine that can be implemented alongside evolutionary algorithms. This feature gradually changes the fitness landscape of an evolutionary algorithm during its run, or even over the course of many runs. The feature is intended to be used to prune local optima from the search space or prevent the algorithm from finding the same global optima across multiple runs. Adaptive memory is incorporated into evolutionary algorithms that can be applied towards a suite of diverse problems; by comparing the adaptive memory version of an evolutionary algorithm with a standard algorithm that is acting on the same suite it is shown how the feature allows for more valuable results to be obtained while only adding a negligible amount of computational cost to the algorithm. One specific problem used for the testing of adaptive memory is the lamplighter puzzle, a single-player discrete time step game; the puzzle is derived from the lamplighter group. A portion of this thesis is dedicated toward verifying whether or not an arbitrary instance of the lamplighter puzzle is solvable. The properties that are required in order to verify solvability prove to be quite mathematically interesting, and so this thesis explains them in detail. The results of this thesis allow one to quickly confirm whether a large subset of instances are solvable without requiring the use of an exhaustive search algorithm.
Date: 2021-12
Terms of Use: All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.

Files in this item

Files Size Format View
Gregor_Connor_202112_PhD.pdf 11.35Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record