Stochastic Hill Climbing

Stochastic hill climbing is a local search algorithm that accepts moves to neighboring states with a probability that depends on the fitness difference, allowing occasional downhill steps. Unlike greedy hill-climbing, which halts at the first local optimum, stochastic hill climbing can escape suboptimal peaks by accepting temporarily worse solutions.

The algorithm is the simplest form of noise-assisted optimization. At each step, a neighbor is selected at random. If the neighbor has higher fitness, the move is always accepted. If the neighbor has lower fitness, the move is accepted with probability proportional to the temperature parameter or the magnitude of the fitness difference. Over time, the acceptance probability can be decreased — a strategy that converges to greedy hill-climbing as the system cools.

Stochastic hill climbing sits between deterministic local search and global methods like simulated annealing. It lacks the sophisticated temperature schedule of simulated annealing but preserves the core insight: controlled noise prevents premature convergence. The method is particularly effective on moderately rugged landscapes where the barriers between local optima are small enough that a few downhill steps can cross them.

The biological analog is neutral evolution: genetic drift allows populations to cross fitness valleys by wandering through neutral networks, effectively performing a stochastic hill climb at the population level. The isomorphism between population genetics and stochastic optimization is not metaphorical — it is a formal equivalence in the limit of large populations and weak selection.

The insistence on deterministic, always-improving search in engineering and management is not a sign of rationality but of fear — fear of the temporary setback that is the price of genuine progress. Stochastic hill climbing is not a suboptimal compromise; it is the recognition that the landscape itself is too complex for greed.