This raises the percentage of problem instances solved by hill climbing from 14% to 94%. For example, we could allow up to say 100 consecutive sideways moves in the 8-queens problem. One common solution is to put a limit on the number of consecutive sideways moves allowed. If we always allow sideways moves when there are no uphill moves, an infinite loop will occur whenever the algorithm reaches a flat local maximum which is not a shoulder. The answer is usually yes, but we must take care. Is it advisable to allow a sideway move in the hope that the plateau is really a shoulder. The algorithm halts if it reaches a plateau where the best successor has the same value as the current state. It works quickly, taking just 4 steps on average when it succeeds and 3 when it gets stuck-not bad for a state space with 8 8 = 17 million states. Starting for a randomly generated 8-queens state, steepest-ascent hill climbing gets stuck 86% of the time, solving only 14% of problem instances. In each case, the algorithm reaches a point at which no progress is being made. This corresponds to moving in several directions at once. To overcome this move apply two or more rules before performing the test. But the orientation of the high region, compared to the set of available moves and direction in which they move makes it impossible to traverse the ridge by single move. It is an area of the search space which is higher than the corresponding areas and that itself has a slope. Ridge is a special kind of local maximum. A hill climbing search might be unable to find its way off the plateau. It can be flat local maximum, from which no uphill exit exists, or a shoulder from which it is possible to make progress. Hill climbing algorithms typically choose randomly among the set of best successors, if there is more than one.Ī plateau is an area of the state space landscape where the evaluation function is flat. The heuristic cost function h is the number of pairs of queens that are attacking each other, either directly or indirectly the global minimum of this function is zero, which occurs only at perfect solutions. The successor function returns all possible states generated by moving a single queen to another square in the same column (so each state has 8*7 = 56 successors). Local search algorithms typically use a complete state formulation, where each state has 8 queens on the board, one per column. To illustrate hill climbing, we will use the 8-queens problem. This resembles trying to find the top of Mount Everest in a thick fog while suffering from amnesia. Hill climbing does not look ahead beyond the immediate neighbours of the current state. It terminates when it reaches “peak” where no neighbour has a higher value, the algorithm does not maintain a search tree, so the current node data structure need only record the state and its objective function value. It is simply a loop which continually moves in the direction of increasing value- that is uphill.
0 Comments
Leave a Reply. |