When to choose Stochastic Hill Climbing over Steepest Hill Climbing?

Question

Stochastic Hill Climbing generally performs worse than Steepest Hill Climbing, but what are the cases in which the former performs better?

Answer 1

The steepest hill climbing algorithms works well for convex optimization. However, real world problems are typically of the non-convex optimization type: there are multiple peaks. In such cases, when this algorithm starts at a random solution, the likelihood of it reaching one of the local peaks, instead of the global peak, is high. Improvements like Simulated Annealing ameliorate this issue by allowing the algorithm to move away from a local peak, and thereby increasing the likelihood that it will find the global peak.

Obviously, for a simple problem with only one peak, the steepest hill climbing is always better. It can also use early stopping if a global peak is found. In comparison, a simulated annealing algorithm would actually jump away from a global peak, return back and jump away again. This would repeat until its cooled down enough or a certain preset number of iterations have completed.

Real world problems deal with noisy and missing data. A stochastic hill climbing approach, while slower, is more robust to these issues, and the optimization routine has a higher likelihood of reaching the global peak in comparison to the steepest hill climbing algorithm.

Epilogue: This is a good question which raises a persistent question when designing a solution or choosing between various algorithms: the performance-computational cost trade-off. As you might have suspected, the answer is always: it depends on your algorithm's priorities. If it is part of some online learning system that is operating on a batch of data, then there is a strong time constraint, but weak performance constraint (next batches of data will correct for erroneous bias introduced by first batch of data). On the other hand, if it is an offline learning task with the entire available data in hand, then performance is the main constraint, and the stochastic approaches are advisable.

Answer 2

Let's begin with some definitions first.
Hill-climbing is a search algorithm simply runs a loop and continuously moves in the direction of increasing value-that is, uphill. The loop terminates when it reaches a peak and no neighbour has a higher value.

Stochastic hill climbing, a variant of hill-climbing, chooses a random from among the uphill moves. The probability of selection can vary with the steepness of the uphill move.Two well-known methods are:
First-choice hill climbing: generates successors randomly until one is generated that is better than the current state. *Considered good if state has many successors (like thousands, or millions).
Random-restart hill climbing: Works on the philosophy of "If you don't succeed, try, try again".

Now to your answer. Stochastic hill climbing can actually perform better in many cases. Consider the following case. The image shows state-space landscape. The example present in the image is taken from the book, Artificial Intelligence: A Modern Approach.

Suppose you are at the point shown by the current state. If you implement simple hill climbing algorithm you will reach the local maximum and the algorithm terminates. Even though there exists state with more optimal objective function value but, the algorithm fails to reach there as it got stuck at a local maximum. Algorithm can also get stuck at flat local maxima.
Random restart hill climbing conducts a series of hill climbing searches from randomly generated initial states until a goal state is found.

The success of hill climbing depends on the shape of the state-space landscape. In case there are only a few local maxima, flat plateaux; random-restart hill climb will find a good solution very quickly. Most real-life problems have very rough state-space landscape, making them not suitable for using hill climbing algorithm, or any of its variant.

NOTE: Hill Climb Algorithm can also be used to find the minimum value, and not just the maximum values. I have used the term maximum in my answer. In case you are looking for minimum values, all things will be reverse, including the graph.

Answer 3

I'm new to these concepts too, but the way I've understood it, Stochastic hill climbing would perform better in cases where computation time is precious (includes the calculation of the fitness function) but it is not really necessary to reach the best possible solution. Reaching even a local optimum would be ok. Robots operating in a swarm would be one example where this could be used.

The only difference I see in steepest hill climbing is the fact that it searches not just the neighbour nodes but also the successors of the neighbours, pretty much like how a chess algorithm searches for many more further moves ahead before selecting the best move.

Answer 4

TLDR: If you are attempting to find the global optimum of $S$, where $S$ is a score function with multiple local optima, such that not all local optima have an equal value.