Hyper-heuristic

Last updated

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. [1] [2] [3]

Contents

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. [4] 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. [2] [5] [6]

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. [7] In order to reduce the gap between tailor-made schemes and hyperheuristic-based strategies, parallel hyperheuristics have been proposed. [8]

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". [9] They used a "choice function" machine learning approach which trades off exploitation and exploration in choosing the next heuristic to use. [10] 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. [11] The origin of the idea (although not the term) can be traced back to the early 1960s [12] [13] and was independently re-discovered and extended several times during the 1990s. [14] [15] [16] In the domain of Job Shop Scheduling, the pioneering work by Fisher and Thompson, [12] [13] 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., [17] [18] 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, [9] [10] 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." [19] 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.

Methodologies to generate heuristics

Generate new heuristic methods using basic components of previously existing heuristic methods.

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 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, [20] 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:

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:

Existing frameworks

Nowadays, there are several frameworks available, in different programming languages. These include, but are not limited to:

HyFlex

ParHyFlex

EvoHyp

MatHH

See also

References and notes

  1. ↑ E. K. Burke, E. Hart, G. Kendall, J. Newall, P. Ross, and S. Schulenburg, Hyper-heuristics: An emerging direction in modern search technology, Handbook of Metaheuristics (F. Glover and G. Kochenberger, eds.), Kluwer, 2003, pp. 457–474.
  2. 1 2 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.
  3. ↑ E. Ozcan, B. Bilgin, E. E. Korkmaz, A Comprehensive Analysis of Hyper-heuristics [ dead link ], Intelligent Data Analysis, 12:1, pp. 3-23, 2008.
  4. ↑ 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.
  5. ↑ 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/stamp/stamp.jsp?arnumber=8335843
  6. ↑ Amaya, 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
  7. ↑ 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.
  8. ↑ 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, ( doi : 10.1007/s12293-010-0044-5 ), 2010.
  9. 1 2 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
  10. 1 2 Cowling P., 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, ISBN   3540424210, ( doi : 10.1007/3-540-44629-X
  11. ↑ Burke E. K., Kendall G., and Soubeiga E. (2003) A Tabu-Search Hyper-Heuristic for Timetabling and Rostering. Journal of Heuristics, 9(6):451-470. ( doi : 10.1023/B:HEUR.0000012446.94732.b6 )
  12. 1 2 H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, Factory Scheduling Conference (Carnegie Institute of Technology), 1961.
  13. 1 2
    • 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.
  14. ↑ R. H. Storer, S. D. Wu, and R. Vaccari, New search spaces for sequencing problems with application to job shop scheduling, Management Science, 38 (10), 1992, 1495–1509.
  15. ↑ H. L. Fang, P. Ross, and D. Corne, A promising genetic algorithm approach to job shop scheduling, rescheduling, and open-shop scheduling problems, Fifth International Conference on Genetic Algorithms (San Mateo) (S. Forrest, ed.), Morgan Kaufmann, 1993, pp. 375–382.
  16. ↑ U. Dorndorf and E. Pesch, Evolution based learning in a job shop scheduling environment, Computers and Operations Research, 22(1), 1995, 25–40.
  17. ↑ J. Gratch, S. Chien, and G. DeJong, Learning search control knowledge for deep space network scheduling, Proceedings of the Tenth International Conference on Machine Learning (Amherst, MA), 1993, pp. 135–142.
  18. ↑ J. Gratch and S. Chien, Adaptive problem-solving for large-scale scheduling problems: a case study, Journal of Artificial Intelligence Research, 4, 1996, 365–396.
  19. ↑ M. Bader-El-Den and R. Poli, Generating sat local-search heuristics using a GP hyper-heuristic framework Archived 2017-08-09 at the Wayback Machine , Artificial Evolution, 8th International Conference, Evolution Artificielle, EA 2007, Tours, France, October 29–31, 2007, Revised Selected Papers. Lecture Notes in Computer Science 4926 Springer, 2008, pp. 37-49.
  20. ↑ 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. ( doi : 10.1016/j.ejor.2019.07.073 )

Hyper-heuristic bibliographies

Research groups

Recent activities

Others

Related Research Articles

<span class="mw-page-title-main">Genetic algorithm</span> Competitive algorithm for searching a problem space

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. Some examples of GA applications include optimizing decision trees for better performance, solving sudoku puzzles, hyperparameter optimization, causal inference, etc.

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 reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators.

<span class="mw-page-title-main">Evolutionary computation</span> Trial and error problem solvers with a metaheuristic or stochastic optimization character

In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, they are a family of population-based trial and error problem solvers with a metaheuristic or stochastic optimization character.

<span class="mw-page-title-main">Particle swarm optimization</span> Iterative simulation method

In computational science, particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. It solves a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formulae over the particle's position and velocity. Each particle's movement is influenced by its local best known position, but is also guided toward the best known positions in the search-space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions.

<span class="mw-page-title-main">Ant colony optimization algorithms</span> Optimization algorithm

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.

In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored. Metaheuristics may make relatively few assumptions about the optimization problem being solved and so may be usable for a variety of problems. Their use is always of interest when exact or other (approximate) methods are not available or are not expedient, either because the calculation time is too long or because, for example, the solution provided is too imprecise.

A memetic algorithm (MA) in computer science and operations research, is an extension of the traditional genetic algorithm (GA) or more general evolutionary algorithm (EA). It may provide a sufficiently good solution to an optimization problem. It uses a suitable heuristic or local search technique to improve the quality of solutions generated by the EA and to reduce the likelihood of premature convergence.

Search-based software engineering (SBSE) applies metaheuristic search techniques such as genetic algorithms, simulated annealing and tabu search to software engineering problems. Many activities in software engineering can be stated as optimization problems. Optimization techniques of operations research such as linear programming or dynamic programming are often impractical for large scale software engineering problems because of their computational complexity or their assumptions on the problem structure. Researchers and practitioners use metaheuristic search techniques, which impose little assumptions on the problem structure, to find near-optimal or "good-enough" solutions.

In mathematical optimization and computer science, heuristic is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution in a search space. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.

<span class="mw-page-title-main">Meta-optimization</span>

In 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.

<span class="mw-page-title-main">Enrique Alba</span> Spanish computer science professor (born 1968)

Enrique Alba is a professor of computer science at the University of Málaga, Spain.

The constructive cooperative coevolutionary algorithm (also called C3) is a global optimisation algorithm in artificial intelligence based on the multi-start architecture of the greedy randomized adaptive search procedure (GRASP). It incorporates the existing cooperative coevolutionary algorithm (CC). The considered problem is decomposed into subproblems. These subproblems are optimised separately while exchanging information in order to solve the complete problem. An optimisation algorithm, usually but not necessarily an evolutionary algorithm, is embedded in C3 for optimising those subproblems. The nature of the embedded optimisation algorithm determines whether C3's behaviour is deterministic or stochastic.

A constructive heuristic is a type of heuristic method which starts with an empty solution and repeatedly extends the current solution until a complete solution is obtained. It differs from local search heuristics which start with a complete solution and then try to improve the current solution further via local moves. Examples of some famous problems that are solved using constructive heuristics are the flow shop scheduling, the vehicle routing problem and the open shop problem.

The Genetic and Evolutionary Computation Conference (GECCO) is the premier conference in the area of genetic and evolutionary computation. GECCO has been held every year since 1999, when it was first established as a recombination of the International Conference on Genetic Algorithms (ICGA) and the Annual Genetic Programming Conference (GP).

This glossary of artificial intelligence is a list of definitions of terms and concepts relevant to the study of artificial intelligence, its sub-disciplines, and related fields. Related glossaries include Glossary of computer science, Glossary of robotics, and Glossary of machine vision.

<span class="mw-page-title-main">Emma Hart (computer scientist)</span> English computer scientist

Professor Emma Hart, FRSE is an English computer scientist known for her work in artificial immune systems (AIS), evolutionary computation and optimisation. She is a professor of computational intelligence at Edinburgh Napier University, editor-in-chief of the Journal of Evolutionary Computation, and D. Coordinator of the Future & Emerging Technologies (FET) Proactive Initiative, Fundamentals of Collective Adaptive Systems.

Memetic computing is a novel computational paradigm that incorporates the notion of meme(s) as basic units of transferable information encoded in computational representations for boosting the performance of artificial evolutionary systems in the domain of search and optimization.

This is a chronological table of metaheuristic algorithms that only contains fundamental computational intelligence algorithms. Hybrid algorithms and multi-objective algorithms are not listed in the table below.

<span class="mw-page-title-main">Gabriela Ochoa</span> Venezuelan British computer scientist

Gabriela Ochoa is a Venezuelan British computer scientist and Professor at the University of Stirling. Her research considers evolutionary algorithms and heuristic search methods.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.