research-article

A runtime analysis of simple hyper-heuristics: to mix or not to mix operators

Authors:

Per Kristian Lehre,

Ender ÖzcanAuthors Info & Claims

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

Pages 97 - 104

https://doi.org/10.1145/2460239.2460249

Published: 16 January 2013 Publication History

Abstract

There is a growing body of work in the field of hyper-heuristics. Hyper-heuristics are high level search methodologies that operate on the space of heuristics to solve hard computational problems. A frequently used hyper-heuristic framework mixes a predefined set of low level heuristics during the search process. While most of the work on such selection hyper-heuristics in the literature are empirical, we analyse the runtime of hyper-heuristics rigorously. Our initial analysis shows that mixing heuristics could lead to exponentially faster search than individual (deterministically chosen) heuristics on chosen problems. Both mixing of variation operators and mixing of acceptance criteria are investigated on some selected problems. It is shown that mixing operators is only efficient with the right mixing distribution (parameter setting). Additionally, some of the existing adaptation mechanisms for mixing operators are also evaluated.

References

[1]

A. Auger and B. Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing Co., Inc., River Edge, NJ, USA, 2011.

Digital Library

[2]

E. Burke, G. Kendall, M. Mısır, and E. Özcan. Monte carlo hyper-heuristics for examination timetabling. Annals of Operations Research, 196:73--90, 2012.

[3]

E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and J. R. Woodward. A classification of hyper-heuristic approaches. In M. Gendreau and J.-Y. Potvin, editors, Handbook of Metaheuristics, volume 146 of International Series in Operations Research and Management Science, pages 449--468. Springer, 2010.

[4]

E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Özcan, and R. Qu. Hyper-heuristics: A survey of the state of the art. Technical Report NOTTCS-TR-SUB-0906241418-2747, School of Computer Science, University of Nottingham, 2010.

[5]

K. Chakhlevitch and P. I. Cowling. Hyperheuristics: Recent developments. In Adaptive and Multilevel Metaheuristics, volume 136 of Studies in Computational Intelligence, pages 3--29. Springer, 2008.

[6]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. McGraw Hill, New York, NY, 2nd edition, 2001.

Digital Library

[7]

P. Cowling, G. Kendall, and E. Soubeiga. A hyper-heuristic approach to scheduling a sales summit. In Practice and Theory of Automated Timetabling III: Third International Conference, PATAT 2000, volume 2079 of LNCS. Springer, 2000.

Digital Library

[8]

P. Cowling, G. Kendall, and E. Soubeiga. Hyperheuristics: A tool for rapid prototyping in scheduling and optimisation. In S. Cagoni, J. Gottlieb, E. Hart, M. Middendorf, and R. Goenther, editors, Applications of Evolutionary Computing: Proceeding of Evo Workshops 2002, volume 2279 of Lecture Notes in Computer Science, pages 1--10, Kinsale, Ireland, April 3-4 2002. Springer-Verlag.

Digital Library

[9]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) Evolutionary Algorithm. Theoretical Computer Science, 276:51--81, 2002.

Digital Library

[10]

W. Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, New York, 1968.

[11]

J. Gibbs, G. Kendall, and E. Özcan. Scheduling english football fixtures over the holiday period using hyper-heuristics. In Proceedings of the 11th international conference on Parallel problem solving from nature: Part I, PPSN'10, pages 496--505, Berlin, Heidelberg, 2010. Springer-Verlag.

Digital Library

[12]

O. Giel and I. Wegener. Maximum cardinality matchings on trees by randomized local search. In Proceedings of the 8th annual conference on Genetic and evolutionary computation, GECCO '06, pages 539--546, New York, NY, USA, 2006. ACM.

Digital Library

[13]

