Beyond benchmarks suites : engineering diagnostic tools to characterize selection schemes

Evolutionary algorithms (EAs) draw inspiration from biological evolution and replicate evolutionary processes into a computational framework that can often solve challenging optimization problems. These algorithms evolve a population of candidate solutions, where the population typically cycles through three phases: evaluation, selection, and reproduction. Specifically, the evaluation phase assesses the qualities of the candidate solutions, the selection phase identifies which regions will be searched further, and the reproduction phase identifies the next positions to search. Clearly, each phase plays a specific role in the evolutionary search that is implemented through one or more interacting components that fully specify the algorithm. Of course, interactions can make it difficult to isolate individual components in some complex EAs. As such, if we want to understand how each component affects the properties of the overall algorithm, we need a framework to formally define each component, and we need tools that characterize how each component contributes to overall problem-solving success. When a new EA is proposed, it is typically evaluated against a benchmark suite or hand-picked test problems that clearly demonstrate its capabilities. Multiple benchmark suites exist to highlight which classes of problems an EA is most effective against. Such suites, however, are limited in their ability to diagnose why an EA performs the way it does. In particular, problems with complex fitness landscapes do not facilitate an intuitive understanding of how an algorithm traverses the search space. At a high level, components in an EA are well-classified for the role they are supposed to play in traversing a search space: evaluation components generate qualities for a candidate solution; selection components use these qualities to identify parents; reproduction components propagate parents and apply variation. However, it is often less clear which particular components would be most effective on a given problem or how different components will alter each other's behavior. Given the importance of component features and interactions, my aim is to disentangle the mechanistic effects of each choice on the search process so that we can better anticipate which combinations of components are most likely to produce an optimal solution to a given problem. In this dissertation, I achieved three synergistic goals: (1) I developed a formal definition for selection scheme components that provides a framework for their study within generational EAs; (2) I crafted a set of diagnostic tools that allow me to isolate the effects of individual selection scheme components within this framework; and (3) I used these diagnostics to characterize the search strategies employed by a set of common selection schemes. In the chapters below, I first present a formal framework for dividing any selection scheme into three fundamental components: population structures, trait processing, and selectors (Chapter 2). Next, I use lexicase selection as the basis of two case studies where I demonstrate how subtle alterations of this selection scheme affect performance on program synthesis problems, sometimes producing dramatic improvements, but leaving many open questions as to when and why these improvements will occur (Chapters 3 and 4). Once this motivation is established, I improve our toolset for understanding selection schemes by developing a set of diagnostics that more precisely and intuitively measure the strengths and weaknesses of a set of schemes (Chapters 5 and 6). Finally, I apply these diagnostics to a new area, island structures, to demonstrate their versatility and expected general usefulness (Chapter 7). This work emphasizes the importance of properly configuring an EA for the problem at hand, and provides a precise and informative contribution to the set of available benchmark suites.