Microsoft PowerPoint – ai3b.pptx
COMP3308/COMP3608, Lecture 3b
ARTIFICIAL INTELLIGENCE
Local Search Algorithms
Reference: Russell and Norvig, ch. 4
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018 1
2
Outline
• Optimisation problems
• Local search algorithms
• Hill-climbing
• Beam search
• Simulated annealing
• Genetic algorithms
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018 3
Optimisation Problems
• Problem setting so far: path finding
• Goal: find a path from S to G
• Solution: the path
• Optimal solution: least cost path
• Search algorithms:
• Uninformed: BFS, UCS, DFS, IDS
• Informed: greedy, A*
• Now a new problem setting: optimisation problem
• Each state has a value v
• Goal: find the optimal state
• = the state with the highest or lowest v score (depending on what is
desirable, maximum or minimum)
• Solution: the state; the path is not important
• A large number of states => can’t be enumerated
• => We can’t apply the previous algorithms – too expensive
4
Optimisation Problems – Example
• n-queens problem
• The solution is the goal configuration, not the path to it
• Non-incremental formulation
• Initial state: n-queens on the board (given or randomly chosen)
• States: any configuration with n-queens on the board
• Goal: no queen is attacking each other
• Operators: “move a queen” or “move a queen to reduce the
number of attacks”
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
5
V-value Landscape
• Each state has a value v that we can compute
• This value is defined by a heuristic evaluation function (also called objective
function)
• Goal – 2 variations depending on the task:
• find the state with the highest value (global maximum) or
• find the state with the lowest value (global minimum)
• Complete local search – finds a goal state if one exists
• Optimal local search – finds the best goal state – the state associated with
the global maximum/minimum
v
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
6
Hill-Climbing Algorithm – Idea
• Also called iterative improvement algorithm
• Idea: Keep only a single state in memory, try to improve it
• Two variations:
• Steepest ascent – the goal is the maximum value
• Steepest descent – the goal is the minimum value
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
7
Hill-climbing Search
• Assume that we are looking for a maximum value (i.e. hill-climbing ascend)
• Idea: move around trying to find the highest peak
• Store only the current state
• Do not look ahead beyond the immediate neighbors of the current state
• If a neighboring state is better, move to it & continue, otherwise stop
• “Like climbing Everest in thick fog with amnesia”
v v
fog fog
we can’t see the whole landscape,
only the neighboring states
keeps only 1 state in memory, no
backtracking to previous states
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
8
Hill-climbing Algorithm
Hill-climbing descent
1) Set current node n to the initial state s
(The initial state can be given or can be randomly selected)
2) Generate the successors of n. Select the best successor nbest ; it is the
successor with the best v score, v(best) (i.e. the lowest score for descent)
3) If v(best) > v(n), return n //compare the child with the parent; if child not
//better – stop; local or global minimum found
Else set n to nbest . Go to step 2 //if better – accept the child and keep
// searching
• Summary: Always expands the best successor, no backtracking
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
9
Hill-climbing – Example 1
• v – value is in brackets; the lower, the better (i.e. descent)
• Expanded nodes: SAF
S (7)
A(4) B(5) C(8)
D(3) E(7) F(2) H(1)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
10
Hill-climbing – Example 2
• Given: 3×3 grid, each cell is colored either red (R) or blue (B)
• Aim: find the coloring with minimum number of pairs of
adjacent cells with the same color
• Ascending or descending? v – # pairs of adjacent
cells with the same color
Picture from N. Nielsen, AI, 1998
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
11
Hill-climbing Search
v
fog fog
Solution (global
maximum)
v
fog fog
Solution (local
maximum)
Weaknesses:
• Not a very clever algorithm – can
easily get stuck in a local optimum
(maximum/minimum)
• However, not all local maxima/minima
are bad – some may be reasonably
good even though not optimal
Advantages: good choice for hard,
practical problems
• Uses very little memory
• Finds reasonable solutions in large
spaces where systematic algorithms
are not useful
Not complete, not optimal but keeps just one node in memory!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
12
Hill-climbing – Escaping Bad Local Optima
• Hill climbing finds the closest local optimum (minimum or
maximum, depending on the version – descent or ascent)
• Which may or may not be the global optimum
• The solution that is found depends on the initial state
• When the solution found is not good enough – random restart:
• run the algorithm several times starting from different points; select
the best solution found (i.e. the best local optimum)
• If at first you don’t succeed, try, try again!
• This is applicable for tasks without a fixed initial state
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
13
Hill-climbing – Escaping Bad Local Optima (2)
• Plateaus (flat areas): no change or very small change in v
• Our version of hill-climbing does not allow visiting states with the
same v as it terminates if the best child’s v is the same as the
parent’s
• But other versions keep searching if the values are the same and this
may result in visiting the same state more than once and walking
endlessly
v• Solution: keep track
of the number of
times v is the same
and do not allow
revisiting of nodes
with the same v
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
• Ridges – the current local maximum is not good enough; we
would like to move up but all moves go down
• Example:
• Possible solutions: combine 2 or more moves in a macro
move that can increase the height or allow a limited
number of look-ahead search
14
Hill-climbing – Escaping Bad Local Optima (3)
– Dark circles = states
– A sequence of local maxima that are
not connected with each other
– – From each of them all available
actions point downhill.
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
• It keeps track of k states rather than just 1
15
Beam Search
• Version 1: Starts with 1
given state
• At each level: generate all
successors of the given state
• If any one is a goal state,
stop; else select the k best
successors from the list and
go to the next level
• Version 2: Starts with k
randomly generated states
• At each level: generate all
successors of all k states
• If any one is a goal state,
stop; else select the k best
successors from the list
and go to the next level
• In nutshell: keeps only k best states
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
16
Beam Search – Example
• Consider the version that starts with 1 given state
• Starting from S, run beam search with k=2 using the values in
brackets as evaluation function (the smaller, the better)
• Expanded nodes = ?
S(7)
A(4) B(5) C(8)
D(3) E(7) F(2) H(1)
– S
– generate ABC
– select AB (the best 2 children)
– generate DEFH
– select FH (the best 2 children)
– expanded nodes: SABFH
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
17
Beam Search and Hill-Climbing Search
• Compare beam search with 1 initial state and hill climbing
with 1 initial state
• Beam – 1 start node, at each step keeps k best nodes
• Hill climbing – 1 start node, at each step keeps 1 best node
• Compare beam search with k random initial states and
hill-climbing with k random initial states
• Beam – k starting positions, k threads run in parallel,
passing of useful information among them as at each step
the best k children are selected
• Hill climbing – k starting positions, k threads run
individually, no passing of information among them
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
18
Beam Search with A*
• Recall that memory was a big problem for A*
• Idea: keep only the best k nodes in the fringe, i.e. use a
priority queue of size k
• Advantage: memory efficient
• Disadvantage: neither complete, nor optimal
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
19
Simulated Annealing
• What is annealing in metallurgy?
• a material’s temperature is gradually decreased (very slowly) allowing its
crystal structure to reach a minimum energy state
• Similar to hill-climbing but selects a random successor instead
of the best successor (step 2 below)
1) Set current node n to the initial state s.
Randomly select m, one of n’s successors
2) If v(m) is better than v(n), n=m //accept the child m
Else n=m with a probability p //accept the child m with probability p
3) Go to step 2 until a predefined number of iterations is reached or the
state reached (i.e. the solution found) is good enough
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
20
The Probability p
• Assume that we are looking for a minimum
• There are different ways to define p, e.g
• Main ideas:
• 1) p decreases exponentially with the badness of the child (move) and
• 2) bad children (moves) are more likely to be allowed at the beginning
than at the end
• nominator – shows how good the child m is
• Bad move (the child is worse than the parent): v(n)
the move
T
mvnv
ep
)()(
child m
parent n
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
• denominator: parameter T that decreases (anneals) over time based
on a schedule, e.g. T=T*0.8
• high T – bad moves are more likely to be allowed
• low T – more unlikely; becomes more like hill-climbing
• T decreases with time and depends on the number of iterations
completed, i.e. until “bored”
• Some versions have an additional step (Metropolis criterion for
accepting the child):
• p is compared with p’, a randomly generated number [0,1]
• If p > p’, accept the child, otherwise reject it
• In summary, simulated annealing combines a hill-climbing step
(accepting the best child) with a random walk step (accepting bad
children with some probability). The random walk step can help
escape bad local minima.
21
The Probability p (2) T
mvnv
ep
)()(
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
22
Simulated Annealing – Theorem
• What is the correspondence?
• v – total energy of the atoms in the material
• T – temperature
• schedule – the rate at which T is lowered
• Theorem: If the schedule lowers T slowly enough, the algorithm will
find global optimum
• i.e. is complete and optimal given a long enough cooling
schedule => annealing schedule is very important
• Simulated annealing has been widely used to solve VLSI layout
problems, factory scheduling and other large-scale optimizations
• It is easy to implement but a “slow enough” schedule may be
difficult to set
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
23
Genetic Algorithms
• Inspired by mechanisms used in evolutionary biology, e.g.
selection, crossover, mutation
• Similar to beam search, in fact a variant of stochastic beam search
• Each state is called an individual. It is coded as a string.
• Each state n has a fitness score f(n) (evaluation function). The
higher the value, the better the state.
• Goal: starting with k randomly generated individuals, find the
optimal state
• Successors are produced by selection, crossover and mutation
• At any time keep a fixed number of states (the population)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
24
Example – 8-queens Problem
1 2 3 4 5 6 7 8 columns
One possible encoding is (3 2 7 5 2 4 1 1)
8
7
6
5
4
3
2
1
position
column 1: a queen
at position 3
column 2: a queen
at position 2
…
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
25
Example – 8-queens Problem (2)
• Suppose that we are given 4 individuals (initial population)
with their fitness values
• Fitness values = number of non-attacking pairs of queens (given 8 queens,
how many different pairs of queens are there? 28 => max value is 28)
• Let the probability for reproduction is proportional to the fitness
(expressed is %)
24 31%
23 29%
20 26%
11 14%
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
26
Example – 8-queens Problem (3)
• Select 4 individuals for reproduction based on the fitness
function
• The higher the fitness function, the higher the probability to be selected
• Let individuals 2, 1, 2 and 3 be selected, i.e. individual 2 is selected twice
while 4 is not selected
• Crossover – random selection of crossover point; crossing over the
parents strings
• Mutation – random change of bits (in this case 1 bit was changed in
each individual)
1
2
3
4
2
1
2
3
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
(3 2 7 5 2 4 1 1) + ( 2 4 7 4 8 5 5 2) = (3 2 7 4 8 5 5 2)
• When the 2 states are different, crossover produces a state
which is a long way from either parents
• Given that the population is diverse at the beginning of the
search, crossover takes big steps in the state space early in the
process and smaller later, when more individuals are similar
27
A Closer Look at the Crossover
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
28
Genetic Algorithm – Pseudo Code (1 variant)
from http://pages.cs.wisc.edu/~jerryzhu/cs540.html
until some individual is fit enough or max number of
iterations have been reached
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
29
Genetic Algorithms – Discussion
• Combine:
• uphill tendency (based on the fitness function)
• random exploration (based on crossover and mutation)
• Exchange information among parallel threads – the
population consists of several individuals
• The main advantage comes from crossover
• Success depends on the representation (encoding)
• Easy to implement
• Not complete, not optimal
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018
30
Acknowledgement
http://pages.cs.wisc.edu/~jerryzhu/cs540.html
Links
Simulated annealing as a training algorithm for backpropagation
neural networks:
• R.S. Sexton, R.E. Dorsey, J.D. Johnson, Beyond backpropagation:
using simulated annealing for training neural networks,
people.missouristate.edu/randallsexton/sabp.pdf
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2018