Artificial Intelligence

Hill Climbing Algorithm in AI


July 20, 2022, Learn eTutorial
1447

In Artificial Intelligence a hill-climbing algorithm is an algorithm used to optimize mathematical problems. It keeps increasing its value continuously until a peak solution is achieved.

What is Hill Climbing Algorithm?

Hill climbing algorithm can be defined as a local search algorithm which is a form of the heuristic search algorithm. It keeps moving upward from the current state or the initial state until the best solution is attained or the peak is reached. Let us have a general example for a better understanding

Hill Climbing Algorithm in AI

Suppose Mr.X is climbing a hill. Mr.X will keep climbing the hill until he reaches the top of the hill. Mr. X is now at point A so the current position of Mr. X is A. Later he is at point B which is a better position than point A. So the current position of Mr. X now points to B. This procedure is continued until he reaches point C which is the peak of the hill. S in terms of our algorithm the current state is A initially and gets a better state B than A then the algorithm changes the current state from A to B this will be continued until it attains the best solution or the best point. Initially, the starting point is referred to as the base of the hill which is a non-optimal state. And it tries to climb or iterate constantly until it reaches the peak value or a certain precondition. The process of improving the current state can be called climbing. This is why it is named a hill-climbing algorithm.

Hill climbing algorithm can be said as a memory-efficient way to solve large computational problems. The best example for a hill-climbing approach is the Travelling Salesman Problem. The Hill climbing approach may not be the way to find the optimal solution but it is good to calculate the local minima/maxima.

STATE-SPACE DIAGRAM

Hill Climbing Algorithm in AI

The above given is a graphical representation of states and the objective function. If the y-axis represents the objective function then we can establish the global/local maxima. If the y-axis is used to represent the cost function we can establish the local/global minima. The x-axis is used to represent the state-space.

  • Local Maxima/Minima: It is a state which is a better state than the neighboring state. But it is not the best possible state that exists. It is better because the value of the objective function/cost function is higher than its neighbors.
  • Global Maxima/Minima:  It is the best possible state. Here the value of the objective function/cost function is highest.
  • Shoulder:  A plateau with upward stretched edges.
  • Flat local maxima:  A flat region where the neighboring solutions have the same value.

FEATURES OF HILL-CLIMBING ALGORITHM

The following are the key features of the hill-climbing algorithm

  1. Greedy approach: The algorithm always keeps moving in the direction of optimizing the cost. This enables the algorithm to establish the local minima/maxima.
  2. No Backtracking: It keeps moving forward. It works on the current state and looks to the succeeding states. Never look back to the previous states.
  3. Feedback mechanism: A variant of the generate-and-test algorithm. It helps to decide the next action. Whether to move up or down the hill.
  4. Incremental Change: Through incremental changes, the algorithm improves the current state.

WORKING OF HILL-CLIMBING ALGORITHM

It is the simplest implementation of a Genetic Algorithm. While comparing with more traditional genetic algorithms, It has a faster iteration but is less thorough than those.
Working on hill climbing is very simple. Let us have a simple description of the work.

  1. Start with an empty solution. This will consider as the “best solution initially”.
  2. Evaluate the present solution.
  3. Mutate the solution randomly.
  4. Evaluate the new solution and if it is found as the best solution then replace the previous solution with this one. Go to step 2 and repeat 2 and 3.

TYPES OF HILL CLIMBING

The following are the types of hill-climbing algorithms:

Types of Hill Climbing Algorithm in AI

1. SIMPLE HILL-CLIMBING 

It is the simplest form of the hill-climbing method where the neighboring solutions are evaluated. If the neighbor state holds a value greater than the current state then the algorithm will set this neighbor state as the current state. It checks only one successor state at a time. Following are the features of this algorithm:

  • Time-consuming is less
  • An optimal solution is less or solutions are suboptimal
  • Not guarantee a solution.
  • Require less computational power.

Algorithm for a simple hill-climbing algorithm.

Step 1:Create a CURRENT node, NEIGHBOR node, and a GOAL node.

Step 2:Evaluate the CURRENT node, If it is the GOAL node then stop and return success.

Step 3:Else set the NEIGHBOR node as the CURRENT node and move ahead.

Step 4:Loop until CURRENT node = GOAL node or there exist no operator to apply.

Step 5:EXIT.

2. STEEPEST ASCENT HILL CLIMBING

It is a variation of the simple hill-climbing algorithm. Here the algorithm will check all the neighboring nodes of the current state and select the one with the value closest to the goal state. As it searches all the neighboring nodes the time consumption is high and also the consumption power is also high.

