Boosting Stochastic Problem Solvers Through Online Self-Analysis of Performance

Vincent Cicirello
doctoral dissertation, tech. report CMU-RI-TR-03-27, Robotics Institute, Carnegie Mellon University, July, 2003

  • Adobe portable document format (pdf) (2MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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

Text Reference
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

BibTeX Reference
   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",
   number= "CMU-RI-TR-03-27",
   address= "Pittsburgh, PA",