SpringerLink
Log in

A hyper-heuristic guided by a probabilistic graphical model for single-objective real-parameter optimization

  • Original Article
  • Published:
International Journal of Machine Learning and Cybernetics Aims and scope Submit manuscript

Abstract

Metaheuristics algorithms are designed to find approximate solutions for challenging optimization problems. The success of the algorithm over a given optimization task relies on the suitability of its search heuristics for the problem-domain. Thus, the design of custom metaheuristic algorithms leads to more accurate solutions. Hyper-heuristics (HH) are important tools commonly used to select low-level heuristics (LLHs) to solve a specific problem. HH are able to acquire knowledge from the problems where they are used. However, as other artificial intelligence tools it is necessary to identify how the knowledge affects the performance of the algorithm. One way to generate such knowledge is to capture interactions between variables using probabilistic graphical models such as Bayesian networks (BN) in conjunction with estimation of distribution algorithms (EDA). This article presents a method based on that used an EDA based on BN as a high-level selection mechanism for HH called Hyper-heuristic approach based on Bayesian learning and evolutionary operators (HHBNO). Here the knowledge is extracted form BN to evolve the sequences of LLHs in an online learning process by exploring the inter-dependencies among the LLHs. The proposes approach is tested over CEC’17 set of benchmark function of single-objective real-parameter optimization. Statical tests verifies that the HHBNO  presents competitive results in comparison with other metaheuristic algorithms with high performance in terms of convergence. The generated BN is further visually investigated to display the acquired knowledge during the evolutionary process, and it is constructed with the probabilities of each LLHs.

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
Fig. 15

Similar content being viewed by others

