Skip to main content
SpringerLink
Log in

Selection hyper-heuristics in dynamic environments

  • Special Issue Paper
  • Published:
Journal of the Operational Research Society

Abstract

Current state-of-the-art methodologies are mostly developed for stationary optimization problems. However, many real-world problems are dynamic in nature, where different types of changes may occur over time. Population-based approaches, such as evolutionary algorithms, are frequently used for solving dynamic environment problems. Selection hyper-heuristics are highly adaptive search methodologies that aim to raise the level of generality by providing solutions to a diverse set of problems having different characteristics. In this study, the performances of 35 single-point-search-based selection hyper-heuristics are investigated on continuous dynamic environments exhibiting various change dynamics, produced by the Moving Peaks Benchmark generator. Even though there are many successful applications of selection hyper-heuristics to discrete optimization problems, to the best of our knowledge, this study is one of the initial applications of selection hyper-heuristics to real-valued optimization as well as being among the very few which address dynamic optimization issues using these techniques. The empirical results indicate that learning selection hyper-heuristics incorporating compatible components can react to different types of changes in the environment and are capable of tracking them. This study shows the suitability of selection hyper-heuristics as solvers in dynamic environments.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6

Notes

  1. Since we have seven low-level heuristics and the Greedy heuristic selection method evaluates all at each step, these values are determined as multiples of 7 to give each method an equal number of evaluations during each stationary period.

