Optimization - Implement Local Search by using Hill Climbing Methods and Random Restart Variants
Introduction:
Local search is Search algorithms that maintain a single node and search by moving to a neighboring node. Local search algorithms are used when we care only about a solution but not the path to a solution. Local search is used in most of the models of AI to search for the optimal solution according to the cost function of that model.
Today we implement the local search by using a hill-climbing algorithm and random restart variants. Hill climbing is one type of local search algorithm. In this algorithm, the neighbor states are compared to the current state to that neighbor state, and if any of them is better, we change the current node from the current state to that neighbor state.
The random restart is a variant of hill-climbing methods. Some time we face some problem in the hill-climbing method for that we can not find out the actual result that's why we are use come variants in hill-climbing methods. Random restart conduct hill-climbing multiple times. Each time, state from a random state, compare the maxima from every trial and choose the highest amongst those.
This is an Artificial Intelligence course conducted in City Universit by Nuruzzaman Faruqui. This is the best course in Bangladesh. Because Sir explained all the necessary things to us well. The problem we are dealing with in the lab. First, sir gives us a very good idea of the problem by using many examples. After that sir explains about the solutions like how we can solve the problem, how they work. For that, we understand everything very easily.
Problem :
First, we have to know about the problem. The problem is :
The python code to implement Local Search
import random # import random to generator random numbers
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):
# Now Add a house at a particular location
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)
)
# Now 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
# Now Start randomly initializing hospitals
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 maxmum 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
# Creating 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.random_restart(maximum=10,image_prefix="hospitals", log=True)
Result :
]
hospitals = s.hill_climb(image_prefix="hospitals", log=True) instead of hospitals = s.random_restart(maximum=10,image_prefix="hospitals", log=True)
No comments