Tutorial: Evolutionary Algorithms and Hyper-Heuristics

Hyper-heuristics is a rapidly developing domain which has proven to be effective at providing generalized solutions to problems and across problem domains. Evolutionary algorithms have played a pivotal role in the advancement of hyper-heuristics, especially generation hyper-heuristics. Evolutionary algorithm hyper-heuristics have been successful applied to solving problems in various domains including packing problems, educational timetabling, vehicle routing, permutation flowshop and financial forecasting amongst others. The aim of the tutorial is to firstly provide an introduction to evolutionary algorithm hyper-heuristics for researchers interested in working in this domain. An overview of hyper- heuristics will be provided including the assessment of hyper-heuristic performance. The tutorial will examine each of the four categories of hyper-heuristics, namely, selection constructive, selection perturbative, generation constructive and generation perturbative, showing how evolutionary algorithms can be used for each type of hyper-heuristic. A case study will be presented for each type of hyper- heuristic to provide researchers with a foundation to start their own research in this area. The EvoHyp library will be used to demonstrate the implementation of a genetic algorithm hyper-heuristic for the case studies for selection hyper-heuristics and a genetic programming hyper-heuristic for the generation hyper-heuristics. A theoretical understanding of evolutionary algorithm hyper-heuristics will be provided. A new measure to assess the performance of hyper-heuristic performance will also be presented. Challenges in the implementation of evolutionary algorithm hyper-heuristics will be highlighted. An emerging research direction is using hyper-heuristics for the automated design of computational intelligence techniques. The tutorial will look at the synergistic relationship between evolutionary algorithms and hyper-heuristics in this area. The use of hyper-heuristics for the automated design of evolutionary algorithms will be examined as well as the application of evolutionary algorithm hyper-heuristics for the design of computational intelligence techniques. The tutorial will end with a discussion session on future directions in evolutionary algorithms and hyper-heuristics.

Content

The tutorial will be divided into three parts. The first will cover introductory topics and provide researchers with a foundation to start research in this domain. The second section covers the emerging research direction of hyper-heuristics and automated design. Hyper-heuristics for evolutionary algorithm design and evolutionary algorithm hyper-heuristics for automated design. The last part is a discussion session looking at future research directions in evolutionary algorithms and hyper-heuristics.

Part I
1. An Overview of Hyper-Heuristics

The section firstly presents low-level heuristics leading to a description of hyper-heuristics. This is followed by a classification of hyper-heuristics which will introduce the four types of hyper-heuristics, namely, selection constructive, selection perturbative, generation constructive and generation perturbative. The section will conclude by examining measures for the performance of hyper-heuristic performance.

1.1 Low-Level Heuristics
1.2 Classification of Hyper-Heuristics
1.3 Assessment of Hyper-Heuristic Performance

2. Evolutionary Algorithm Hyper-Heuristics

This section will describe details of the evolutionary algorithms used and applications for each type of hyper-heuristic. A case study will be presented for each type of hyper-heuristic to illustrate how the hyper-heuristic can be applied. The EvoHyp Java evolutionary algorithm hyper-heuristic library will be used to demonstrate the implementation of evolutionary algorithm hyper-heuristics for each case study. A theoretical understanding of evolutionary algorithm hyper-heuristics will be presented. The section concludes by looking at the challenges associated with the implementation of evolutionary algorithm hyper-heuristics and potential solutions.

2.1 Selection Constructive Hyper-Heuristics 2.2 Selection Perturbative Hyper-Heuristics 2.3 Generation Constructive Hyper-Heuristics 2.4 Generation Perturbative Hyper-Heuristics 2.5 Theoretical Analysis

2.6 Challenges


Part II
3. Hyper-Heuristics for Evolutionary Algorithm Design

Hyper-heuristics have proven to be effective in the design of evolutionary algorithms. This has ranged from parameter tuning, selection of operators, to generation of operators and algorithm components. This section will provide a synopsis of how evolutionary algorithms can be designed using hyper- heuristics.

4. Evolutionary Algorithm Hyper-Heuristics for Design

One of the recent research directions in the area of hyper-heuristics is the use of hyper-heuristics for design. This section provides an account of the use of evolutionary algorithm hyper-heuristics for design. An overview of how evolutionary algorithms can be used for the design of algorithms and techniques such as metaheuristics, and example applications will be provided.

Part III

5. Discussion Session: Future Research Directions

Presenter

Nelishia Pillay is chair of the IEEE Task Force on Hyper-Heuristics with the Technical Committee of Intelligent Systems and Applications at IEEE Computational Intelligence Society. She is an active researcher in the field of evolutionary algorithm hyper-heuristics for combinatorial optimization and automated design. This is one of the focus areas of the NICOG (Nature-Inspired Computing Optimization) research group which she has established. She has worked on the project “Automated Intelligent Design Support Using Hyper-Heuristics” in collaboration with the University of Nottingham which was supported by a Royal Society Newton International exchange grant. She is the first author of the first book on hyper-heuristics “Hyper-Heuristics: Theory and Applications”, which was published in October 2018.