程序代写代做代考 algorithm Microsoft PowerPoint – ai3b.pptx

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) p exponentially decreases with the badness of

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