A hyper-heuristic is a

heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate ...

search method that seeks to automate, often by the incorporation of

machine learning Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence. Machine ...

techniques, the process of selecting, combining, generating or adapting several simpler heuristics (or components of such heuristics) to efficiently solve computational search problems. One of the motivations for studying hyper-heuristics is to build systems which can handle classes of problems rather than solving just one problem.P. Ross, Hyper-heuristics, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (E. K. Burke and G. Kendall, eds.), Springer, 2005, pp. 529-556.E. Ozcan, B. Bilgin, E. E. Korkmaz
A Comprehensive Analysis of Hyper-heuristics
Intelligent Data Analysis, 12:1, pp. 3-23, 2008. There might be multiple heuristics from which one can choose for solving a problem, and each heuristic has its own strength and weakness. The idea is to automatically devise algorithms by combining the strength and compensating for the weakness of known heuristics.E. Ozcan, B. Bilgin, E. E. Korkmaz, Hill Climbers and Mutational Heuristics in Hyperheuristics, Lecture Notes in Computer Science, Springer-Verlag, The 9th International Conference on Parallel Problem Solving From Nature, 2006, pp. 202-211. In a typical hyper-heuristic framework there is a high-level methodology and a set of low-level heuristics (either constructive or perturbative heuristics). Given a problem instance, the high-level method selects which low-level heuristic should be applied at any given time, depending upon the current problem state (or search stage) determined by features.Amaya, I., Ortiz-Bayliss, J.C., Rosales-Perez, A., Gutierrez-Rodriguez, A.E., Conant-Pablos, S.E., Terashima-Marin, H. and Coello, C.A.C., 2018. Enhancing Selection Hyper-Heuristics via Feature Transformations. IEEE Computational Intelligence Magazine, 13(2), pp.30-41. https://ieeexplore.ieee.org/iel7/10207/8335819/08335843.pdfAmaya, I., Ortiz-Bayliss, J.C., Gutiérrez-Rodríguez, A.E., Terashima-Marín, H. and Coello, C.A.C., 2017, June. Improving hyper-heuristic performance through feature transformation. In 2017 IEEE Congress on Evolutionary Computation (CEC) (pp. 2614-2621). IEEE. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7969623

Hyper-heuristics versus metaheuristics

The fundamental difference between

metaheuristics In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimiza ...

and hyper-heuristics is that most implementations of metaheuristics search within a search space of problem solutions, whereas hyper-heuristics always search within a search space of heuristics. Thus, when using hyper-heuristics, we are attempting to find the right method or sequence of heuristics in a given situation rather than trying to solve a problem directly. Moreover, we are searching for a generally applicable methodology rather than solving a single problem instance. Hyper-heuristics could be regarded as "off-the-peg" methods as opposed to "made-to-measure" metaheuristics. They aim to be generic methods, which should produce solutions of acceptable quality, based on a set of easy-to-implement low-level heuristics.

Motivation

Despite the significant progress in building search methodologies for a wide variety of application areas so far, such approaches still require specialists to integrate their expertise in a given problem domain. Many researchers from

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech r ...

and

operational research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...

have already acknowledged the need for developing automated systems to replace the role of a human expert in such situations. One of the main ideas for automating the design of heuristics requires the incorporation of

mechanisms into algorithms to adaptively guide the search. Both learning and adaptation processes can be realised on-line or off-line, and be based on constructive or perturbative heuristics. A hyper-heuristic usually aims at reducing the amount of

domain knowledge Domain knowledge is knowledge of a specific, specialized discipline or field, in contrast to general (or domain-independent) knowledge. The term is often used in reference to a more general discipline—for example, in describing a software engin ...

in the search methodology. The resulting approach should be cheap and fast to implement, requiring less expertise in either the problem domain or heuristic methods, and (ideally) it would be robust enough to effectively handle a range of problem instances from a variety of domains. The goal is to raise the level of generality of decision support methodology perhaps at the expense of reduced - but still acceptable - solution quality when compared to tailor-made metaheuristic approaches.Burke E.K., Landa Silva J.D., Soubeiga E.
Multi-objective Hyper-heuristic Approaches for Space Allocation and Timetabling
In Meta-heuristics: Progress as Real Problem Solvers, Selected Papers from the 5th Metaheuristics International Conference (MIC 2003), pp 129-158, 2005. In order to reduce the gap between tailor-made schemes and hyperheuristic-based strategies, parallel hyperheuristics have been proposed.C. Segura, G. Miranda and C. León: Parallel hyperheuristics for the frequency assignment problem Special issue on nature inspired cooperative strategies for optimization, In Memetic Computing, Special issue on nature inspired cooperative strategies for optimization,

, 2010.

Origins

