Optimization Problems and Local Search

Optimization Problems

• 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

• 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.

Hill-Climbing Search (HCS)

• 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

• 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.

Local Beam Search (LBS)

• 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.