Heuristic Selection for Stochastic Search Optimization: Modeling Solution Quality by Extreme Value Theory

September 2004

Heuristic Selection for Stochastic Search Optimization: Modeling Solution Quality by Extreme Value Theory

Authors:

V. Cicirello and S. F. Smith

Abstract:

The success of stochastic algorithms is often due to their ability to effectively amplify the performance of search heuristics. This is certainly the case with stochastic sampling algorithms such as heuristic-biased stochastic sam- pling (HBSS) and value-biased stochastic sampling (VBSS), wherein a heuristic is used to bias a stochastic policy for choosing among alternative branches in the search tree. One complication in getting the most out of algorithms like HBSS and VBSS in a given problem domain is the need to identify the most effective search heuristic. In many domains, the relative performance of various heuristics tends to vary across different problem instances and no single heuristic domi- nates. In such cases, the choice of any given heuristic will be limiting and it would be advantageous to gain the collective power of several heuristics. Toward this goal, this paper describes a framework for integrating multiple heuristics within a stochastic sampling search algorithm. In its essence, the framework uses online-generated statistical models of the search performance of different base heuristics to select which to employ on each subsequent iteration of the search. To estimate the solution quality distribution resulting from repeated application of a strong heuristic within a stochastic search, we propose the use of models from extreme value theory (EVT). Our EVT-motivated approach is validated on the NP-Hard problem of resource-constrained project scheduling with time win- dows (RCPSP/max). Using VBSS as a base stochastic sampling algorithm, the integrated use of a set of project scheduling heuristics is shown to be competitive with the current best known heuristic algorithm for RCPSP/max and in some cases even improves upon best known solutions to difficult benchmark instances.
@conference{Cicirello-2004-120497,
author = {V. Cicirello And S. F. Smith},
title = {Heuristic Selection for Stochastic Search Optimization: Modeling Solution Quality by Extreme Value Theory},
booktitle = {Proceedings 10th International Conference on Principles and Practice of Constraint Programming (CP '04)},
year = {2004},
month = {September},
pages = {197 - 211},
}
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.