Vfrdtyky

What are the limitations of the hill climbing algorithm? How can we overcome these limitations?

As @nbro 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

Hill climbing 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" (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).