Does restarting guarantee a better answer each time?

No. Individual runs can be worse; the best-so-far record preserves earlier gains.

How many restarts are enough?

That depends on the landscape, sampling rule, success criterion, and budget. A fixed number has no universal guarantee.

Must the initial state be uniformly random?

No. Other distributions are possible, but their effect on coverage and success must be understood.

AI Glossary / Graphs and symbolic AI / Intermediate

Random-restart hill climbing

Definition

Random-restart hill climbing is a local-search strategy that runs hill climbing from several randomly selected starting states. Each run improves its current candidate according to a local neighborhood rule. Restarting gives the search opportunities to enter different regions of the solution space, reducing dependence on a single starting point.

What it means

Hill climbing can stop at a local optimum: a candidate that has no better permitted neighbor even though a better solution exists elsewhere. A restart abandons that local trajectory and begins another one from a newly sampled candidate.
The method is useful when the desired result is a good final configuration rather than a particular route to reach it. “Hill climbing” usually describes maximization, but the same idea applies to minimizing a cost by moving downhill. The restart strategy does not repair a badly chosen objective or neighborhood. It only changes where local improvement begins and, depending on implementation, which random choices occur within a run.

How it works

Specify an objective, legal candidate states, a neighborhood, and a stopping rule for one hill-climbing run. Sample an initial state, perform local improvement, and retain the best result found. Repeat until a recognizable goal is reached or a total computation budget is exhausted.
For a finite-budget optimization problem, returning the best candidate across all runs prevents a poor final restart from replacing a better earlier result. Starting-state distribution matters: uniform sampling over one encoding may not be uniform over meaningful solutions. Rules for ties, sideways moves, and invalid candidates must also be explicit. A restart budget can be expressed in runs, objective evaluations, or elapsed computation.

Three practical examples

A scheduling prototype can generate several feasible initial schedules and improve each through allowed swaps, retaining the lowest-cost result.
A puzzle solver can restart after reaching a configuration with unresolved conflicts and no improving move under its neighborhood.
A layout experiment can compare results from different initial placements, measuring whether one favorable start is masking unreliable typical performance.

Think of it this way

Think of starting several climbs from different valleys when the landscape contains separate peaks. Reaching one nearby summit does not tell you whether it is the highest. The analogy is limited because a computational landscape may have millions of dimensions, and sampling starting points or finding valid neighbors can itself be difficult.

Worked example

Consider an invented maximization problem with ten possible starting states, sampled independently and uniformly with replacement. Assume deterministic hill climbing sends eight of those starts to a local optimum scoring 70 and the other two to a global optimum scoring 100. Every run terminates, and the toy landscape is fully known for this calculation.
The probability that one run finds the global optimum is p = 2/10 = 0.2. The probability that five independent runs all miss it is 0.8⁵ = 0.32768. Therefore the chance of at least one success is 1 − 0.8⁵ = 0.67232, about 67.2%.
The expected number of runs through the first success is 1/p = 5. If the first run is not counted as a restart, the expected number of additional restarts is 5 − 1 = 4. Keeping those counting conventions separate avoids an off-by-one misunderstanding.
For a success probability of at least 95% under these exact assumptions, choose k such that 1 − 0.8^k is at least 0.95. The smallest integer is 14, giving about 95.6%. This is not a universal recommended restart count. In a real problem, p may be unknown, runs may be dependent, and the global optimum may not be recognizable.
Suppose actual run scores are 70, 70, 100, 70, 70. With a five-run budget, retaining the best-so-far candidate returns 100 even though the final run returns 70.

Illustrative case study

Fictional case: Pine Scheduling Lab optimizes a demonstration roster using single-shift swaps. One initial roster repeatedly reaches a locally good arrangement, but another starting roster produces a better final score. The team introduces independent restarts and logs the best score against total objective evaluations.
It compares the method with a revised neighborhood that permits paired swaps. This helps distinguish the benefit of more starting points from the benefit of better moves. The fictional case does not claim that the resulting roster is globally optimal or that restarts always outperform a more carefully designed local search.

Common misconceptions and mistakes

Do not confuse random restarts with choosing every next move randomly. A run can use deterministic steepest improvement while only its starting point is random. Nor is restarting the same as allowing occasional worsening moves, as in simulated annealing.
The formula 1 − (1 − p)^k requires independent runs with the same success probability. Reusing the same seed and deterministic start-generation sequence can repeat the same search rather than provide new opportunities. A method whose success probability approaches one under suitable assumptions still offers no finite-time certainty. In continuous spaces, claims based on sampling an exact optimum require particular care.

Business use

Businesses can use random-restart hill climbing as a relatively transparent optimization baseline when good feasible configurations are valuable and an exact solution is expensive. It is especially useful for revealing sensitivity to initialization.
Evaluate the method under an equal overall budget against alternatives. Report the distribution of results across repeated experiments, not only the best lucky run. Make feasibility checks part of the objective pipeline, preserve the best valid solution, and state whether the stopping condition means a verified goal, a quality threshold, or simply exhaustion of time.

Check your understanding

In the toy model, does an expected five runs mean the fifth run must succeed?

Answer: No. Five is an average over repetitions of the experiment. Some searches succeed immediately and others need more than five runs.

Related terms

Local search
Hill climbing
Neighborhood
Simulated annealing
local optimum
global optimum
multistart optimization
initialization

Learn next

Change the toy success probability to 0.5. Five independent runs then succeed at least once with probability 1 − 0.5⁵ = 96.875%, and the expected number of runs is two. Explain why improving the starting distribution can matter as much as increasing the restart budget.

Sources

Sources: Russell and Norvig, author-hosted Informed Search and Exploration chapter, random-restart hill climbing: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap04.pdf . AIMA original Lisp documentation, random-restart-search: https://aima.cs.berkeley.edu/lisp/doc/overview-SEARCH.html .

Previous: Random projection Next: Random rounding