6
$\begingroup$

I am reading about local search: hill climbing, and its types, and simulated annealing

One of the hill climbing versions is "stochastic hill climbing", which has the following definition:

Stochastic hill climbing does not examine for all its neighbor before moving. Rather, this search algorithm selects one neighbor node at random and decides whether to choose it as a current state or examine another state

Some sources mentioned that it can be used to avoid local optima.

Then I was reading about simulated annealing and its definition:

At every iteration, a random move is chosen. If it improves the situation then the move is accepted, otherwise it is accepted with some probability less than 1

So, what is the main difference between the two approaches? Does the stochastic choose only random (uphill) successor? If it chooses only (uphill-successors), then how does it avoid local optima?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Russell and Norvig's book (3rd edition) describe these two algorithms (section 4.1.1., p. 122) and this book is the reference that you should generally use when studying search algorithms in artificial intelligence. I am familiar with simulated annealing (SA), given that I implemented it in the past to solve a combinatorial problem, but I am not very familiar with stochastic hill climbing (SHC), so let me quote the parts of the book that describe SHC.

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.

So, SHC chooses at random one "uphill move", i.e. a move that improves the objective function (for example, if you're trying to solve the travelling salesman problem, a "uphill move" could be any change to the current Hamiltonian cycle, a solution, so that the new Halmitonian cycle has a shorter cost) among the uphill moves (so among some set of moves that improve the objective).

In simulated annealing, you perform some move. If that move leads to a better solution, you always keep the better solution. If it leads to a worse solution, you accept that worse solution with a certain probability. There are other details, such as how you accept the worse solution (which you can find in Russell and Norvig's book), but this should already clarify that SA is different from SHC: SA can accept worse solutions in order to escape from local minima, while SHC accepts only uphill moves.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you very much, now it is clear to me, one thing left, since SHC chooses only random uphill moves, does this algorithm avoid local optima? $\endgroup$
    – yaminoyuki
    Commented Nov 23, 2020 at 22:45
  • 1
    $\begingroup$ @yaminoyuki I think SHC can still get stuck in a local minimum. This should be due to the fact that SHC never takes a "downhill move". In any case, the book says that, in some "landscapes", SHC may find better solutions than the usual HC algorithm, and this may be true because SHC doesn't always choose the same uphill move and so has more stochasticity in it. $\endgroup$
    – nbro
    Commented Nov 24, 2020 at 10:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .