Does stochastic mean the objective itself is random?

No. The objective can be deterministic while the move selection is random.

Can it escape every local maximum?

No. An uphill-only version has no acceptable move at a strict local maximum.

Must larger improvements have higher selection probability?

No. Uniform choice among improving neighbors is one valid version; the weighting rule must be stated.

AI Glossary / Graphs and symbolic AI / Intermediate

Stochastic hill climbing

Definition

Stochastic hill climbing is a local-search method that randomly selects among improving moves instead of always choosing the best immediate neighbor. The selection probabilities may be equal or may favor larger improvements. It introduces variety into an uphill search path while retaining the basic idea of moving toward better objective values.

What it means

A local-search problem needs a candidate representation, an objective, and a rule defining neighboring candidates. Stochastic hill climbing uses those ingredients but leaves part of the next-move decision to a random choice.
In the uphill-only meaning used here, randomness does not permit arbitrary worsening moves. The method can choose a smaller improvement that leads to a better region later, but it still stops when no permitted improvement exists. Simulated annealing uses a different acceptance mechanism that can allow downhill moves. Random restarts are another distinct mechanism: they change where a search begins rather than merely choosing among its current improving neighbors.

How it works

At the current state, identify or sample improving neighbors according to the implementation's rule. Choose one using a specified probability distribution, move there, and repeat. A simple version samples uniformly from the full set of improving neighbors. Another assigns weights based on the size of each improvement.
Record what happens when there are no improvements and whether equal-value moves are allowed. The strict-improvement version terminates on a finite state space with exact scores because every accepted move raises the objective and prevents revisiting a previous state. That termination property does not prove global optimality. Random choices influence which local optimum is reached.

Three practical examples

A scheduling prototype can randomly choose among swaps that improve its objective rather than always taking the largest immediate gain.
A puzzle experiment can compare the distribution of final scores across repeated uphill-only runs.
A configuration optimizer can test uniform selection against improvement-weighted selection under the same starting conditions and evaluation budget.

Think of it this way

Think of choosing randomly among several uphill trails instead of automatically taking the steepest one. A gentler first climb may lead toward a higher summit. The analogy is limited because an uphill-only traveler still cannot cross a valley just because the trail choice is random; another mechanism is needed to accept an initial loss of elevation.

Worked example

Consider an original directed search problem with a starting state S of score 10. Its improving neighbors are A with score 13, B with score 12, and C with score 11. There is also a neighbor D with score 9, which the strict uphill-only rule excludes.
From A, no further improving move exists. From B, a single improving move reaches a terminal state T of score 20. From C, a single improving move reaches a terminal state U of score 14. There are no other transitions. All objective evaluations are exact.
Steepest ascent chooses A immediately and stops at score 13. Uniform stochastic hill climbing selects A, B, or C with probability one third each. Its final scores are therefore 13, 20, and 14, each with probability one third. The expected final score is (13 + 20 + 14)/3 = 47/3, approximately 15.67.
Now choose among improving neighbors with weights proportional to their gains over S. The gains are 3 for A, 2 for B, and 1 for C, giving probabilities one half, one third, and one sixth. The expected final score becomes 13/2 + 20/3 + 14/6 = 15.5.
Both randomized rules outperform the deterministic rule in expected score on this stipulated example. That conclusion is specific to the graph; it is not a general performance guarantee. A different continuation beyond A, B, or C could reverse the comparison.
For three independent runs of the uniform rule from S, the probability of reaching T at least once is 1 − (2/3)³ = 19/27, about 70.4%. This calculation assumes independent choices and a separate best-found record across runs. It does not mean that a single run has a 70.4% chance.
Finally, give D a successor with score 30. The uphill-only method still cannot reach that successor from S because its first required move would decrease the score from 10 to 9. Random choice among improvements does not solve every local-search barrier.

Illustrative case study

In a fictional allocation experiment, a team compares steepest ascent with two stochastic selection rules. It runs each method repeatedly from the same starting allocation and records accepted moves, evaluation effort, and final feasibility.
The team reports the distribution of outcomes and the best result found within a fixed budget. It does not present one lucky randomized run as typical. This fictional case illustrates an evaluation design rather than claiming a measured advantage for a real organization.

Common misconceptions and mistakes

Stochastic hill climbing is not the same as choosing any random neighbor regardless of quality. It also does not automatically include restarts, sideways moves, or simulated annealing.
Do not assume that uniform selection among improving neighbors is equivalent to every procedure that repeatedly samples neighbors until an improvement appears; the proposal distribution matters. Do not compare expected performance using only one run. Finally, if scores are noisy, an apparently improving move may not be a true improvement, so the exact-score analysis needs reconsideration.

Business use

The method provides a simple way to test whether always taking the largest immediate gain is too restrictive. It can be an understandable baseline for optimization tasks where candidate changes and objective improvements are easy to inspect.
Keep the neighborhood, objective, and budget fixed when comparing selection rules. Record the random-seed practice and distinguish run-level results from a best-of-many result. Include the cost of identifying improving neighbors, because accepting fewer moves does not necessarily mean performing less computation.

Check your understanding

Why does adding a score-30 successor after D fail to help the strict uphill-only search from S?

Answer: Reaching it requires first taking the disallowed worsening move from score 10 to score 9.

Related terms

Hill climbing
Steepest ascent
Simulated annealing
Neighborhood
Expected value
Local optimum
Random restart
Search evaluation

Learn next

Next, calculate the probability that three independent uniform runs all stop at A: (1/3)³ = 1/27. Compare that event with failing to reach T, which also includes runs ending at U. Explain why those are different failure definitions.

Sources

Primary source: Russell and Norvig, AIMA, stochastic hill-climbing and related local-search variants: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap04.pdf . The directed graph, outcome expectations, and repeated-run probabilities are original examples.

Previous: Stochastic grammar Next: Stochastic matrix