An experimental investigation of model-based parameter optimisation: SPO and beyond

ABSTRACT

This work experimentally investigates model-based approaches for optimising the performance of parameterised randomised algorithms. We restrict our attention to procedures based on Gaussian process models, the most widely-studied family of models for this problem. We evaluated two approaches from the literature, and found that sequential parameter optimisation (SPO) [4] offered the most robust performance. We then investigated key design decisions within the SPO paradigm, characterising the performance consequences of each. Based on these findings, we propose a new version of SPO, dubbed SPO⁺, which extends SPO with a novel intensification procedure and log-transformed response values. Finally, in a domain for which performance results for other (model-free) parameter optimisation approaches are available, we demonstrate that SPO+ achieves state-of-the-art performance.

REFERENCES

• 1: Belarmino Adenso-Diaz , Manuel Laguna, Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search, Operations Research, v.54 n.1, p.99-114, January-February 2006 [doi>10.1287/opre.1050.0243]
• 2: Charles Audet , Dominique Orban, Finding Optimal Algorithmic Parameters Using Derivative-Free Optimization, SIAM Journal on Optimization, v.17 n.3, p.642-664, September 2006 [doi>10.1137/040620886]
• 3: P. Balaprakash, M. Birattari, and T. Stützle. Improvement strategies for the f-race algorithm: Sampling design and iterative refinement. In T. Bartz-Beielstein, M. J. Blesa Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, and M. Sampels, editors, 4th International Workshop on Hybrid Metaheuristics (MH'07), pages 108--122, 2007.
• 4: Thomas Bartz-Beielstein, Experimental Research in Evolutionary Computation: The New Experimentalism (Natural Computing Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: T. Bartz-Beielstein, C. Lasarczyk, and M. Preuss. Sequential parameter optimization. In B. McKay et al, editor, Proc. of CEC-05, pages 773--780. IEEE Press, 2005.
• 6: T. Bartz-Beielstein, C. Lasarczyk, and M. Preuss. Sequential parameter optimization toolbox. Manual version 0.5, September 2008, available at http://www.gm.fh-koeln.de/imperia/md/content/personen/lehrende/bartz_beielstein_thomas/spotdoc.pdf, 2008.
• 7: T. Bartz-Beielstein and M. Preuss. Considerations of budget allocation for sequential parameter optimization (SPO). In L. Paquete et al., editor, Proc. of EMAA-06, pages 35--40, 2006.
• 8: B. Beachkofski and R. Grandhi. Improved distributed hypercube sampling. American Institute of Aeronautics and Astronautics Paper 2002-1274, 2002.
• 9: Mauro Birattari , Thomas Stützle , Luis Paquete , Klaus Varrentrapp, A Racing Algorithm for Configuring Metaheuristics, Proceedings of the Genetic and Evolutionary Computation Conference, p.11-18, July 09-13, 2002
• 10: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 11: Steven P. Coy , Bruce L. Golden , George C. Runger , Edward A. Wasil, Using Experimental Design to Find Effective Parameter Settings for Heuristics, Journal of Heuristics, v.7 n.1, p.77-97, January 2001 [doi>10.1023/A:1026569813391]
• 12: N. Hansen. The CMA evolution strategy: a comparing review. In J.A. Lozano, P. Larranaga, I. Inza, and E. Bengoetxea, editors, Towards a new evolutionary computation. Advances on estimation of distribution algorithms, pages 75--102. Springer, 2006.
• 13: N. Hansen and S. Kern. Evaluating the CMA evolution strategy on multimodal test functions. In X. Yao et al., editors, Parallel Problem Solving from Nature PPSN VIII, volume 3242 of LNCS, pages 282--291. Springer, 2004.
• 14: N. Hansen and A. Ostermeier. Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation. In Proc. of CEC-96, pages 312--317. Morgan Kaufmann, 1996.
• 15: D. Huang , T. T. Allen , W. I. Notz , N. Zeng, Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models, Journal of Global Optimization, v.34 n.3, p.441-466, March 2006 [doi>10.1007/s10898-005-2454-3]
• 16: F. Hutter, H. Hoos, K. Leyton-Brown, and T. Stützle. ParamILS: An automatic algorithm configuration framework. Technical Report TR-2009-01, University of British Columbia, January 2009.
• 17: F. Hutter, H. H. Hoos, and T. Stützle. Automatic algorithm configuration based on local search. In Proc. of AAAI-07, pages 1152--1157, 2007.
• 18: Frank Hutter , Dave A. D. Tompkins , Holger H. Hoos, Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.233-248, September 09-13, 2002
• 19: Donald R. Jones , Matthias Schonlau , William J. Welch, Efficient Global Optimization of Expensive Black-Box Functions, Journal of Global Optimization, v.13 n.4, p.455-492, December 1998 [doi>10.1023/A:1008306431147]
• 20: Kevin Leyton-Brown , Eugene Nudelman , Yoav Shoham, Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.556-572, September 09-13, 2002
• 21: J. Sacks, W. J. Welch, T. J. Welch, and H. P. Wynn. Design and analysis of computer experiments. Statistical Science, 4(4):409--423, November 1989.
• 22: T. J. Santner, B. J. Williams, and W. I. Notz. The Design and Analysis of Computer Experiments. Springer Verlag, New York, 2003.
• 23: M. Schonlau, W. J. Welch, and D. R. Jones. Global versus local search in constrained optimization of computer models. In N. Flournoy, W.F. Rosenberger, and W.K. Wong, editors, New Developments and Applications in Experimental Design, volume 34, pages 11--25. Institute of Mathematical Statistics, Hayward, California, 1998.
• 24: D. A. D. Tompkins and H. H. Hoos. Ubcsat: An implementation and experimentation environment for SLS algorithms for SAT&MAX-SAT. In Proc. of SAT-04, 2004.
• 25: B. J. Williams, T. J. Santner, and W. I. Notz. Sequential design of computer experiments to minimize integrated response functions. Statistica Sinica, 10:1133--1152, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
active learning, gaussian processes, noisy optimization, parameter tuning, sequential experimental design