Lecture 4:
Advanced Search
CSSE 5600/6600: Artificial Intelligence
Instructor: Bo Liu
slide 1
Informed Search
Lecturer: Ji Liu
Thanks for Jerry Zhu's slides
[Based on slides from Andrew Moore http://www.cs.cmu.edu/~awm/tutorials ]
slide 1
Informed Search
Lecturer: Ji Liu
Thanks for Jerry Zhu's slides
[Based on slides from Andrew Moore http://www.cs.cmu.edu/~awm/tutorials ]
Content
• Optimization Problem Setting
• Hill Climbing
• Neighborhood
• Local Optima
• Improvement
• Simulated Annealing
slide 2
Optimization problems
• Previously we want a path from start to goal
 Uninformed search: g(s): Iterative Deepening
 Informed search: g(s)+h(s): A*
• Now a different setting:
 Each state s has a score f(s) that we can compute
 The goal is to find the state with the highest score, or
a reasonably high score
 Do not care about the path
 This is an optimization problem
 Enumerating the states is intractable
 Even previous search algorithms are too expensive
slide 3
Examples
• N-queen: f(s) = number of conflicting queens
in state s
Note we want s with the lowest score f(s)=0. The techniques
are the same. Low or high should be obvious from context.
slide 4
Examples
• N-queen: f(s) = number of conflicting queens
in state s
• Traveling salesperson problem (TSP)
 Visit each city once, return to first city
 State = order of cities, f(s) = total mileage
Note we want s with the lowest score f(s)=0. The techniques
are the same. Low or high should be obvious from context.
slide 5
Examples
• N-queen: f(s) = number of conflicting queens
in state s
• Traveling salesperson problem (TSP)
 Visit each city once, return to first city
 State = order of cities, f(s) = total mileage
• Boolean satisfiability (e.g., 3-SAT)
 State = assignment to variables
 f(s) = # satisfied clauses
Note we want s with the lowest score f(s)=0. The techniques
are the same. Low or high should be obvious from context.
A ∨ ¬B ∨ C
¬A ∨ C ∨ D
B ∨ D ∨ ¬E
¬C ∨ ¬ D ∨ ¬ E
¬A ∨ ¬ C ∨ E
Content
• Optimization Problem Setting
• Hill Climbing
• Neighborhood
• Local Optima
• Improvement
• Simulated Annealing
slide 6
1. HILL CLIMBING
slide 7
Hill climbing
• Very simple idea: Start from some state s,
 Move to a neighbor t with better score. Repeat.
• Question: what’s a neighbor?
 You have to define that!
 The neighborhood of a state is the set of neighbors
 Also called ‘move set’
 Similar to successor function
slide 8
Neighbors: N-queen
• Example: N-queen (one queen per column). One
possibility:
…
s
f(s)=1
Neighborhood
of s
slide 9
Neighbors: N-queen
• Example: N-queen (one queen per column). One
possibility:
 Pick the right-most most-conflicting column;
 Move the queen in that column vertically to a
different location.
…
s
f(s)=1
Neighborhood
of s
f=1
f=2
tie breaking more promising?
slide 10
Neighbors: TSP
• state: A-B-C-D-E-F-G-H-A
• f = length of tour
slide 11
Neighbors: TSP
• state: A-B-C-D-E-F-G-H-A
• f = length of tour
• One possibility: 2-change
A-B-C-D-E-F-G-H-A
A-E-D-C-B-F-G-H-A
flip
slide 12
Neighbors: SAT
• State: (A=T, B=F, C=T, D=T, E=T)
• f = number of satisfied clauses
• Neighbor:
A ∨ ¬B ∨ C
¬A ∨ C ∨ D
B ∨ D ∨ ¬E
¬C ∨ ¬ D ∨ ¬ E
¬A ∨ ¬ C ∨ E
slide 13
Neighbors: SAT
• State: (A=T, B=F, C=T, D=T, E=T)
• f = number of satisfied clauses
• Neighbor: flip the assignment of one variable
A ∨ ¬B ∨ C
¬A ∨ C ∨ D
B ∨ D ∨ ¬E
¬C ∨ ¬ D ∨ ¬ E
¬A ∨ ¬ C ∨ E
(A=F, B=F, C=T, D=T, E=T)
(A=T, B=T, C=T, D=T, E=T)
(A=T, B=F, C=F, D=T, E=T)
(A=T, B=F, C=T, D=F, E=T)
(A=T, B=F, C=T, D=T, E=F)
slide 14
Hill climbing
• Question: What’s a neighbor?
 (vaguely) Problems tend to have structures. A small
change produces a neighboring state.
 The neighborhood must be small enough for
efficiency
 Designing the neighborhood is critical. This is the
real ingenuity – not the decision to use hill climbing.
• Question: Pick which neighbor?
• Question: What if no neighbor is better than the
current state?
slide 15
Hill climbing
• Question: What’s a neighbor?
 (vaguely) Problems tend to have structures. A small
change produces a neighboring state.
 The neighborhood must be small enough for
efficiency
 Designing the neighborhood is critical. This is the
real ingenuity – not the decision to use hill climbing.
• Question: Pick which neighbor? The best one (greedy)
• Question: What if no neighbor is better than the
current state? Stop. (Doh!)
slide 16
Hill climbing algorithm
1. Pick initial state s
2. Pick t in neighbors(s) with the largest f(t)
3. IF f(t) ≤ f(s) THEN stop, return s
4. s = t. GOTO 2.
• Not the most sophisticated algorithm in the world.
• Very greedy.
• Easily stuck.
slide 17
Hill climbing algorithm
1. Pick initial state s
2. Pick t in neighbors(s) with the largest f(t)
3. IF f(t) ≤ f(s) THEN stop, return s
4. s = t. GOTO 2.
• Not the most sophisticated algorithm in the world.
• Very greedy.
• Easily stuck.
your enemy:
local
optima
slide 18
Local optima in hill climbing
• Useful conceptual picture: f surface = ‘hills’ in state
space
• But we can’t see the landscape all at once. Only see
the neighborhood. Climb in fog.
state
f
Global optimum,
where we want to be
state
f
fog
slide 19
Local optima in hill climbing
• Local optima (there can be many!)
• Plateaux
Declare top-
of-the-world?
state
f
state
f
Where shall I go?
slide 20
Local optima in hill climbing
• Local optima (there can be many!)
• Plateaus
fog
Declare top of
the world?
state
f
state
f
fog
Where shall I go?
The rest of the lecture is
about
Escaping
local optima
slide 21
Not every local minimum should be escaped
slide 22
Variation 1: hill climbing with random
restarts
• Very simple modification
1. When stuck, pick a random new start, run basic
hill climbing from there.
2. Repeat this k times.
3. Return the best of the k local optima.
• Can be very effective
• Should be tried whenever hill climbing is used
slide 23
Variations 2 and 3 of hill climbing
• Question: How do we make hill climbing less greedy?
 Stochastic hill climbing
• Randomly select among better neighbors
• The better, the more likely
• Pros / cons compared with basic hill climbing?
slide 24
Variations 2 and 3 of hill climbing
• Question: How do we make hill climbing less greedy?
 Stochastic hill climbing
• Randomly select among better neighbors
• The better, the more likely
• Pros / cons compared with basic hill climbing?
• Question: What if the neighborhood is too large to
enumerate? (e.g. N-queen if we need to pick both the
column and the move within it)
slide 25
Variations 2 and 3 of hill climbing
• Question: How do we make hill climbing less greedy?
 Stochastic hill climbing
• Randomly select among better neighbors
• The better, the more likely
• Pros / cons compared with basic hill climbing?
• Question: What if the neighborhood is too large to
enumerate? (e.g. N-queen if we need to pick both the
column and the move within it)
 First-choice hill climbing
• Randomly generate neighbors, one at a time
• If better, take the move
• Pros / cons compared with basic hill climbing?
Algorithms
1. Pick initial state s
2. Compute subset S of all the states with a better score.
3. Randomly pick t from S.
4. GOTO 2 until bored.
V2:Stochastic HC
V3:First-choice HC
1. Pick initial state s
2. Randomly pick t in neighbors(s) #RANDOMLY PICK ONE
3. IF f(t) better THEN accept.
4. GOTO 2 until bored.
Background: Mean of Geometric distribution. Mean = 1/p
QUESTIONS:
1 Equal prob. among better states?
2 Which is more efficient?
slide 26
Variation 4 of hill climbing
• We are still greedy! Only willing to move upwards.
• Important observation in life:
Sometimes one
needs to
temporarily step
back in order to
move forward.
Sometimes one
needs to move to an
inferior neighbor in
order to escape a
local optimum.
=
slide 27
Variation 4 of hill climbing
• Consider 3 neighbors
• If any improves f, accept the best
• If none improves f:
 50% of the time pick the least bad neighbor
 50% of the time pick a random neighbor
A ∨ ¬B ∨ C
¬A ∨ C ∨ D
B ∨ D ∨ ¬E
¬C ∨ ¬ D ∨ ¬ E
¬A ∨ ¬ C ∨ E
WALKSAT [Selman]
This is the best known algorithm for
satisfying Boolean formulae.
Content
• Optimization Problem Setting
• Hill Climbing
• Neighborhood
• Local Optima
• Improvement
• Simulated Annealing
slide 28
2. SIMULATED ANNEALING
slide 29
Simulated Annealing
anneal
• To subject (glass or metal) to a process of heating
and slow cooling in order to toughen and reduce
brittleness.
slide 30
Simulated Annealing
1. Pick initial state s
2. Randomly pick t in neighbors(s)
3. IF f(t) better THEN accept st.
4. ELSE /* t is worse than s */
5. accept st with a small probability
6. GOTO 2 until bored.
slide 31
Simulated Annealing
1. Pick initial state s
2. Randomly pick t in neighbors(s)
3. IF f(t) better THEN accept st.
4. ELSE /* t is worse than s */
5. accept st with a small probability
6. GOTO 2 until bored.
How to choose the small probability?
idea 1: p = 0.1
Near-sighted rabbit climbing hills
Near-sighted rabbit climbing hills:
ØSober
ØSlightly drunk:
1. always slighted drunk
2. becoming gradually sober
3. following a probability distribution
slide 31
Simulated Annealing
1. Pick initial state s
2. Randomly pick t in neighbors(s)
3. IF f(t) better THEN accept st.
4. ELSE /* t is worse than s */
5. accept st with a small probability
6. GOTO 2 until bored.
How to choose the small probability?
idea 1: p = 0.1
slide 32
Simulated Annealing
1. Pick initial state s
2. Randomly pick t in neighbors(s)
3. IF f(t) better THEN accept st.
4. ELSE /* t is worse than s */
5. accept st with a small probability
6. GOTO 2 until bored.
How to choose the small probability?
idea 1: p = 0.1
idea 2: p decreases with time
slide 33
Simulated Annealing
1. Pick initial state s
2. Randomly pick t in neighbors(s)
3. IF f(t) better THEN accept st.
4. ELSE /* t is worse than s */
5. accept st with a small probability
6. GOTO 2 until bored.
How to choose the small probability?
idea 1: p = 0.1
idea 2: p decreases with time
idea 3: p decreases with time, also as the ‘badness’
|f(s)-f(t)| increases
slide 34
Simulated Annealing
• If f(t) better than f(s), always accept t
• Otherwise, accept t with probability
Boltzmann
distributionexp(−|f ( s )−f (t )|Temp )
2

slide 35
Simulated Annealing
• If f(t) better than f(s), always accept t
• Otherwise, accept t with probability
• Temp is a temperature parameter that ‘cools’
(anneals) over time, e.g. TempTemp*0.9 which
gives Temp=(T0)
#iteration
 High temperature: almost always accept any t
 Low temperature: first-choice hill climbing
• If the ‘badness’ (formally known as energy difference)
|f(s)-f(t)| is large, the probability is small.
Boltzmann
distributionexp(−|f ( s )−f (t )|Temp )
2
slide 37
Simulated Annealing issues
• Cooling scheme important
• Neighborhood design is the real ingenuity, not the
decision to use simulated annealing.
• Not much to say theoretically
 With infinitely slow cooling rate, finds global
optimum with probability 1.
• Proposed by Metropolis in 1953 based on the
analogy that alloys manage to find a near global
minimum energy state, when annealed slowly.
• Easy to implement.
• Try hill-climbing with random restarts first!
Nicholas Metropolis
• An incompletely list of contributions:
• 1946: The Metropolis Algorithm for Monte Carlo.
• 1953: The Simulated Annealing method.
• 1950s: Led a group of researchers, including John von Neumann and Stanislaw Ulam,
developed the Monte Carlo method.
GOAT Algorithms
Take-home:
Near-sighted rabbit climbing hills:
ØSober
ØSlightly drunk:
1. always slighted drunk
2. becoming gradually sober
3. following a probability distribution
slide 38
GENETIC ALGORITHM
http://www.genetic-programming.org/






























































































































































































































































































































































































































































学霸联盟