Hill Climbing in AI

Hill climbing is a local search algorithm that improves one candidate solution at a time until no neighboring solution scores higher than the current one. The algorithm stops at the first point where no improvement is possible, and that point is often a local maximum rather than the best solution available in the entire search space..

This article defines hill climbing, breaks down every variant, works through a numeric example, compares it against three other search methods, and implements it in Python.

What Is Hill Climbing in AI?

Hill climbing is an iterative optimization algorithm that starts from an arbitrary solution and repeatedly moves to a better neighboring solution until no neighbor improves the result.

This method is a member of local search algorithms. Unlike other search algorithms, e.g. breadth-first search, which keeps several partial solutions, a local search algorithm works with one current solution at each step.

The following three properties are characteristic of a hill climbing algorithm:

• Greedy selection– At each iteration the algorithm selects a neighbor with the maximum evaluation value. It does not care about the future consequences of such a move.
• Single-state search– The algorithm keeps track of exactly one current solution at each iteration. It does not keep any search tree or population of candidates.
• No backtracking– when the algorithm selects a new state, it cannot come back to the old state even though the latter might have brought the algorithm to a better state in the future.

Hill climbing appears in Russell and Norvig’s Artificial Intelligence: A Modern Approach, the standard reference textbook for classical AI search algorithms, where it is presented alongside simulated annealing and genetic algorithms as a local search method.

How the Hill Climbing Algorithm Works

Steps of hill climbing are as follows:

1. Generate initial state: Create an initial state either randomly or heuristically.
2. Evaluate current state: Calculate the current solution score using some objective function.
3. Generate neighboring states: Create one or more candidate solutions through making slight changes in the current state.
4. Compare and select: Move towards a neighboring state if the score of a neighboring state is higher than the score of the current state.
5. Terminate: If there is no neighboring state with a higher score than the current state, terminate the algorithm and produce the current state as output.

The algorithm requires an objective function, also called a fitness function or cost function, to score each state numerically.

A Worked Numeric Example

Consider the function f(x) = −x² + 8, which has its maximum value at x = 0. A hill climbing search that starts at x = 3 with a step size of 1 proceeds as follows:

Step	Current x	f(x)	Neighbor (x+1)	f(x+1)	Neighbor (x−1)	f(x−1)	Move to
1	3	−1	4	−8	2	4	x = 2
2	2	4	3	−1	1	7	x = 1
3	1	7	2	4	0	8	x = 0
4	0	8	1	7	−1	7	Terminate

The algorithm reaches x = 0 in three moves and stops at step four, because neither neighbor scores higher than 8. This confirms the search found the global maximum in this case, because the function has only one peak. A function with multiple peaks would not guarantee this outcome, which is the basis of the local maxima problem covered next.

The State-Space Diagram: Local Maxima, Plateaus, Ridges & Shoulders

In the state-space graph, all the states that are visited by the algorithm are plotted along the x-axis while the values of the objective function for each state are plotted along the y-axis. The graph consists of five regions.

Region	Definition	Effect on the algorithm
Global maximum	The single highest point across the entire state space	The correct stopping point; the algorithm should terminate here
Local maximum	A point higher than all its immediate neighbors, but lower than the global maximum	The algorithm terminates here incorrectly and cannot detect a better solution exists elsewhere
Plateau	A flat region where neighboring states share the same objective function value	The algorithm cannot identify a direction to move and stalls
Ridge	A sequence of local maxima not directly adjacent to each other, forming a diagonal path in the state space	The algorithm cannot traverse the ridge efficiently because it only evaluates immediate neighbors
Shoulder	A plateau with an uphill edge on one side	The algorithm can escape a shoulder and continue climbing, unlike a true plateau

A local maximum stops hill climbing prematurely because the algorithm has no mechanism to detect higher-value states outside its immediate neighborhood. This is the central limitation of the algorithm and the reason every variant covered in the next section exists.

Types of Hill Climbing in AI

Five variants of hill climbing address different trade-offs between search speed and solution quality.

1. Simple Hill Climbing

