A greedy hyper-heuristic in dynamic environments

ABSTRACT

If an optimisation algorithm performs a search in an environment that changes over time, it should be able to follow these changes and adapt itself for handling them in order to achieve good results. Different types of dynamics in a changing environment require the use of different approaches. Hyper-heuristics represent a class of methodologies that are high level heuristics performing search over a set of low level heuristics. Due to the generality of hyper-heuristic frameworks, they are expected to be adaptive. Hence, a hyper-heuristic can be used in a dynamic environment to determine the approach to apply, adapting itself accordingly at each change. This study presents an initial investigation of hyper-heuristics in dynamic environments. A greedy hyper-heuristic is tested over a set of benchmark functions.

REFERENCES

• 1: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 2001
• 2: E. K. Burke, E. Hart, G. Kendall, J. Newall, P. Ross, and S. Schulenburg. Hyper-heuristics: An emerging direction in modern search technology. In Handbook of Metaheuristics, pages 457--474. Kluwer, 2003.
• 3: E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J. R. Woodward. Exploring Hyper-heuristic methodologies with genetic programming. In Studies in Computational Intelligence: collaboration, fusion and emergence, chapter 6. Springer, 2009.
• 4: Peter I. Cowling , Graham Kendall , Eric Soubeiga, A Hyperheuristic Approach to Scheduling a Sales Summit, Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling III, p.176-190, August 16-18, 2000
• 5: Peter I. Cowling , Graham Kendall , Eric Soubeiga, Hyperheuristics: A Tool for Rapid Prototyping in Scheduling and Optimisation, Proceedings of the Applications of Evolutionary Computing on EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTIM/EvoPLAN, p.1-10, April 03-04, 2002
• 6: L. Davis. Bit climbing, representational bias, and test suite design. In Proceedings of the 4th Int. Conference on Genetic Algorithms, pages 18--23, 1991.
• 7: Y. Jin and J. Branke. Evolutionary optimisation in uncertain environments -- a survey. IEEE Transactions on Evolutionary Computation, 9(3):303--317, 2005.
• 8: Ronald W. Morrison, Designing Evolutionary Algorithms for Dynamic Environments, SpringerVerlag, 2004
• 9: E. Ozcan, B. Bilgin, and E. E. Korkmaz. Hill climbers and mutational heuristics in Hyper-heuristics. In Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN 2006), volume 4193 of Lecture Notes in Computer Science, pages 202--211, Springer, 2006.
• 10: Ender Özcan , Burak Bilgin , Emin Erkan Korkmaz, A comprehensive analysis of hyper-heuristics, Intelligent Data Analysis, v.12 n.1, p.3-23, January 2008
• 11: Kenneth Price , Rainer M. Storn , Jouni A. Lampinen, Differential Evolution: A Practical Approach to Global Optimization (Natural Computing Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 12: K. Weicker, editor. Evolutionary Algorithms and Dynamic optimisation Problems. Der Andere Verlag, 2003.
• 13: Shengxiang Yang , Yew-Soon Ong , Yaochu Jin, Evolutionary Computation in Dynamic and Uncertain Environments (Studies in Computational Intelligence), Springer-Verlag New York, Inc., Secaucus, NJ, 2007

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
adaptive, dynamic environments, greedy, hill climbing, hyper-heuristics, mutational heuristics