CS 2710, ISSP 2610: R&N Chapter 4.1 Local Search and Optimization

CS 2710, ISSP 2610
R&N Chapter 4.1

Local Search and Optimization
1
Search Types
– Backtracking state-space search

– Local Search and Optimization
– Constraint satisfaction search
– Adversarial search
2
Local Search and Optimization
• Previous searches: keep paths in memory, and remember
alternatives so search can backtrack. Solution is a path to a
goal.
• Path may be irrelevant, if only the final configuration is
needed (8-queens, IC design, network optimization, …)
3
Local Search
• Use a single current state and move only to neighbors.

• Use little space
• Can find reasonable solutions in large or infinite (continuous)
state spaces for which the other algorithms are not suitable
4
Optimization
• Local search is often suitable for optimization problems.

Search for best state by optimizing an objective function.
• F(x) where often x is a vector of continuous or discrete
values
• Begin with a complete configuration
• A successor of state S is S with a single element changed
• Move from the current state to a successor state
• Low memory requirements, because the search tree or graph
is not maintained in memory (paths are not saved)
5
Examples
• 8 queens: find an arrangement of 8 queens on a chess board

such that no two queens are attacking each other
• Start with some arrangement of the queens, one per column
• X[j]: row of queen in column j
• Successors of a state: move one queen
• F: # pairs attacking each other
6
Examples
• Traveling salesman problem: visit each city exactly once

• Start with some ordering of the cities
• State representation – order of the cities visited (for eg)
• Successor state: a change to the current ordering
• F: length of the route
7
Examples
• Flight Travel problem

• See file on schedule. We will look at the details later, but
the general problem is for all members of the Glass family
to travel to the same place.
• A state consists of flights for each member of the family.
• Successor states: All schedules that have one person on the
next later or the next earlier departing or returning flight.
• F: sum of different types of costs ($$, time, etc)
8
Examples
• Cryptosystems: resistance to types of attacks is often

discussed in terms of Boolean functions used in them
• Much work on constructing Boolean functions with desired
cryptographic properties (balancedness, high nonlinearity,
etc.)
• One approach: local search, where states are represented
with truth tables (that’s a simplification); a successor
results from a change to the truth table; objective
functions have been devised to assess (estimate) relevant
qualities of the Boolean functions
9
Examples
• Racing yacht hull design

• Design representation has multiple components, including a
vector of B-Spline surfaces.
• Successors: modification of a B-Spline surface (e.g.).
• Objective function estimates the time the yacht would take
to traverse a course given certain wind conditions (e.g.)
10
Comparison to tree/graphsearch framework
• Chapter 3: start state is typically not a complete

configuration. Chapter 4: all states are
• Chapter 3: binary goal test; Chapter 4: no binary goal test,
unless one can define one in terms of the objective function
for the problem (e.g., no attacking pairs in 8-queens)
• h: estimate of the distance to the nearest goal
• objective function: preference/quality measure – how good
is this state?
• Chapter 3: saving paths
• Chapter 4: start with a complete configuration and make
modifications to improve it
11
Visualization
• States are laid out in a landscape

• Height corresponds to the objective function value
• Move around the landscape to find the highest (or lowest)
peak
• Only keep track of the current states and immediate
neighbors
12
Local Search Alogorithms
• Two strategies for choosing the state to visit next

– Hill climbing
– Simulated annealing
• Then, an extension to multiple current states:
– Genetic algorithms
13
Hillclimbing
(Greedy Local Search)
• Generate nearby successor states to the current state
• Pick the best and replace the current state with that one.
• Loop
14
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
Local maximum Plateau Ridge

15
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
16
Simulated Annealing
• Based on a metallurgical metaphor

– Start with a temperature set very high and slowly reduce it.
– Run hillclimbing with the twist that you can occasionally replace
the current state with a worse state based on the current
temperature and how much worse the new state is.
17
Simulated Annealing
• Annealing: harden metals and glass by heating them to a

high temperature and then gradually cooling them
• At the start, make lots of moves and then gradually slow
down
18
Simulated Annealing
• More formally…
– Generate a random new neighbor from current state.
– If it’s better take it.
– If it’s worse then take it with some probability proportional to
the temperature and the delta between the new and old states.
19
Simulated annealing
• Probability of a move decreases with the amount ΔE by

