Doctoral Dissertations

Date of Award

12-2000

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Computer Science

Major Professor

Michael D. Vose

Committee Members

Brad Zanden

Abstract

A theoretical framework is constructed to analyze the behavior of all determin-istic non-repeating search algorithms as they apply to all possible functions of a given finite domain and range. A population table data structure is introduced for this purpose, and many properties of the framework are discovered, including the number of deterministic non-repeating search algorithms. Canonical forms are pre-sented for all elements of the framework, as well as methods for converting between the objects and their canonical numbers and back again. The theorems regarding population tables allow for a simple, alternate form of the No Free Lunch (NFL) theorem, an important theorem regarding search algorithm performance over all functions. Previously, this theorem has only been proven in overly-complicated, confusing fashion. Other statements of the NFL theorem are shown in the light of this framework and the theorem is extended to non-complete sets of functions and to a non-trivial definition of stochastic search. The framework allows for an extensive study of minimax distinctions between search algorithms. A change of representation is easily expressed in the framework with obvious performance im-plications. The expected performance of random search with replacement, random search without replacement, and enumeration will be studied in some detail. Claims in the field regarding search algorithm robustness will be tested empirically. Experiments were performed to determine how the compressibility of a function impacts its performance, with an emphasis on randomly selected functions. A genetic algorithm was run on two sets of functions: one set contained functions that were known to be compressible, and the other contained functions that had a high probability of being incompressible. Performance was found to be the same for both sets.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS