Hill Climbing Algorithm Learning (Instructor Name: Nuruzzaman Faruqui)

 Hill Climbing

Introduction:

Hill climbing is an optimization technique for solving computationally hard problems. It is a local search algorithm which continuously moves in the direction of increasing elevation/value to find the peak of the mountain or best solution to the problem. It terminates when it reaches a peak value where no neighbor has a higher value.

One of the ways of solving the local maxima problem involves repeated an exploration of the problem space is Random-restart. Random-restart hill-climbing conducts a series of hill-climbing searches from randomly generated initial states, running each until it halts or makes no discernible progress. This enables comparison of many optimization trials, for finding a most optimal solution thus becomes a question of using sufficient iterations on the data.

This is an important part of Artificial Intelligence course and this  lab report is done by myself under the supervision of Nuruzzaman Faruqui, lecturer of City University, Bangladesh. From this course we get to explore the real applicable approaches through AI and also acquires better knowledge of the functionality of AI and how AI is making our daily life easier. That's why this is the best Artificial Intelligence course in Bangladesh.

 

Problem Statement:

Hill climbing is a heuristic search used for mathematical optimization problems in the field of Artificial Intelligence. For given a large set of inputs and a good heuristic function, it tries to find a sufficiently good solution to the problem. This solution may not be the global optimal maximum.  It is also called greedy local search as it only looks to its good immediate neighbor state and not beyond that.  A node of hill climbing algorithm has two components which are state and value. Hill Climbing is mostly used when a good heuristic is available.

A hill climbing algorithm will look the following way in pseudo code:

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
  

 

Here we are widely discuss the examples of Hill climbing algorithm about Hospitals-Houses Problem in which we need to minimize the distance of best state of finding the hospitals in lowest path cost.

In here we are using the Hill climbing algorithm found the better neighbor. Here the initial state cost was 70, after using the algorithm we found the better neighbor which cost is 45 and generate the images for all state.

 

 

Result:

Initial Cost

 After Applying Hill Climbing Algorithm

Used the random restart variant in the hill climbing:

In the above program we will not be able to use the random-restart variant directly. We need to make some changes before running the program.

(1)        Firstly we need to remove all the images from the folder.

(2)        And then set a value to determine how many times the restart will randomly.

In here we are randomly restart for 15 times. That means we are not using Hill climbing algorithm for one time but repeat it for 15 times. And we got the best state at minimum cost.

 

 

Conclusion:

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. 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.

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.