In simple hill climbing, adjacent states are evaluated one by one until an adjacent state with a better score than the current state is found. This procedure does not look through all the adjacent states before making a move.

This type of algorithm is fast since it stops searching for adjacent states as soon as it finds an improvement. It yields less effective results than steepest-ascent hill climbing if several improvements can be found among adjacent states.

2. Steepest-Ascent Hill Climbing

In steepest ascent hill climbing, all neighbors of the current state are examined, and a move is made to the best-scoring neighbor. Steepest ascent hill climbing needs more processing time per step than ordinary hill climbing, since it examines all neighbors before making any decision.

The path produced by steepest-ascent hill climbing is more direct than the path produced by simple hill climbing, because steepest-ascent hill climbing always selects the best available move at each step.

3. Stochastic Hill Climbing

In the case of stochastic hill climbing, a randomly chosen neighbor from among all those that offer a better score compared to the current state is selected instead of the neighbor offering the best score or first score.

By using randomness in the above process, stochastic hill climbing ends up at different local maxima during different executions; hence, the chances of finding a better solution increase.

4. Random-Restart Hill Climbing

Random-restart hill climbing solves the local maxima problem directly, because each restart has an independent chance of beginning its search near the global maximum rather than a local one.

Executing random restart ten times in a search space with three local maxima is more likely to locate the global maxima than executing a search once.

5. First-Choice Hill Climbing

In first-choice hill climbing, neighbor nodes are generated randomly and the first one that provides an improvement over the current solution is selected as the new current node, after which generation of neighbors stops for the current step. First-choice hill climbing is a stochastic algorithm derived from simple hill climbing to be used on problems where each state has many neighbors, such as continuous-valued state spaces.

First-choice hill climbing takes less computational effort than steepest-ascent hill climbing if there are many neighbors possible for each node because it doesn’t need to evaluate all neighbors before making the selection.

Hill Climbing in Real AI Systems

In addition to classic search problems described in textbooks, hill climbing can be applied in three different areas of production in relation to machine learning and artificial intelligence systems.

The technique called coordinate ascent, which involves optimizing individual parameters independently while keeping all other parameters constant, is used for hyperparameter tuning in machine learning models, such as adjusting learning rate and regularization strength. In this case, each of the parameters represents one dimension of the state space, and the hill-climbing algorithm goes one dimension at a time until there are no individual-parameter changes left that improve validation score.

Policy gradient methods in reinforcement learning move policy parameters in the direction of the gradient of expected reward. Hill climbing and policy gradient both search for a local maximum of the same objective, but they differ in mechanism: hill climbing tests neighboring solutions directly, while policy gradient methods compute or estimate the gradient and step in that direction.

The optimization of prompts for language models is an example of hill climbing in the discrete space of candidate prompts. In this case, one candidate prompt is assessed based on its score on the benchmark task, and neighboring prompts are generated either by substituting individual words or sentences within the prompt.

Common Applications

The hill climbing technique is used to solve optimization problems under four major types of problems: 

• Traveling Salesman Problem (TSP): The algorithm begins with a random solution by generating a path connecting all the cities and then makes swaps between two adjacent cities to minimize the distance.
• Hyperparameter tuning: The algorithm changes one parameter of a machine learning model and accepts any changes that increase validation accuracy.
• Automated scheduling: The algorithm reschedules the tasks or resources to reduce conflicts or optimize the use of resources.
• Robotics path planning: The algorithm tries all possible actions a robot can perform at its current state and chooses the best action that minimizes the distance to the goal.

Limitations of Hill Climbing

There are seven issues that will lead to a suboptimal solution or non-termination of the algorithm at the optimal point by hill climbing.

1. Local Maxima

The algorithm stops at any point where there is no neighbor that has a higher score than the current point even when there is a better point somewhere else. It has no way of identifying when the algorithm is stuck in such a situation since it only examines the immediate neighbors of the current state.

2. Plateaus

This is where all the neighbors have an equal score. There is no direction for the algorithm to take as none of the neighbors has a higher score than the current state.

3. Ridges

This is where to get a higher score, you need to take a diagonal step, which the algorithm is not capable of taking as it can only examine neighbors immediately around the current state.

