The Robotics Institute

• Adobe portable document format (pdf) (2MB)

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.