The term "hyperheuristics" was first coined in a 2000 publication by Cowling and Soubeiga, who used it to describe the idea of "heuristics to choose heuristics".Cowling P. and Soubeiga E. Neighborhood Structures for Personnel Scheduling: A Summit Meeting Scheduling Problem (abstract), in proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, Burke E.K. and Erben W. (eds), 16-18 Aug 2000, Constance, Germany They used a "choice function" machine learning approach which trades off exploitation and exploration in choosing the next heuristic to use.Cowling P., Graham Kendall, Kendall G. and Soubeiga E., A Hyperheuristic Approach to Scheduling a Sales Summit, 2001, Lecture Notes in Computer Science 2079, Springer-Verlag, pp. 176–190, 2001, , ( Subsequently, Cowling, Soubeiga, Kendall, Han, Ross and other authors investigated and extended this idea in areas such as evolutionary algorithms, and pathological low level heuristics. The first journal article to use the term appeared in 2003. The origin of the idea (although not the term) can be traced back to the early 1960sH. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, Factory Scheduling Conference (Carnegie Institute of Technology), 1961.* H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules,Industrial Scheduling (New Jersey) (J. F. Muth and G. L. Thompson, eds.), Prentice-Hall, Inc, 1963, pp. 225–251. and was independently re-discovered and extended several times during the 1990s. In the domain of Job Shop Scheduling, the pioneering work by Fisher and Thompson, hypothesized and experimentally proved, using probabilistic learning, that combining scheduling rules (also known as priority or dispatching rules) was superior than any of the rules taken separately. Although the term was not then in use, this was the first "hyper-heuristic" paper. Another root inspiring the concept of hyper-heuristics comes from the field of

. More specifically, it comes from work on

automated planning Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...

systems, and its eventual focus towards the problem of learning control knowledge. The so-called COMPOSER system, developed by Gratch et al., was used for controlling satellite communication schedules involving a number of earth-orbiting satellites and three ground stations. The system can be characterized as a hill-climbing search in the space of possible control strategies.

Classification of approaches

Hyper-heuristic approaches so far can be classified into two main categories. In the first class, captured by the phrase ''heuristics to choose heuristics'', the hyper-heuristic framework is provided with a set of pre-existing, generally widely known heuristics for solving the target problem. The task is to discover a good sequence of applications of these heuristics (also known as low-level heuristics within the domain of hyper-heuristics) for efficiently solving the problem. At each decision stage, a heuristic is selected through a component called selection mechanism and applied to an incumbent solution. The new solution produced from the application of the selected heuristic is accepted/rejected based on another component called acceptance criterion. Rejection of a solution means it is simply discarded while acceptance leads to the replacement of the incumbent solution. In the second class, ''heuristics to generate heuristics'', the key idea is to "evolve new heuristics by making use of the components of known heuristics." The process requires, as in the first class of hyper-heuristics, the selection of a suitable set of heuristics known to be useful in solving the target problem. However, instead of supplying these directly to the framework, the heuristics are first decomposed into their basic components. These two main broad types can be further categorised according to whether they are based on constructive or perturbative search. An additional orthogonal classification of hyper-heuristics considers the source providing feedback during the learning process, which can be either one instance (''on-line learning'') or many instances of the underlying problem studied (''off-line learning'').

Methodologies to choose heuristics

Discover good combinations of fixed, human-designed, well-known low-level heuristics. * Based on constructive heuristics * Based on perturbative heuristics

Methodologies to generate heuristics

Generate new heuristic methods using basic components of previously existing heuristic methods. * Based on basic components of constructive heuristics * Based on basic components of perturbative heuristics

On-line learning hyper-heuristics

The learning takes place while the algorithm is solving an instance of a problem, therefore, task-dependent local properties can be used by the high-level strategy to determine the appropriate low-level heuristic to apply. Examples of on-line learning approaches within hyper-heuristics are: the use of

reinforcement learning Reinforcement learning (RL) is an area of machine learning concerned with how intelligent agents ought to take actions in an environment in order to maximize the notion of cumulative reward. Reinforcement learning is one of three basic machine ...

for heuristic selection, and generally the use of

as high-level search strategies over a search space of heuristics.

Off-line learning hyper-heuristics

The idea is to gather knowledge in form of rules or programs, from a set of training instances, which would hopefully generalise to the process of solving unseen instances. Examples of off-line learning approaches within hyper-heuristics are:

learning classifier system Learning classifier systems, or LCS, are a paradigm of rule-based machine learning methods that combine a discovery component (e.g. typically a genetic algorithm) with a learning component (performing either supervised learning, reinforcement lear ...

s, case-base reasoning and

genetic programming In artificial intelligence, genetic programming (GP) is a technique of evolving programs, starting from a population of unfit (usually random) programs, fit for a particular task by applying operations analogous to natural genetic processes to t ...

. An extended classification of ''selection'' hyper-heuristics was provided in 2020,Drake J. H, Kheiri A., Ozcan E., Burke E. K., (2020) Recent Advances in Selection Hyper-heuristics. European Journal of Operational Research, 285(2), pp. 405-428.

to provide a more comprehensive categorisation of contemporary selection hyper-heuristic methods.

Applications

Hyper-heuristics have been applied across many different problems. Indeed, one of the motivations of hyper-heuristics is to be able to operate across different problem types. The following list is a non-exhaustive selection of some of the problems and fields in which hyper-heuristics have been explored: *

bin packing problem The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has ma ...

boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

* educational timetabling * job shop scheduling * multi-objective problem solving and space allocation * nurse rostering * personnel scheduling *

traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...

vehicle routing problem The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises ...

* multidimensional knapsack problem *

0-1 knapsack problem The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit an ...

* maximum cut problem *

quadratic assignment problem The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems first introduced by Ko ...

* wind farm layout

Related areas

Hyper-heuristics are not the only approach being investigated in the quest for more general and applicable search methodologies. Many researchers from computer science,

and

have already acknowledged the need for developing automated systems to replace the role of a human expert in the process of tuning and adapting search methodologies. The following list outlines some related areas of research: * adaptation and self-adaptation of algorithm parameters * adaptive

memetic algorithm A memetic algorithm (MA) in computer science and operations research, is an extension of the traditional genetic algorithm. It may provide a sufficiently good solution to an optimization problem. It uses a local search technique to reduce the like ...

* adaptive large neighborhood search * algorithm configuration * algorithm control * algorithm portfolios * autonomous search *

* indirect encodings in

evolutionary algorithms In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduct ...

* variable neighborhood search * reactive search

References and notes

External links

Hyper-heuristic bibliographies

https://mustafamisir.github.io/hh.html

Research groups

Artificial Intelligence (ART+I) LaboratoryYeditepe University

Turkey Turkey ( tr, Türkiye ), officially the Republic of Türkiye ( tr, Türkiye Cumhuriyeti, links=no ), is a transcontinental country located mainly on the Anatolian Peninsula in Western Asia, with a small portion on the Balkan Peninsula in ...

Automated Scheduling, Optimisation and Planning (ASAP) Research GroupUniversity of Nottingham
UK
Combinatorial Optimisation and Decision Support (CODeS) Research GroupKU Leuven

Belgium Belgium, ; french: Belgique ; german: Belgien officially the Kingdom of Belgium, is a country in Northwestern Europe. The country is bordered by the Netherlands to the north, Germany to the east, Luxembourg to the southeast, France to th ...

Computational-Heuristics, Operations Research and Decision-Support (CHORDS) Research GroupUniversity of Stirling
UK
Evolutionary Computation Research GroupVictoria University of Wellington

New Zealand New Zealand ( mi, Aotearoa ) is an island country in the southwestern Pacific Ocean. It consists of two main landmasses—the North Island () and the South Island ()—and over 700 smaller islands. It is the sixth-largest island count ...

Intelligent Systems LabHeriot-Watt University
UK
Intelligent Systems Research GroupTecnologico de Monterrey

Mexico Mexico (Spanish: México), officially the United Mexican States, is a country in the southern portion of North America. It is bordered to the north by the United States; to the south and west by the Pacific Ocean; to the southeast by Guatema ...

.
Machine lEarning and Operations Research (MEmORy) LabNanjing University of Aeronautics and Astronautics
P.R.China
Modelling Optimisation Scheduling and Intelligent Control (MOSAIC) Research GroupUniversity of Bradford
UK
Operational Research (OR) GroupQueen Mary University of London
UK
Optimising Software by Computation from ARtificial intelligence (OSCAR) Research GroupDalian University of Technology
P.R.China

Recent activities

Stream on Hyper-heuristics @ EURO 2019

* ttp://web.mst.edu/~tauritzd/ECADA/GECCO2018/index.html 8th Workshop on Evolutionary Computation for the Automated Design of Algorithms (ECADA) @ GECCO 2018
Stream on Hyper-heuristics @ EURO 2018

* ttp://seal2017.com/Tutorial.html Tutorial on Algorithm Selection: Offline + Online Techniques @ SEAL 2017
1st AISB Symposium on Meta-Optimisation: Hyper-heuristics and Beyond @ AISB Convention 2013

Modern Hyperheuristics for Large Scale Optimization Problems @ META2012

* ttp://www.sigevo.org/gecco-2012/organizers-tracks.html#ss Self-* Search Track @ GECCO 2012
Special Session on Evolutionary Based Hyperheuristics and Their Applications @ IEEE CEC2012 (WCCI2012)

Special Session on Cross-domain Heuristic Search (LION-CHESC) @ LION2012

Cross-domain Heuristic Search Challenge 2011 (CHeSC 2011)

* ttp://www.cs.nott.ac.uk/~gxo/ppsn2010-selfstar.html Workshop on Self-tuning, self-configuring and self-generating search heuristics (Self* 2010) @ PPSN 2010
Workshop on Hyper-heuristics @ PPSN 2008

Others

in th

at th
IEEE Computational Intelligence Society
{{DEFAULTSORT:Hyper-Heuristic Optimization algorithms and methods Heuristics