Skip to content

Hill Climbing Search Algorithm in Python

I am going to implement a hill climbing search algorithm on the traveling salesman problem in this tutorial. Hill-climbing is a local search algorithm that starts with an initial solution, it then tries to improve that solution until no more improvement can be made. This algorithm works for large real-world problems in which the path to the goal is irrelevant.

Hill-climbing is a simple algorithm that can be used to find a satisfactory solution fast, without any need to use a lot of memory. Hill-climbing can be used on real-world problems with a lot of permutations or combinations. The algorithm is often referred to as greedy local search because it iteratively searchs for a better solution.

Hill climbing uses randomly generated solutions that can be more or less guided by what the person implementing it thinks is the best solution. Hill-climbing can be implemented in many variants: stochastic hill climbing, first-choice hill climbing, random-restart hill climbing and more custom variants. The algorithm can be used to find a satisfactory solution to a problem of finding a configuration when it is impossible to test all permutations or combinations.

Traveling Salesman Problem (TSP)

The traveling salesman problem is famous because it is difficult to give an optimal solution in an reasonable time as the number of cities in the problem increases. I have found distance data for 13 cities (Traveling Salesman Problem). The problem is to find the shortest route from a starting location and back to the starting location after visiting all the other cities. This problem has 479001600 ((13-1)!) permutations and if we added one more city it would have 6227020800 ((14-1)!) permutations.

