0

What are some examples that cause Simple Hill Climbing to reach problems like local maxima, ridges and alleys, and plateau problem(s)? I have tried searching:

  • Link one: which gives a fairly good example of Simple Hill Climbing stuck-in-local-maxima problem in block arrangements. However, it does not show the steps.
  • Link two: which gives steps to finding the solution in SHC. However, I don't understand how h(1) can be -6 when all there are only four blocks and four of them are misplaced, therefore only yielding -4. It also doesn't show the problem(s) encountered by SHC.
  • Link three: I understand how the concept of reaching state 'g' makes your algorithm reach a local maximum and get stuck. However, it's rather ambiguous what the states are and I don't know what state 'g' and the final states refer to.

From the lecture note I read, I was given the TSP problem. The graph was a complete graph with four nodes: A, B, C and D. We used both Simple Hill Climbing and Steepest-Ascent Hill Climbing to solve the problem. The heuristic value used to solve that problem was the total distance of each state. We can explore other neighbouring states by switching positions of the characters "ABCD" using 6 different combinations (first letter <-> second, second <-> third, etc.). However, in the example given, it did not show what exactly "stuck at a local maximum" is. Neither did it show the ridges and alleys problem nor the plateau problem.

Could someone give me an example of how we reach those problems and what those problems actually are in examples (I understand the definition of each problem: here and here)? For reference, this below is the image of the TSP problem I mentioned: TSP Map

Richard
  • 7,037
  • 2
  • 23
  • 76

1 Answers1

1

When your simple hill climbing walk this Ridge looking for an ascent, it will be inefficient since it will walk in x or y-direction ie follow the lines in this picture. It results in a zig-zag motion.

To reach this state, given a random start position, the algorithm evaluates the 4 positions (x+1,y) (x-1,y) (x, y+1) (x, y-1) (for a step of 1) and pics the highest. So it will start to move toward the ridge.

Let's illustrate this behavior with the previous picture. Given a start at the origin (0,0), and a step of 1. The thin dark lines intersect on the surface are the unit point ((0,1),(0,2),...,(1,0),...) images through the function. The algorithm chooses in those points, but only those directly adjacent (because it moves along the axis). This is the path it will take. (forgive my poor paint skills).

In the link 2, to compute the heuristic function, you evaluate each block, if the block is misplaced (aka not at the right index on the pile) each block under it add -1, otherwise, each block under it add +1. h(1) = -3 -2 -1 (A is misplaced, there is 3 blocks under it so -3, same for B but 2 blocks so -2, C -1 and D has no block under it so does not add anything)

For the plateau problem, if you reach a flat surface or almost flat, the algorithm will not be able to find a better position.

I hope I understood your question.

Pilou
  • 26
  • 5
  • Hello, thank you for the answer. I'd like to point out that **I know what plateau problem is**. I've also included one example on Link Three above. However, I'd like more examples of SHC encountering plateau problem. As for ridges and alleys, I don't understand why it would walk in a zig-zag motion. Could you please elaborate further? – Richard Mar 29 '19 at 07:11
  • I see, I think I understand what ridges and alleys mean now. A simplified version would be, it could actually skip the zig-zag motion and walk "straight" (which is not provided in its path) to reach solution faster, right? So it's more about the problem of the solution not being optimal? – Richard Mar 30 '19 at 03:24
  • Not optimal as in being inefficient as you mentioned or "slow", right? – Richard Mar 30 '19 at 04:17
  • Yes the problem is that this algorithm does not perform well on ridges / valley, especially as the ridge get sharper. There is an algorithm with moves choosing the steepest slope (ie going "straight"), and it is called gradient descent. – Pilou Mar 31 '19 at 12:13
  • Okay, thank you for your time and for your answer :-D – Richard Apr 02 '19 at 02:28