4

What is the difference between stochastic hill climbing and first-choice hill climbing algorithms?

Md. Abu Nafee Ibna Zahid
  • 455
  • 1
  • 6
  • 19
user5492770
  • 357
  • 3
  • 5
  • 13

3 Answers3

10

Hill Climbing Search Algorithm is one of the family of local searches that move based on the better states of its neighbors. Stochastic Hill Climbing chooses a random better state from all better states in the neighbors while first-choice Hill Climbing chooses the first better state from randomly generated neighbors.

First-Choice Hill Climbing will become a good strategy if the current state has a lot of neighbors.

Md. Abu Nafee Ibna Zahid
  • 455
  • 1
  • 6
  • 19
Gusti Ahmad Fanshuri Alfarisy
  • 151
  • 5
  • Do you mean by first-choice Hill Climbing is the classic hill climbing algorithm? – Nasser Jan 21 '18 at 17:20
  • 2
    No, Hill Climbing algorithm choose the best of all neighbors ( all neighbors have been visited/computed ) which better than current state while first-choice only choose the first found of a better state ( not all neighbors have been visited/computed). – Gusti Ahmad Fanshuri Alfarisy Jan 24 '18 at 02:31
  • @GustiAhmadFanshuriAlfarisy, Thank you for your nice answer. I think you might missed a vital point. In generic stochastic hill climbing the probability of selection usually vary with the steepness of the uphill move. – Md. Abu Nafee Ibna Zahid Mar 04 '18 at 05:26
  • Thank you for your correction @Md.AbuNafeeIbnaZahid, the probability of neighbor selection is vary with the steepness of the uphill move. – Gusti Ahmad Fanshuri Alfarisy Mar 28 '18 at 07:12
1

I am quoting from Artificial Intelligence: A Modern Approach (3rd ed.) (2010) by Russell, Norvig

Stochastic hill climbing chooses at random from among the uphill moves; the probability of selection can vary with the steepness of the uphill move. This usually converges more slowly than steepest ascent, but in some state landscapes, it finds better solutions. First-choice hill climbing implements stochastic hill climbing by generating successors randomly until one is generated that is better than the current state. This is a good strategy when a state has many (e.g., thousands) of successors.

So First-choice hill climbing is a special kind of stochastic hill climbing.

Md. Abu Nafee Ibna Zahid
  • 455
  • 1
  • 6
  • 19
1

General hill climbing is a local search algorithm which chooses the best of the neighbor that is it chooses a neighbor with the steepest path and the best objective function value. But due to this it may fail to reach the global maximum and get stuck at the local maximum. Whereas, in the case of stochastic hill climbing it chooses the neighbor with uphill move randomly and the probability of selection might change with the steepness of the uphill moves.In the case of first choice hill climbing it generates the next move randomly and does the search until a state which is better than all the states is found.

Udbhav
  • 11
  • 2