Hill climbing (or gradient ascent/descent)

• Iteratively maximize “value” of current state, by replacing it by successor state that

has highest value, as long as possible.

Note: minimizing a “value” function v(n) is equivalent to maximizing –v(n), thus both

notions are used interchangeably.

• Algorithm:

1. determine successors of current state

2. choose successor of maximum goodness (break ties randomly)

3. if goodness of best successor is less than current state's goodness, stop

4. otherwise make best successor the current state and go to step 1

• No search tree is maintained, only the current state.

• Like greedy search, but only states directly reachable from the current state are

considered.

• Problems:

Local maxima

Once the top of a hill is reached the algorithm will halt since every possible step

leads down.

Plateaux

If the landscape is flat, meaning many states have the same goodness, algorithm

degenerates to a random walk.

Ridges

If the landscape contains ridges, local improvements may follow a zigzag path up

the ridge, slowing down the search.

• Shape of state space landscape strongly influences the success of the search

process. A very spiky surface which is flat in between the spikes will be very

difficult to solve.

• Can be combined with nondeterministic search to recover from local maxima.

• Random-restart hill-climbing is a variant in which reaching a local maximum

causes the current state to be saved and the search restarted from a random point.

After several restarts, return the best state found. With enough restarts, this

method will find the optimal solution.

• Gradient descent is an inverted version of hill-climbing in which better states are

represented by lower cost values. Local minima cause problems instead of local

maxima.

Hill climbing - example

• Complete state formulation for 8 queens

– Successor function: move a single queen to another square in the same column

– Cost: number of pairs that are attacking each other.

• Minimization problem