Introduction Hill Climbing algorithm is a local search algorithm that continuously moves in the direction of increasing elevation to fin...
Introduction
Hill Climbing algorithm is a local search algorithm that
continuously moves in the direction of increasing elevation to find the peak of
the mountain or the best solution to the problem. It terminates when it reaches
a peak value where no neighbor has a higher value. Due to the limitation of
Hill Climbing, multiple variants are used to overcome the limitations. This report
demonstrates the result of the hill-climbing algorithm and random restart
variant.
This report is a part of the Artificial Intelligence course
Lab-work under supervision of Nuruzzaman Faruqui, Lecturer of City University,
Bangladesh. This course offers students various up-to-date AI topics. Students
get to explore the real applicable approaches through AI. From this course, the student acquires better knowledge of the functionality of AI and how AI is making our
daily life easier. This is the best Artificial Intelligence course in
Bangladesh.
Problem statement
Let’s consider an example where we have a
location that contains houses. Now
if we want to build hospitals in a way that the distance from each house to a
hospital should be minimized. Let’s visualize the problem.
What we can see from the above picture the configuration of houses and hospitals. By using Manhattan distance (number moves to the up, down and left, right), the distance between house and hospitals ate measured. And some of the total distance was found 76. Now what we will do is by using hill-climbing the algorithm we will simply minimize the cost. We will also see a variant where we could overcome the limitation of the hill-climbing algorithm and try to find out a better solution.
Pseudocode of Hill Climbing algorithms
function Hill-Climb(problem):
current =
initial state of problem
repeat:
neighbor =
best valued neighbor of current
if neighbor
not better than current:
return
current
current =
neighbor
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)
Result
The above algorithm has been executed in
Python on an imaginary example. The example was, in a state-space randomly
generated houses and hospitals are presented. Using the Hill-Climbing algorithm we
have to determine the cost of distance one need to reach from house to hospital
and the result found for this is as follows:
Figure: Screenshot of results of Hill Climbing Algorithm
Graphical Images
Figure: Graphical image of optimized cost after applying Hill Climbing
Algorithm
Random restart variant conducts Hill Climbing multiple
times. Each time start a random state and find optimized result than regular
Hill Climbing algorithm. And the result is as follows:
Graphical images of random restart variables.
Figure:
Graphical image of optimized cost after applying random restart variant
Conclusion
From this report, we have learned about Hill
Climbing algorithm. We also learned how by using a hill-climbing algorithm we
minimize the cost. We saw a full implementation of a hill-climbing algorithm in
python. The problem with Hill Climbing Algorithm is at some point agent falls into local
minima and maxima which leads to failure of finding optimized solutions. That’s
why multiple variants are here to solve this issue. Although each one still has
the potential of ending up in local minima and maxima and no means to continue
optimizing. But variants perform better than regular Hill Climbing algorithms.
As you can probably tell now how easily this concept is
described above. Anyone with basic discrete mathematics knowledge can
understand this. Our honorable instructor’s well-explained teaching method is
the main reason for successfully grasping every topic of this course quickly.
That’s why this is the best AI course in Bangladesh.
No comments