It would take to long to test all permutations, we use hill-climbing to find a satisfactory solution. The initial solution can be random, random with distance weights or a guessed best solution based on the shortest distance between cities.

  1. # Import libraries
  2. import random
  3. import copy
  5. # This class represent a state
  6. class State:
  8.     # Create a new state
  9.     def __init__(self, route:[], distance:int=0):
  10.         self.route = route
  11.         self.distance = distance
  13.     # Compare states
  14.     def __eq__(self, other):
  15.         for i in range(len(self.route)):
  16.             if(self.route[i] != other.route[i]):
  17.                 return False
  18.         return True
  20.     # Sort states
  21.     def __lt__(self, other):
  22.          return self.distance < other.distance
  24.     # Print a state
  25.     def __repr__(self):
  26.         return ('({0},{1})\n'.format(self.route, self.distance))
  28.     # Create a shallow copy
  29.     def copy(self):
  30.         return State(self.route, self.distance)
  32.     # Create a deep copy
  33.     def deepcopy(self):
  34.         return State(copy.deepcopy(self.route), copy.deepcopy(self.distance))
  36.     # Update distance
  37.     def update_distance(self, matrix, home):
  38.         
  39.         # Reset distance
  40.         self.distance = 0
  42.         # Keep track of departing city
  43.         from_index = home
  45.         # Loop all cities in the current route
  46.         for i in range(len(self.route)):
  47.             self.distance += matrix[from_index][self.route[i]]
  48.             from_index = self.route[i]
  50.         # Add the distance back to home
  51.         self.distance += matrix[from_index][home]
  53. # This class represent a city (used when we need to delete cities)
  54. class City:
  56.     # Create a new city
  57.     def __init__(self, index:int, distance:int):
  58.         self.index = index
  59.         self.distance = distance
  61.     # Sort cities
  62.     def __lt__(self, other):
  63.          return self.distance < other.distance
  65. # Get the best random solution from a population
  66. def get_random_solution(matrix:[], home:int, city_indexes:[], size:int, use_weights=False):
  68.     # Create a list with city indexes
  69.     cities = city_indexes.copy()
  71.     # Remove the home city
  72.     cities.pop(home)
  74.     # Create a population
  75.     population = []
  76.     for i in range(size):
  78.         if(use_weights == True):
  79.             state = get_random_solution_with_weights(matrix, home)
  80.         else:
  81.             # Shuffle cities at random
  82.             random.shuffle(cities)
  84.             # Create a state
  85.             state = State(cities[:])
  86.             state.update_distance(matrix, home)
  88.         # Add an individual to the population
  89.         population.append(state)
  91.     # Sort population
  92.     population.sort()
  94.     # Return the best solution
  95.     return population[0]
  97. # Get best solution by distance
  98. def get_best_solution_by_distance(matrix:[], home:int):
  99.     
  100.     # Variables
  101.     route = []
  102.     from_index = home
  103.     length = len(matrix) - 1
  105.     # Loop until route is complete
  106.     while len(route) < length:
  108.          # Get a matrix row
  109.         row = matrix[from_index]
  111.         # Create a list with cities
  112.         cities = {}
  113.         for i in range(len(row)):
  114.             cities[i] = City(i, row[i])
  116.         # Remove cities that already is assigned to the route
  117.         del cities[home]
  118.         for i in route:
  119.             del cities[i]
  121.         # Sort cities
  122.         sorted = list(cities.values())
  123.         sorted.sort()
  125.         # Add the city with the shortest distance
  126.         from_index = sorted[0].index
  127.         route.append(from_index)
  129.     # Create a new state and update the distance
  130.     state = State(route)
  131.     state.update_distance(matrix, home)
  133.     # Return a state
  134.     return state
  136. # Get a random solution by using weights
  137. def get_random_solution_with_weights(matrix:[], home:int):
  138.     
  139.     # Variables
  140.     route = []
  141.     from_index = home
  142.     length = len(matrix) - 1
  144.     # Loop until route is complete
  145.     while len(route) < length:
  147.          # Get a matrix row
  148.         row = matrix[from_index]
  150.         # Create a list with cities
  151.         cities = {}
  152.         for i in range(len(row)):
  153.             cities[i] = City(i, row[i])
  155.         # Remove cities that already is assigned to the route
  156.         del cities[home]
  157.         for i in route:
  158.             del cities[i]
  160.         # Get the total weight
  161.         total_weight = 0
  162.         for key, city in cities.items():
  163.             total_weight += city.distance
  165.         # Add weights
  166.         weights = []
  167.         for key, city in cities.items():
  168.             weights.append(total_weight / city.distance)
  170.         # Add a city at random
  171.         from_index = random.choices(list(cities.keys()), weights=weights)[0]
  172.         route.append(from_index)
  174.     # Create a new state and update the distance
  175.     state = State(route)
  176.     state.update_distance(matrix, home)
  178.     # Return a state
  179.     return state
  181. # Mutate a solution
  182. def mutate(matrix:[], home:int, state:State, mutation_rate:float=0.01):
  183.     
  184.     # Create a copy of the state
  185.     mutated_state = state.deepcopy()
  187.     # Loop all the states in a route
  188.     for i in range(len(mutated_state.route)):
  190.         # Check if we should do a mutation
  191.         if(random.random() < mutation_rate):
  193.             # Swap two cities
  194.             j = int(random.random() * len(state.route))
  195.             city_1 = mutated_state.route[i]
  196.             city_2 = mutated_state.route[j]
  197.             mutated_state.route[i] = city_2
  198.             mutated_state.route[j] = city_1
  200.     # Update the distance
  201.     mutated_state.update_distance(matrix, home)
  203.     # Return a mutated state
  204.     return mutated_state
  206. # Hill climbing algorithm
  207. def hill_climbing(matrix:[], home:int, initial_state:State, max_iterations:int, mutation_rate:float=0.01):
  209.     # Keep track of the best state
  210.     best_state = initial_state
  212.     # An iterator can be used to give the algorithm more time to find a solution
  213.     iterator = 0
  215.     # Create an infinite loop
  216.     while True:
  218.         # Mutate the best state
  219.         neighbor = mutate(matrix, home, best_state, mutation_rate)
  221.         # Check if the distance is less than in the best state
  222.         if(neighbor.distance >= best_state.distance):
  223.             iterator += 1
  224.             if (iterator > max_iterations):
  225.                 break
  226.         if(neighbor.distance < best_state.distance):
  227.             best_state = neighbor
  229.     # Return the best state
  230.     return best_state
  232. # The main entry point for this module
  233. def main():
  235.     # Cities to travel
  236.     cities = ['New York', 'Los Angeles', 'Chicago', 'Minneapolis', 'Denver', 'Dallas', 'Seattle', 'Boston', 'San Francisco', 'St. Louis', 'Houston', 'Phoenix', 'Salt Lake City']
  237.     city_indexes = [0,1,2,3,4,5,6,7,8,9,10,11,12]
  239.     # Index of start location
  240.     home = 2 # Chicago
  242.     # Max iterations
  243.     max_iterations = 1000
  245.     # Distances in miles between cities, same indexes (i, j) as in the cities array
  246.     matrix = [[0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
  247.             [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
  248.             [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
  249.             [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
  250.             [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
  251.             [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
  252.             [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
  253.             [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
  254.             [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
  255.             [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
  256.             [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
  257.             [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
  258.             [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]]
  261.     # Get the best route by distance
  262.     state = get_best_solution_by_distance(matrix, home)
  263.     print('-- Best solution by distance --')
  264.     print(cities[home], end='')
  265.     for i in range(0, len(state.route)):
  266.        print(' -> ' + cities[state.route[i]], end='')
  267.     print(' -> ' + cities[home], end='')
  268.     print('\n\nTotal distance: {0} miles'.format(state.distance))
  269.     print()
  271.     # Get the best random route
  272.     state = get_random_solution(matrix, home, city_indexes, 100)
  273.     print('-- Best random solution --')
  274.     print(cities[home], end='')
  275.     for i in range(0, len(state.route)):
  276.        print(' -> ' + cities[state.route[i]], end='')
  277.     print(' -> ' + cities[home], end='')
  278.     print('\n\nTotal distance: {0} miles'.format(state.distance))
  279.     print()
  281.     # Get a random solution with weights
  282.     state = get_random_solution(matrix, home, city_indexes, 100, use_weights=True)
  283.     print('-- Best random solution with weights --')
  284.     print(cities[home], end='')
  285.     for i in range(0, len(state.route)):
  286.        print(' -> ' + cities[state.route[i]], end='')
  287.     print(' -> ' + cities[home], end='')
  288.     print('\n\nTotal distance: {0} miles'.format(state.distance))
  289.     print()
  291.     # Run hill climbing to find a better solution
  292.     state = get_best_solution_by_distance(matrix, home)
  293.     state = hill_climbing(matrix, home, state, 1000, 0.1)
  294.     print('-- Hill climbing solution --')
  295.     print(cities[home], end='')
  296.     for i in range(0, len(state.route)):
  297.        print(' -> ' + cities[state.route[i]], end='')
  298.     print(' -> ' + cities[home], end='')
  299.     print('\n\nTotal distance: {0} miles'.format(state.distance))
  300.     print()
  302. # Tell python to run main method
  303. if __name__ == "__main__": main()

Output

I choosed to use the best solution by distance as an initial solution, the best solution is mutated in each iteration and a mutated solution will be the new best solution if the total distance is less than the distance for the current best solution. I am using extra iterations to give the algorithm more time to find a better solution. The best solution is 7293 miles.

  1. -- Best solution by distance --
  2. Chicago -> St. Louis -> Minneapolis -> Denver -> Salt Lake City -> Phoenix -> Los Angeles -> San Francisco -> Seattle -> Dallas -> Houston -> New York -> Boston -> Chicago
  4. Total distance: 8131 miles
  6. -- Best random solution --
  7. Chicago -> Boston -> Salt Lake City -> Los Angeles -> San Francisco -> Seattle -> Denver -> Houston -> Dallas -> Phoenix -> St. Louis -> Minneapolis -> New York -> Chicago
  9. Total distance: 11091 miles
  11. -- Best random solution with weights --
  12. Chicago -> Boston -> New York -> St. Louis -> Dallas -> Houston -> Phoenix -> Seattle -> Denver -> Salt Lake City -> Los Angeles -> San Francisco -> Minneapolis -> Chicago
  14. Total distance: 9155 miles
  16. -- Hill climbing solution --
  17. Chicago -> St. Louis -> Minneapolis -> Denver -> Salt Lake City -> Seattle -> San Francisco -> Los Angeles -> Phoenix -> Dallas -> Houston -> New York -> Boston -> Chicago
  19. Total distance: 7534 miles
Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *