程序代写代做代考 algorithm 6G6Z1109: So+ware Agents and

6G6Z1109: So+ware Agents and
Op8misa8on

Term 2, Lecture 6: GA for Travelling
Salesman Problem

Travelling Salesman Problem (TSP)

•  We might also refer to this (in gender-neutral
terms) as the “Delivery Driver Problem”

•  TSP is the commonly-accepted 8tle, so we will
go with that

•  Archetypal NP-complete/NP-hard problem
(depending on formula8on of ques8on)

•  Used as a test-bed for many different
op8misa8on algorithms

TSP formula8on

•  Given a set of ci#es
distributed in space, find
the shortest possible
route that visits all ci8es
only once and then
returns to the start point

•  That is, find a circular
tour of minimum length

Wikipedia

Why is the TSP interes8ng?

•  Apart from being inherently hard (and
therefore challenging), the TSP finds many
applica8ons in various domains such as
– Transporta8on (best way for a school bus to pick
up n children, best way to make deliveries to n
loca8ons)

– Circuit board drilling (minimise “travel 8me” for
drill head to make n holes in a board)

– Crew scheduling, adver8sement loop placement,
etc. etc.

TSP formula8on
•  Some variants of the TSP
include the edges
(corresponding to a set of
roads)

•  We focus on the Euclidean
TSP, which simply
distributes ci8es in 2D
space, and assumes that
there exists a direct
straight road between any
possible pair of ci8es)

Lee Jacobson

TSP hardness

•  Why is the TSP hard?
•  For n ci8es (n>=3), there
are (n-1)!/2 possible tours

•  So, for 20 ci8es, there are
(19*18*17*16…*1)/2
possible tours

•  60,822,550,204,416,000
for this par8cular instance Lee Jacobson

TSP hardness
•  Why (n-1)!/2 possible tours?
•  For n=20, if we start at arbitrary city, A,

we then have 19 to choose from…
•  Once we move to the next city, we then

have 18 to choose from, and so on….
(which gives us the factorial)

•  n-1, because we have one fewer choice
to make (as, by default, we have to
return to the start point)

•  We divide the number of tours by two,
because we don’t care about the
direc#on of the tour (that is, ACDBE is
considered iden8cal to EBDCA)

•  A tour is a permuta#on of ci8es (that is,
an ordering of ci8es)

Lee Jacobson

TSP encoding
•  Given that a tour is
simply an ordering
of ci8es, it seems
natural to use a
string of city labels
to represent a
solu8on

•  Each individual,
therefore, starts
with a shuffled
(randomised)
version of the city
list as its genome

TSP evalua8on

•  We then need to calculate the length of the
tour encoded by the list of ci8es

•  This gives us the fitness of the tour (where
lower (ie. shorter) values are considered
bejer)

•  So, for the sequence DBCAE, we would add
together distances D-B, B-C, A-E, then E back
to D

New class, Map, which is a
version of the Graph class

Takes string of city
labels as input

New class, Map, which is a
version of the Graph class

For each pair of city
labels (including “wrap
around to start”)….

New class, Map, which is a
version of the Graph class

Extract the appropriate
nodes from the ordered
list, calculate distance
between them, and add

to running total

New class, Map, which is a
version of the Graph class

Distance between two points

Added to Node class

Calculates absolute distances in X and Y
(that way, it doesn’t majer which
heading the other node is from the
current node)

Then uses Pythagoras’ theorem to
calculate distance

Tiger Algebra

Processing also has a dist()
func8on…

Problem (1): Crossover

Imagine we have two genomes:
ADBCE

DBCEA
Crossing them over using standard one-point
operator will generate illegal tours…
AD|BCE

DB|CEA = ADCEA DBBCE

Visit some ci8es
more than once,
don’t visit all ci8es

Solu8on: new crossover operator