Local Search Algorithms and Optimization Problems

Finding a Good State without worrying about the path to get there.

Outline

• Local search algorithms
• Hill-climbing search
• Simulated annealing search
• Local beam search
• Genetic algorithms

Local Search and Optimization

• Local search= use single current state and move to neighboring states.
• Advantages:
• Use very little memory
• Find often reasonable solutions in large or infinite state spaces.
• Are also useful for pure optimization problems.
• Find best state according to some objective function.

Local search algorithms

• In many optimization problems, the path to the goal is irrelevant; the goal state itself is the solution.
• e.g., n-queens.

​

​

• E.g., Integrated-circuit design
• Job scheduling
• Telecommunication network optimization
• …

​

Local Search and Optimization

• Previously: systematic exploration of search space.
• Path to goal is solution to problem
• YES, for some problems path is irrelevant.
• E.g. 8-queens
• Different algorithms�can be used
• Local search

8-Queens Problem

• Put 8 queens on an 8 × 8 board with no two queens attacking each other.
• No two queens share the same row, column, or diagonal.

​

8-Queens Problem

• Incremental formulation
• Complete-state formulation

​

​

Local search algorithms

• In many optimization problems, the path to the goal is irrelevant; the goal state itself is the solution.
• e.g., n-queens.

​

​

• We can use local search algorithms:
• keep a single "current" state, try to improve it
• generally move to neighbors
• The paths are not retained

​

​

Advantages to local search

• Use very little memory
• Can often find reasonable solutions in large state spaces
• Useful for solving pure optimization problems
• maximize goodness measure
• Many do not fit in “standard” model:
• Darwinian evolution (Goal test? Path cost?)

​

• Local search algorithms can’t backtrack

​

Example: n-queens

• Move a queen to reduce number of conflicts

​

Hill-Climbing Search

• "Like climbing Everest in thick fog with amnesia"

​

Hill-Climbing Search

function HILL-CLIMBING( problem) return a state that is a local maximum

input: problem, a problem

local variables: current, a node.

neighbor, a node.

current ← MAKE-NODE(INITIAL-STATE[problem])

loop do

neighbor ← a highest valued successor of current

if VALUE [neighbor] ≤ VALUE[current]

then return STATE[current]

current ← neighbor

Hill Climbing Search for 8-Puzzle Problem

• Initial State: Start with a random arrangement of tiles.
• Goal State: Define the target configuration.
• Heuristic Function (h(n)): Choose a heuristic to evaluate the current state. Common heuristics include:
• Misplaced Tiles: Count of tiles in the wrong position.
• Manhattan Distance: Sum of the distances of all tiles from their correct positions.

Generate Successors: Find all possible moves (up, down, left, right) by sliding a tile into the empty space.

• Select the Best Move: Choose the move that results in the lowest heuristic value.
• Move to the New State: If the new state is better than the current, move to it; otherwise, stop (can get stuck in local optima).
• Repeat Until Goal is Reached or No Better Move Exists.

​

​

Hill Climbing Search for 8-Puzzle Problem

1 2 3

4 8 5

6 _ 7

​

1 2 3

4 5 6

7 8 _

​

Initial State

Goal State

Hill-Climbing Search: 8-Queens Problem

• h = number of pairs of queens that are attacking each other, either directly or indirectly
• h = 17 for the state�in this example

Hill-Climbing Search: 8-Queens Problem

• A local minimum with h = 1

Drawbacks

• Local maximum = a peak higher than its neighboring states but lower than the global maximum
• Ridge = sequence of local maxima difficult for greedy algorithms to navigate
• Plateaux, shoulder = an area of the state space where the evaluation function is flat.
• Gets stuck 86% of the time.

Drawbacks

ridge

Hillclimbing �(Greedy Local Search)

• Generate nearby successor states to the current state
• Pick the best and replace the current state with that one.
• Loop

Hill-climbing search problems�(this slide assumes maximization rather than minimization)

• Local maximum: a peak that is lower than the highest peak, so a suboptimal solution is returned
• Plateau: the evaluation function is flat, resulting in a random walk
• Ridges: slopes very gently toward a peak, so the search may oscillate from side to side

20

Local maximum

Plateau

Ridge

Random restart hill-climbing�(note: there are many variants of hill climbing)

• Start different hill-climbing searches from random starting positions stopping when a goal is found
• Save the best result from any search so far
• If all states have equal probability of being generated, it is complete with probability approaching 1 (a goal state will eventually be generated).
• Finding an optimal solution becomes the question of sufficient number of restarts
• Surprisingly effective, if there aren’t too many local maxima or plateaux

​

Hill-climbing search (steepest-ascent version)

​

​

​

​

​

​

