Hyper-heuristic
Encyclopedia
A hyper-heuristic is a heuristic
search method that seeks to automate, often by the incorporation of machine learning
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.
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. 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.
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.
, artificial intelligence
and operational research 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 machine learning
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 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. In order to reduce the gap between tailor-made schemes and hyperheuristic-based strategies, parallel hyperheuristics have been proposed.
. More specifically, it comes from work on automated planning 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.
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).
for heuristic selection, and generally the use of metaheuristics as high-level search strategies over a search space of heuristics.
within hyper-heuristics are: learning classifier system
s, case-base reasoning and genetic programming
.
and operational research 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:
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
search method that seeks to automate, often by the incorporation of machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
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.
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. 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.
Hyper-heuristics versus meta-heuristics
The fundamental difference between metaheuristics and hyper-heuristics is that most implementations of metaheuristics search within a search spaceSearch space
Search space may refer to one of the following.*In optimization, the domain of the function to be optimized*In search algorithms of computer science, the set of all possible solutions...
of problem solutions, whereas hyper-heuristics always search within a search space
Search space
Search space may refer to one of the following.*In optimization, the domain of the function to be optimized*In search algorithms of computer science, the set of all possible solutions...
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 scienceComputer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
and operational research 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 machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
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 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. In order to reduce the gap between tailor-made schemes and hyperheuristic-based strategies, parallel hyperheuristics have been proposed.
Origins
The term hyper-heuristics was first coined in 1997 by Jörg Denzinger, Matthias Fuchs and Marc Fuchs. They used it to describe a protocol that chooses and combines several AI methods. Several years later in 2000, Cowling and Soubeiga used it to describe the idea of "heuristics to choose heuristics". The first easily accessible paper to use the term appeared in 2001. 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 1960s 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 artificial intelligenceArtificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
. More specifically, it comes from work on automated planning 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 for efficiently solving the problem. 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 learningReinforcement learning
Inspired by behaviorist psychology, reinforcement learning is an area of machine learning in computer science, concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward...
for heuristic selection, and generally the use of metaheuristics 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 approacheswithin hyper-heuristics are: learning classifier system
Learning classifier system
A learning classifier system, or LCS, is a machine learning system with close links to reinforcement learning and genetic algorithms. First described by John Holland, his LCS consisted of a population of binary rules on which a genetic algorithm altered and selected the best rules.Rule fitness...
s, case-base reasoning and genetic programming
Genetic programming
In artificial intelligence, genetic programming is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program...
.
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 problemBin packing problemIn computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used....
- boolean satisfiability problemBoolean satisfiability problemIn computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
- educational timetabling
- job shop scheduling
- multi-objective problem solving and space allocation
- nurse rostering
- personnel scheduling
- traveling salesman problem
- vehicle routing problemVehicle routing problemThe vehicle routing problem is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields of transportation, distribution and logistics...
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, artificial intelligenceArtificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
and operational research 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 algorithmMemetic algorithmMemetic algorithms represent one of the recent growing areas of research in evolutionary computation. The term MA is now widely used as a synergy of evolutionary or any population-based approach with separate individual learning or local improvement procedures for problem search...
- adaptive large neighborhood search
- algorithm configuration
- algorithm control
- algorithm portfolios
- genetic programmingGenetic programmingIn artificial intelligence, genetic programming is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program...
- indirect encodings in evolutionary algorithms
- variable neighborhood search
- reactive search
See also
- Meta-optimizationMeta-optimizationIn numerical optimization, meta-optimization is the use of one optimization method to tune another optimization method. Meta-optimization is reported to have been used as early as in the late 1970s by Mercer and Sampson for finding optimal parameter settings of a genetic algorithm...
is closely related to hyper-heuristics. - genetic algorithms
- genetic programmingGenetic programmingIn artificial intelligence, genetic programming is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program...
- evolutionary algorithms
- local search (optimization)Local search (optimization)In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
- machine learningMachine learningMachine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
- memetic algorithms
- metaheuristics
- no free lunch in search and optimization
- particle swarm optimizationParticle swarm optimizationIn computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
- reactive search
Research groups
- Artificial Intelligence (ART+I) Laboratory, Yeditepe University, TurkeyTurkeyTurkey , known officially as the Republic of Turkey , is a Eurasian country located in Western Asia and in East Thrace in Southeastern Europe...
- Automated Scheduling, Optimisation and Planning (ASAP) Research Group, University of Nottingham, UK
- Combinatorial Optimisation and Decision Support (CODeS), Katholieke Universiteit Leuven, BelgiumBelgiumBelgium , officially the Kingdom of Belgium, is a federal state in Western Europe. It is a founding member of the European Union and hosts the EU's headquarters, and those of several other major international organisations such as NATO.Belgium is also a member of, or affiliated to, many...
- Intelligent Systems Lab, Heriot-Watt University, UK
- IT Research Group, KaHo Sint-Lieven, Associate K.U. Leuven, BelgiumBelgiumBelgium , officially the Kingdom of Belgium, is a federal state in Western Europe. It is a founding member of the European Union and hosts the EU's headquarters, and those of several other major international organisations such as NATO.Belgium is also a member of, or affiliated to, many...
- Modelling Optimisation Scheduling and Intelligent Control (MOSAIC) Research Group, University of Bradford, UK
Recent activities
- Cross-domain Heuristic Search Challenge 2011 (CHeSC 2011)
- Workshop on Hyper-heuristics, to be held in conjunction with PPSN X, 10th International Conference on Parallel Problem Solving From Nature, Dortmund, Germany