Optimizing Cost Function Through Hill Climbing Algorithm & Random Restart Variant
Introduction
Hill climbing is a mathematical optimization algorithm, which means its purpose is to find the best solution to a problem that has a (large) number of possible solutions. Explaining the algorithm (and optimization in general) is best done using an example. In the Travelling salesman problem, we have a salesman who needs to visit a number of cities exactly once, after which he returns to the first city. The distances between each pair of cities are known, and we need to find the shortest route. As you can imagine, there is (often) a large number of possible solutions (routes) to a specific Travelling salesman problem; the goal is to find the best (i.e. the shortest) solution.
Hill Climbing Variants
Due to the limitations of Hill Climbing, multiple variants have been thought of to overcome the problem of being stuck in local minima and maxima. What all variations of the algorithm have in common is that no matter the strategy, each one still has the potential of ending up in local minima and maxima and no means to continue optimizing. The algorithms below are phrased such that a higher value is better, but they also apply to cost functions, where the goal is to minimize cost.
In this article, we will only work on the Random restart variant.
Random-restart:
Conduct hill-climbing multiple times. Each time, start from a random state. Compare the maxima from every trial, and choose the highest amongst those.
Background/ Interest
This report is a part of the “Artificial Intelligence” course at City University, Dhaka, Bangladesh conducted by Nuruzzaman Faruqui. This is the best AI course in Bangladesh.
In this course, we learned AI from scratch. We started from Basic python and ended in Natural language processing. We learned theoretical concepts, essential mathematics properly in the “CSE 417: Artificial Intelligence” course, then implemented our knowledge in the Lab course 'CSE 418: Artificial Intelligence Laboratory'. We have done a lot of lab sessions to master the course and gradually we learned each necessary concept of Artificial Intelligence.
Now we can build our machine learning model and also can build a neural network to solve a complex problem.
Problem Statement:
In this illustration, we are seeing a possible configuration of houses and hospitals. The distance between them is measured using Manhattan distance (number of moves up, down, and to the sides; discussed in more detail in lecture 0), and the sum of the distances from each house to the nearest hospital is 17. We call this the cost because we try to minimize this distance. In this case, a state would be anyone configuration of houses and hospitals.
Hill Climbing Algorithm
In this algorithm, we start with a current state. In some problems, we will know what the current state is, while, in others, we will have to start with selecting one randomly. Then, we repeat the following actions: we evaluate the neighbors, selecting the one with the best value. Then, we compare this neighbor’s value to the current state’s value. If the neighbor is better, we switch the current state to the neighbor state and then repeat the process. The process ends when we compare the best neighbor to the current state, and the current state is better. Then, we return to the current state.
Using the hill-climbing algorithm, we can start to improve the locations that we assigned to the hospitals in our example. After a few transitions, we get to the following state:
The Python code to implement Hill-Climbing Algorithm & Random Restart variant
Note: Firstly Download the images of Hospital & House.
Save downloaded files in your project directory like below:
Driver Code:
import random # pseudo-random number generators
class Space():
def __init__(self, height, width, num_hospitals):
"""Create a new state space with given dimensions."""
self.height = height
self.width = width
self.num_hospitals = num_hospitals
self.houses = set()
self.hospitals = set()
def add_house(self, row, col):
"""Add a house at a particular location in state space."""
self.houses.add((row, col))
def available_spaces(self):
"""Returns all cells not currently used by a house or hospital."""
# Consider all possible cells
candidates = set(
(row, col)
for row in range(self.height)
for col in range(self.width)
)
# Remove all houses and hospitals
for house in self.houses:
candidates.remove(house)
for hospital in self.hospitals:
candidates.remove(hospital)
return candidates
def hill_climb(self, maximum=None, image_prefix=None, log=False):
"""Performs hill-climbing to find a solution."""
count = 0
# Start by initializing hospitals randomly
self.hospitals = set()
for i in range(self.num_hospitals):
self.hospitals.add(random.choice(list(self.available_spaces())))
if log:
print("Initial state: cost", self.get_cost(self.hospitals))
if image_prefix:
self.output_image(f"{image_prefix}{str(count).zfill(3)}.png")
'''zfill() method adds zeros (0) at the beginning of the string'''
# Continue until we reach maximum number of iterations
while maximum is None or count < maximum:
count += 1
best_neighbors = []
best_neighbor_cost = None
# Consider all hospitals to move
for hospital in self.hospitals:
# Consider all neighbors for that hospital
for replacement in self.get_neighbors(*hospital):
# Generate a neighboring set of hospitals
neighbor = self.hospitals.copy() # Slide 28
neighbor.remove(hospital) # slide 29
neighbor.add(replacement) # Slide 30
# Check if neighbor is best so far
cost = self.get_cost(neighbor)
if best_neighbor_cost is None or cost < best_neighbor_cost:
best_neighbor_cost = cost
best_neighbors = [neighbor]
elif best_neighbor_cost == cost:
best_neighbors.append(neighbor)
# None of the neighbors are better than the current state
if best_neighbor_cost >= self.get_cost(self.hospitals):
return self.hospitals
# Move to a highest-valued neighbor
else:
if log:
print(f"Found better neighbor: cost {best_neighbor_cost}")
self.hospitals = random.choice(best_neighbors)
# Generate image
if image_prefix:
self.output_image(f"{image_prefix}{str(count).zfill(3)}.png")
def random_restart(self, maximum, image_prefix=None, log=False):
"""Repeats hill-climbing multiple times."""
best_hospitals = None
best_cost = None
# Repeat hill-climbing a fixed number of times
for i in range(maximum):
hospitals = self.hill_climb()
cost = self.get_cost(hospitals)
if best_cost is None or cost < best_cost:
best_cost = cost
best_hospitals = hospitals
if log:
print(f"{i}: Found new best state: cost {cost}")
else:
if log:
print(f"{i}: Found state: cost {cost}")
if image_prefix:
self.output_image(f"{image_prefix}{str(i).zfill(3)}.png")
return best_hospitals
def get_cost(self, hospitals):
"""Calculates sum of distances from houses to nearest hospital."""
cost = 0
for house in self.houses:
cost += min(
abs(house[0] - hospital[0]) + abs(house[1] - hospital[1])
for hospital in hospitals
)
return cost
def get_neighbors(self, row, col):
"""Returns neighbors not already containing a house or hospital."""
candidates = [
(row - 1, col),
(row + 1, col),
(row, col - 1),
(row, col + 1)
]
neighbors = []
for r, c in candidates:
if (r, c) in self.houses or (r, c) in self.hospitals:
continue
if 0 <= r < self.height and 0 <= c < self.width:
neighbors.append((r, c))
return neighbors
def output_image(self, filename):
"""Generates image with all houses and hospitals."""
from PIL import Image, ImageDraw, ImageFont
cell_size = 100
cell_border = 2
cost_size = 40
padding = 10
# Create a blank canvas
img = Image.new(
"RGBA",
(self.width * cell_size,
self.height * cell_size + cost_size + padding * 2),
"white"
)
house = Image.open("assets/images/House.png").resize(
(cell_size, cell_size)
)
hospital = Image.open("assets/images/Hospital.png").resize(
(cell_size, cell_size)
)
font = ImageFont.truetype("assets/fonts/OpenSans-Regular.ttf", 30)
draw = ImageDraw.Draw(img)
for i in range(self.height):
for j in range(self.width):
# Draw cell
rect = [
(j * cell_size + cell_border,
i * cell_size + cell_border),
((j + 1) * cell_size - cell_border,
(i + 1) * cell_size - cell_border)
]
draw.rectangle(rect, fill="black")
if (i, j) in self.houses:
img.paste(house, rect[0], house)
if (i, j) in self.hospitals:
img.paste(hospital, rect[0], hospital)
# Add cost
draw.rectangle(
(0, self.height * cell_size, self.width * cell_size,
self.height * cell_size + cost_size + padding * 2),
"black"
)
draw.text(
(padding, self.height * cell_size + padding),
f"Cost: {self.get_cost(self.hospitals)}",
fill="white",
font=font
)
img.save(filename)
# Create a new space and add houses randomly
s = Space(height=10, width=20, num_hospitals=3)
for i in range(15):
s.add_house(random.randrange(s.height), random.randrange(s.width))
# # Use local search to determine hospital placement
# hospitals = s.hill_climb(image_prefix="hospitals", log=True)
# Use Random Restart to determine hospital placement
hospitals = s.random_restart(maximum=10,image_prefix="hospitals", log=True)
Result
We have implemented random restart variants and conducted the hill-climbing algorithm through the random restart 10 times. The best neighbor cost is:
The best neighbor cost image is :
To implement Random Restart only, In the last line
# Use local search to determine hospital placement
hospitals = s.hill_climb(image_prefix="hospitals", log=True)
Instead of,
# Use Random Restart to determine hospital placement
hospitals= s.random_restart(
maximum=10,image_prefix="hospitals", log=True
)
Conclusion
In this lab report, we learned how to implement Hill Climbing Algorithm & Random Restart variants to optimize solutions. However, you can optimize other similar problems by implementing the code snippet given above. This is a simple and easier implementation of the “ CSE 418: Artificial Intelligence Lab” course at City University, Dhaka, Bangladesh conducted by Nuruzzaman Faruqui Sir. Which is the best AI course in Bangladesh.
You are free to copy the code from here or some other concluding remarks for your project.