Abstract
dc:description.abstractRandomized search heuristics such as evolutionary algorithms are general-purposetechniques that have been shown to be effective at solving combinatorial optimiza-tion problems. In this thesis, we use both empirical and theoretical techniques toexamine the use of a simple evolutionary algorithm, the (1+1) EA, applied to com-binatorial optimization problems from graph theory. First, we investigate the evo-lutionary algorithm on problemsk-VertexCover,k-FeedbackVertexSet, andk-OddCycleTransversal, and present Fixed-Parameter Tractable performanceguarantees for the (1+1) EA equipped with a tailored jump-and-repair operator. Wethen follow up with empirical results of the (1+1) EA applied to thek-VertexCoverproblem. Next we move on to investigate the (1+1) EA applied to graceful labeling.We present the first rigorous runtime analysis of an evolutionary algorithm findinggraceful labelings of graphs, and prove polynomial time upper bounds for paths, stars,and complete bipartite graphs with a constant sized partition. To supplement thetheoretical results, we also empirically compare the performance of the (1+1) EA tothat of a complete constraint solver.ii
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Branson, Luke
Subjects
dc:subject × 8Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Citation
- Branson, Luke. (2023). Evolving Solutions to Graph Theory Problems. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/258562.