• A simple loop that continuously moves in the direction of increasing value – uphill
• Terminates when reaches a “peak”
• does not look ahead beyond the immediate neighbors, does not maintain a search tree

8-queens problem

​

​

​

​

​

​

​

​

• How many successors we can derive from one state?
• Each state has 8*7 = 56 successors.

complete-state formulation

vs.

incremental formulation

8-queens problem

​

​

​

​

​

​

​

​

• h = number of pairs of queens that are attacking each other, either directly or indirectly (h=0 solution)
• h = 17 for the above state

​

Hill-climbing search

• “Greedy local search”
• grabs a good neighbor state without thinking ahead about where to go next
• makes rapid progress

Hill climbing search: �8-queens problem

​

​

​

​

​

​

​

​

• Only 5 steps from h = 17 to h = 1

Hill-climbing search

• Problem: depending on initial state, can get stuck in local maxima.

Problems for hill climbing

​

​

​

​

​

​

​

​

• A local maxima with h = 1

Problems for hill climbing

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

​

30

Hill climbing search

• ☹ Starting from a randomly generated 8-queen state, steepest-ascent hill climbing gets stuck 86% of the time.

​

• ☺ It takes 4 steps on average when it succeeds and 3 when it gets stuck.

​

• The steepest ascent version halts if the best successor has the same value as the current.

​

​

​

Some solutions

• allow a sideways move
• ☺ shoulder
• ☹ flat local maximum, that is not a shoulder

Some solutions

• Solution: a limit on the number of consecutive sideway moves
• E.g., 100 consecutive sideways moves in the 8-queens problem
• ☺ successful rate: raises from14% to 94%
• ☹ cost: 21 steps on average for each successful instance, 64 for each failure

​

Some more solutions�(Variants of hill climbing )

• Stochastic hill climbing
• chooses at random from among the uphill moves
• converge more slowly, but finds better solutions
• First-choice hill climbing
• generates successors randomly until one is better than the current state
• good when with many (thousands) of successors

Some more solutions�(Variants of hill climbing )

• Random-restart hill climbing
• “If you don’t succeed, try, try again.”
• Keep restarting from randomly generated initial states, stopping when goal is found

​

Simulated Annealing

• Escape local maxima by allowing “bad” moves.
• Idea: but gradually decrease their size and frequency.
• Origin; metallurgical annealing
• One can prove: If T decreases slowly enough, then best state is reached with probability approaching 1.
• Applied for VLSI layout, airline scheduling, etc.

Simulated Annealing

• A hill-climbing algorithm that never makes “downhill” moves is guaranteed to be incomplete.
• Idea: escape local maxima by allowing some “bad” moves

​

Simulated Annealing

• Picks a random move (instead of the best)
• If “good move”
• accepted;
• else
• accepted with some probability

​

• The probability decreases exponentially with the “badness” of the move
• It also decreases as temperature “T” goes down

Simulated Annealing

• Simulated annealing was first used extensively to solve VLSI (Very-Large-Scale Integration) layout problems.
• It has been applied widely to factory scheduling and other large-scale optimization tasks.

Local Beam Search

• Keep track of k states rather than just one
• Start with k randomly generated states
• At each iteration, all the successors of all k states are generated
• If any one is a goal state, stop; else select the k best successors from the complete list and repeat.

Local Beam Search

• Idea: keep k states instead of 1; choose top k of all their successors
• Not the same as k searches run in parallel!
• Searches that find good states recruit other searches to join them
• moves the resources to where the most progress is being made

Local Beam Search

• Problem: quite often, all k states end up on same local hill (concentrated in a small region)
• Idea: choose k successors randomly (stochastic beam search)

Simulated Annealing Search

function SIMULATED-ANNEALING( problem, schedule) return a solution state

input: problem, a problem

schedule, a mapping from time to temperature

local variables: current, a node.

next, a node.

T, a “temperature” controlling the probability of downward steps

current ← MAKE-NODE(INITIAL-STATE[problem])

for t ← 1 to ∞ do

T ← schedule[t]

if T = 0 then return current

next ← a randomly selected successor of current

∆E ← VALUE[next] - VALUE[current]

if ∆E > 0 then current ← next

else current ← next only with probability e^{∆E /T}

Genetic Algorithms

• A successor state is generated by combining two parent states
• Start with k randomly generated states (population)
• A state is represented as a string over a finite alphabet (often a string of 0s and 1s)
• Evaluation function (fitness function). Higher values for better states.
• Produce the next generation of states by selection, crossover, and mutation

Genetic Algorithms

​

​

​

​

​

• Fitness function: number of non-attacking pairs of queens (min = 0, max = 8 × 7/2 = 28)
• 24/(24+23+20+11) = 31%
• 23/(24+23+20+11) = 29% etc

Genetic Algorithms