Hyper-heuristics versus metaheuristics
The fundamental difference between metaheuristics 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, 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.Burke E.K., Landa Silva J.D., Soubeiga E.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 artificial intelligence. 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 aClassification 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 heuristicsMethodologies 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 heuristicsOn-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 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 approaches within hyper-heuristics are: learning classifier systems, case-base reasoning and genetic programming. 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.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 * boolean satisfiability problem * educational timetabling * job shop scheduling * multi-objective problem solving and space allocation * nurse rostering * personnel scheduling * traveling salesman problem * vehicle routing problem * multidimensional knapsack problem * 0-1 knapsack problem * maximum cut problem *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 intelligence 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 * adaptiveSee also
* Constructive heuristic *References and notes
External links
Hyper-heuristic bibliographies
Research groups
Recent activities
Others