Carnegie Mellon Robotics Institute
doctoral dissertation, tech. report CMU-RI-TR-03-27, Robotics Institute, Carnegie Mellon University, July, 2003
|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.
The search frameworks of this thesis are evaluated on combinatorial optimization problems. Specifically, we show that: 1) VBSS is an effective method for amplifying heuristic performance for the weighted tardiness sequencing problem with sequence-dependent setups; 2) QD-BEACON can enhance the current best known algorithm for weighted tardiness sequencing; and 3) QD-BEACON and VBSS together provide the new best heuristic algorithm for the constrained optimization problem known as RCPSP/max.
Associated Center(s) / Consortia:
Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Reliable Autonomous Systems Lab and Intelligent Coordination and Logistics Laboratory
Associated Project(s): Federation of Intelligent Robotic Explorers Project
|Vincent Cicirello, "Boosting Stochastic Problem Solvers Through Online Self-Analysis of Performance," doctoral dissertation, tech. report CMU-RI-TR-03-27, Robotics Institute, Carnegie Mellon University, July, 2003|
author = "Vincent Cicirello",
title = "Boosting Stochastic Problem Solvers Through Online Self-Analysis of Performance",
booktitle = "",
school = "Robotics Institute, Carnegie Mellon University",
month = "July",
year = "2003",
address= "Pittsburgh, PA",
|The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.|
Contact Us | Update Instructions