Answers.Body: <p><a href="https://github.com/aimacode/aima-pseudocode/blob/master/md/Hill-Climbing.md" rel="noreferrer">Hill climbing</a> is not an algorithm, but a family of "local search" algorithms. Specific algorithms which fall into the category of "hill climbing" algorithms are 2-opt, 3-opt, 2.5-opt, 4-opt, or, in general, any N-opt. See chapter 3 of the paper "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.1635&amp;rep=rep1&amp;type=pdf" rel="noreferrer"><em>The Traveling Salesman Problem: A Case Study in Local Optimization</em></a>" (by David S. Johnson and Lyle A. McGeoch) for more details regarding some of these local search algorithms (applied to the TSP). </p>
  
  <p>What differentiates one algorithm in this category from the other is the "neighbourhood function" they use (in simple words, the way they find neighbouring solutions to a given solution). Note that, in practice, this is not always the case: often these algorithms have several different implementations.</p>
  
  <p>The most evident limitation of hill climbing algorithms is due to their nature, that is, they are local search algorithms. Hence they usually just find <em>local</em> maxima (or minima). So, if any of these algorithms has already converged to a local minimum (or maximum) and, in the solution or search space, there is, close to this found solution, a better solution, none of these algorithms will be able to find this better solution. They will basically be trapped.</p>
  
  <p>Local search algorithms are not usually used alone. They are used as sub-routines of other meta-heuristic algorithms, like simulated annealing, iterated-local search or in any of the ant-colony algorithms. So, to overcome their limitations, we usually do not use them alone, but we use them in conjunction with other algorithms, which have a probabilistic nature and can find global minima or maxima (e.g., any of the ant-colony algorithms).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-15T16:08:19.773Z
Answers.Text: Nice answer (+1)! Can you recommend a resource (YouTube, blog post, arxive paper, book) to learn about ant-colony algorithms? I've never heard about that and would like to get a rough idea of them.
Answers.UserDisplayName: Martin Thoma
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-15T16:16:15.123Z
Answers.Text: @MartinThoma I am afraid I really don't know of a very nice tutorial on ACS. Maybe you can start with the following brief tutorial and the corresponding implementation: http://www.cleveralgorithms.com/nature-inspired/swarm/ant_colony_system.html. If you're also interested in a more serious implementation, applied to the TSP, then have a look at this one: http://www.aco-metaheuristic.org/aco-code/, implemented by Stützle (and others), one of the contributors to the development of these techniques.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-15T16:16:46.867Z
Answers.Text: @MartinThoma Anyway, you can also have a look at the research papers. I can only tell you a few important researchers: Dorigo (the first one that introduced these techniques, AFAIK), Gambardella and Stützle. Look at their papers. I am not sure which one to suggest. Also, there's a book dedicated to swarm intelligence (by Bonabeau), if you're really want to go into the details.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-15T15:33:43.450Z
Answers.LastActivityDate: 2018-11-15T15:39:24.283Z
Answers.LastEditDate: 2018-11-15T15:39:24.283Z
Answers.UserDisplayName: nbro
Answers.Body: <p>As @nbro has already said that Hill Climbing is a family of <strong>local search algorithms</strong>. So, when you said Hill Climbing in the question I have assumed you are talking about the standard hill climbing. The standard version of hill climb has some limitations and often gets stuck in the following scenario:</p>
  
  <ul>
  <li>Local Maxima: Hill-climbing algorithm reaching on the vicinity a local maximum value, gets drawn towards the peak and gets stuck there, <em>having no other place to go</em>.</li>
  <li>Ridges: These are <em>sequences of local maxima</em>, making it difficult for the algorithm to navigate.</li>
  <li>Plateaux: This is a <em>flat state-space region</em>. As there is no uphill to go, algorithm often gets lost in the plateau.
  <br></li>
  </ul>
  
  <p>To resolve these issues many variants of hill climb algorithms have been developed. These are most commonly used:</p>
  
  <ul>
  <li><strong>Stochastic Hill Climbing</strong> selects at random from the uphill moves. The probability of selection varies with the steepness of the uphill move.</li>
  <li><strong>First-Choice Climbing</strong> implements the above one by generating successors randomly until a better one is found.</li>
  <li><strong>Random-restart hill climbing</strong> searches from randomly generated initial moves until the goal state is reached.</li>
  </ul>
  
  <p>The success of hill climb algorithms depends on the architecture of the state-space landscape. Whenever there are few maxima and plateaux the variants of hill climb searching algorithms work very fine. But in real-world problems have a landscape that looks more like a widely scattered family of balding porcupines on a flat floor, with miniature porcupines living on the tip of each porcupine needle (as described in the 4th Chapter of the book Artificial Intelligence: A Modern Approach). NP-Hard problems typically have an exponential number of local maxima to get stuck on.<br>
  Given algorithms have been developed to overcome these kinds of issues:</p>
  
  <ul>
  <li>Stimulated Annealing</li>
  <li>Local Beam Search</li>
  <li>Genetic Algorithms</li>
  </ul>
  
  <p>Reference <a href="https://rads.stackoverflow.com/amzn/click/0136042597" rel="noreferrer">Book - Artificial Intelligence: A Modern Approach</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-15T16:28:18.853Z
