In this article, let’s try to understand the Hill Climbing Algorithm. This is a commonly used Heuristic search technique in the field of artificial intelligence. The heuristic technique is a criterion for choosing which of multiple options will be most successful in accomplishing a particular goal.
Also read: Branch and Bound Search with Examples and Implementation in Python
What is Hill Climbing Algorithm?
Hill climbing comes from quality measurement in Depth-First search (a variant of generating and test strategy). It is an optimization strategy that is a part of the local search family.
It is a fairly straightforward implementation strategy as a popular first option is explored. There are instances where hill climbing is effective, even though more complex algorithms may produce greater benefits.
Hill climbing can solve problems with many solutions but where some solutions are better than others. The traveling salesman problem can be solved with hill climbing. It is simple to locate a solution that visits every city, but this solution is likely to be subpar compared to the ideal one.
Search efficiency may be increased if there is a technique to arrange the options so that the most promising node is explored first. Hill Climbing progresses through a tree of paths in depth-first order, but the options are arranged in accordance with some heuristic value (ie, a measure of remaining cost from current to goal state).
For example, in the traveling salesman problem, a straight line (as the crow flies) distance between two cities can be a heuristic measure of the remaining distance.
Properties to remember
- Local Search algorithm
- Follows greedy approach
- No backtracking.
Types of Hill Climbing Algorithm
Simple Hill Climbing: The simplest method of climbing a hill is called simple hill climbing. The goal is to ascend to the mountain’s highest peak. Here, the climber’s steps and moves determine how he moves. He continues to move if he thinks his next step will be better than the one before it, or if he stays in the same position. This search is just concerned with his previous and subsequent actions.
Steepest-ascent Hill Climbing: In contrast to a straightforward hill-climbing search, it compares all of the succeeding nodes and selects the one that is closest to the answer. Because it concentrates on each node rather than just one, the steepest hill-climbing search is comparable to the best-first search.
Stochastic hill climbing: The nodes are not all concentrated on in stochastic hill climbing. It chooses one node at random and then determines whether to enlarge it or look for a better one.
Random-restart Hill Climbing: Try-and-try approach is the foundation of the random-restart algorithm. Up till the target is not reached, it iteratively searches the node and chooses the best candidate at each stage. Success is frequently determined by the hill’s form. It is simpler to get there if there aren’t many ridges, plateaus, or local maxima.
Simple Example of Hill Climbing
To understand the concept in a better way, let’s try to implement the problem of a traveling salesman using the hill climbing algorithm. A description of the problem is given below.
Finding the shortest path between a number of points and places that must be visited is the goal of the algorithmic problem known as the “traveling salesman problem” (TSP). The input here is a 2D array of coordinates of cities and the output is a list of integers that indicates the numbers of cities in order(starting from zero)
Implementing the Hill Climbing Algorithm in Python
import random
import numpy as np
import networkx as nx
#coordinate of the points/cities
coordinate = np.array([[1,2], [30,21], [56,23], [8,18], [20,50], [3,4], [11,6], [6,7], [15,20], [10,9], [12,12]])
#adjacency matrix for a weighted graph based on the given coordinates
def generate_matrix(coordinate):
matrix = []
for i in range(len(coordinate)):
for j in range(len(coordinate)) :
p = np.linalg.norm(coordinate[i] - coordinate[j])
matrix.append(p)
matrix = np.reshape(matrix, (len(coordinate),len(coordinate)))
#print(matrix)
return matrix
#finds a random solution
def solution(matrix):
points = list(range(0, len(matrix)))
solution = []
for i in range(0, len(matrix)):
random_point = points[random.randint(0, len(points) - 1)]
solution.append(random_point)
points.remove(random_point)
return solution
#calculate the path based on the random solution
def path_length(matrix, solution):
cycle_length = 0
for i in range(0, len(solution)):
cycle_length += matrix[solution[i]][solution[i - 1]]
return cycle_length
#generate neighbors of the random solution by swapping cities and returns the best neighbor
def neighbors(matrix, solution):
neighbors = []
for i in range(len(solution)):
for j in range(i + 1, len(solution)):
neighbor = solution.copy()
neighbor[i] = solution[j]
neighbor[j] = solution[i]
neighbors.append(neighbor)
#assume that the first neighbor in the list is the best neighbor
best_neighbor = neighbors[0]
best_path = path_length(matrix, best_neighbor)
#check if there is a better neighbor
for neighbor in neighbors:
current_path = path_length(matrix, neighbor)
if current_path < best_path:
best_path = current_path
best_neighbor = neighbor
return best_neighbor, best_path
def hill_climbing(coordinate):
matrix = generate_matrix(coordinate)
current_solution = solution(matrix)
current_path = path_length(matrix, current_solution)
neighbor = neighbors(matrix,current_solution)[0]
best_neighbor, best_neighbor_path = neighbors(matrix, neighbor)
while best_neighbor_path < current_path:
current_solution = best_neighbor
current_path = best_neighbor_path
neighbor = neighbors(matrix, current_solution)[0]
best_neighbor, best_neighbor_path = neighbors(matrix, neighbor)
return current_path, current_solution
final_solution = hill_climbing(coordinate)
print("The solution is \n", final_solution[1])
OUTPUT
The solution is
[2, 4, 8, 3, 7, 5, 0, 6, 9, 10, 1]
Problems with Hill Climbing
There are a few problems with hill climbing. The search process may reach a position that is not a solution but from there no move improves the situation. This will happen if we have reached the local maximum, a plateau, or a ridge.
Local maximum: It is a state that is better than all its neighbors but not better than some other states which are far away, (there might be a better solution ahead and this solution is referred to as the global maximum.) From this state, all moves look to be worse. In such a situation, backtrack to some earlier state and try going in a different direction to find a solution.
Plateau: It is a flat area of the search space where all neighboring states have the same value. It is not possible to determine the best direction. In such a situation make a big jump in some direction and try to get to a new section of the search space. It is also known as flat maximum.
Ridge: It is an area of search space that is higher than surrounding areas but that cannot be traversed by single moves in any one direction. It is a special kind of local maxima. Here apply two or more rules before doing the test, i.e. moving in several directions at once.
Summary
This article explains the concept of the Hill Climbing Algorithm in depth. We understood the different types as well as the implementation of algorithms to solve the famous Traveling Salesman Problem. the Hill Climbing algorithm is widely used in data science and Artificial Intelligence domain.