Hill Climbing

Definition

Hill Climbing is a local search algorithm that begins with an initial solution and repeatedly replaces it with a neighboring solution if the neighbor is better according to an evaluation function, until no better neighbor is found.

In simple words, it is a method of moving from one solution to a better nearby solution until improvement is no longer possible.

Example idea:

If the goal is to maximize profit, hill climbing keeps choosing the neighboring option with higher profit.
If the goal is to minimize cost, it keeps choosing the neighboring option with lower cost.

Main Content

1. First Concept: Local Search and State Space

State space

is the set of all possible solutions to a problem. In hill climbing, each state represents one possible configuration.

Local search

means the algorithm does not explore the entire search tree like brute force; instead, it only checks states near the current one.

Hill climbing is called a local search method because it focuses only on the current state and its immediate neighbors. It does not remember all previously visited states and does not systematically explore all possibilities. This makes it memory-efficient, but also increases the chance of missing the global optimum.

Example

Suppose we want to maximize the value of a function:

f(x) = -(x - 5)^2 + 25

The maximum is at x = 5.

If we start at x = 1, hill climbing checks nearby values such as x = 2 or x = 0, chooses the better one, and continues moving until it reaches the highest point near the current area.

Why this concept matters

It reduces computation compared to exhaustive search.
It is suitable when only a good solution is needed, not necessarily the perfect one.
It works well when the landscape of solutions changes gradually.

2. Second Concept: Evaluation Function and Neighbor Selection

Evaluation function

measures how good a state is.
The algorithm compares neighboring states and chooses the one with the best evaluation value.

The success of hill climbing depends heavily on the quality of the evaluation function. If the function properly reflects the desirability of states, the algorithm can make good progress. If the function is misleading, the search may move in the wrong direction.

There are two common forms:

Maximization problem

: choose the neighbor with the highest score.

Minimization problem

: choose the neighbor with the lowest cost.

Example

In job scheduling, the evaluation function may measure:

total completion time,
number of delayed jobs,
machine idle time.

Hill climbing will try to improve the schedule by swapping jobs or changing assignments in a way that improves the chosen score.

Key idea

At each step:

generate neighboring states,
evaluate them,
move to the best one if it is better than the current state.

If no neighbor is better, the algorithm stops.

3. Third Concept: Types of Hill Climbing

Simple Hill Climbing

: checks neighbors one by one and moves as soon as it finds a better one.

Steepest-Ascent Hill Climbing

: checks all neighbors and chooses the best improvement.

Stochastic Hill Climbing

: randomly picks among the better neighbors instead of always choosing the best.

These variants differ in how they choose the next state.

Simple Hill Climbing

Compares one neighbor at a time.
Stops as soon as it finds a better state.
Fast, but may miss a much better neighbor.

Steepest-Ascent Hill Climbing

Evaluates all available neighbors.
Selects the one with the greatest improvement.
More accurate than simple hill climbing, but slower.

Stochastic Hill Climbing

Does not always choose the single best neighbor.
Randomly selects a promising improvement.
Helps reduce some local trapping issues.

Example of difference

If the current solution has neighbors with scores:

A = 10
B = 15
C = 12
Current = 8

Then:

Simple hill climbing may stop at A if it is examined first and is better than 8.
Steepest-ascent will choose B.
Stochastic may choose B or C depending on probability.

Working / Process

1. Start with an initial state

Choose any starting solution.
This may be random or based on a heuristic.
The starting point can strongly affect the final result.

2. Generate neighboring states

Find all states that are one small change away from the current state.
A “neighbor” depends on the problem:
- in map navigation, a nearby city,
- in puzzle solving, a state obtained by moving one tile,
- in scheduling, a schedule created by swapping two jobs.

3. Move to a better neighbor

Compare the current state with its neighbors using the evaluation function.
If a better neighbor exists, move to it.
Repeat this process until no better neighbor is available.

Example process illustration

Consider a simple maximization landscape:

        25
       /  \
     20    22
    /        \
   15         18
  /             \
10               12

Starting from 10:

Compare with neighbors and move to 15.
From 15, move to 20.
From 20, move to 25.
At 25, no better neighbor exists, so stop.

Important behavior during the process

The algorithm is greedy: it always prefers immediate improvement.
It does not look ahead to see whether a temporary worse move could lead to a better final solution.
Therefore, it may stop at a local optimum instead of the global optimum.

Common stopping conditions

No neighboring state is better than the current state.
A maximum number of iterations is reached.
A satisfactory solution is found.
Improvement becomes too small to matter.

Advantages / Applications

Simple and easy to implement

: Hill climbing is one of the easiest search algorithms to understand and code.

Uses very little memory

: It stores only the current state and a few neighbors, making it efficient for large problems.

Useful in optimization problems

: It is applied in scheduling, route finding, machine learning tuning, feature selection, and game strategy improvement.

Fast in many practical cases

: When the problem landscape is well-behaved, it quickly reaches a good solution.

Works well for approximate solutions

: Even when the perfect answer is hard to find, hill climbing often finds a useful near-optimal answer.

Common applications

Traveling and route optimization

Job scheduling

Network design

Robot path improvement

Parameter tuning in machine learning

Puzzle and game solving

Resource allocation

Layout and circuit optimization

Summary

Hill climbing is a local search method that improves a solution step by step.
It always moves toward a better neighboring state based on an evaluation function.
It is simple and efficient, but it may get stuck in local optima.
Key terms: state space, neighbor, evaluation function, local optimum, global optimum, steepest-ascent, stochastic hill climbing