Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Identifying Key Algorithm Parameters and Instance Features Using Forward Selection

  • Conference paper
  • First Online:
Learning and Intelligent Optimization (LION 2013)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7997))

Included in the following conference series:

Abstract

Most state-of-the-art algorithms for large-scale optimization problems expose free parameters, giving rise to combinatorial spaces of possible configurations. Typically, these spaces are hard for humans to understand. In this work, we study a model-based approach for identifying a small set of both algorithm parameters and instance features that suffices for predicting empirical algorithm performance well. Our empirical analyses on a wide variety of hard combinatorial problem benchmarks (spanning SAT, MIP, and TSP) show that—for parameter configurations sampled uniformly at random—very good performance predictions can typically be obtained based on just two key parameters, and that similarly, few instance features and algorithm parameters suffice to predict the most salient algorithm performance characteristics in the combined configuration/feature space. We also use these models to identify settings of these key parameters that are predicted to achieve the best overall performance, both on average across instances and in an instance-specific way. This serves as a further way of evaluating model quality and also provides a tool for further understanding the parameter space. We provide software for carrying out this analysis on arbitrary problem domains and hope that it will help algorithm developers gain insights into the key parameters of their algorithms, the key features of their instances, and their interactions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    A further advantage of forward selection is that it can be used in combination with arbitrary modeling techniques. Although here, we focus on using our best-performing model, random forests, we also provide summary results for other model types.

  2. 2.

    In fact, it also applies to classification algorithms and has, e.g., been used to derive classifiers for predicting the solubility of SAT instances based on 1–2 features [30].

  3. 3.

    In fact, in many cases, the best setting of the key parameters were their default values.

