The previous search algorithms all cares about the path from the initial state to the solution(which include the path), but if the path doesn’t matter, we can consider a different kind of algorithm. Local search algorithms operate using a single current node (rather than multiple paths) and generally move only to neighbors of that node, and the path followed by the search are typically not retained. In addition to finding goals, local search algorithms are useful for solving pure optimization problems, in which the aim is to find the best state according to an objective function.

Hill-Climbing Search

The hill-climbing search algorithm is simply a loop that continually moves in the direction of increasing value—that is, uphill. It terminates when it reaches a “peak” where no neighbor has a higher value.

function Hill_Climbing(problem):
	let curr = MAKE_NODE(problem.INITIAL_STATE)
	while true:
		let neighbor = highest-value successor of curr
		if neighbor.value <= curr.val:
			return curr.STATE
		curr = neighbor

Hill climbing is sometimes called greedy local search because it grabs a good neighbor state without thinking ahead about where to go next. While it’s efficient to improve a bad state, it has problem of getting stuck when facing the following situations:

• Local Maxima: a peak that is higher than each of its neighboring states but lower than the global maximum

• Ridges: result in a sequence of local maxima that is very difficult for greedy algorithms to navigate.

  

• Plateaux: a flat area of the state-space landscape

Many variants of hill climbing have been invented to prevent those problems:

• Stochastic hill climbing chooses at random from among the uphill moves; the probability of selection can vary with the steepness of the uphill move.
• First-choice hill climbing implements stochastic hill climbing by generating successors randomly until one is generated that is better than the current state
• Random-restart hill climbing conducts a series of hill-climbing searches from randomly generated initial states, until a goal is found.

Simulated Annealing

Idea: to escape local maxima by allowing some of the “bad” moves and the probability of the “bad” moves that we allow will decrease over time

• If a move improves the situation, then the move is always accepted. Otherwise, the algorithm will accept the move with a probability less than 1
• The probability of accepting “bad” moves decreases exponentially with the “badness” of the move-the amount $\Delta E$ by which the evaluation is worsened
• The probability decrease as the temperature goes down; “bad” moves are more likely to happen when T is high and become less likely when T decreases
• If the schedule lowers T slowly enough, the algorithm will find a global optimum with probability approaching 1

Local Beam Search