Answers.Body: <p><strong>TL:DR</strong>: Hyper-heuristics <em>are</em> metaheuristics, suited for solving the same kind of optimization problems, but (in principle) affording a "rapid prototyping" approach for non-expert practitioners. In practice, there are issues with the prevailing approach, motivating an emerging perspective on <a href="http://www.cs.nott.ac.uk/~pszeo/docs/publications/HHrecharacterization.pdf" rel="nofollow noreferrer">'whitebox' hyper-heuristics</a>.</p>
  
  <p>In more detail:</p>
  
  <p>Metaheuristics are methods for searching an intractably large space of possible solutions in order to find a 'high quality' solution. Popular metaheuristics include Simulated Annealing, Tabu Search, Genetic Algorithms etc.</p>
  
  <p>The essential difference between metaheuristics and hyper-heuristics is the addition of a level of search indirection: informally, hyper-heuristics can be described as 'heuristics for searching the space of heuristics'. One can therefore use any metaheuristic as a hyper-heuristic, providing the nature of the 'space of heuristics' to be searched is appropriately defined.</p>
  
  <p>The application area for hyper-heuristics is therefore the same as metaheuristics. Their applicability (relative to metaheuristics) is as a 'rapid prototyping tool': the original motivation was to allow non-expert practitioners to apply metaheuristics to their specific optimization problem (e.g. "Travelling-Salesman (TSP) plus time-windows plus bin-packing") without requiring expertise in the highly-specific problem domain. The idea was that this could be done by:</p>
  
  <ol>
  <li>Allowing practitioners to implement only very simple (effectively,
  randomized) heuristics for transforming potential solutions. For
  example, for the TSP: "swap two random cities" rather than (say) the more
  complex <a href="https://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic" rel="nofollow noreferrer">Lin-Kernighan</a> heuristic. </li>
  <li>Achieve effective results (despite using these simple heuristics) by combining/sequencing them in an intelligent way, typically by employing some form of learning mechanism.</li>
  </ol>
  
  <p>Hyper-heuristics can be described as 'selective' or 'generative' depending on whether the heuristics are  (respectively) sequenced or combined. Generative hyper-heuristics thus often use methods such as Genetic Programming to combine primitive heuristics and are therefore typically customized by the practitioner to solve a specific problem. For example, the <a href="http://s3.amazonaws.com/academia.edu.documents/44119367/Hyper-heuristics_Learning_To_Combine_Sim20160326-8451-ouh5fe.pdf?AWSAccessKeyId=AKIAJ56TQJRTWSMTNPEA&amp;Expires=1472329757&amp;Signature=KT1E2ATKreC%2BGlTvPmJGYBFRSRY%3D&amp;response-content-disposition=inline%3B%20filename%3DHyper-heuristics_learning_to_combine_sim.pdf" rel="nofollow noreferrer">original paper</a> on generative hyper-heuristics used a Learning Classifier System to combine heuristics for bin-packing. Because generative approaches are problem-specific, the comments below do not apply to them.</p>
  
  <p>In contrast, the <a href="http://www.cs.nott.ac.uk/~pszgxk/papers/evocop02exs.pdf" rel="nofollow noreferrer">original motivator</a> for selective hyper-heuristics was that researchers would be able to create a hyper-heuristic solver that was then likely to work well in an unseen problem domain, using only simple randomized heuristics.</p>
  
  <p>The way that this has traditionally been implemented was via the introduction of the <a href="http://www.cs.stir.ac.uk/~goc/papers/ChapterClassHH.pdf" rel="nofollow noreferrer">'hyper-heuristic domain barrier'</a> (see figure, below), whereby generality across problem domains is claimed to be achievable by preventing the solver from having knowledge of the domain on which it is operating. Instead, it would solve the problem by operating only on opaque integer indices into a list of available heuristics (e.g. in the manner of the <a href="https://en.wikipedia.org/wiki/Multi-armed_bandit" rel="nofollow noreferrer">'Multi-armed Bandit Problem'</a>).</p>
  
  <p><a href="https://i.sstatic.net/6IFna.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6IFna.png" alt="Traditional notion of Selective Hyper-heuristic"></a></p>
  
  <p>In practice, this 'domain blind' approach has not resulted in solutions of sufficient quality. In order to achieve results anywhere comparable to problem-specific metaheuristics, hyper-heuristic researchers have had to implement complex problem-specific heuristics, thereby failing in the goal of rapid prototyping.</p>
  
  <p>It is still possible <em>in principle</em> to create a selective hyper-heuristic solver which is capable of generalizing to new problem domains, but this has been made more difficult since the above notion of domain barrier means that only a very limited feature set is available for cross-domain learning (e.g. as exemplified by a popular <a href="https://arxiv.org/abs/1107.5462" rel="nofollow noreferrer">selective hyper-heuristic framework</a>).</p>
  
  <p>A more recent research perspective towards <a href="http://www.cs.nott.ac.uk/~pszeo/docs/publications/HHrecharacterization.pdf" rel="nofollow noreferrer">'whitebox' hyper-heuristics</a> advocates a declarative, feature-rich approach to describing problem domains. This approach has a number of claimed advantages:</p>
  
  <ol>
  <li>Practitioners now need no longer <em>implement</em> heuristics, but rather simply <em>specify</em> the problem domain.</li>
  <li>It eliminates the domain-barrier, putting hyper-heuristics on the same 'informed' status about the problem as problem-specific metaheuristics.</li>
  <li>With a whitebox problem description, the infamous <a href="https://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf" rel="nofollow noreferrer">'No Free Lunch' theorem</a> (which essentially states that, considered over the space of all <em>black box</em> problems, Simulated Annealing with an infinite annealing schedule is, on average, as good as any other approach) no longer applies.</li>
  </ol>
  
  <p>DISCLAIMER: I work in this research area, and it is therefore impossible to remove all personal bias from the answer.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-27T19:37:35.330Z