J. He, F. He, and H. Dong. Pure strategy or mixed strategy? - an initial comparison of their asymptotic convergence rate and asymptotic hitting time. In J.-K. Hao and M. Middendorf, editors, Evolutionary Computation in Combinatorial Optimization - 12th European Conference, EvoCOP 2012, Málaga, Spain, April 11--13, 2012. Proceedings, volume 7245 of Lecture Notes in Computer Science, pages 218--229. Springer, 2012.

Digital Library

[14]

J. He and X. Yao. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3(1):21--35, 2004.

Digital Library

[15]

T. Jansen. On the analysis of dynamic restart strategies for evolutionary algorithms. In J. J. M. Guervós, P. Adamidis, H.-G. Beyer, J. L. F.-V. Martín, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature PPSN VII, volume 2439 of Lecture Notes in Computer Science, pages 33--43. Springer Berlin / Heidelberg, 2002.

Digital Library

[16]

T. Jansen and I. Wegener. Evolutionary algorithms - how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Transactions on Evolutionary Computation, 5(6):589--599, 2001.

Digital Library

[17]

I. Maden, A. S. Uyar, and E. Özcan. Landscape analysis of simple perturbative hyper-heuristics. In Mendel 2009: 15th International Conference on Soft Computing, pages 16--22, 2009.

[18]

M. Mısır. Group decision making in hyper-heuristics. Master's thesis, Department of Computer Engineering, Yeditepe University, 2008.

[19]

M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and GA performance. In F. J. Varela and P. Bourgine, editors, Proceedings of the First European Conference on Artificial Life, 1991, pages 245--254, Paris, 11-13 1992. MIT Press.

[20]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[21]

A. Nareyek. Choosing search heuristics by non-stationary reinforcement learning. In M. G. C. Resende, J. P. de Sousa, and A. Viana, editors, Metaheuristics, pages 523--544. Kluwer Academic Publishers, Norwell, MA, USA, 2004.

Digital Library

[22]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer-Verlag New York, Inc., New York, NY, USA, 1st edition, 2010.

Digital Library

[23]

G. Ochoa, R. Qu, and E. K. Burke. Analyzing the landscape of a graph based hyper-heuristic for timetabling problems. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, GECCO '09, pages 341--348, New York, NY, USA, 2009. ACM.

Digital Library

[24]

G. Ochoa, J. A. Vázquez-Rodríguez, S. Petrovic, and E. Burke. Dispatching rules for production scheduling: a hyper-heuristic landscape analysis. In Proceedings of the Eleventh conference on Congress on Evolutionary Computation, CEC'09, pages 1873--1880, Piscataway, NJ, USA, 2009. IEEE Press.

Digital Library

[25]

E. Özcan, B. Bilgin, and E. E. Korkmaz. A comprehensive analysis of hyper-heuristics. Intelligent Data Analysis, 12:3--23, 2008.

Digital Library

[26]

E. Özcan, M. Mısır, G. Ochoa, and E. Burke. A reinforcement learning -- great-deluge hyper-heuristic for examination timetabling. International Journal of Applied Metaheuristic Computing (IJAMC), 1(1):39--59, 2010.

[27]

D. Pisinger and S. Ropke. A general heuristic for vehicle routing problems. Computers and Operations Research, 34:2403-- 2435, 2007.

Digital Library

[28]

P. Ross. Hyper-heuristics. In E. K. Burke and G. Kendall, editors, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, chapter 17, pages 529--556. Springer, 2005.

[29]

T. Storch and I. Wegener. Real royal road functions for constant population size. Theoretical Computer Science, 320(1):123--134, 2004.

Digital Library

Cited By

Zheng WDoerr BWooldridge MDy JNatarajan S(2024)Runtime analysis of the SMS-EMOA for many-objective optimizationProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i18.30077(20874-20882)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i18.30077
Dang DOpris ASudholt D(2024)Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective OptimisationArtificial Intelligence10.1016/j.artint.2024.104098(104098)Online publication date: Feb-2024
https://doi.org/10.1016/j.artint.2024.104098
Doerr BDremaux ALutzeyer JStumpf ASilva SPaquete L(2023)How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and CliffsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590509(990-999)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590509
Show More Cited By