4. Dependence on the Initial Solution

The ultimate outcome of the hill climbing algorithm is dependent on the initial state. An initial state that is located near a local optimum will lead to a poor outcome despite how well the rest of the algorithm works.

5. No Backtracking

There is no backtracking involved in the algorithm. The algorithm cannot revert to previous states once it leaves those states despite the possibility of those previous states leading to the global optimum.

6. Neighbor Selection Trade-offs

A limited neighborhood will limit the search for possible outcomes to a region near the current state, thus missing out on some better options. A larger neighborhood means that the algorithm will spend more time evaluating all candidates.

7. Time Complexity and Termination

Hill climbing makes one evaluation of the objective function for each neighbor at each iteration. Simple hill climbing makes an evaluation of only one neighbor before deciding on movement, leading to a best case cost of one evaluation per iteration. Steepest ascent hill climbing makes evaluations of all the neighbors in each iteration, making its cost dependent on the number of neighbors per iteration. The algorithm guarantees termination in finite spaces since it makes movements that lead to increase of objective function score, which makes it impossible to visit a state twice.

Hill Climbing vs. Simulated Annealing vs. Genetic Algorithms vs. Beam Search

Method	Search unit	Accepts worse moves	Escapes local maxima	Typical use case
Hill climbing	One state	No	No (without variants)	Fast local refinement of a single candidate
Simulated annealing	One state	Yes, with decreasing probability over time	Yes	Problems where escaping local maxima early in the search matters more than speed
Genetic algorithms	A population of states	Yes, through crossover and mutation	Yes	Problems with a large, complex search space and no clear neighbor structure
Beam search	A fixed-size set of top-scoring states	No	Partially, by tracking multiple candidates	Problems where evaluating several candidates in parallel is computationally feasible

Simulated annealing extends hill climbing by accepting worse-scoring neighbors with a probability that decreases over time, which allows the search to escape local maxima early and converge on a high-quality solution as the acceptance probability falls toward zero.

Genetic algorithms and particle swarm optimization operate on a population of candidate solutions rather than a single state. Hill climbing is frequently combined with both methods as a local refinement step: the population-based method explores the search space broadly, and hill climbing polishes each candidate into its nearest local optimum.

When to Use (and When Not to Use) Hill Climbing

Hill Climbing Algorithm is suitable for situations where the objective function is relatively easy to compute, there are few local maximums in the search space, and the optimal solution found locally suffices the need of the problem.

It is not suited to situations where there are many local maximums in relation to the size of the neighborhood, when the objective function is costly to compute, and many random restarts are impractical to perform, or where a global optimal solution is needed to solve the problem.

Implementing Hill Climbing in Python

The following implementation applies hill climbing to a hyperparameter-tuning task: finding the learning rate that minimizes a validation loss function.

import numpy as np

def validation_loss(learning_rate):

    # Simulated validation loss curve with a single minimum near lr = 0.05

    return (learning_rate - 0.05) ** 2 + 0.01

def generate_neighbors(learning_rate, step_size=0.01):

    return [

        max(learning_rate + step_size, 1e-6),

        max(learning_rate - step_size, 1e-6),

    ]

def hill_climbing_minimize(objective, initial, n_iterations=100, step_size=0.01):

    current = initial

    current_score = objective(current)

    for i in range(n_iterations):

        neighbors = generate_neighbors(current, step_size)

        neighbor_scores = [objective(n) for n in neighbors]

        best_idx = np.argmin(neighbor_scores)

        if neighbor_scores[best_idx] < current_score:

            current = neighbors[best_idx]

            current_score = neighbor_scores[best_idx]

        else:

            print(f"Converged after {i} steps.")

            break

    return current, current_score

best_lr, best_loss = hill_climbing_minimize(validation_loss, initial=0.2)

print(f"Best learning rate: {best_lr:.4f}, Validation loss: {best_loss:.4f}")

Unlike other approaches where the objective function is maximized, this one seeks to minimize the objective function by taking steps towards the lower scoring neighbors. This method converges when none of the neighbors have a lower loss than the learning rate.

Frequently Asked Questions