which the evaluation is worsened
• A second parameter T is also used to determine the
probability: high T allows more worse moves, T close to zero
results in few or no bad moves
• Schedule input determines the value of T as a function of
the completed cycles
20
function Simulated-Annealing(start,schedule)
current ← start
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
21
Intuitions
• Hill-climbing is incomplete
• Pure random walk, keeping track of the best state found so
far, is complete but very inefficient
• Combine the ideas: add some randomness to hill-climbing to
allow the possibility of escape from a local optimum
22
Intuitions
• the algorithm wanders around during the early parts of the

search, hopefully toward a good general region of the state
space
• Toward the end, the algorithm does a more focused search,
making few bad moves
23
Theoretical Completeness
• There is a proof that if the schedule lowers T slowly enough,

simulated annealing will find a global optimum with
probability approaching 1
• In practice, that may be way too many iterations
• In practice, though, SA can be effective at finding good
solutions
24
Local Beam Search
• Keep track of k states rather than just one, as in hill

climbing
• In comparison to beam search we saw earlier, this algorithm
is state-based rather than node-based.
25
Local Beam Search
• Begins with k randomly generated states

• At each step, all successors of all k states are generated
• If any one is a goal, alg halts
• Otherwise, selects best k successors from the complete list,
and repeats
26
Local Beam Search
• Successors can become concentrated in a small

part of state space
• Stochastic beam search: choose k successors,
with probability of choosing a given successor
increasing with value
• Like natural selection: successors (offspring) of a
state (organism) populate the next generation
according to its value (fitness)
27
Genetic Algorithms
• Variant of stochastic beam search

• Combine two parent states to generate successors
28
function GA (pop, fitness-fn)
Repeat
new-pop = {}
for i from 1 to size(pop):
x = rand-sel(pop,fitness-fn)
y = rand-sel(pop,fitness-fn)
child = reproduce(x,y)
if (small rand prob): child mutate(child)
add child to new-pop
pop = new-pop
Until an indiv is fit enough, or out of time
Return best indiv in pop, according to fitness-fn
29
function reproduce(x,y)
n = len(x)
c = random num from 1 to n
return:
append(substr(x,1,c),substr(y,c+1,n)
30
Example: n-queens
• Put n queens on an n × n board with no two queens on the

same row, column, or diagonal
•
31
Genetic Algorithms
Notes
• Representation of individuals
– Classic approach: individual is a string over a finite
alphabet with each element in the string called a gene
– Usually binary instead of AGTC as in real DNA
• Selection strategy
– Random
– Selection probability proportional to fitness
– Selection is done with replacement to make a very fit
individual reproduce several times
• Reproduction
– Random pairing of selected individuals
– Random selection of cross-over points
– Each gene can be altered by a random mutation
32
Genetic Algorithms
When to use them?
• Genetic algorithms are easy to apply
• Results can be good on some problems, but bad on other
problems
• Genetic algorithms are not well understood
33
Example Local Search Problem Formulation
• Group travel: people traveling from different places: See

chapter4example.txt on the course schedule.
• From Segaran, T. Programming Collective Intelligence,
O’Reilly, 2007.
34
Wrapup
• The relevant part of the book is Chapter 4.1
35

CS 2710, ISSP 2610: R&N Chapter 4.1 Local Search and Optimization

Uploaded by

Copyright:

Available Formats

CS 2710, ISSP 2610: R&N Chapter 4.1 Local Search and Optimization

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CS 2710, ISSP 2610: R&N Chapter 4.1 Local Search and Optimization

Uploaded by

Copyright:

Available Formats

CS 2710, ISSP 2610

R&N Chapter 4.1

– Backtracking state-space search

• Use a single current state and move only to neighbors.

• Local search is often suitable for optimization problems.

• 8 queens: find an arrangement of 8 queens on a chess board

• Traveling salesman problem: visit each city exactly once

• Flight Travel problem

• Cryptosystems: resistance to types of attacks is often

• Racing yacht hull design

• Chapter 3: start state is typically not a complete

• States are laid out in a landscape

• Two strategies for choosing the state to visit next

• Local maximum: a peak that is lower than the highest peak,

Local maximum Plateau Ridge

• Start different hill-climbing searches from random starting

• Based on a metallurgical metaphor

• Annealing: harden metals and glass by heating them to a

• Probability of a move decreases with the amount ΔE by

• the algorithm wanders around during the early parts of the

• There is a proof that if the schedule lowers T slowly enough,

• Keep track of k states rather than just one, as in hill

• Begins with k randomly generated states

• Successors can become concentrated in a small

• Variant of stochastic beam search

• Put n queens on an n × n board with no two queens on the

• Group travel: people traveling from different places: See

• The relevant part of the book is Chapter 4.1

You might also like