Answers.LastActivityDate: 2016-08-28T07:36:35.337Z
Answers.LastEditDate: 2016-08-28T07:36:35.337Z
Answers.UserDisplayName: NietzscheanAI
Body: <p>I wanted to know what the differences between <em>hyper-heuristics</em> and <em>meta-heuristics</em> are, and what their main applications are. Which problems are suited to be solved by hyper-heuristics?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-08-27T15:06:49.150Z
Comments.Text: I think this question could be really interesting if you share your research (e.g. links to interesting things you've found so far). Once we see a little background on your question, we can provide a better answer for you.
Comments.UserDisplayName: Ben N
Tags: <comparison><definitions><optimization><meta-heuristics>
Title: What are hyper-heuristics, and how are they different from meta-heuristics?
UserDisplayName: bmwalide
ThreadText: # What are hyper-heuristics, and how are they different from meta-heuristics?
  
  (Asked by: username_0 on 2016-08-27)
  
  I wanted to know what the differences between *hyper-heuristics* and *meta-heuristics* are, and what their main applications are. Which problems are suited to be solved by hyper-heuristics?
  
  **Tags:** comparison, definitions, optimization, meta-heuristics
  > **Comments:**
  > **username_1**: I think this question could be really interesting if you share your research (e.g. links to interesting things you've found so far). Once we see a little background on your question, we can provide a better answer for you.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2016-08-27. Score: 8 | Accepted answer
  
  **TL:DR**: Hyper-heuristics *are* metaheuristics, suited for solving the same kind of optimization problems, but (in principle) affording a "rapid prototyping" approach for non-expert practitioners. In practice, there are issues with the prevailing approach, motivating an emerging perspective on ['whitebox' hyper-heuristics](http://www.cs.nott.ac.uk/~pszeo/docs/publications/HHrecharacterization.pdf).
  
  In more detail:
  
  Metaheuristics are methods for searching an intractably large space of possible solutions in order to find a 'high quality' solution. Popular metaheuristics include Simulated Annealing, Tabu Search, Genetic Algorithms etc.
  
  The essential difference between metaheuristics and hyper-heuristics is the addition of a level of search indirection: informally, hyper-heuristics can be described as 'heuristics for searching the space of heuristics'. One can therefore use any metaheuristic as a hyper-heuristic, providing the nature of the 'space of heuristics' to be searched is appropriately defined.
  
  The application area for hyper-heuristics is therefore the same as metaheuristics. Their applicability (relative to metaheuristics) is as a 'rapid prototyping tool': the original motivation was to allow non-expert practitioners to apply metaheuristics to their specific optimization problem (e.g. "Travelling-Salesman (TSP) plus time-windows plus bin-packing") without requiring expertise in the highly-specific problem domain. The idea was that this could be done by:
  
  1. Allowing practitioners to implement only very simple (effectively,
     randomized) heuristics for transforming potential solutions. For
     example, for the TSP: "swap two random cities" rather than (say) the more
     complex [Lin-Kernighan](https://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic) heuristic.
  2. Achieve effective results (despite using these simple heuristics) by combining/sequencing them in an intelligent way, typically by employing some form of learning mechanism.
  
  Hyper-heuristics can be described as 'selective' or 'generative' depending on whether the heuristics are (respectively) sequenced or combined. Generative hyper-heuristics thus often use methods such as Genetic Programming to combine primitive heuristics and are therefore typically customized by the practitioner to solve a specific problem. For example, the [original paper](http://s3.amazonaws.com/academia.edu.documents/44119367/Hyper-heuristics_Learning_To_Combine_Sim20160326-8451-ouh5fe.pdf?AWSAccessKeyId=AKIAJ56TQJRTWSMTNPEA&Expires=1472329757&Signature=KT1E2ATKreC%2BGlTvPmJGYBFRSRY%3D&response-content-disposition=inline%3B%20filename%3DHyper-heuristics_learning_to_combine_sim.pdf) on generative hyper-heuristics used a Learning Classifier System to combine heuristics for bin-packing. Because generative approaches are problem-specific, the comments below do not apply to them.
  
  In contrast, the [original motivator](http://www.cs.nott.ac.uk/~pszgxk/papers/evocop02exs.pdf) for selective hyper-heuristics was that researchers would be able to create a hyper-heuristic solver that was then likely to work well in an unseen problem domain, using only simple randomized heuristics.
  
  The way that this has traditionally been implemented was via the introduction of the ['hyper-heuristic domain barrier'](http://www.cs.stir.ac.uk/~goc/papers/ChapterClassHH.pdf) (see figure, below), whereby generality across problem domains is claimed to be achievable by preventing the solver from having knowledge of the domain on which it is operating. Instead, it would solve the problem by operating only on opaque integer indices into a list of available heuristics (e.g. in the manner of the ['Multi-armed Bandit Problem'](https://en.wikipedia.org/wiki/Multi-armed_bandit)).
  
  [![Traditional notion of Selective Hyper-heuristic](https://i.sstatic.net/6IFna.png)](https://i.sstatic.net/6IFna.png)
  
  In practice, this 'domain blind' approach has not resulted in solutions of sufficient quality. In order to achieve results anywhere comparable to problem-specific metaheuristics, hyper-heuristic researchers have had to implement complex problem-specific heuristics, thereby failing in the goal of rapid prototyping.
  
  It is still possible *in principle* to create a selective hyper-heuristic solver which is capable of generalizing to new problem domains, but this has been made more difficult since the above notion of domain barrier means that only a very limited feature set is available for cross-domain learning (e.g. as exemplified by a popular [selective hyper-heuristic framework](https://arxiv.org/abs/1107.5462)).
  
  A more recent research perspective towards ['whitebox' hyper-heuristics](http://www.cs.nott.ac.uk/~pszeo/docs/publications/HHrecharacterization.pdf) advocates a declarative, feature-rich approach to describing problem domains. This approach has a number of claimed advantages:
  
  1. Practitioners now need no longer *implement* heuristics, but rather simply *specify* the problem domain.
  2. It eliminates the domain-barrier, putting hyper-heuristics on the same 'informed' status about the problem as problem-specific metaheuristics.
  3. With a whitebox problem description, the infamous ['No Free Lunch' theorem](https://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf) (which essentially states that, considered over the space of all *black box* problems, Simulated Annealing with an infinite annealing schedule is, on average, as good as any other approach) no longer applies.
  
  DISCLAIMER: I work in this research area, and it is therefore impossible to remove all personal bias from the answer.
  
  
  ---
  
  