Index Terms

A runtime analysis of simple hyper-heuristics: to mix or not to mix operators
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

A comparative study of hyper-heuristics for solving the school timetabling problem
SAICSIT '13: Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference

Hyper-heuristics have proven to be an effective means of obtaining generalized solutions to optimization problems. One such domain in which they have been a success is educational timetabling. However, all the research in this area has focused on ...
Selection Hyper-Heuristic Using a Portfolio of Derivative Heuristics
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Generally, we distinguish between two classes of hyper-heuristic approaches, heuristic selection and heuristic generation. The former one works with existing heuristics and tries to find their optimal order for solving the instance. The later approach ...
Batched Mode Hyper-heuristics
LION 7: Revised Selected Papers of the 7th International Conference on Learning and Intelligent Optimization - Volume 7997

A primary role for hyper-heuristics is to control search processes based on moves generated by neighbourhood operators. Studies have shown that such hyper-heuristics can be effectively used, without modification, for solving unseen problem instances not ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

January 2013

198 pages

ISBN:9781450319904

DOI:10.1145/2460239

General Chairs:
Frank Neumann
The University of Adelaide, Australia
,
Kenneth De Jong
George Mason University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '13

Sponsor:

SIGEVO

FOGA '13: Foundations of Genetic Algorithms XII

January 16 - 20, 2013

Adelaide, Australia

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
205
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zheng WDoerr BWooldridge MDy JNatarajan S(2024)Runtime analysis of the SMS-EMOA for many-objective optimizationProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i18.30077(20874-20882)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i18.30077
Dang DOpris ASudholt D(2024)Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective OptimisationArtificial Intelligence10.1016/j.artint.2024.104098(104098)Online publication date: Feb-2024
https://doi.org/10.1016/j.artint.2024.104098
Doerr BDremaux ALutzeyer JStumpf ASilva SPaquete L(2023)How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and CliffsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590509(990-999)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590509
Doerr BEl Ghazi El Houssaini TRajabi AWitt CSilva SPaquete L(2023)How Well Does the Metropolis Algorithm Cope With Local Optima?Proceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590390(1000-1008)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590390
Misir M(2022)Cross-domain Algorithm Selection: Algorithm Selection across Selection Hyper-heuristics2022 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI51031.2022.10022078(22-29)Online publication date: 4-Dec-2022
https://doi.org/10.1109/SSCI51031.2022.10022078
Venske SAlmeida CLüders RDelgado M(2022)Selection hyper-heuristics for the multi and many-objective quadratic assignment problemComputers and Operations Research10.1016/j.cor.2022.105961148:COnline publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1016/j.cor.2022.105961
Warwicker J(2022)Hyper-heuristics for Combinatorial OptimisationEncyclopedia of Optimization10.1007/978-3-030-54621-2_728-1(1-5)Online publication date: 21-Sep-2022
https://doi.org/10.1007/978-3-030-54621-2_728-1
Sánchez-Díaz XOrtiz-Bayliss JAmaya ICruz-Duarte JConant-Pablos STerashima-Marín H(2021)A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack ProblemApplied Sciences10.3390/app11211020911:21(10209)Online publication date: 31-Oct-2021
https://doi.org/10.3390/app112110209
Mısır M(2021)Hyper-heuristics: Autonomous Problem SolversAutomated Design of Machine Learning and Search Algorithms10.1007/978-3-030-72069-8_7(109-131)Online publication date: 29-Jul-2021
https://doi.org/10.1007/978-3-030-72069-8_7
Oliveto P(2021)Rigorous Performance Analysis of Hyper-heuristicsAutomated Design of Machine Learning and Search Algorithms10.1007/978-3-030-72069-8_4(45-71)Online publication date: 29-Jul-2021
https://doi.org/10.1007/978-3-030-72069-8_4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten