Simplest Hill-Climbing and Steppest Hill-Climbing Search Algorithms – Artificial Intelligence
In hill climbing the basic idea is to always head towards a state which is better than the current one.
So, if you are in town A and you can get to town B and town C (and your target is town D) then you should make a move IF town B or C appear nearer to town D than town A does.
Simplest Hill-CLimbing Search Algorithm
1. Evaluate the initial state.
If it is also goal state then return it, otherwise continue with the initial state as the current state.
2. Loop until the solution is found or until there are no new operators to be applied in the current state
a) Select an operator that has not yet been applied to the current state and apply it to produce new state
b) Evaluate the new state
i) If it is a goal state then return it and quit
ii) If it is not a goal state but it is better than the current state, then make it as current state
iii) If it is not better than the current state, then continue in loop.To understand the concept easily, we will take up a very simple example,
The key point while solving any hill-climbing problem is to choose an appropriate heuristic function.
Let’s define such function h:
h(x) = +1 for all the blocks in the support structure if the block is correctly positioned otherwise -1 for all the blocks in the support structure.
Steepest-Ascent Hill Climbing Search Algorithm in Artificial Intelligence
A variation on simple hill climbing.
Instead of moving to the first state that is better, move to the best possible state that is one move away.
The order of operators does not matter.
Not just climbing to a better state, climbing up the steepest slope.
Considers all the moves from the current state.
Selects the best one as the next state.
Basic hill-climbing first applies one operator n gets a new state. If it is better that becomes the current state whereas the steepest climbing tests all possible solutions n chooses the best.
1. Evaluate the initial state.
If it is also a goal state then return it and quit. Otherwise continue with the initial state as the current state.
2. Loop until a solution is found or until a complete iteration produces no change to current state:
a) Let SUCC be a state such that any possible successor of the current state will be better than SUCC.
b) For each operator that applies to the current state do:
i) Apply the operator and generate a new state.
ii) Evaluate the new state. If it is a goal state, then return it and quit.
If not compare it to SUCC. If it is better, then set SUCC to this state.
If it is not better, leave SUCC alone.
c) IF the SUCC is better than current state, then set current state to SUCC.
Hill Climbing Termination
Local Optimum: all neighboring states are worse or the same.
Plateau – all neighboring states are the same as the current state.
Ridge – local optimum that is caused by the inability to apply 2 operators at once.
Disadvantages of Hill Climbing
Hill climbing is a local method: Decides what to do next by looking only at the “immediate” consequences of its choices.
Will terminate when at a local optimum.
The order of application of operators can make a big difference.
Global information might be encoded in heuristic functions.
Summary
This article discusses Simplest Hill-Climbing and Steppest Hill-Climbing Search Algorithms – Artificial Intelligence. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.