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, 2021
1
• Optimisation problems
• Local search algorithms
• Hill-climbing
• Beam search
• Simulatedannealing • Geneticalgorithms
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3b, 2021
2
Outline
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
• =thestatewiththehighestorlowestvscore(dependingonwhatis 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
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2021 3
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, 2021
4
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, 2021
5
• •
•
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
Hill-Climbing Algorithm – Idea
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2021
6
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 and continue, otherwise stop
“Like climbing Everest in thick fog with amnesia”
we can’t see the whole landscape, only the neighboring states
vv
keeps only 1 state in memory, no backtracking to previous states
fog
fog
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2021
7
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, 2021
8
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, 2021
9
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?
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3b, 2021
10
v – # pairs of adjacent cells with the same color
Picture from N. Nielsen, AI, 1998
Hill-climbing Search
Solution (global maximum)
fog
v
fog
Solution (local maximum)
fog
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
v
fog
Not complete, not optimal but keeps just one node in memory!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2021
11
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, 2021
12
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
• Solution: keep track of the number of
times v is the same and do not allow revisiting of nodes with the same v
v
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3b, 2021
13
Hill-climbing – Escaping Bad Local Optima (3)
• Ridges – the current local maximum is not good enough; we would like to move up but all moves go down
• Example:
•
– Dark circles = states
– A sequence of local maxima that are
not connected with each other
– – From each of them all available
actions point downhill.
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
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2021
14
•
• • •
Beam Search
It keeps track of k states rather than just 1
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, 2021
15
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 = ?
A(4)
S(7)
B(5) C(8)
-S
– generate ABC
– select AB (the best 2 children) – generate DEFH
– select FH (the best 2 children) – expanded nodes: SABFH
D(3) E(7)
F(2)
H(1)
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 3b, 2021
16
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, 2021
17
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, 2021
18
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, 2021 19
The Probability p
• Assume that we are looking for a minimum
• There are different ways to define p, e.g.
• Main ideas:
parent n child m
• 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)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2021
20
p=e
v(n)−v(m) T
The Probability p (2)
• 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.
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2021
21
p=e
v(n)−v(m) T
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, 2021
22
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, 2021
23
Example – 8-queens Problem
8 7 6 5 4 3 2 1
One possible encoding is (3 2 7 5 2 4 1 1)
1 2 3 4 5 6 7 8 columns 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, 2021
24
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, 2021
25
•
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, 2021
26
A Closer Look at the Crossover
(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
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2021
27
Genetic Algorithm – Pseudo Code (1 variant)
from http://pages.cs.wisc.edu/~jerryzhu/cs540.html
until some individual is fit enough or a predefined
maximum number of iterations has been reached
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 3b, 2021
28
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, 2021
29
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, 2021
30