Answers.LastActivityDate: 2018-11-15T16:28:18.853Z
Answers.UserDisplayName: Ugnes
Body: <p>What are the limitations of the <em>hill climbing algorithm</em>? How can we overcome these limitations?</p>
  
Tags: <algorithm><search><optimization><problem-solving><hill-climbing>
Title: What are the limitations of the hill climbing algorithm and how to overcome them?
UserDisplayName: Abbas Ali
ThreadText: # What are the limitations of the hill climbing algorithm and how to overcome them?
  
  (Asked by: username_0 on 2018-11-15)
  
  What are the limitations of the *hill climbing algorithm*? How can we overcome these limitations?
  
  **Tags:** algorithm, search, optimization, problem-solving, hill-climbing
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2018-11-15. Score: 6 | Accepted answer
  
  As @username_1 has already said that Hill Climbing is a family of **local search algorithms**. So, when you said Hill Climbing in the question I have assumed you are talking about the standard hill climbing. The standard version of hill climb has some limitations and often gets stuck in the following scenario:
  
  * Local Maxima: Hill-climbing algorithm reaching on the vicinity a local maximum value, gets drawn towards the peak and gets stuck there, *having no other place to go*.
  * Ridges: These are *sequences of local maxima*, making it difficult for the algorithm to navigate.
  * Plateaux: This is a *flat state-space region*. As there is no uphill to go, algorithm often gets lost in the plateau.
  
  To resolve these issues many variants of hill climb algorithms have been developed. These are most commonly used:
  
  * **Stochastic Hill Climbing** selects at random from the uphill moves. The probability of selection varies with the steepness of the uphill move.
  * **First-Choice Climbing** implements the above one by generating successors randomly until a better one is found.
  * **Random-restart hill climbing** searches from randomly generated initial moves until the goal state is reached.
  
  The success of hill climb algorithms depends on the architecture of the state-space landscape. Whenever there are few maxima and plateaux the variants of hill climb searching algorithms work very fine. But in real-world problems have a landscape that looks more like a widely scattered family of balding porcupines on a flat floor, with miniature porcupines living on the tip of each porcupine needle (as described in the 4th Chapter of the book Artificial Intelligence: A Modern Approach). NP-Hard problems typically have an exponential number of local maxima to get stuck on.  
  Given algorithms have been developed to overcome these kinds of issues:
  
  * Stimulated Annealing
  * Local Beam Search
  * Genetic Algorithms
  
  Reference [Book - Artificial Intelligence: A Modern Approach](https://rads.stackoverflow.com/amzn/click/0136042597)
  
  
  ---
  
  ### Answer by username_1 on 2018-11-15. Score: 5
  
  [Hill climbing](https://github.com/aimacode/aima-pseudocode/blob/master/md/Hill-Climbing.md) is not an algorithm, but a family of "local search" algorithms. Specific algorithms which fall into the category of "hill climbing" algorithms are 2-opt, 3-opt, 2.5-opt, 4-opt, or, in general, any N-opt. See chapter 3 of the paper "[*The Traveling Salesman Problem: A Case Study in Local Optimization*](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.1635&rep=rep1&type=pdf)" (by David S. Johnson and Lyle A. McGeoch) for more details regarding some of these local search algorithms (applied to the TSP).
  
  What differentiates one algorithm in this category from the other is the "neighbourhood function" they use (in simple words, the way they find neighbouring solutions to a given solution). Note that, in practice, this is not always the case: often these algorithms have several different implementations.
  
  The most evident limitation of hill climbing algorithms is due to their nature, that is, they are local search algorithms. Hence they usually just find *local* maxima (or minima). So, if any of these algorithms has already converged to a local minimum (or maximum) and, in the solution or search space, there is, close to this found solution, a better solution, none of these algorithms will be able to find this better solution. They will basically be trapped.
  
  Local search algorithms are not usually used alone. They are used as sub-routines of other meta-heuristic algorithms, like simulated annealing, iterated-local search or in any of the ant-colony algorithms. So, to overcome their limitations, we usually do not use them alone, but we use them in conjunction with other algorithms, which have a probabilistic nature and can find global minima or maxima (e.g., any of the ant-colony algorithms).
  
  > **Comments:**
  > **username_2**: Nice answer (+1)! Can you recommend a resource (YouTube, blog post, arxive paper, book) to learn about ant-colony algorithms? I've never heard about that and would like to get a rough idea of them.  
  > **username_1**: @username_2 I am afraid I really don't know of a very nice tutorial on ACS. Maybe you can start with the following brief tutorial and the corresponding implementation: http://www.cleveralgorithms.com/nature-inspired/swarm/ant_colony_system.html. If you're also interested in a more serious implementation, applied to the TSP, then have a look at this one: http://www.aco-metaheuristic.org/aco-code/, implemented by Stützle (and others), one of the contributors to the development of these techniques.  
  > **username_1**: @username_2 Anyway, you can also have a look at the research papers. I can only tell you a few important researchers: Dorigo (the first one that introduced these techniques, AFAIK), Gambardella and Stützle. Look at their papers. I am not sure which one to suggest. Also, there's a book dedicated to swarm intelligence (by Bonabeau), if you're really want to go into the details.  
  
  ---
  
  