Hill climbing algorithm: a practical optimisation tutorial
Hill climbing is one of the oldest and most direct techniques in the optimisation toolbox. It searches for the best answer to a problem by repeatedly nudging a candidate solution toward neighbours that score better under the chosen objective. When you want something that runs in seconds, explains itself in a few lines of pseudocode, and beats a random baseline, this family of methods is often the first port of call. It is also the conceptual ancestor of more sophisticated approaches such as simulated annealing and tabu search, so understanding it well pays dividends across machine learning, operations research, and combinatorial problem solving. Learn more about A Guide To The Newton Raphson Method For Root Finding.
The technique belongs to the broader category of local search. Unlike a Newton-Raphson walkthrough, which uses calculus to converge to a precise root, hill climbing relies only on evaluating the objective at nearby points and accepting the move when it improves the score. That makes it trivially generalisable to non-differentiable or even discontinuous objective functions, including the discrete landscapes that dominate scheduling, routing, and feature selection. Learn more about Data Structures.
Across Australia, engineers at firms such as Rio Tinto and BHP routinely tackle large combinatorial problems tied to the Pilbara iron ore supply chain, while software teams in Sydney and Melbourne apply the same ideas to electricity dispatch, freight routing, and the matching of support workers to NDIS participants. The algorithm's appeal in these settings is its transparency: a reviewer can read the pseudocode, replay the steps, and reproduce the outcome without proprietary tooling, which matters when an audit under the Privacy Act 1988 is on the horizon. Learn more about Understanding The Softmax Function And Its Uses.
The core idea behind local search
Hill climbing keeps a single current solution in memory. At each iteration it generates a set of neighbour solutions through a perturbation rule and chooses one that strictly improves the objective value. The process stops when no neighbour offers an improvement, at which point the algorithm has reached a local optimum. Because it never accepts a worsening move, the score is monotonically non-decreasing along the trajectory, which makes the method easy to debug and easy to plot.
A useful mental image is climbing a foggy mountain. You cannot see the summit, but you can always feel which direction goes up. Each step takes you to the highest reachable neighbour, and you keep walking until every step around you would take you downhill. That summit may be the true peak, or it may be a foothill, since the algorithm has no way to tell, which is both its weakness and the reason for the many variants discussed later.
The objective landscape matters a great deal. On a smooth, bowl-shaped surface such as a convex quadratic, a single greedy climb is almost always enough to reach the global minimum. On a rugged surface with many ridges and basins, the algorithm gets trapped. The data structures used to represent a solution, whether an array of bits, a permutation, or a real-valued vector, determine what counts as a neighbour and therefore shape the entire search.
Pseudocode, complexity, and a comparison of variants
The skeleton of any hill climber fits in roughly a dozen lines. The complexity is dominated by the cost of evaluating the objective and the size of the neighbourhood, with each iteration typically running in O(k · f) where k is the number of neighbours sampled and f is the cost of one objective evaluation. There is no polynomial guarantee of finding the global optimum, so any analysis must be framed in terms of expected behaviour over repeated runs.
| Variant | Neighbour selection | Acceptance rule | Strength | Weakness |
|---|---|---|---|---|
| Simple hill climbing | First improving neighbour | Strictly better | Fastest per step | Unpredictable trajectory |
| Steepest ascent | Best neighbour in window | Strictly better | Stronger local moves | Costlier per step |
| Stochastic | Random neighbour | Probabilistic | Escapes shallow ridges | Tunable noise parameter |
| Random restart | Independent runs | Strictly better per run | Handles multimodality | Needs a budget cap |
| Simulated annealing | Random neighbour | Allows worsening with cooling | Strong global search | More parameters to tune |
The simple form takes the first neighbour that beats the current value, which keeps each iteration cheap but produces trajectories that depend heavily on the ordering of the neighbourhood. Steepest ascent evaluates the entire window and picks the best move, trading speed for a sharper climb. Stochastic variants sample one neighbour at random and accept it with a probability that may briefly allow worsening steps, mimicking thermal noise to escape small local maxima. Random restart simply runs the whole procedure many times from fresh starts, an embarrassingly parallel strategy that fits nicely with cloud runners in Sydney or Melbourne. Simulated annealing is included here as the canonical extension, since it shares the same scaffolding but adds a temperature schedule.
Implementing the algorithm step by step
A working implementation only needs four pieces: a way to encode a candidate solution, a function that scores it, a rule that perturbs it to produce neighbours, and a loop that walks the search. In Python this translates to a handful of functions and a while-loop. For continuous problems the perturbation is typically a Gaussian step added to a real-valued vector, while for combinatorial problems it is often a swap, an insertion, or a bit flip applied to a discrete representation.
For a continuous benchmark such as the sphere function f(x) = Σ xᵢ², the steepest ascent variant can be written by sampling k random directions, evaluating the objective along each, and accepting the direction with the largest improvement. The same skeleton handles higher-dimensional problems, though the curvature of the landscape then becomes the deciding factor for whether the climb converges in a reasonable number of steps.
For discrete problems the pattern is identical. A classic toy example is the eight queens puzzle, where each configuration is an array of column positions and each neighbour differs by moving a single queen one square vertically. A simple climber places queens randomly, scores the number of attacking pairs, and climbs until the score hits zero. The same logic scales to vehicle routing instances solved by logistics teams in Brisbane or Adelaide, where the perturbation swaps two customer visits in a tour and the score combines distance, time windows, and load balance.
Where hill climbing earns its keep
Hill climbing continues to be a workhorse in production systems across multiple industries. In the energy sector the Australian Energy Market Operator uses local search techniques inside its dispatch and ancillary services engines, where the objective mixes price, ramp rates, and reserve margins. Telecommunications companies operating the National Broadband Network rely on local search when configuring transmission parameters across thousands of nodes, since a closed-form solution is rarely available.
Feature selection in machine learning is another natural fit. Given a model with hundreds of candidate inputs, a hill climber can flip a bit, retrain or refit, and keep the change when the validation score improves. Compared with brute-force grid search over softmax in classification tasks in neural classifiers, the local approach is dramatically cheaper and often finds near-optimal subsets in a fraction of the time. Hyperparameter tuning for gradient boosted trees follows the same recipe, and tuning of regularisation strength in logistic models behaves similarly when paired with cross-validation under the ACCC's data-handling expectations for consumer-facing analytics.
The method also appears in scheduling problems faced by Australian universities and hospitals. Universities such as the University of Melbourne and UNSW timetable thousands of classes into lecture halls under hard constraints, and a stochastic climber with random restarts is routinely part of the toolchain. Hospitals running theatre scheduling under the Australian Private Health Insurance arrangements use similar logic to balance surgeon availability, equipment, and recovery bays, where the privacy obligations set out in the Privacy Act 1988 add a further incentive to keep models auditable.
Common pitfalls and practical tips
- Always fix a random seed during development so that bugs become reproducible, then remove it for production runs.
- Track the best solution seen so far, not just the current one, because restarts and stochastic moves can briefly descend.
- Profile the objective function before anything else, since an optimiser is only as fast as its evaluation step.
- Use random restarts as a cheap insurance policy whenever the landscape is suspected to be multimodal.
- Visualise the trajectory in two or three dimensions whenever possible, since patterns of stuck runs often reveal structural problems with the neighbourhood.
- When the climber plateaus early, suspect a poorly chosen perturbation before suspecting the algorithm itself.