Tutorial 1: Evolutionary Algorithm Hyper-Heuristics
Hyper-heuristics is a fairly new field that aims at providing a more generalized solution to combinatorial optimization problems. This is achieved by exploring a space of low-level heuristics or heuristic combinations which is mapped onto a solution space rather than searching the solution space directly. These low-level heuristics can be constructive or perturbative. Hyper-heuristics have been found to be effective in solving combinatorial optimization problems such us university course and examination timetabling, school timetabling, nurse and personnel rostering, packing problems and the travelling salesman problem, amongst others. Evolutionary algorithms such as genetic algorithms and genetic programming have played an important role in the development of the field of hyper-heuristics. Genetic programming in particular is the technique chiefly employed by hyper-heuristics to generate low-level heuristics. This tutorial will provide an introduction to hyper-heuristics and evolutionary algorithm hyper-heuristics, illustrate the application and effectiveness of evolutionary algorithm hyper-heuristics in solving combinatorial optimization problems and highlight directions for future research.
Presenter
Nelishia Pillay
Associate Professor, School of Mathematics, Statistics and Computer Science,
University of KwaZulu-Natal,
South Africa
E-mail: pillayn32@ukzn.ac.za
http://nicog.cs.ukzn.ac.za/
http://www.titan.cs.unp.ac.za/~nelishiap/
Tutorial Material
Topics
v Introduction to hyper-heuristics - will provide an introduction to hyper-heuristics.
v Combinatorial optimization and low-level heuristics - will provide a brief introduction to combinatorial optimization and how low-level constructive and perturbative heuristics are used in this domain.
v Types of hyper-heuristics - the four types of hyper-heuristics will be presented, namely, selection constructive, selection perturbative, generation constructive and generation perturbative.
v Evolutionary algorithm hyper-heuristics - will look at how evolutionary algorithms have been employed by the four different types of hyper-heuristics.
v Application of evolutionary algorithm hyper-heuristics - will examine how evolutionary algorithm hyper-heuristics can be applied to combinatorial optimization problems and the effectiveness of this.
v Why do evolutionary algorithm hyper-heuristics work? - this section will examine why searching of a heuristic space is effective and more effective than searching the solution space directly.
v Growth of the field - a brief overview of the development of evolutionary algorithm hyper-heuristics since its inception, including recent applications and the cross-domain challenge.
v Future research directions for evolutionary algorithm hyper-heuristics.
Target Audience
The tutorial is aimed at researchers in the field of evolutionary algorithms and other nature-inspired methods for combinatorial optimization. The tutorial provides an introduction to evolutionary algorithm hyper-heuristics and as such requires an introductory knowledge of evolutionary algorithms and combinatorial optimization.
Bibliography
1. Bader-El-Ben, M., Poli, R. & Fatima, S. (2009) Evolving Timetabling Heuristics Using Grammar-Based Genetic Programming Hyper-Heuristic Framework. Memetic Computing, 2009(1), 205-219.
2. Burke, E. K., Curtois, T., Hyde, M., Kendall, G., Ochoa, G., Petrovic, S. & Vazquez-Rodriguez, J. A. (2009a) HyFlex: A Flexible Framework for the Design and Analysis of Hyper-Heuristics. In proceedings of the Multidisciplinary International Scheduling Conference (MISTA '09) (pp. 790-797).
3. Burke, E.K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E. & Qu, R. (2013) Hyper-heuristics: A Survey of the State of the Art. Journal of the Operational Research Society, 64, 1695-1724.
4. Burke, E., Hart, E., Kendall, G., Newall, J., Ross, P. & Schulenburg, S. (2003) Hyper-Heuristics: An Emerging Direction in Modern Research. In the Handbook of Metaheuristics, Chapter 16, 457-474.
5. Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E. &Woodard, J. (2009b) Exploring Hyper-Heuristic Methodologies with Genetic Programming. Computational Intelligence, 6, 177-201.
6. Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E. &Woodard, J. (2010a) A Classification of Hyper-Heuristic Approaches. In the Handbook of Metaheuristics, International Series in Operations Research and Management Science, Volume 146, 449-468.
7. McKay, R.I., Hoai, N.X., Whigham, P.A., Shan, Y. & O'Neill, M. (2010) Grammar-Based Genetic Programming: A Survey. Genetic Programming and Evolvable Hardware, 11(3-4), 365-396.
8. Pappa, G.L., Ochoa, G., Hyde, M.R., Freitas, A.A., Woodward, J. & Swan, J. (2014) Contrasting Meta-Learning and Hyper-Heuristic Research: the Role of Evolutionary Algorithms. Genetic Programming and Evolvable Machines,15(1), 3-35.
9. Pillay, N. (2011a) A Hyper-Heuristic Approach to Solving School Timetabling Problems. In proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications, MISTA 2011 (pp.628-632).
10. Pillay, N. (2012) Evolving Hyper-Heuristics for the Uncapacitated Examination Timetabling Problem. Journal of the Operational Research Society, 63, 47-58.
11. Pillay, N. (2013b) A Study of Hyper-Heuristics for Hybridizing Search. Advances in Artificial Intelligence - Proceedings of ALEA 2013, 9-12 September, Portugal (pp. 128-139).
12. Ross, P. (2005) Hyper-Heuristics. In Burke, E.K. & Kendall, G., Search Methodologies : Introductory Tutorials in Optimization and Decision Support Techniques, Chapter 17, 529-556, Springer.
13. Ross, P. (2014) Hyper-Heuristics. In Burke, E.K. & Kendall, G., Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, 611-638.
14. Ross, P. & Marin-Blazquez, J.G. (2005) Constructive Hyper-Heuristics in Class Timetabling. In proceedings of the IEEE Congress of Evolutionary Computation CEC '05 (pp. 1493-1500).
15. Ross, P., Marin-Blazquez, J.G. & Hart, E. (2004) Hyper-Heuristics Applied to Class and Exam Timetabling Problems. In proceedings of the IEEE Congress of Evolutionary Computation CEC '04 (pp. 1691-1698).
16. Sabar, N. R. Ayob, M, Kendall, G. & Qu, R. (2013) Grammatical Evolution Hyper-Heuristic for Combinatorial Optimization Problems. IEEE Transactions on Evolutionary Computation, in press, http://www.cs.nott.ac.uk/~rxq/files/TEC13.pdf.
17. Swan, J. & Woodward, J. (2014) Searching the Hyper-Heuristic Design Space. Cognitive Computation, 6(1), 66-73.