Scribd
Upload
17 views2 pages

Exno 3 Implementing The Hill Climbing Algorithm in Python

The document outlines the implementation of the Hill Climbing Algorithm in Python for solving optimization problems. It includes functions for generating a distance matrix from coordinates, finding random solutions, calculating path lengths, and identifying neighboring solutions. The final output presents the best solution found by the algorithm as a sequence of indices representing the optimal path.

Uploaded by

hemavasanth69
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
17 views2 pages

Exno 3 Implementing The Hill Climbing Algorithm in Python

The document outlines the implementation of the Hill Climbing Algorithm in Python for solving optimization problems. It includes functions for generating a distance matrix from coordinates, finding random solutions, calculating path lengths, and identifying neighboring solutions. The final output presents the best solution found by the algorithm as a sequence of indices representing the optimal path.

Uploaded by

hemavasanth69
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 2

Implementing the Hill Climbing Algorithm in Python

Algorithm
1. # hill climbing local search algorithm. def hillclimbing(objective, bounds, n_iterations, step_size):
2. # generate an initial point. ...
3. # evaluate the initial point. ...
4. # run the hill climb. ...
5. # take a step. ...
6. # evaluate candidate point. ...
7. # check if we should keep the new point. ...
8. # store the new point.

program

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]

You might also like