Masters Theses

Keywords and Phrases

Automated Design of Algorithms; Black-Box Search Algorithms; Evolutionary Computation; Genetic Programming; Hyper-Heuristics

Abstract

"Within the field of Black-Box Search Algorithms (BBSAs), there is a focus on improving algorithm performance over increasingly diversified problem classes. However, these general purpose problem solvers have no guarantee to perform well on an arbitrary problem class that a practitioner needs to solve. The problem classes that the research in this thesis most applies to are difficult problems that are going to be solved multiple times. BBSAs tailored to one of these problem class can be expected to significantly outperform the more general purpose problem solvers, including canonical Evolutionary Algorithms (EAs). The first paper in this thesis explores a novel method in which these BBSAs can be created through the use of hyper-heuristics.

Hyper-heuristics have the tendency to over-specialize on the problem configuration that it is given rather than generalizing to the problem class. The evolved BBSA should be robust to changes in problem configuration. The second paper in this thesis presents a multi-sample approach geared towards increasing the robustness of the resulting BBSAs.

As with other CI techniques, such as Genetic Programming, hyper-heuristics are affected by the size of the search space. If the hyper-heuristic has too much genetic material, it could cause the search space to be too large to effectively traverse. However if the hyper-heuristic has too little genetic material, it may not be capable of creating a high quality BBSA. The third paper in this thesis explores the scalability of hyper-heuristics as the amount of genetic material is increased. Additionally, this paper explores the impact that the nature of the added primitives have on the performance of the hyper-heuristic. These papers show that hyper-heuristics can be used to evolve BBSAs that perform well on a problem of indiscriminate type"--Abstract, page iv.

Advisor(s)

Tauritz, Daniel R.

Committee Member(s)

Yin, Zhaozheng
Mulder, Samuel

Department(s)

Computer Science

Degree Name

M.S. in Computer Science

Sponsor(s)

Sandia National Laboratories
United States. National Nuclear Security Administration

Comments

Sandia National Laboratories provided funding through their Critical Skills Master's Program. Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the United States Department of Energy's National Nuclear Security Administration under contract DE-AC04-94AL85000.

Publisher

Missouri University of Science and Technology

Publication Date

Fall 2015

Journal article titles appearing in thesis/dissertation

  • Evolving Black-Box Search Algorithms Employing Genetic Programming
  • A Problem Conguration Study of the Robustness of a Black-Box Search Algorithm Hyper-Heuristic
  • Hyper-Heuristics: A Study On Increasing Primitive-Space

Pagination

xiii, 90 pages

Note about bibliography

Includes bibliographical references.

Rights

© 2015 Matthew Allen Martin, All rights reserved.

Document Type

Thesis - Open Access

File Type

text

Language

English

Subject Headings

Evolutionary computationGenetic programming (Computer science)Heuristic algorithms

Thesis Number

T 10793

Electronic OCLC #

936208678

Download

Share

 
COinS