EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login

Hill Climbing in Artificial Intelligence

By Priya PedamkarPriya Pedamkar

Home » Data Science » Data Science Tutorials » Artificial Intelligence Tutorial » Hill Climbing in Artificial Intelligence

hill climing in artificial intelligence 3

Introduction to Hill Climbing in Artificial Intelligence

Hill Climbing is a form of heuristic search algorithm which is used in solving optimization related problems in Artificial Intelligence domain. The algorithm starts with a non-optimal state and iteratively improves its state until some predefined condition is met. The condition to be met is based on the heuristic function. The aim of the algorithm is to reach an optimal state which is better than its current state. The starting point which is the non-optimal state is referred to as the base of the hill and it tries to constantly iterate (climb) untill it reaches the peak value, that is why it is called Hill Climbing Algorithm.

Hill Climbing Algorithm is a memory-efficient way of solving large computational problems. It takes into account the current state and immediate neighbouring state. The Hill Climbing Problem is particularly useful when we want to maximize or minimize any particular function based on the input which it is taking. The most commonly used Hill Climbing Algorithm is “Travelling Salesman” Problem” where we have to minimize the distance travelled by the salesman. Hill Climbing Algorithm may not find the global optimal (best possible) solution but it is good for finding local minima/maxima efficiently.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Key Features of Hill Climbing in Artificial Intelligence

Following are few of the key features of Hill Climbing Algorithm

  • Greedy Approach: The algorithm moves in the direction of optimizing the cost i.e. finding Local Maxima/Minima
  • No Backtracking: It cannot remember the previous state of the system so backtracking to the previous state is not possible
  • Feedback Mechanism: The feedback from the previous computation helps in deciding the next course of action i.e. whether to move up or down the slope

State Space Diagram – Hill Climbing in Artificial Intelligence

  • Local Maxima/Minima: Local Minima is a state which is better than its neighbouring state, however, it is not the best possible state as there exists a state where objective function value is higher 
  • Global Maxima/Minima: It is the best possible state in the state diagram. Here the value of the objective function is highest
  • Current State: Current State is the state where the agent is present currently
  • Flat Local Maximum: This region is depicted by a straight line where all neighbouring states have the same value so every node is local maximum over the region

hill climing in artificial intelligence

Problems in Hill Climbing Algorithm

Here ve discuss the problems in the hill-climbing algorithm:

1. Local Maximum

The algorithm terminates when the current node is local maximum as it is better than its neighbours. However, there exists a global maximum where objective function value is higher

Solution: Back Propagation can mitigate the problem of Local maximum as it starts exploring alternate paths when it encounters Local Maximum

2. Ridge

Ridge occurs when there are multiple peaks and all have the same value or in other words, there are multiple local maxima which are same as global maxima

Popular Course in this category
Artificial Intelligence Training (3 Courses, 2 Project)3 Online Courses | 2 Hands-on Project | 32+ Hours | Verifiable Certificate of Completion | Lifetime Access
4.5 (5,507 ratings)
Course Price

View Course

Related Courses
All in One Data Science Bundle (360+ Courses, 50+ projects)Machine Learning Training (17 Courses, 27+ Projects)

hill climing in artificial intelligence 1

Solution: Ridge obstacle can be solved by moving in several directions at the same time

3. Plateau

Plateau is the region where all the neighbouring nodes have the same value of objective function so the algorithm finds it hard to select an appropriate direction.

Plateau

Solution: Plateau obstacle can be solved by taking making a big jump from the current state which will land you in non-plateau region

Types of Hill Climbing Algorithm in Artificial Intelligence

Here we discuss the types of a hill-climbing algorithm in artificial intelligence:

1. Simple Hill Climbing

It is the simplest form of the Hill Climbing Algorithm. It only takes into account the neighboring node for its operation. If the neighboring node is better than the current node then it sets the neighbor node as the current node. The algorithm checks only one neighbor at a time. Following are a few of the key feature of the Simple Hill Climbing Algorithm

  • Since it needs low computation power, it consumes lesser time
  • The algorithm results in sub-optimal solutions and at times the solution is not guaranteed

Algorithm

1. Examine the current state, Return success if it is a goal state

2. Continue the Loop until a new solution is found or no operators are left to apply

3. Apply the operator to the node in the current state

4. Check for the new state

  • If Current State = Goal State, Return success and exit
  • Else if New state is better than current state then Goto New state
  • Else return to step 2

5. Exit

2. Steepest-Ascent Hill Climbing