References

  1. Hutter, F., Hoos, H.H., Leyton-Brown, K.: Automated configuration of mixed integer programming solvers. In: Proceedings of CPAIOR-10, pp. 186–202 (2010)

    Google Scholar 

  2. Nannen, V., Eiben, A.E.: Relevance estimation and value calibration of evolutionary algorithm parameters. In: Proceedings of IJCAI-07, pp. 975–980 (2007)

    Google Scholar 

  3. Ansotegui, C., Sellmann, M., Tierney, K.: A gender-based genetic algorithm for the automatic configuration of solvers. In: Proceedings of CP-09, pp. 142–157 (2009)

    Google Scholar 

  4. Birattari, M., Yuan, Z., Balaprakash, P., Stützle, T.: F-race and iterated F-race: an overview. In: Bartz-Beielstein, T., Chiarandini, M., Paquete, L., Preuss, M. (eds.) Empirical Methods for the Analysis of Optimization Algorithms. Springer, Heidelberg (2010)

    Google Scholar 

  5. Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. JAIR 36, 267–306 (2009)

    MATH  Google Scholar 

  6. Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: Coello, C.A.C. (ed.) LION 5. LNCS, vol. 6683, pp. 507–523. Springer, Heidelberg (2011)

    Google Scholar 

  7. Hutter, F., Hoos, H.H., Leyton-Brown, K.: Parallel algorithm configuration. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, vol. 7219, pp. 55–70. Springer, Heidelberg (2012)

    Google Scholar 

  8. Hutter, F., Babić, D., Hoos, H.H., Hu, A.J.: Boosting verification by automatic tuning of decision procedures. In: Proceedings of FMCAD-07, pp. 27–34 (2007)

    Google Scholar 

  9. Chiarandini, M., Fawcett, C., Hoos, H.: A modular multiphase heuristic solver for post enrolment course timetabling. In: Proceedings of PATAT-08 (2008)

    Google Scholar 

  10. Vallati, M., Fawcett, C., Gerevini, A.E., Hoos, H.H., Saetti, A.: Generating fast domain-optimized planners by automatically configuring a generic parameterised planner. In: Proceedings of ICAPS-PAL11 (2011)

    Google Scholar 

  11. Ridge, E., Kudenko, D.: Sequential experiment designs for screening and tuning parameters of stochastic heuristics. In: Proceedings of PPSN-06, pp. 27–34 (2006)

    Google Scholar 

  12. Chiarandini, M., Goegebeur, Y.: Mixed models for the analysis of optimization algorithms. In: Bartz-Beielstein, T., Chiarandini, M., Paquete, L., Preuss, M. (eds.) Experimental Methods for the Analysis of Optimization Algorithms, pp. 225–264. Springer, Berlin (2010)

    Chapter  Google Scholar 

  13. Bartz-Beielstein, T.: Experimental Research in Evolutionary Computation: The New Experimentalism. Natural Computing Series. Springer, Berlin (2006)

    Google Scholar 

  14. Finkler, U., Mehlhorn, K.: Runtime prediction of real programs on real machines. In: Proceedings of SODA-97, pp. 380–389 (1997)

    Google Scholar 

  15. Fink, E.: How to solve it automatically: selection among problem-solving methods. In: Proceedings of AIPS-98, pp. 128–136. AAAI Press (1998)

    Google Scholar 

  16. Howe, A.E., Dahlman, E., Hansen, C., Scheetz, M., Mayrhauser, A.: Exploiting competitive planner performance. In: Biundo, S., Fox, M. (eds.) ECP 1999. LNCS, vol. 1809, pp. 62–72. Springer, Heidelberg (2000)

    Google Scholar 

  17. Leyton-Brown, K., Nudelman, E., Shoham, Y.: Learning the Empirical Hardness of Optimization Problems. In: Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 556–572. Springer, Heidelberg (2002)

    Google Scholar 

  18. Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)

    Article  Google Scholar 

  19. Smith-Miles, K.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. 41(1), 6:1–6:25 (2009)

    Google Scholar 

  20. Smith-Miles, K., Lopes, L.: Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res. 39(5), 875–889 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  21. Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for SAT. JAIR 32, 565–606 (2008)

    MATH  Google Scholar 

  22. Hutter, F., Hamadi, Y., Hoos, H.H., Leyton-Brown, K.: Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 213–228. Springer, Heidelberg (2006)

    Google Scholar 

  23. Hutter, F., Xu, L., Hoos, H.H., Leyton-Brown, K.: Algorithm runtime prediction: the state of the art. CoRR, abs/1211.0906 (2012)

    Google Scholar 

  24. Smith-Miles, K., van Hemert, J.: Discovering the suitability of optimisation algorithms by learning from evolved instances. AMAI 61, 87–104 (2011)

    MATH  Google Scholar 

  25. Bartz-Beielstein, T., Markon, S.: Tuning search algorithms for real-world applications: a regression tree based approach. In: Proceedings of CEC-04, pp. 1111–1118 (2004)

    Google Scholar 

  26. Bishop, C.M.: Pattern recognition and machine learning. Springer, New York (2006)

    MATH  Google Scholar 

  27. Rasmussen, C.E., Williams, C.K.I.: Gaussian Processes for Machine Learning. MIT Press, Cambridge (2006)

    MATH  Google Scholar 

  28. Breiman, L.: Random forests. Mach. Learn. 45(1), 5–32 (2001)

    Article  MATH  Google Scholar 

  29. Leyton-Brown, K., Nudelman, E., Shoham, Y.: Empirical hardness models: methodology and a case study on combinatorial auctions. J. ACM 56(4), 1–52 (2009)

    Article  MathSciNet  Google Scholar 

  30. Xu, L., Hoos, H.H., Leyton-Brown, K.: Predicting satisfiability at the phase transition. In: Proceedings of AAAI-12 (2012)

    Google Scholar 

  31. Friedman, J.: Multivariate adaptive regression splines. Ann. Stat. 19(1), 1–141 (1991)

    Article  MATH  Google Scholar 

  32. IBM Corp.: IBM ILOG CPLEX Optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/ (2012). Accessed 27 Oct 2012

  33. Babić, D., Hutter, F.: Spear theorem prover. Solver description SAT competition (2007)

    Google Scholar 

  34. Helsgaun, K.: General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1(2–3), 119–163 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  35. Styles, J., Hoos, H.H., Müller, M.: Automatically configuring algorithms for scaling performance. In: Hamadi, Y., Schoenauer, M. (eds.) LION 6. LNCS, vol. 7219, pp. 205–219. Springer, Heidelberg (2012)

    Google Scholar 

  36. Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. JMLR 13, 281–305 (2012)

    MathSciNet  Google Scholar 

  37. Wang, Z., Zoghi, M., Hutter, F., Matheson, D., de Freitas, N.: Bayesian optimization in a billion dimensions via random embeddings. ArXiv e-prints, January (2013). arXiv:1301.1942

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of British Columbia, 2366 Main Mall, Vancouver BC, V6T 1Z4, Canada

    Frank Hutter, Holger H. Hoos & Kevin Leyton-Brown

Authors
  1. Frank Hutter
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Holger H. Hoos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kevin Leyton-Brown
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kevin Leyton-Brown .

Editor information

Editors and Affiliations

  1. Università Catania Dipto. Matematica e Informatica, Catania, Italy

    Giuseppe Nicosia

  2. Industrial & Systems Engineering, University of Florida, Gainesville, Florida, USA

    Panos Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hutter, F., Hoos, H.H., Leyton-Brown, K. (2013). Identifying Key Algorithm Parameters and Instance Features Using Forward Selection. In: Nicosia, G., Pardalos, P. (eds) Learning and Intelligent Optimization. LION 2013. Lecture Notes in Computer Science(), vol 7997. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-44973-4_40

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-44973-4_40

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-44972-7

  • Online ISBN: 978-3-642-44973-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation