The Adaptive Memory Feature & the Lamplighter Puzzle

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.