References

  1. Finkel DE (2005) Global optimization with the DIRECT algorithm. North Carolina State University, Raleigh

    Google Scholar 

  2. Baker CA, Watson LT, Grossman BM, Mason WH, Haftka RT (2000) Parallel global aircraft configuration design space exploration. Department of Computer Science, Virginia Polytechnic Institute & State University

  3. Jones DR, Schonlau M, Welch WJ (1998) Efficient global optimization of expensive black-box functions. J Glob Optim 13(4):455–492

    Article  MathSciNet  MATH  Google Scholar 

  4. Regis RG, Shoemaker CA (2005) Constrained global optimization of expensive black box functions using radial basis functions. J Glob Optim 31(1):153–171

    Article  MathSciNet  MATH  Google Scholar 

  5. Jones DR (2001) A taxonomy of global optimization methods based on response surfaces. J Glob Optim 21(4):345–383

    Article  MathSciNet  MATH  Google Scholar 

  6. Strongin RG, Sergeyev YD (1992) Global multidimensional optimization on parallel computer. Parallel Comput 18(11):1259–1273

    Article  MathSciNet  MATH  Google Scholar 

  7. Kvasov DE, Sergeyev YD (2015) Deterministic approaches for solving practical black-box global optimization problems. Adv Eng Softw 80:58–66

    Article  Google Scholar 

  8. Paulavičius R, Žilinskas J (2014) Simplicial Global Optimization. Springer, Berlin

    Book  MATH  Google Scholar 

  9. Glover FW, Kochenberger GA (2006) Handbook of Metaheuristics, vol 57. Springer, Berlin

    MATH  Google Scholar 

  10. Nesmachnow S (2014) An overview of metaheuristics: accurate and efficient methods for optimisation. Int J Metaheuristics 3(4):320–347

    Article  Google Scholar 

  11. Sabar NR, Ayob M, Kendall G, Qu R (2014) Automatic design of a hyper-heuristic framework with gene expression programming for combinatorial optimization problems. IEEE Trans Evolut Comput 19(3):309–325

    Article  Google Scholar 

  12. Drake JH, Hyde M, Ibrahim K, Ozcan E (2014) A genetic programming hyper-heuristic for the multidimensional knapsack problem. Kybernetes 43(9/10):1500–1511

    Article  Google Scholar 

  13. Ross P (2005) Hyper-Heuristics. In: Burke EK, Kendall G (eds) Search Methodologies. Springer, Boston, MA. https://doi.org/10.1007/0-387-28356-0_17

  14. Burke EK, Gendreau M, Hyde M, Kendall G, Ochoa G, Özcan E, Qu R (2013) Hyper-heuristics: a survey of the state of the art. J Oper Res Soc 64(12):1695–1724

    Article  Google Scholar 

  15. García S, Luengo J, Herrera F (2015) Data preprocessing in data mining. Springer, Berlin

    Book  Google Scholar 

  16. El Yafrani M, Martins M, Wagner M, Ahiod B, Delgado M, Lüders R (2018) A hyperheuristic approach based on low-level heuristics for the travelling thief problem. Genet Program Evolvable Mach 19(1):121–150

    Article  Google Scholar 

  17. Ferreira TN, Lima JAP, Strickler A, Kuk JN, Vergilio SR, Pozo A (2017) Hyper-heuristic based product selection for software product line testing. IEEE Comput Intell Mag 12(2):34–45

    Article  Google Scholar 

  18. Cao P, Fan Z, Gao R, Tang J (2017) A manufacturing oriented single point search hyper-heuristic scheme for multi-objective optimization. In: International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Vol. 58134, American Society of Mechanical Engineers, pp V02BT03A031

  19. Li W, Özcan E, John R (2017) A learning automata-based multiobjective hyper-heuristic. IEEE Transactions on Evolutionary Computation 23(1):59–73

    Article  Google Scholar 

  20. Asta S, Özcan E (2015) A tensor-based selection hyper-heuristic for cross-domain heuristic search. Inf Sci 299:412–432

    Article  Google Scholar 

  21. Choong SS, Wong L-P, Lim CP (2018) Automatic design of hyper-heuristic based on reinforcement learning. Inf Sci 436:89–107

    Article  MathSciNet  Google Scholar 

  22. Mühlenbein H, Paass G (1996) September). From recombination of genes to the estimation of distributions I. Binary parameters. Springer, Berlin, Heidelberg, pp 178–187

    Google Scholar 

  23. Koller D, Friedman N (2009) Probabilistic Graphical Models: Principles and Techniques. The MIT Press, Cambridge

    MATH  Google Scholar 

  24. Qu R, Pham N, Bai R, Kendall G (2015) Hybridising heuristics within an estimation distribution algorithm for examination timetabling. Appl Intell 42(4):679–693

    Article  Google Scholar 

  25. Uludag G, Kiraz B, Uyar AŞE, Özcan E (2012) Heuristic selection in a multi-phase hybrid approach for dynamic environments. In: 2012 12th UK Workshop on Computational Intelligence (UKCI), IEEE, pp 1–8

  26. Martins MSR, El Yafrani M, Delgado MRBS, Wagner M, Ahiod B, Lüders R (2017) HSEDA: a heuristic selection approach based on estimation of distribution algorithm for the travelling thief problem. In: Proceedings of the genetic and evolutionary computation conference. GECCO’17, pp 361–368. ACM, New York

  27. Awad N, Ali M, Liang J, Qu B, Suganthan P (2016) Problem definitions and evaluation criteria for the CEC 2017 special session and competition on single objective real-parameter numerical optimization. Nanyang Technological University, Jordan University of Science and Technology and Zhengzhou University, Singapore and Zhenzhou, China, Technical Report 201611

  28. Cuesta-Cañada A, Garrido L, Terashima-Marín H (2005) Building hyper-heuristics through ant colony optimization for the 2D bin packing problem. In: Proceedings of the 9th international conference, KES 2005. Springer, Melbourne, pp 654–660

  29. Burke EK, Hyde M, Kendall G, Ochoa G, Özcan E, Woodward JR (2010) A Classification of Hyper-heuristic Approaches. Springer, Boston, pp 449–468

    Google Scholar 

  30. Sosa-Ascencio A, Ochoa G, Terashima-Marin H, Conant-Pablos SE (2016) Grammar-based generation of variable-selection heuristics for constraint satisfaction problems. Genet Program Evolvable Mach 17(2):119–144

    Article  Google Scholar 

  31. Drake JH, Hyde M, Ibrahim K, Ozcan E (2014) A genetic programming hyper-heuristic for the multidimensional knapsack problem. Kybernetes 43(9/10):1500–1511

    Article  Google Scholar 

  32. Cowling P, Kendall G, Soubeiga E (2000) A hyperheuristic approach to scheduling a sales summit. In: Proceedings of the third international conference on practice and theory of automated timetabling, PATAT 2000. Springer, Konstanz, pp 176–190

  33. Cowling P, Kendall G, Soubeiga E (2001) A parameter-free hyperheuristic for scheduling a sales summit. In: Proceedings of the 4th Metaheuristic International Conference, MIC, Vol. 2001, pp 127–131

  34. Krasnogor N, Smith J (2001) Emergence of profitable search strategies based on a simple inheritance mechanism. In: Proceedings of the 3rd annual conference on genetic and evolutionary computation. GECCO’01. Morgan Kaufmann Publishers Inc., San Francisco, pp 432–439

  35. Burke EK, Kendall G, Soubeiga E (2003) A Tabu-search hyperheuristic for timetabling and rostering. J Heuristics 9(6):451–470

    Article  Google Scholar 

  36. Ross P, Marín-Blázquez JG, Schulenburg S, Hart E (2003) Learning a procedure that can solve hard bin-packing problems: a new GA-based approach to hyper-heuristics. In: Proceedings of the genetic and evolutionary computation 2003, GECCO’03. Springer, Chicago, pp 1295–1306

  37. Dowsland KA, Soubeiga E, Burke E (2007) A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation. Eur J Oper Res 179(3):759–774

    Article  MATH  Google Scholar 

  38. Ahmed L, Mumford C, Kheiri A (2019) Solving urban transit route design problem using selection hyper-heuristics. Eur J Oper Res 274(2):545–559. https://doi.org/10.1016/j.ejor.2018.10.022

    Article  MathSciNet  MATH  Google Scholar 

  39. Wei D, Wang F, Ma H (2019) Autonomous path planning of AUV in large-scale complex marine environment based on swarm hyper-heuristic algorithm. Appl Sci 9(13):2654

    Article  Google Scholar 

  40. Qin W, Zhuang Z, Huang Z, Huang H (2021) A novel reinforcement learning-based hyper-heuristic for heterogeneous vehicle routing problem. Comput Ind Eng 156:107252. https://doi.org/10.1016/j.cie.2021.107252

    Article  Google Scholar 

  41. Lin J, Li Y-Y, Song H-B (2022) Semiconductor final testing scheduling using q-learning based hyper-heuristic. Expert Syst Appl 187:115978

    Article  Google Scholar 

  42. Song H-B, Lin J (2021) A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times. Swarm Evolut Comput 60:100807

    Article  MathSciNet  Google Scholar 

  43. Hong L, Woodward JR, Özcan E, Liu F (2021) Hyper-heuristic approach: automatically designing adaptive mutation operators for evolutionary programming. Complex Intell Syst 7(6):3135–3163

    Article  Google Scholar 

  44. Cruz-Duarte JM, Amaya I, Ortiz-Bayliss JC, Conant-Pablos SE, Terashima-Marín H, Shi Y (2021) Hyper-heuristics to customise metaheuristics for continuous optimisation. Swarm Evolut Comput 66:100935

    Article  Google Scholar 

  45. Olgun B, Koç Ç, Altıparmak F (2021) A hyper heuristic for the green vehicle routing problem with simultaneous pickup and delivery. Comput Ind Eng 153:107010

    Article  Google Scholar 

  46. de Carvalho VR, Özcan E, Sichman JS (2021) Comparative analysis of selection hyper-heuristics for real-world multi-objective optimization problems. Appl Sci 11(19):9153

    Article  Google Scholar 

  47. Larrañaga P, Lozano JA (2002) Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, vol 2. Springer, Dordrecht

    MATH  Google Scholar 

  48. Martins MSR, Delgado MRBS, Santana R, Lüders R, Gonçalves RA, de Almeida CP (2016) HMOBEDA: hybrid multi-objective Bayesian estimation of distribution algorithm. In: Proceedings of the 2016 on genetic and evolutionary computation conference. GECCO’16. ACM, New York, pp 357–364

  49. Martins MS, Delgado M, Lüders R, Santana R, Gonçalves RA, de Almeida CP (2018) Exploring the probabilistic graphic model of a hybrid multi-objective Bayesian estimation of distribution algorithm. Appl Soft Comput 73:328–343

    Article  Google Scholar 

  50. Scoczynski M, Delgado M, Lüders R, Oliva D, Wagner M, Sung I, El Yafrani M (2021) Saving computational budget in Bayesian network-based evolutionary algorithms. Nat Comput 20(4):775–790

    Article  MathSciNet  Google Scholar 

  51. Martins MS, Yafrani ME, Delgado M, Lüders R, Santana R, Siqueira HV, Akcay HG, Ahiod B (2021) Analysis of Bayesian network learning techniques for a hybrid multi-objective Bayesian estimation of distribution algorithm: a case study on MNK landscape. J Heuristics 27(4):549–573

    Article  Google Scholar 

  52. Pearl J (1988) Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, San Mateo

    MATH  Google Scholar 

  53. Bengoetxea E (2002) Inexact graph matching using estimation of distribution algorithms. PhD thesis, University of the Basque Country, Basque Country

  54. De Campos LM, Fernández-Luna JM, Huete JF, Rueda-Morales MA (2010) Combining content-based and collaborative recommendations: a hybrid approach based on Bayesian networks. Int J Approx Reason 51(7):785–799

    Article  Google Scholar 

  55. Smith JQ, Daneshkhah A (2010) On the robustness of Bayesian networks to learning from non-conjugate sampling. Int J Approx Reason 51(5):558–572

    Article  MathSciNet  MATH  Google Scholar 

  56. Cheng Y, Diakonikolas I, Kane D, Stewart A (2018) Robust learning of fixed-structure Bayesian networks. Advances in Neural Information Processing Systems, 31

  57. Cooper G, Herskovits E (1992) A Bayesian method for the induction of probabilistic networks from data. Mach Learn 9(4):309–347

    Article  MATH  Google Scholar 

  58. Tsamardinos I, Aliferis CF, Statnikov AR, Statnikov E (2003) Algorithms for large scale Markov blanket discovery. In: FLAIRS conference, vol 2. AAAI Press, St. Augustine, pp 376–380

  59. Colombo D, Maathuis MH (2014) Order-independent constraint-based causal structure learning. J Mach Learn Res 15(1):3741–3782

    MathSciNet  MATH  Google Scholar 

  60. Scutari M, Ness R (2012) bnlearn: Bayesian network structure learning, parameter learning and inference. R package version 3

  61. Tsamardinos I, Brown LE, Aliferis CF (2006) The max-min hill-climbing Bayesian network structure learning algorithm. Mach Learn 65(1):31–78

    Article  MATH  Google Scholar 

  62. Moran S, He Y, Liu K (2009) Choosing the best Bayesian classifier: an empirical study. IAENG Int J Comput Sci 36(4):322–331

    Google Scholar 

  63. Behjati S, Beigy H (2020) Improved k2 algorithm for Bayesian network structure learning. Eng Appl Artif Intell 91:103617

    Article  Google Scholar 

  64. Eshelman LJ, Schaffer JD (1993) Real-coded genetic algorithms and interval-schemata. In: Foundations of genetic algorithms, vol 2. Elsevier, Amsterdam, pp 187–202

  65. Deb K, Joshi D, Anand A (2002) Real-coded evolutionary algorithms with parent-centric recombination. In: Proceedings of the 2002 Congress on evolutionary computation. CEC’02 (Cat. No. 02TH8600), vol 1. IEEE, New York, pp 61–66

  66. Ortiz-Boyer D, Hervás-Martínez C, García-Pedrajas N (2007) Improving crossover operator for real-coded genetic algorithms using virtual parents. J Heuristics 13(3):265–314

    Article  Google Scholar 

  67. Deb K, Beyer H-G (2001) Self-adaptive genetic algorithms with simulated binary crossover. Evolut Comput 9(2):197–221

    Article  Google Scholar 

  68. Ono I (1997) Real-coded genetic algorithm for function optimization using unimodal normal distribution crossover. In: Proceedings of 7th ICGA, pp 246–253

  69. Kita H, Ono I, Kobayashi S (2000) Multi-parental extension of the unimodal normal distribution crossover for real-coded genetic algorithms. Trans Soc Instrum Control Eng 36(10):875–883

    Article  Google Scholar 

  70. Deb K (2005) A population-based algorithm-generator for real-parameter optimization. Soft Comput 9(4):236–253

    Article  MATH  Google Scholar 

  71. Tizhoosh HR (2005) Opposition-based learning: a new scheme for machine intelligence. In: International conference on computational intelligence for modelling, control and automation, 2005 and international conference on intelligent agents, web technologies and internet commerce, vol 1. IEEE, New York, pp 695–701

  72. Higashi N, Iba H (2003) Particle swarm optimization with Gaussian mutation. In: Proceedings of the 2003 IEEE swarm intelligence symposium. SIS’03 (Cat. No. 03EX706). IEEE, New York, pp 72–79

  73. Esquivel SC, Coello CC (2003) On the use of particle swarm optimization with multimodal functions. In: The 2003 Congress on evolutionary computation, 2003. CEC’03, vol 2. IEEE, New York, pp 1130–1136

  74. Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs. Springer, Berlin

    Book  MATH  Google Scholar 

  75. Qin AK, Huang VL, Suganthan PN (2008) Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evolut Comput 13(2):398–417

    Article  Google Scholar 

  76. Eberhart R, Kennedy J (1995) Particle swarm optimization. In: Proceedings of the IEEE international conference on neural networks, Vol. 4, pp. 1942–1948

  77. Lipowski A, Lipowska D (2012) Roulette-wheel selection via stochastic acceptance. Phys A Stat Mech Appl 391(6):2193–2196

    Article  Google Scholar 

  78. Thierens D, Goldberg D (1994) Convergence models of genetic algorithm selection schemes. In: International conference on parallel problem solving from nature. Springer, Berlin, pp 119–129

  79. Goldberg DE (2006) Genetic algorithms. Pearson Education India, Delhi

    Google Scholar 

  80. Civicioglu P (2012) Transforming geocentric Cartesian coordinates to geodetic coordinates by using differential search algorithm. Comput Geosci 46:229–247

    Article  Google Scholar 

  81. Auger A, Hansen N (2012) Tutorial CMA-ES: evolution strategies and covariance matrix adaptation. In: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation, pp 827–848

  82. Gharehchopogh FS, Gholizadeh H (2019) A comprehensive survey: Whale Optimization Algorithm and its applications. Swarm Evol Comput 48:1–24

    Article  Google Scholar 

  83. Mirjalili SM, Mirjalili SZ, Saremi S, Mirjalili S (2020) Sine cosine algorithm: theory, literature review, and application in designing bend photonic crystal waveguides. Nature-inspired optimizers, pp 201–217

  84. Mohamed AW, Hadi AA, Mohamed AK (2020) Gaining-sharing knowledge based algorithm for solving optimization problems: a novel nature-inspired algorithm. Int J Mach Learn Cybern 11(7):1501–1529

    Article  Google Scholar 

  85. Heckerman D, Geiger D, Chickering D (1995) Learning Bayesian networks: the combination of knowledge and statistical data. Mach Learn 20(3):197–243

    Article  MATH  Google Scholar 

  86. DeGroot MH (2005) Optimal statistical decisions, vol 82. Wiley, New York

    MATH  Google Scholar 

  87. Henrion M (1988) Propagating uncertainty in Bayesian networks by probabilistic logic sampling. In: Machine intelligence and pattern recognition, North-Holland, vol 5, pp 149–163

  88. Conover WJ (1999) Practical nonparametric statistics, 3rd edn. Wiley, New York

    Google Scholar 

  89. Casella G, Berger RL (2001) Statistical inference, 2nd edn. Duxbury

  90. Fan G-F, Yu M, Dong S-Q, Yeh Y-H, Hong W-C (2021) Forecasting short-term electricity load using hybrid support vector regression with grey catastrophe and random forest modeling. Util Policy 73:101294

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Depto. de Innovación Basada en la Información y el Conocimiento, Universidad de Guadalajara, CUCEI, (UDG), Guadalajara, Mexico

    Diego Oliva

  2. Federal University of Technology-Paraná (UTFPR), Curitiba, Brazil

    Marcella S. R. Martins

  3. School of Engineering and Sciences, Tecnologico de Monterrey (ITESM), Zapopan, Mexico

    Salvador Hinojosa

  4. Faculty of Computer Science and Engineering, Galala University (GU), Suez, Egypt

    Mohamed Abd Elaziz

  5. Department of Mathematics, Faculty of Science, Zagazig University (ZU), Zagazig, Egypt

    Mohamed Abd Elaziz

  6. Universidade Federal de Goiás (UFG), Goiânia, Brazil

    Paulo Victor dos Santos & Gelson da Cruz

  7. Hakin Sabzevari University (HSU), Sabzevar, Iran

    Seyed Jalaleddin Mousavirad

  8. Universidade da Beira Interior, Covilha, Portugal

    Seyed Jalaleddin Mousavirad

Authors
  1. Diego Oliva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marcella S. R. Martins
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Salvador Hinojosa
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mohamed Abd Elaziz
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Paulo Victor dos Santos
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Gelson da Cruz
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Seyed Jalaleddin Mousavirad
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Diego Oliva.

Ethics declarations

Conflict of interest

None of the authors of this paper have a financial or personal relationship with other people or organizations that could inappropriately influence or bias the content of the paper. It is to specifically state that “No Competing interests are at stake and there is No Conflict of Interest” with other people or organizations that could inappropriately influence or bias the content of the paper.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Publisher's Note

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

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file1 (PDF 2966 kb)

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Oliva, D., Martins, M.S.R., Hinojosa, S. et al. A hyper-heuristic guided by a probabilistic graphical model for single-objective real-parameter optimization. Int. J. Mach. Learn. & Cyber. 13, 3743–3772 (2022). https://doi.org/10.1007/s13042-022-01623-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13042-022-01623-6

Keywords

Search

Navigation