References

  • Ayob M and Kendall G (2003). A Monte Carlo hyper-heuristic to optimise component placement sequencing for multi head placement machine. In: Proceedings of the International Conference on Intelligent Technologies, pp 132–141.

  • Bai R, Blazewicz J, Burke EK, Kendall G and McCollum B (2007). A simulated annealing hyper-heuristic methodology for flexible decision support. Technical Report NOTTCS-TR-2007-8, School of CSIT, University of Nottingham.

  • Bai R and Kendall G (2005). An investigation of automated planograms using a simulated annealing based hyper-heuristics. In: Ibaraki T, Nonobe K and Yagiura M (eds). Metaheuristics: Progress as Real Problem Solver—(Operations Research/Computer Science Interface Series, Vol. 32). Springer: New York, pp 87–108.

    Chapter  Google Scholar 

  • Beyer HG and Schwefel HP (2002). Evolution strategies—a comprehensive introduction. Natural Computing 1 (1): 3–52.

    Article  Google Scholar 

  • Bilgin B, Özcan E and Korkmaz EE (2006). An experimental study on hyper-heuristics and exam timetabling. In: Burke EK and Rudová H (eds). Proceedings of the 6th International Conference on Practice and Theory of Automated Timetabling. Springer: New York, pp 123–140.

  • Branke J (1999). Memory enhanced evolutionary algorithms for changing optimization problems. In: Angeline PJ, Michalewicz Z, Schoenauer M, Yao X and Zalzala A (eds). Congress on Evolutionary Computation CEC 99, Vol. 3. IEEE: New York, pp 1875–1882.

  • Branke J (2002). Evolutionary Optimization in Dynamic Environments. Kluwer: Dordrecht, MA.

    Book  Google Scholar 

  • Branke J, Salihoğlu E and Uyar AŞ (2005). Towards an analysis of dynamic environments. In: Beyer H-G et al (eds). Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, GECCO’05. ACM: New York, pp 1433–1440.

  • Burke E, Hart E, Kendall G, Newall J, Ross P and Schulenburg S (2003). Hyper-heuristics: An emerging direction in modern search technology. In: Glover F and Kochenberger G (eds). Handbook of Metaheuristics. Kluwer: Dordrecht, MA, pp 457–474.

    Chapter  Google Scholar 

  • Burke EK, Hyde M, Kendall G, Ochoa G, Özcan E and Rong Q (2009a). A survey of hyper-heuristics. Technical report.

  • Burke EK, Hyde MR, Kendall G, Ochoa G, Özcan E and Woodward JR (2009b). Exploring hyper-heuristic methodologies with genetic programming. In: Kacprzyk J, Jain LC, Mumford CL and Jain LC (eds). Computational Intelligence. Vol. 1. Intelligent Systems Reference Library. Springer: New York, pp 177–201.

    Chapter  Google Scholar 

  • Burke EK, Hyde M, Kendall G, Ochoa G, Özcan E and Woodward JR (2010a). A classification of hyper-heuristic approaches. In: Gendreau M and Potvin J-Y (eds). Handbook of Metaheuristics. Vol. 146. International Series in Operations Research and Management Science. Springer: New York, pp 449–468.

    Chapter  Google Scholar 

  • Burke EK, Kendall G, Misir M and Özcan E (2010b). Monte Carlo hyper-heuristics for examination timetabling. Annals of Operations Research 196 (1): 1–18.

    Google Scholar 

  • Chakhlevitch K and Cowling P (2008). Hyperheuristics: Recent developments. In: Cotta C, Sevaux M and Sirensen K (eds). Adaptive and Multilevel Metaheuristics. Vol. 136. Studies in Computational Intelligence. Springer: Berlin, Heidelberg, pp 3–29.

    Chapter  Google Scholar 

  • Cobb HG (1990). An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuous, time-dependent nonstationary environments. Technical Report AIC-90-001, Naval Research Lab, Washington DC.

  • Cowling P, Kendall G and Soubeiga E (2000). A hyper-heuristic approach to scheduling a sales summit. In: Burke EK and Erben W (eds). Practice and Theory of Automated Timetabling III: Third International Conference, PATAT 2000, Vol. 2079. LNCS, Springer: New York.

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

  • Cowling P, Kendall G and Soubeiga E (2002). Hyperheuristics: A tool for rapid prototyping in scheduling and optimisation. In: Cagnoni S, Gottlieb J, Hart E, Middendorf M and Raidl GR (eds). EvoWorkShops. Vol. 4193. Lecture Notes in Computer Science. Springer: New York, pp 1–10.

    Google Scholar 

  • Crowston WB, Glover F, Thompson GL and Trawick JD (1963). Probabilistic and parametric learning combinations of local job shop scheduling rules. ONR Research Memorandum, GSIA, Carnegie Mellon University, Pittsburgh (117).

  • Cruz C, Gonzalez J and Pelta D (2011). Optimization in dynamic environments: A survey on problems, methods and measures. Soft Computing—A Fusion of Foundations, Methodologies and Applications 15 (7): 1427–1448.

    Google Scholar 

  • Denzinger J, Fuchs M and Fuchs M (1997). High performance ATP systems by combining several AI methods. In: 4th Asia-Pacific Conference on SEAL. Morgan Kaufmann: Los Altos, CA, pp 102–107.

  • Dowsland KA, Soubeiga E and Burke EK (2007). A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation. European Journal of Operational Research 179 (3): 759–774.

    Article  Google Scholar 

  • Fisher H and Thompson GL (1963). Probabilistic learning combinations of local job-shop scheduling rules. In: Muth JF and Thompson GL (eds). Industrial Scheduling. Prentice-Hall: Englewood Cliffs, NJ, pp 225–251.

    Google Scholar 

  • Gibbs J, Kendall G and Özcan E (2011). Scheduling english football fixtures over the holiday period using hyper-heuristics. In: Schaefer R, Cotta C, Kolodziej J and Rudolph G (eds). Parallel Problem Solving from Nature—PPSN XI. Vol. 6238. Lecture Notes in Computer Science. Springer: Berlin/Heidelberg, pp 496–505.

    Google Scholar 

  • Grefenstette JJ (1992). Genetic algorithms for changing environments. In: Maenner R and Manderick B (eds). Proceedings of Parallel Problem Solving from Nature, pp 137–1446.

  • Hansen N (2011). The CMA evolution strategy: a tutorial. Technical report, 28 June.

  • Hansen N and Ostermeier A (2001). Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation 9 (2): 159–195.

    Article  Google Scholar 

  • Hansen N, Müller SD and Koumoutsakos P (2003). Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation 11 (1): 1–18.

    Article  Google Scholar 

  • Jin Y and Branke J (2005). Evolutionary optimization in uncertain environments—a survey. IEEE Transactions on Evolutionary Comp 9 (3): 303–317.

    Article  Google Scholar 

  • Kendall G and Mohamad M (2004). Channel assignment in cellular communication using a great deluge hyperheuristic. In: Mastorakis N, Mladenov V and Savkovic-Stevanovic J (eds). IEEE International Conference on Network, World Scientific and Engineering Academy and Society (WSEAS): Stevens Point, WI, pp 769–773.

  • Kiraz B and Topcuoglu HR (2010). Hyper-heuristic approaches for the dynamic generalized assignment problem. In: 10th International Conference on Intelligent Systems Design and Applications (ISDA). IEEE: New York, pp 1487–1492.

  • Kiraz B, Uyar AŞ and Özcan E (2011). An investigation of selection hyper-heuristics in dynamic environments. In: Di Chio C, et al (eds). Proceedings of EvoApplications 2011, Vol. 6624 of LNCS, Springer: New York.

  • Lewis J, Hart E and Ritchie G (1998). A comparison of dominance mechanisms and simple mutation on nonstationary problems. In: Eiben AE, Bäck T, Schoenauer M and Schwefel HP (eds). Proceedings of Parallel Problem Solving from Nature. Springer: New York, pp 139–148.

  • Lundy M and Mees A (1986). Convergence of an annealing algorithm. Mathematical Programming 34 (1): 111–124.

    Article  Google Scholar 

  • Morrison RW (2004). Designing Evolutionary Algorithms for Dynamic Environments. Springer: New York.

    Book  Google Scholar 

  • Nareyek A (2001). Choosing search heuristics by non-stationary reinforcement learning. In: Resende MGC and de Sous JP (eds). Metaheuristics: Computer Decision-Making. Kluwer Academic Publishers: Norwell, MA, pp 523–544.

    Google Scholar 

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

    Google Scholar 

  • Özcan E, Uyar AŞ and Burke E (2009). A greedy hyper-heuristic in dynamic environments. In: Rothlauf F (ed). GECCO 2009 Workshop on Automated Heuristic Design: Crossing the Chasm for Search Methods. ACM: New York, pp 2201–2204.

  • Özcan E, Misir M, Ochoa G and Burke EK (2010). A reinforcement learning—Great-deluge hyper-heuristic for examination timetabling. International Journal of Applied Metaheuristic Computing 1 (1): 39–59.

    Article  Google Scholar 

  • Ross P (2005). Hyper-heuristics. In: Burke EK and Kendall G (eds). Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Chapter 17. Springer: New York, pp 529–556.

    Chapter  Google Scholar 

  • Salihoğlu E (2005). Towards an analysis of dynamic environments. Master's thesis, Istanbul Technical University, http://web.itu.edu.tr/etaner/thesis-salihoglu-05.pdf.

  • Ursem RK (2000). Multinational GA optimization techniques in dynamic environments. In: Whitley D, Goldberg D, Cantu-Paz E, Spector L, Parmee I and Beyer H-G (eds). Proceedings of the Genetic and Evolutionary Conference. Morgan Kaufmann: Burlington, MA, pp 19–26.

  • Uyar AŞ and Harmanci AE (2005). A new population based adaptive domination change mechanism for diploid genetic algorithms in dynamic environments. Soft Computing 9 (11): 803–814.

    Article  Google Scholar 

  • Vavak F, Jukes K and Fogarty TC (1997). Adaptive combustion balancing in multiple burner boiler using a genetic algorithm with variable range of local search. In: Bäck T (ed). Proceedings of the International Conference on Genetic Algorithms. Morgan Kaufmann: Los Altos, CA, pp 719–726.

  • Yang S (2008). Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evolutionary Computation 16 (3): 385–416.

    Article  Google Scholar 

  • Yang S, and Yao X (2008). Population-based incremental learning with associative memory for dynamic environments. IEEE Transactions on Evolutionary Comp 12 (5): 542–561.

    Article  Google Scholar 

  • Yang S, Ong YS and Jin Y (eds) (2007). Evolutionary Computation in Dynamic and Uncertain Environments. Vol. 51. Studies in Computational Intelligence. Springer: New York.

    Book  Google Scholar 

Download references

Acknowledgements

This work is supported in part by the EPSRC, grant EP/F033214/1 (The LANCS Initiative Postdoctoral Training Scheme) and Berna Kiraz is fully supported by the TÜBİTAK 2211-National Scholarship Programme for PhD students.

Author information

Authors and Affiliations

  1. Institute of Science and Technology, Istanbul Technical University, Istanbul, Turkey

    B Kiraz

  2. Department of Computer Engineering, Istanbul Technical University, Istanbul, Turkey

    A Ş Etaner-Uyar

  3. University of Nottingham, Nottingham, UK

    E Özcan

Authors
  1. B Kiraz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A Ş Etaner-Uyar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. E Özcan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A Ş Etaner-Uyar.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kiraz, B., Etaner-Uyar, A. & Özcan, E. Selection hyper-heuristics in dynamic environments. J Oper Res Soc 64, 1753–1769 (2013). https://doi.org/10.1057/jors.2013.24

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2013.24

Keywords

Search

Navigation