SpringerLink
Log in

Automated parameter tuning as a bilevel optimization problem solved by a surrogate-assisted population-based approach

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

This work presents a proposal for the automated parameter tuning problem (APTP) modeled as a bilevel optimization problem. Different definitions and theoretical results are given in order to formalize the APTP in the context of this hierarchical optimization problem. The obtained bilevel optimization problem is solved via a population-based algorithm added with surrogate models to identify promising regions in the parameter search space. The approach is tested by configuring four representative metaheuristics for numerical optimization on a set of well-known and recent test problems; also a competitive algorithm for a popular combinatorial optimization problem was configured (considering a large benchmark suite). The experimental results are compared against those of a state-of-the-art parameter tuning method called IRACE. The results, validated by the Bayesian signed-rank statistical test, indicate that BCAP, even it is based on an usually costly model (i.e. a bilevel optimization problem), with only half of the calls to the target algorithm, is able to find better configurations than those obtained by the compared approach.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

References

  1. Eiben AE, Smit SK (2011) Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm Evol Comput 1(1):19–31

    Article  Google Scholar 

  2. Hoos HH (2011) Automated algorithm configuration and parameter tuning. In: Autonomous search. Springer, pp 37–71

  3. Yuan B, Gallagher M (2004) Statistical racing techniques for improved empirical evaluation of evolutionary algorithms. In: international conference on parallel problem solving from nature. Springer, pp 172–181

  4. Birattari M, Kacprzyk J (2009) Tuning metaheuristics: a machine learning perspective, vol 197. Springer

  5. López-Ibáñez M, Dubois-Lacoste J, Pérez-Cáceres L, Birattari M, Stützle T (2016) The irace package: Iterated racing for automatic algorithm configuration. Oper Res Perspect 3:43–58

    MathSciNet  Google Scholar 

  6. Smit SK, Eiben AE (2009) Comparing parameter tuning methods for evolutionary algorithms. In: 2009 IEEE congress on evolutionary computation. IEEE, pp 399–406

  7. Yuan B, Gallagher M (2007) Combining meta-eas and racing for difficult ea parameter tuning tasks. In: Parameter setting in evolutionary algorithms. Springer, pp 121–142

  8. Hutter F, Hoos HH (2007) Automatic algorithm configuration based on local search. In: Proceedings of the 22nd national conference on artificial intelligence Vol. 2. AAAI Press, pp 1152–1157

  9. Hutter F, Hoos HH, Leyton-Brown K, Stützle T (2009) Paramils: an automatic algorithm configuration framework. J Artif Intell Res 36:267–306

    Article  Google Scholar 

  10. El-Beltagy MA, Nair PB, Keane AJ (1999) Metamodeling techniques for evolutionary optimization of computationally expensive problems: Promises and limitations. In: Proceedings of the 1st annual conference on genetic and evolutionary computation-volume 1. Morgan Kaufmann Publishers Inc.,x pp 196–203

  11. Sinha A, Malo P, Deb K (2018) A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Trans Evol Comput 22(2):276–295

    Article  Google Scholar 

  12. Sinha A, Malo P, Xu P, Deb K (2014) A bilevel optimization approach to automated parameter tuning. In: Proceedings of the 2014 annual conference on genetic and evolutionary computation. ACM, pp 847–854

  13. Andersson M, Bandaru S, Ng AHC, Syberfeldt A (2015) Parameter tuned cma-es on the cec’15 expensive problems. In: 2015 IEEE congress on evolutionary computation (CEC). IEEE, pp 1950–1957

  14. Andersson M, Bandaru S, Ng AHC (2016) Tuning of multiple parameter sets in evolutionary algorithms. In: Proceedings of the genetic and evolutionary computation conference 2016. ACM, pp 533–540

  15. Adenso-Diaz B, Laguna M (2006) Fine-tuning of algorithms using fractional experimental designs and local search. Oper Res 54(1):99–114

    Article  Google Scholar 

  16. Bartz-Beielstein T, Lasarczyk CWG, Preuß M (2005) Sequential parameter optimization. In: 2005 IEEE congress on evolutionary computation, vol 1. IEEE, pp 773–780

  17. Birattari M, Stützle T, Paquete L, Varrentrapp K (2002) A racing algorithm for configuring metaheuristics. In: Proceedings of the 4th annual conference on genetic and evolutionary computation. Morgan Kaufmann Publishers Inc., pp 11–18

  18. Gómez-Santillán C, Cruz-Reyes L, Rivera-Zarate G, GonzálezBarbosa J, Quiroz-Castellanos M (2012) Impact of initial tuning for algorithm that solve query routing. In: Casillas J, Martínez-López FJ, CorchadoRodríguez JM (eds) Management Intelligent Systems. Springer, Berlin, pp 315–323

  19. Hutter F, Hoos HH, Leyton-Brown K (2011) Sequential model-based optimization for general algorithm configuration. In: International conference on learning and intelligent optimization. Springer, pp 507–523

  20. Hutter F, Hoos HH, Leyton-Brown K, Murphy K (2010) Time-bounded sequential parameter optimization. In: International conference on learning and intelligent optimization. Springer, pp 281–298

  21. Rangel-Valdez N, Torres-Jiménez J, Bracho-Ríos J, Quiz-Ramos P (2009) Problem and algorithm fine-tuning-a case of study using bridge club and simulated annealing. In: IJCCI, pp 302–305

  22. Coy SP, Golden BL, Runger GC, Wasil EA (2001) Using experimental design to find effective parameter settings for heuristics. J Heurist 7(1):77–97

    Article  Google Scholar 

  23. Ansótegui C, Sellmann M, Tierney K (2009) A gender-based genetic algorithm for the automatic configuration of algorithms. In: International conference on principles and practice of constraint programming. Springer, pp 142–157

  24. Torres-Jimenez J, Izquierdo-Marquez I, Garcia-Robledo A, Gonzalez-Gomez A, Bernal J, Kacker RN (2015) A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs. Inf Sci 303:33–49

    Article  MathSciNet  Google Scholar 

  25. Bagchi TP (1993) Taguchi methods explained: Practical steps to robust design. Prentice-Hall

  26. Myers R, Hancock ER (2001) Empirical modelling of genetic algorithms. Evol Comput 9 (4):461–493

    Article  Google Scholar 

  27. Xu J, Chiu SY, Glover F (1998) Fine-tuning a tabu search algorithm with statistical tests. Int Trans Oper Res 5(3):233–244

    Article  Google Scholar 

  28. Michalewicz Z (2013) Genetic algorithms+ data structures= evolution programs. Springer Science & Business Media

  29. Fernandez E, Gomez C, Rivera G, Cruz-Reyes L (2015) Hybrid metaheuristic approach for handling many objectives and decisions on partial support in project portfolio optimisation. Inf Sci 315:102–122

    Article  MathSciNet  Google Scholar 

  30. Carazo AF, Contreras I, Gómez T, Pérez F (2012) A project portfolio selection problem in a group decision-making context. J Ind Manag Optim 8(1):243–261

    MathSciNet  MATH  Google Scholar 

  31. Balaprakash P, Birattari M, Stützle T (2007) Improvement strategies for the f-race algorithm: Sampling design and iterative refinement. In: International workshop on hybrid metaheuristics. Springer, pp 108–122

  32. Birattari M, Yuan Z, Balaprakash P, Stützle T (2010) F-race and iterated f-race: An overview. In: Experimental methods for the analysis of optimization algorithms. Springer, pp 311–336

  33. López-Ibáñez M, Stützle T (2010) Automatic configuration of multi-objective aco algorithms. In: International conference on swarm intelligence. Springer, pp 95–106

  34. Nannen V, Eiben AE (2006) A method for parameter calibration and relevance estimation in evolutionary algorithms. In: Proceedings of the 8th annual conference on Genetic and evolutionary computation. ACM, pp 183–190

  35. Nannen V, Eiben AE (2007) Efficient relevance estimation and value calibration of evolutionary algorithm parameters. In: 2007 IEEE congress on evolutionary computation. IEEE, pp 103–110

  36. Grefenstette JJ (1986) Optimization of control parameters for genetic algorithms. IEEE Trans Syst Man Cybern 16(1):122–128

    Article  Google Scholar 

  37. Smit SK, Eiben AE (2010) Parameter tuning of evolutionary algorithms: Generalist vs. specialist. In: European conference on the applications of evolutionary computation. Springer, pp 542–551

  38. Dréo J (2009) Using performance fronts for parameter setting of stochastic metaheuristics. In: Proceedings of the 11th annual conference companion on genetic and evolutionary computation conference: Late Breaking Papers. ACM, pp 2197–2200

  39. Smit SK, Eiben AE, Szlávik Z (2010) An moea-based method to tune ea parameters on multiple objective functions. In: IJCCI (ICEC), pp 261–268

  40. Dymond AS, Engelbrecht AP, Kok S, Heyns PS (2015) Tuning optimization algorithms under multiple objective function evaluation budgets. IEEE Trans Evol Comput 19(3):341–358

    Article  Google Scholar 

  41. Franceschi L, Frasconi P, Salzo S, Grazzi R, Pontil M (2018) Bilevel programming for hyperparameter optimization and meta-learning. ar**v:1806.04910

  42. Kunapuli G, Bennett KP, Hu J, Pang J-S (2008) Classification model selection via bilevel programming. Optim Methods Softw 23(4):475–489

    Article  MathSciNet  Google Scholar 

  43. Liang JZ, Miikkulainen R (2015) Evolutionary bilevel optimization for complex control tasks. In: Proceedings of the 2015 annual conference on genetic and evolutionary computation, pp 871–878

  44. Eiben AE, Smit SK (2011) Evolutionary algorithm parameters and methods to tune them. In: Autonomous search. Springer, pp 15–36

  45. Storn R, Price K (1995) Differential evolution - a simple and efficient adaptive scheme for global optimization over continuous spaces. ICSI, Berkeley

  46. Dempe S (2002) Foundations of bilevel programming. Springer Science & Business Media

  47. Vicente LN, Calamai PH (1994) Bilevel and multilevel programming: A bibliography review. J Glob Optim 5(3):291–306

    Article  MathSciNet  Google Scholar 

  48. Talbi EG (2013) A taxonomy of metaheuristics for bi-level optimization. In: Metaheuristics for bi-level optimization. Springer, pp 1–39

  49. Von-Stackelberg H (2010) Market structure and equilibrium. Springer Science & Business Media

  50. Bracken J, McGill JT (1973) Mathematical programs with optimization problems in the constraints. Oper Res 21(1):37–44

    Article  MathSciNet  Google Scholar 

  51. Candler W, Norton R (1977) Multilevel programming. Technical Report, vol 20. World Bank Development Research

  52. Back T (1996) Evolutionary algorithms in theory and practice. Oxford University Press

  53. Rao SS (2009) Engineering optimization: theory and practice. Wiley

  54. Chong EKP, Zak SH (2013) An introduction to optimization, vol 76. Wiley

  55. Rardin RL (2016) Optimization in operations research. Prentice Hall

  56. Bard JF (2013) Practical bilevel optimization: algorithms and applications, vol 30. Springer Science & Business Media

  57. Jeroslow RG (1985) The polynomial hierarchy and a simple model for competitive analysis. Math Programm 32(2):146–164

    Article  MathSciNet  Google Scholar 

  58. Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J Sci Stat Comput 13(5):1194–1217

    Article  MathSciNet  Google Scholar 

  59. Vicente L, Savard G, Júdice J (1994) Descent approaches for quadratic bilevel programming. J Optim Theory Appl 81(2):379–399

    Article  MathSciNet  Google Scholar 

  60. Colson B, Marcotte P, Savard G (2007) An overview of bilevel optimization. Ann Oper Res 153(1):235–256

    Article  MathSciNet  Google Scholar 

  61. Forrester AIJ, Keane AJ (2009) Recent advances in surrogate-based optimization. Progress Aerosp Sci 45(1-3):50–79

    Article  Google Scholar 

  62. ** Y (2005) A comprehensive survey of fitness approximation in evolutionary computation. Soft Comput 9(1):3–12

    Article  Google Scholar 

  63. Kotsiantis SB, Zaharakis I, Pintelas P (2007) Supervised machine learning: A review of classification techniques. Emerg Artif Intell Appl Comput Eng 160:3–24

    Google Scholar 

  64. Miranda-Varela ME, Mezura-Montes E (2016) Surrogate-assisted differential evolution with an adaptive evolution control based on feasibility to solve constrained optimization problems. In: Proceedings of fifth international conference on soft computing for problem solving. Springer, pp 809–822

  65. Carpenter WC, Barthelemy JFM (1993) A comparison of polynomial approximations and artificial neural nets as response surfaces. Struct Optim 5(3):166–174

    Article  Google Scholar 

  66. Scholkopf B, Sung KK, Burges CJC, Girosi F, Niyogi P, Poggio T, Vapnik V (1997) Comparing support vector machines with gaussian kernels to radial basis function classifiers. IEEE Trans Signal Process 45(11):2758–2765

    Article  Google Scholar 

  67. Ong YS, Nair PB, Keane AJ (2003) Evolutionary optimization of computationally expensive problems via surrogate modeling. AIAA J 41(4):687–696

    Article  Google Scholar 

  68. Shawe-Taylor J, Cristianini N (2004) Kernel methods for pattern analysis. Cambridge university press

  69. Mühlenstädt T, Kuhnt S (2011) Kernel interpolation. Comput Stat Data Anal 55 (11):2962–2974

    Article  MathSciNet  Google Scholar 

  70. Cheng R, He C, ** Y, Yao X (2018) Model-based evolutionary algorithms: a short survey. Compl Intell Syst 4(4):283–292

    Article  Google Scholar 

  71. Mejía-de Dios JA, Mezura-Montes E (2020) A surrogate-assisted metaheuristic for bilevel optimization. In: Proceedings of the ACM genetic and evolutionary computation conference (GECCO). ACM Press, pp in press

  72. Mejía-de Dios JA, Mezura-Montes E (2019) A new evolutionary optimization method based on center of mass. In: Decision science in action. Springer, pp 65–74

  73. Lewis AS, Overton ML (2013) Nonsmooth optimization via quasi-newton methods. Math Program 141(1-2):135–163

    Article  MathSciNet  Google Scholar 

  74. Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM Rev 59(1):65–98

    Article  MathSciNet  Google Scholar 

  75. Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Technical Report, Technical report-tr06, Erciyes university, engineering faculty, computer engineering department

  76. Kennedy J (1995) Particle swarm optimization. IEEE Int Conf Neural Netw:1942–1948

  77. Quiroz-Castellanos M, Cruz-Reyes L, Torres-Jimenez J, Gómez C, FraireHuacuja HJ, Alvim ACF (2015) A grou** genetic algorithm with controlled gene transmission for the bin packing problem. Comput Oper Res 55:52–64

    Article  MathSciNet  Google Scholar 

  78. Awad NH, Ali MZ, BY Q, Liang JJ, Suganthan PN (2016) Problem definitions and evaluation criteria for the cec 2017 special session and competition on single objective bound constrained real-parameter numerical optimization. Technological University, Singapore, Technical Report, http://www.ntu.edu.sg/home/epnsugan/

  79. Veček N, Mernik M, Filipič B, Črepinšek M (2016) Parameter tuning with chess rating system (crs-tuning) for meta-heuristic algorithms. Inf Sci 372:446–469

    Article  Google Scholar 

  80. Carrasco J, García S, Rueda MM, Das S, Herrera F (2020) Recent trends in the use of statistical tests for comparing swarm and evolutionary computing algorithms: Practical guidelines and a critical review. Swarm Evol Comput 54:100665

    Article  Google Scholar 

  81. Akay B, Karaboga D (2009) Parameter tuning for the artificial bee colony algorithm. In: International conference on computational collective intelligence. Springer, pp 608–619

  82. Gamperle R, Muller SD, Koumoutsakos P (2002) A parameter study for differential evolution. In: WSEAS Int. Conf. on advances in intelligent systems, fuzzy systems, evolutionary computation. Press, pp 293–298

  83. Das S, Mullick SS, Suganthan PN (2016) Recent advances in differential evolution an updated survey. Swarm Evol Comput 27:1–30

    Article  Google Scholar 

  84. Jiang M, Luo YP, Yang SY (2007) Stochastic convergence analysis and parameter selection of the standard particle swarm optimization algorithm. Inf Process Lett 102(1):8–16

    Article  MathSciNet  Google Scholar 

  85. Vanden Bergh F, Engelbrecht AP (2006) A study of particle swarm optimization particle trajectories. Inf Sci 176(8):937–971

    Article  MathSciNet  Google Scholar 

  86. Trelea IC (2003) The particle swarm optimization algorithm: convergence analysis and parameter selection. Inf Process Lett 85(6):317–325

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The first author acknowledges support from CONACyT and the University of Veracruz to pursue graduate studies at the Artificial Intelligence Research Center.

Author information

Authors and Affiliations

  1. Artificial Intelligence Research Center, University of Veracruz, Sebastián Camacho 5, Centro, Xalapa, Veracruz, 91000, México

    Jesús-Adolfo Mejía-de-Dios, Efrén Mezura-Montes & Marcela Quiroz-Castellanos

Authors
  1. Jesús-Adolfo Mejía-de-Dios
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Efrén Mezura-Montes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marcela Quiroz-Castellanos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jesús-Adolfo Mejía-de-Dios.

Ethics declarations

Conflict of interests

The authors declare that they have no conflict of interest.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mejía-de-Dios, JA., Mezura-Montes, E. & Quiroz-Castellanos, M. Automated parameter tuning as a bilevel optimization problem solved by a surrogate-assisted population-based approach. Appl Intell 51, 5978–6000 (2021). https://doi.org/10.1007/s10489-020-02151-y

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-020-02151-y

Keywords

Search

Navigation