4-Local search Artificial Intelligent Presentation

Artificial Intelligent Presentation

1. Localsearchalgorithms Local

search

algorithms
•In man
y
o
p
timization
p
roblems
,
the state s
p
ace is the
yp p ,
p
space of all possible completesolutions
• We have an objective function that tells us how “good”
i tti d ttfidth lti ( l)
a g
iven s
t
a
t
e
is, an
d
we wan
t

t
o
fi
n
d

th
e so
lu
ti
on
(
goa
l)

by minimizing or maximizing the value of this function

2. Example:
n
-
queensproblem
Example:

n
queens

problem
•Put n
q
ueens on an n ×nboard with no two
q
ueens on
q
q
the same row, column, or diagonal
•State space: all possible n-queen configurations
• What’s the objective function?
– Number of pairwise conflicts

3. Example: Traveling salesman
problem
• Find the shortest tour connectin
g
a
g
iven set of cities
gg
•State space: all possible tours
•Objective function: length of tour

4. Localsearchalgorithms Local

search

algorithms
•In man
y
o
p
timization
p
roblems
,
the state s
p
ace is the
yp p , p
space of all possible completesolutions
• We have an objective function that tells us how “good” a
i tti d ttfidth lti ( l)b
g
iven s
t
a
t
e
is, an
d
we wan
t

t
o
fi
n
d

th
e so
lu
ti
on
(
goa
l)

b
y
minimizing or maximizing the value of this function
•
Thestartstatemaynotbespecified The

start

state

may

not

be

specified
• The path to the goal doesn’t matter • In such cases, we can use local search algorithms that
keep a single “current” state and gradually try to improve it

5. Example:
n
-
queensproblem
Example:

n
queens

problem
•Put n
q
ueens on an n ×nboard with no two
q
ueens on
q
q
the same row, column, or diagonal
•State space: all possible n-queen configurations
•Objective function:number of pairwiseconflicts
• What’s a possible local improvement strategy?
Move one queen within its column to reduce conflicts
–
Move

one

queen

within

its

column

to

reduce

conflicts

6. Example:
n
-
queensproblem
Example:

n
queens

problem
•Put n
q
ueens on an n ×nboard with no two
q
ueens on
q
q
the same row, column, or diagonal
•State space: all possible n-queen configurations
•Objective function:number of pairwiseconflicts
• What’s a possible local improvement strategy?
Move one queen within its column to reduce conflicts
–
Move

one

queen

within

its

column

to

reduce

conflicts
h = 17

7. Example: Traveling Salesman
Problem
• Find the shortest tour connectin
g
n cities
g
•State space: all possible tours
•Objective function:length of tour
• What’s a possible local improvement strategy?
– Start with any complete tour, perform pairwise exchanges

8. Hill
-
climbingsearch
Hill
climbing

search
•
Initialize
current
tostartingstate
Initialize

current
to

starting

state
• Loop:
–
Let
next
=highest
-
valuedsuccessorof
current
Let

next
=

highest
-
valued

successor

of

current
–If value(next) < value(current) return current
Elselet
current
=
next
–
Else

let

current
=

next
•
Variants:choosefirstbettersuccessor randomly
•
Variants:

choose

first

better

successor
,
randomly

choose among better successors
•
“
LikeclimbingmountEverestinthickfogwith
•
Like

climbing

mount

Everest

in

thick

fog

with

amnesia”

9. Hill
-
climbingsearch
Hill
climbing

search
•
Isitcomplete/optimal? Is

it

complete/optimal?
– No –can get stuck in local optima –
Exam
p
le: local o
p
timum for the 8-
q
ueens
p
roblem
pp
qp
h = 1

10. The state space “landscape”
• How to escape local maxima?
– Random restart hill-climbing
• What about “shoulders”? • What about “plateaux”?

11. Simulated annealing search
• Idea: escape local maxima by allowing some
"
bad
"
movesbutgraduallydecreasetheir
bad

moves

but

gradually

decrease

their

frequency
–
Probabilityoftakingdownhillmovedecreaseswith Probability

of

taking

downhill

move

decreases

with

number of iterations, steepness of downhill move
– Controlled by annealing schedule
• Inspired by tempering of glass, metal

12. Simulated annealing search
• Initializecurrentto starting state •
For
i
=1to
∞
•
For

i
=

1

to

∞
– If T(i) = 0 return current –
Let
next
=
randomsuccessorof
current
Let

next

random

successor

of

current
– Let Δ= value(next) –value(current)
– If Δ> 0 then let current= next
– Else let current= nextwith probability exp(Δ/T(i))

13. Effectoftemperature Effect

of

temperature
exp(Δ/T)
ΔΔ

14. Simulated annealing search
• One can prove: If temperature decreases slowly
h th i l t d li h illfi d
enoug
h
,
th
en s
imu
la
t
e
d
annea
li
ng searc
h
w
ill

fi
n
d

a global optimum with probability approaching one
H
•
H
owever:
– This usually takes impractically long
Themoredownhillstepsyouneedtoescapealocal
–
The

more

downhill

steps

you

need

to

escape

a

local

optimum, the less likely you are to make all of them in a
row
• More modern techniques: general family of
Markov Chain Monte Carlo(MCMC) algorithms
fli litdtt f
or exp
lor
ing comp
li
ca
t
e
d
s
t
a
t
e spaces

15. Local beam search
• Start with krandomly generated states
•
A
t each iteration, all the successors of all
k
states are
generated
• If any one is a goal state, stop; else select the kbest
successorsfromthecompletelistand
repeat
successors

from

the

complete

list

and

repeat
• Is this the same as running kgreedy searches in
ll l?
para
ll
e
l?
Greedy search Beam search