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 sampling (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 dominates. 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 windows (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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bresina, J.L.: Heuristic-biased stochastic sampling. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence and the Eighth Innovative Applications of Artificial Intelligence Conference, vol. 1, pp. 271–278. AAAI Press, Menlo Park (1996)
Cicirello, V.A., Smith, S.F.: Amplification of search performance through randomization of heuristics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 124–138. Springer, Heidelberg (2002)
Cicirello, V.A.: Boosting Stochastic Problem Solvers Through Online Self-Analysis of Performance. PhD thesis, The Robotics Institute, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA (2003); Also available as technical report CMU-RI-TR-03-27
Goldberg, D., Cicirello, V., Dias, M.B., Simmons, R., Smith, S., Stentz, A.: Market-based multi-robot planning in a distributed layered architecture. In: Multi-Robot Systems: From Swarms to Intelligent Automata: Proceedings of the 2003 International Workshop on Multi- Robot Systems, Washington, DC, vol. 2, pp. 27–38. Kluwer Academic Publishers, Dordrecht (2003)
Allen, J.A., Minton, S.: Selecting the right heuristic algorithm: Runtime performance predictors. In: Proceedings of the Canadian AI Conference (1996)
Cowling, P., Kendall, G., Soubeiga, E.: Hyperheuristics: A tool for rapid prototyping in scheduling and optimisation. In: Cagnoni, S., Gottlieb, J., Hart, E., Middendorf, M., Raidl, G.R. (eds.) EvoIASP 2002, EvoWorkshops 2002, EvoSTIM 2002, EvoCOP 2002, and EvoPlan 2002. LNCS, vol. 2279, pp. 1–10. Springer, Heidelberg (2002)
Nareyek, A.: Choosing search heuristics by non-stationary reinforcement learning. In: Resende, M.G.C., de Sousa, J.P. (eds.) Metaheuristics: Computer Decision Making, Kluwer Academic Publishers, Dordrecht (2003)
Gomes, C.P., Selman, B.: Algorithm portfolios. Artificial Intelligence 126, 43–62 (2001)
Talukdar, S., Baerentzen, L., Gove, A., de Souza, P.: Asynchronous teams: Cooperation schemes for autonomous agents. Journal of Heuristics 4, 295–321 (1998)
Gomes, C.P., Selman, B., Crato, N.: Heavy-tailed distributions in combinatorial search. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 121–135. Springer, Heidelberg (1997)
Bresina, J., Drummond, M., Swanson, K.: Expected solution quality. In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pp. 1583–1590. Morgan Kaufmann, San Francisco (1995)
Coles, S.: An Introduction to Statistical Modeling of Extreme Values. Springer, Heidelberg (2001)
Hosking, J.R.M.: Algorithm AS 215: Maximum-likelihood estimation of the paramaters of the generalized extreme-value distribution. Applied Statistics 34, 301–310 (1985)
Silverman, B.W.: Density Estimation for Statistics and Data Analysis. Monographs on Statistics and Applied Probability. Chapman and Hall, Boca Raton (1986)
Epanechnikov, V.A.: Non-parametric estimation of a multivariate probability density. Theory of Probability and Its Applications 14, 153–158 (1969)
NIST/SEMATECH: e-Handbook of Statistical Methods. NIST/SEMATECH (2003), http://www.itl.nist.gov/div898/handbook/
Kaelbling, L.P., Littman, M.L., Moore, A.W.: Reinforcement learning: A survey. Journal of Artificial Intelligence Research 4, 237–285 (1996)
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983)
Dorndorf, U., Pesch, E., Phan-Huy, T.: A time-oriented branch-and-bound algorithm for resource-constrained project scheduling with generalised precedence constraints. Management Science 46, 1365–1384 (2000)
Franck, B., Neumann, K., Schwindt, C.: Truncated branch-and-bound, scheduleconstruction, and schedule-improvement procedures for resource-constrained project scheduling. OR Spektrum 23, 297–324 (2001)
Neumann, K., Schwindt, C., Zimmermann, J.: Project Scheduling with Time Windows and Scarce Resources: Temporal and Resource-Constrained Project Scheduling with Regular and Nonregular Objective Functions. Lecture Notes in Economics and Mathematical Systems. Springer, Heidelberg (2002)
Cesta, A., Oddi, A., Smith, S.F.: A constraint-based method for project scheduling with time windows. Journal of Heuristics 8, 109–136 (2002)
Franck, B., Neumann, K.: Resource-constrained project scheduling with time windows: Structural questions and priority-rule methods. Technical Report WIOR-492, Universität Karlsruhe, Karlsruhe, Germany (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cicirello, V.A., Smith, S.F. (2004). Heuristic Selection for Stochastic Search Optimization: Modeling Solution Quality by Extreme Value Theory. In: Wallace, M. (eds) Principles and Practice of Constraint Programming – CP 2004. CP 2004. Lecture Notes in Computer Science, vol 3258. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30201-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-30201-8_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23241-4
Online ISBN: 978-3-540-30201-8
eBook Packages: Springer Book Archive