Accession Number:

ADA636870

Title:

Boosting Stochastic Problem Solvers Through Online Self-Analysis of Performance

Descriptive Note:

Doctoral thesis

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST

Personal Author(s):

Report Date:

2003-07-21

Pagination or Media Count:

221.0

Abstract:

In many combinatorial domains, simple stochastic algorithms often exhibit superior performance when compared to highly customized approaches. Many of these simple algorithms outperform more sophisticated approaches on difficult benchmark problems and often lead to better solutions as the algorithms are taken out of the world of benchmarks and into the real-world. Simple stochastic algorithms are often robust, scalable problem solvers. This thesis explores methods for combining sets of heuristics within a single stochastic search. The ability of stochastic search to amplify heuristics is often a key factor in its success. Heuristics are not, however, infallible and in most domains no single heuristic dominates. It is therefore desirable to gain the collective power of a set of heuristics and to design a search control framework capable of producing a hybrid algorithm from component heuristics with the ability to customize itself to a given problem instance. A primary goal is to explore what can be learned from quality distributions of iterative stochastic search in combinatorial optimization domains and to exploit models of quality distributions to enhance the performance of stochastic problem solvers. We hypothesize that models of solution quality can lead to effective search control mechanisms, providing a general framework for combining multiple heuristics into an enhanced decision-making process. These goals lead to the development of a search control framework, called QD-BEACON that uses online-generated statistical models of search performance to effectively combine search heuristics. A prerequisite goal is to develop a suitable stochastic sampling algorithm for combinatorial search problems. This goal leads to the development of an algorithm called VBSS that makes better use, in general, of the discriminatory power of a given search heuristic as compared to existing sampling approaches.

Subject Categories:

  • Numerical Mathematics
  • Statistics and Probability
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE