Stochastic heuristic search and evaluation methods for constrained optimization
John L. Bresina, Saul Amarel · 1998
This dissertation is concerned with the process of solving constrained optimization problems via stochastic heuristic search methods. The primary contribution is the definition of a new search framework called Heuristic-Biased Stochastic Sampling (scHBSS). scHBSS employs biased, informed sampling to explore the search space in the neighborhood of the greedy trajectory defined by a given search heuristic. The context in which this approach is best suited is when more knowledge-intensive approaches are not feasible, either due to the lack of the required information or a lack of a cost-effective utilization of the available information. scHBSS is a general, robust, satisficing search-based approach that makes few assumptions about the problem characteristics, does not require much a priori knowledge of the global problem structure, and scales up with problem size. This dissertation is also concerned with characterizing constrained optimization problems and evaluating the problem-solving performance of satisficing methods, like scHBSS, on such problems. A secondary contribution is an evaluation methodology, referred to as the Expected Solution Quality (scESQ) methodology, that accomplishes this. The scESQ methodology employs unbiased stochastic sampling to statistically characterize problems in terms of a probability density function with respect to solution quality. This quality density function serves as a background against which problem solving performance can be meaningfully evaluated, even when optimal solution quality is unknown. If the scQDF's cumulative distribution function is known, the scESQ methodology also provides a dimensionless metric that combines both solution quality and solution generation time. The original motivation for both scHBSS and the scESQ methodology was a real-world application of telescope observation scheduling. scHBSS is an integral part of the deployed scheduling system in operation at Fairborn Observatory. The scHBSS technique is demonstrated and empirically analyzed using the scESQ methodology within this application context. The results demonstrate that scHBSS significantly outperforms the application's gold standard, a dispatch scheduling policy, even though the domain expert fine-tuned the observation requests to make the dispatcher perform well. On every one of the fifty test problems, scHBSS found a better solution than dispatch, in only ten samples; the average improvement was more than one standard deviation.