Steepest-Ascent hill climbing is an advanced form of simple Hill Climbing Algorithm. It runs through all the nearest neighbor nodes and selects the node which is nearest to the goal state. The algorithm requires more computation power than Simple Hill Climbing Algorithm as it searches through multiple neighbors at once.

Algorithm

1. Examine the current state, Return success if it is a goal state

2. Continue the Loop until a new solution is found or no operators are left to apply

Let ‘Temp’ be a state such that any successor of the current state will have a higher value for the objective function. For all operators that can be applied to the current state

  • Apply the operator to create a new state
  • Examine new state
  • If Current State = Goal State, Return success and exit
  • Else if New state is better than Temp then set this state as Temp
  • If Temp is better than Current State set Current state to Target

3. Stochastic Hill Climbing

Stochastic Hill Climbing doesn’t look at all its neighboring nodes to check if it is better than the current node instead, it randomly selects one neighboring node, and based on the pre-defined criteria it decides whether to go to the neighboring node or select an alternate node.

Advantage of Hill Climbing Algorithm in Artificial Intelligence

Advantage of Hill Climbing Algorithm in Artificial Intelligence is given below:

  • Hill Climbing is very useful in routing-related problems like Travelling Salesmen Problem, Job Scheduling, Chip Designing, and Portfolio Management
  • It is good in solving the optimization problem while using only limited computation power
  • It is more efficient than other search algorithms

Hill Climbing Algorithm is a very widely used algorithm for Optimization related problems as it gives decent solutions to computationally challenging problems. It has certain drawbacks associated with it like its Local Minima, Ridge, and Plateau problem which can be solved by using some advanced algorithm.

Recommended Articles

This is a guide to Hill Climbing in Artificial Intelligence. Here we discuss the introduction and key features hill-climbing algorithm along with its advantages and its types. You can also go through our other suggested articles to learn more –

  1. Differences Between Machine Learning vs Artificial Intelligence
  2. Key Benefits of Artificial Intelligence
  3. Different Types of Artificial Intelligence
  4. How Does Artificial Intelligence Apply?
  5. PowerShell Where Object | Parameters | Examples

Artificial Intelligence Training (3 Courses, 2 Project)

3 Online Courses

2 Hands-on Project

32+ Hours

Verifiable Certificate of Completion

Lifetime Access

Learn More

1 Shares
Share
Tweet
Share
Primary Sidebar
Artificial Intelligence Tutorial
  • Basics
    • Introduction to Artificial Intelligence
    • What is Artificial Intelligence
    • Careers in Artificial Intelligence
    • Future of Artificial Intelligence
    • Uses of Artificial Intelligence
    • Artificial Intelligence Ethics
    • Types of Artificial Intelligence
    • Artificial Intelligence Tools & Applications
    • Artificial Intelligence Applications
    • Advantages of Artificial Intelligence
    • Artificial Intelligence Tools
    • Benefits of Artificial Intelligence
    • Artificial Intelligence Companies
    • Artificial Intelligence Techniques
    • Artificial Intelligence Software
    • How Artificial Intelligence Works
    • Importance of Artificial Intelligence
    • Subsets of Artificial Intelligence
    • Artificial Intelligence Problems
    • Artificial Intelligence Technology
    • Application of Neural Network
    • Applications of NLP
    • Global Positioning Systems
    • Production System in AI
    • Agents in Artificial Intelligence
    • Intelligent Agent in AI
    • Artificial Intelligence Algorithm
    • Search Algorithms in AI
    • Informed Search
    • Bidirectional Search
    • Adversarial Search
    • Uninformed Search
    • Uniform Cost Search
    • Hill Climbing in Artificial Intelligence
    • Propositional Logic in AI
    • Minimax Algorithm
    • Applications of Fuzzy Logic
    • Fuzzy Logic System
    • Implementation of Neural Networks
    • Turing Test in AI
    • Recurrent Neural Networks (RNN)
    • Spiking Neural Network
    • Feedforward Neural Networks
    • Probabilistic Neural Network
    • Overfitting Neural Network
    • Means-Ends Analysis
    • DNN Neural Network
    • Principal Component Analysis
    • Artificial Intelligence Interview
  • Pattern Recognition
    • Pattern Recognition
    • Pattern Recognition Algorithms
    • Forensic Tools
    • PRTools
    • Pattern Recognition Applications

Related Courses

Artificial Intelligence Training Courses

All One Data Science Training Courses

Machine Learning Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA Login

Forgot Password?

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - Artificial Intelligence Training (3 Courses, 2 Project) Learn More