6G6Z1109: So+ware Agents and
Op8misa8on
Term 2, Lecture 7:
Local Search
Local search
• For many problems, we can improve the
quality of gene8c search by somehow
embedding knowledge of the problem into the
algorithm
• Benefits:
– Reduces the probability of “illegal” solu8ons
– Simplifies the representa8on scheme
– Speeds up search/reduces size of solu8on space
An example
• Imagine we wish to pack
a collec8on of non-
overlapping circles with
specified radii into the
smallest possible
containing radius (i.e.,
the assignment)
• How might we represent
a solu8on to the
problem in a GA?
B
D
C
A
E F
One idea
• Represent a solu8on
as a set of x,y
coordinate pairs, one
for each circle’s centre
point
B
D
C
A
E
F
A B C D E F
x,y x,y x,y x,y x,y x,y
One idea
• Represent a solu8on
as a set of x,y
coordinate pairs, one
for each circle’s centre
point
B
D
C
A
E
F
A B C D E F
x,y x,y x,y x,y x,y x,y
Problems with this approach?
First problem
• For a (e.g.) 30×30 discrete
space, there are 30×30=90
possible loca8ons for each
circle
• 90x90x90x90 = 90n
possibili8es of placement
for n circles
• n=10,
90n=34,867,844,010,000,00
0,000
• Problem 1: size of search
space for even modest
probem instances
B
D
C
A
E
F
First problem
• For a (e.g.) 30×30 discrete
space, there are 30×30=90
possible loca8ons for each
circle
• 90x90x90x90 = 90n
possibili8es of placement
for n circles
• n=10,
90n=34,867,844,010,000,00
0,000
• Problem 1: size of search
space for even modest
probem instances
B
D
C
A
E
F
Next problem?
Second problem
• Nothing in this encoding
prevents circles from
overlapping
• Illegal solu8ons are
actually much (MUCH)
more likely than legal
ones, as legal solu8ons
require all circles to be
disjoint
• Problem 2: illegal
solu8ons are the norm
B
D
C
A
E
F
Second problem
• Nothing in this encoding
prevents circles from
overlapping
• Illegal solu8ons are
actually much (MUCH)
more likely than legal
ones, as legal solu8ons
require all circles to be
disjoint
• Problem 2: illegal
solu8ons are the norm
B
D
C
A
E
F
Which type of encoding would
address both of these problems?
Order-based encoding
• Recall that an order-
based encoding
specifies a sequence of
“things”/moves/etc
• We can use this type of
encoding to specify the
order in which circles
are placed
B
D
C
A
E
F
Order-based encoding: example
• If we assume that the
first circle is placed in
the centre of the space,
then an ordering
CDAEFB is shown to the
right
C
Order-based encoding: example
• If we assume that the
first circle is placed in
the centre of the space,
then an ordering
CDAEFB is shown to the
right
D
C
Order-based encoding: example
• If we assume that the
first circle is placed in
the centre of the space,
then an ordering
CDAEFB is shown to the
right
D
C
A
Order-based encoding: example
• If we assume that the
first circle is placed in
the centre of the space,
then an ordering
CDAEFB is shown to the
right
D
C
A
E
Order-based encoding: example
• If we assume that the
first circle is placed in
the centre of the space,
then an ordering
CDAEFB is shown to the
right
D
C
A
E
F
Order-based encoding: example
• If we assume that the
first circle is placed in
the centre of the space,
then an ordering
CDAEFB is shown to the
right B
D
C
A
E
F
Order-based encoding: benefits
• If we get the placement algorithm
right, then this encoding
automa9cally prevents illegal
solu8ons
• Number of possible solu8ons/
permuta8ons of n circles = n!
• 10!=3,628,800
• Significantly less than 9010
(9010=34,867,844,010,000,000,000)
• Placement ordering is independent
of size of 2D space in which circles
are placed (unlike direct placement
encoding)
B
D
C
A
E
F
Order-based encoding: benefits
• If we get the placement algorithm
right, then this encoding
automa9cally prevents illegal
solu8ons
• Number of possible solu8ons/
permuta8ons of n circles = n!
• 10!=3,628,800
• Significantly less than 9010
(9010=34,867,844,010,000,000,000)
• Placement ordering is independent
of size of 2D space in which circles
are placed (unlike direct placement
encoding)
B
D
C
A
E
F
This is our “local search”. For each circle in turn, we “search
locally” for the best place in which to put it…
Circle placement
• Assume a set of circles, with specified radii
• We place the first circle in the centre of the
space
• Where do we place the next circle?
A
A
B
A
The summed radii of
the circles defines a
“shell” of valid
placement
points for B….
B
A
B
A
B
x,y
Given a point x,y, a radius r, and an
angle, g, we can find the loca8on
of the point on the circle using:
px=x + cos(a) * r
py=y + sin(a) * r
NB: all angles must be in radians
NB: r must be equal to the radius
of a plus the radius of b
r
g
When adding a new circle, we start by calcula8ng the
set of “shells” that must exist for each exis9ng circle…
Green lines represent the set
of open points; that is, given
a circle to be added, open
points represent the
sum of all of the “shells”
minus the points on the
shells that would place the
new circle overlapping another
circle
Green lines represent the set
of open points; that is, given
a circle to be added, open
points represent the
sum of all of the “shells”
minus the points on the
shells that would place the
new circle overlapping another
circle
Green lines represent the set
of open points; that is, given
a circle to be added, open
points represent the
sum of all of the “shells”
minus the points on the
shells that would place the
new circle overlapping another
circle
Green lines represent the set
of open points; that is, given
a circle to be added, open
points represent the
sum of all of the “shells”
minus the points on the
shells that would place the
new circle overlapping another
circle
Green lines represent the set
of open points; that is, given
a circle to be added, open
points represent the
sum of all of the “shells”
minus the points on the
shells that would place the
new circle overlapping another
circle
How do we check to see if two circles overlap?
If the distance, d, between their centre points is
between the sum and the difference of their radii,
then they overlap
d
r1 r2
r1+r2
d
To place the circle, we simply
find the open point closest to
the centre of the space…
Code!
Create the “shell” of open points around
all other exis9ng circles, based on the radius
of the circle, c, currently being placed
Accepts an array of the circles, returns the list of
open points (only in order to draw them)
Find the open point closest to
the centre of the space (cx, cy)
Next lecture
• Next week: Compara8ve analysis of
algorithms, more help with the assignment
• This week’s lab: Start to implement
assignment solu8on!