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. ]]J. Branke. Evolutionary optimisation in Dynamic Environments. Kluwer, 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. ]]P. Cowling, G. Kendall, and E. Soubeiga. A Hyper-heuristic approach for scheduling a sales summit. In Selected Papers of the Third International Conference on the Practice And Theory of Automated Timetabling, PATAT 2000, Lecture Notes in Computer Science, pages 176--190, Springer, 2000.
5. ]]P. Cowling, G. Kendall, and E. Soubeiga. Hyper-heuristics: A tool for rapid prototyping in scheduling and optimisation. In Applications of Evolutionary Computing: Proceeding of Evo Workshops 2002, volume 2279 of Lecture Notes in Computer Science, pages 1--10, Springer, 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. ]]R. Morrison. Designing Evolutionary Algorithms for Dynamic Environments. Springer, 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. ]]E. Ozcan, B. Bilgin, and E. E. Korkmaz. A comprehensive survey of Hyper-heuristics. Intelligent Data Analysis, 12(1):1--21, 2008.
11. ]]K. V. Price and R. M. Storn and J. A. Lampinen. Differential Evolution, A Practical Approach to Global optimisation. Springer, 2005.
12. ]]K. Weicker, editor. Evolutionary Algorithms and Dynamic optimisation Problems. Der Andere Verlag, 2003.
13. ]]S. Yang, Y.-S. Ong, and Y. Jin, editors. Evolutionary Computation in Dynamic and Uncertain Environments, volume 51 of Studies in Computational Intelligence. Springer, 2004.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Heuristic function construction