1
$\begingroup$

One-point Hill Climbing can get stuck due to which of the following phenomenon?

  1. Local Maxima
  2. Inadmissible heuristic
  3. Ridges
  4. Plateau
Improve this question
$\endgroup$
  • 4
    $\begingroup$ This looks to me like an exams question. Can you show some o the research you have done yourself to try and answer the question? See, for example, en.wikipedia.org/wiki/Hill_climbing $\endgroup$ – Oliver Mason Feb 19 '20 at 15:31
  • 1
    $\begingroup$ When do get stuck in any non-convex optimization problem? $\endgroup$ – kosa Feb 19 '20 at 15:33
  • 1
    $\begingroup$ I think this is a homework question too, but it may be a useful thing to have an answer to on this site, especially because the real answer will depend a lot on the way the instructor chooses to present hill climbing. $\endgroup$ – John Doucette♦ Feb 22 '20 at 1:04
1
$\begingroup$

This question really looks like a homework problem, in part because it is too vague (what does it mean to 'get stuck' exactly?).

  1. Hill climbing stops when it reaches a local maximum.

  2. Hill climbing is an uninformed search algorithm, so it does not make use of a heuristic.

  3. Hill climbing may or may not stop on a ridge, depending on the implementation. Some common implementations move randomly when equal (but not better) moves are available. Others stop in this situation.

  4. Hill climbing may or may not stop on a plateau, depending on how the implementation handles the case of ties, like with ridges. Whether you think it 'gets stuck' depends a lot on your definition. Implementations that stop when encountering a tie will stop. Implementations that don't stop will eventually exit the plateau through random movements, but it could take infinite time if your movements in the gradient-free region are unlucky.

Improve this answer
$\endgroup$
0
$\begingroup$

It should be crystal clear to those who understand the word "stuck" that the term "get stuck" means, in this context, to either

  1. reach an answer that appears to be an optimum before reaching an optimum and stopping or

  2. never stopping.

The answer to the question is simply 1.

If 4. is the global maximum, that it is a plateau is irrelevant. The value (height) function finds all values on the surface of the plateau equal in value.

If 3. is encountered but it is not a local maximum, the gradient would direct ascension around the ridge unless the ridge were perfectly perpendicular to the normal line.

If a logical system were added to the inversion (gradient ascent) of gradient descent to augment it in some way, which is the only way 2. would make sense, it would be inadmissible to allow the insertion of rules, heuristic or not, that were inadmissible, so 2. applies only if the system designer was of the kind that does not understand fault resistant systems architecture.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.