Optimization Problems and Local Search

Study Notes

In many optimization problems, the path to the goal is irrelevant, and the goal state itself is the solution.
State space is a set of "complete" configurations of a problem, and the target is to find a configuration that satisfies constraints.

Local search algorithms are useful for solving pure optimization problems, where the aim is to find the best state according to an objective function.
These algorithms explore the state-space landscape, where "location" is defined by the state, and "elevation" is defined by a heuristic cost or objective function.
The aim is to find the lowest valley (global minimum) or the highest peak (global maximum) in the landscape.

HCS is a loop that continually moves in the direction of increasing value and terminates when it reaches a "peak" where no neighbor has a higher value.
It does not maintain a search tree, so the current node only needs to record the state and the value of the objective function.
HCS is an incomplete algorithm that can get stuck on a local maximum.

Simulated Annealing Search is an extension of HCS that escapes local maxima by allowing some "bad" moves but gradually decreases their size and frequency.
It picks a random move, takes some downhill steps to escape the local maximum, and accepts the move with some probability less than 1.
Physical analogy: annealing process to harden metals, where the heuristic value is the energy, E, and the temperature parameter, T, controls the speed of convergence.
If T decreases slowly enough, then simulated annealing search will find a global optimum with probability approaching 1.

LBS keeps track of k states rather than just one, starting with k randomly generated states.
At each iteration, all the successors of all k states are generated, and the k best successors are selected and repeated.
LBS quickly abandons unfruitful searches and moves its resources to where the most progress is being made, but it can suffer from a lack of diversity among the k states.