Local Search: Hill Climbing Search
A Short Look at Hill Climbing Search and Variations
December 11, 2013
Introduction
Local Search is a method that is used to solve optimization problems, where we are after a solution's state, and the path to the goal is not the solution it self. This contrast from shortest-path problems we can solve with A* and Dijkstra's Algorithm, in that the solution it is the path from a start to a goal node. We only care about a final configuration.
Local search is a way to solve problems like vehicle routing, portfolio management, scheduling, and positioning problems without having to explore all possible solutions which increases in complexity with the number of variables.
In this post I will be quickly covering what Hill Climbing, Simulated Annealing, Local Beam, and Genetic Search are and what their algorithms look like.
The important thing to note about Local Search is that we must be aware that the search space has a sort of landscape that has slope with global and local maxima and minima at which our algorithms can get stuck, and since these algorithms do not explore all areas of a search space it is also possible to arrive at a solution which is good enough to solve a problem, such as in the case of scheduling.
The majority of the algorithms are derivations of those presented in AIMA by Peter Norvig.
Hill Climbing
Hill Climbing is an algorithm that move in a direction of increasing value, and terminates once it reaches a peak. At every step of the way it uses a heuristic evaluation function, which we can call \(h(n)\) to evaluate its state and the state of all its neighboring solutions.
After using \(h(n)\) to evaluate the neighboring solutions it makes a move to the next best state, in other words, we can consider Hill Climbing to be greedy. Since this is a greedy algorithm we know it is likely that we will reach a local maxima sooner than later, but weather or not this is a solution good enough is dependent on the problem definition.
The problem with hill climbing is that it is possible to get stuck at a local maxima which does not solve our problem. Similarly, it is also possible to reach a plateau where we do not have a next best move and we can wonder infinitely back and forth if we allow sideways moves.
Best First Hill Climbing Algorithm
// Pseudo Code
h(State s) {
function // Heuristic Evaluation Function
}
// Pseudo Code
HillClimbing(State s) {
function State best = s;
State current;
while (true) {
= best;
current for (State next : s.nextStates()) // foreach...in..
// Move to the next best possible state
= h(best) < h(next) ? next : best;
best
// If current & best are STILL the same, then we reached a peak.
if (best == current)
return best;
}
}
Hill Climbing Variations
To get around some of the limitations on Hill Climbing like reaching a plateau or a local maxima we can go about allowing a limited number of sideways moves before failing, or we can go about making choices in a stochastic manner or simply doing a randomized restart when the Hill Climbing gets stuck.
Stochastic Hill Climbing
We can try choosing a randomized uphill move, rather than a greedy one. This would still move us towards a solution, but would lead us to explore different areas of the search space, and depending on the problem it could lead to better solutions.
// Pseudo Code
h(State s) {
function // Heuristic Evaluation Function
}
List::ChooseRandom() {
function // return move with probability proportional to the improvement.
}
HillClimbing(State s) {
function State best = s;
State current;
List betterMoves = List();
while (true) {
= best;
current
// Look for better moves
for (State next : s.nextStates()) // foreach...in..
if (h(best) < h(next))
.add(next);
betterMoves
// Choose randomly, from better moves -- if any
if (betterMoves.length() > 0)
= betterMoves.chooseRandom();
best
// If current & best are STILL the same, then we reached a peak.
if (best == current)
return best;
}
}
Fist Choice Hill Climbing
First Choice Hill Climbing is all about generating successors randomly until a better one than our current state is generated. The reason you would want to do this is that in certain problems the number of successors states can be too big to compare directly to the current state, so generating randomly and moving to a better state may yield a better outcome in less time.
// Pseudo Code
h(State s) {
function // Heuristic Evaluation Function
}
generateRandomState() {
function // return a new randomly generated state.
}
HillClimbing(State s) {
function State best = s;
State current;
while (true) {
= best;
current
// Look for better moves.
for(i = 0; i < THRESH_HOLD; i++) // foreach...in..
{
= generateRandomState();
generated if (h(best) < h(generated)) {
= generated
best break;
}
}
// If current & best are STILL the same, then we reached a peak.
if (best == current)
return best;
}
}
Random Restart Hill Climbing
Random Restart Hill Climbing is all about doing a series of Hill Climbing searches from randomly generated initial states, until a goal is found. So every time the algorithm gets stuck at a local maxima, or plateau the algorithm simply does a random restart and tries again and again.
// Pseudo Code
main() {
function State current = new State(...); // Initial state
while (true) {
= HillClimbing(current)
solution if (isSolution(solution))
break;
// Solution good enough has not been found do a randomized restart.
= generateRandomState()
current }
}
generateRandomState() {
function // Generate a Random State to start from.
}
h(State s) {
function // Heuristic Evaluation Function
}
// Best-First Hill Climbing, but may be any type of hill climbing.
HillClimbing(State s) {
function State best = s;
State current;
while (true) {
= best;
current for (State next : s.nextStates()) // foreach...in..
// Move to the next best possible state
= h(best) < h(next) ? next : best;
best
// If current & best are STILL the same, then we reached a peak.
if (best == current)
return best;
}
}
Conclusion
Hill Climbing appears to be a powerful method for local search problems where we are looking to get to a solution configuration. Some version of the algorithm like the Greedy Best First will be incomplete, and fail to find a solution where there is one if it gets stuck in a local maxima, or plateau. We can also see that that can be resolved by adding in a randomized restart which will allow the hill climbing to start in another location of the search space. The goal was to more or less introduce the general idea of hill climbing and present some pseudo code to possible implementations.
Additional References
Artificial Intelligence a Modern Approach
Hill Climbing
Local Search