Algorithm for steepest-ascent hill climbing

Step 1:Create a CURRENT node, NEIGHBOR node, and a GOAL node.

Step 2:Evaluate the CURRENT node, If it is the GOAL node then stop and return success.

Step 3:Else set a state (X) where the current state successors have higher values than it.

Step 4:Operate with the new operator and generate a new solution.

Step 5: Compare this new solution with the GOAL node. If yes then EXIT the program, Else compare it with the state (X).

Step 6:If the new state is higher than the state (X), then set it as X

Step 7:Continue the loop. Repeat steps 4 and 5.

Step 8:EXIT.

3. STOCHASTIC HILL CLIMBING

Here the algorithm never focuses on all the neighboring nodes. It selects one neighboring node randomly to check whether it is better than the current node. The selection of neighboring nodes randomly is performed based on some pre-defined criteria.

Algorithm for stochastic hill climbing

Step 1:Create a CURRENT node, NEIGHBOR node, and a GOAL node.

Step 2:Evaluate the CURRENT node, If it is the GOAL node then stop and return success.

Step 3:Else select a NEIGHBOR node randomly and evaluate NEIGHBOR.

NEIGHBOR is selected with probability  Types of Hill Climbing Algorithm in AI

Step 4: If NEIGHBOR = GOAL return success and exit. Else set CURRENT node=NEIGHBOR and continue the loop. Repeat steps 2, 3, 4

Step 5:EXIT.

4. RANDOM RESTART HILL CLIMBING

Here a try-and-try strategy is used. Here the nodes are searched iteratively and then selects the best one at each step. This will continue until the goal is found. The success of the procedure depends on the shape of the hill. With a few plateaus, local maxima, and ridges it is easy to get to the destination. It is also known as shotgun hill climbing. A successful algorithm with probability p runs n times or a solution is found, will solve with probability  Types of Hill Climbing Algorithm in AI

PROBLEMS WITH HILL CLIMBING

There are three main regions in which the hill-climbing algorithm cannot attain an optimal solution.

  1. LOCAL MAXIMUM

    At the point of local maximum, the greedy approaching feature of the algorithm will lead to a termination since the neighboring states have a value lower than the current state. But this is not the best possible solution, there exists a global maximum.

     

    Types of Hill Climbing Algorithm in AI

    Solution: The backtracking technique can be used to overcome the problem of the local maximum. The visited states are listed and if the search reaches an undesired state, it can backtrack and explore a new path.

  2. RIDGE

    Points on ridge always look like a peak. All the possible moves from a point on the ridge are downward. So, the algorithm will terminate from such a state.

    Types of Hill Climbing Algorithm in AI

    Solution: Make movements in several directions at once.

  3. PLATEAU

    On the plateau, all the neighbors are with the same value. So it is difficult to select the best direction.

    Types of Hill Climbing Algorithm in AI

    Solution: Take a huge jump to reach a non-plateau space.

SIMULATED ANNEALING

As we know the hill-climbing algorithm never makes a downward movement or a move towards a lower value. And is incomplete since it will be stuck on a local maximum. If the algorithm makes a random walk, then it can be complete but not efficient.

Simulated annealing is a solution or an algorithm that allows downward steps for escape from local maxima.

Annealing can be defined as the process of hardening a metal to a high temperature then cooling gradually, So the metal will reach a low-energy crystalline state mechanically. A similar process is used in the simulated annealing. Here the algorithm picks a random move rather than the best move. If the selected random move improves the state, then the same path is followed. Else it follows a path with a probability of less than 1, or it will make a move downward and choose another path.

ADVANTAGES OF HILL-CLIMBING ALGORITHM IN AI.

  • Useful for routing-related problems like Travelling Salesman Problem, Job Scheduling, Chip Designing, and Portfolio Management.
  • With limited computation power, it can be used to solve the optimization problem.
  • Efficient than other searching algorithms.

APPLICATIONS OF THE HILL-CLIMBING ALGORITHM

The following areas can make use of the hill-climbing algorithm.

MARKETING

It can be used to generate good marketing plans. This technique is widely used to solve Travelling Salesman Problems. It can be used to establish the local minima efficiently.

ROBOTICS

It can be used to enhance the coordination of different components and systems in robots.

JOB SCHEDULING

In job scheduling, the system resources are allocated to different tasks and there is a migration of jobs from one node to another. Hill climbing can be used to establish the right route.