tsp ga.py

import math
import random
import functools
import sys

# an inefficient ga for the travelling salesman problem
# stuff to think about:
#   chromosomes can't be repeated, so crossover and mutation have to be changed
#   mutation: swap two elements
#   crossover: use ordered crossover

cities = [(21, 54), (88, 47), (74, 27), (83, 62), (1, 39), (64, 64), (18, 59), (2, 50), (98, 95), (16, 97), (29, 46), (39, 91), (17, 58), (73, 18), (60, 65), (41, 80), (4, 8), (37, 18), (78, 67), (70, 39), (98, 29), (97, 23), (28, 2), (53, 44), (79, 79), (97, 44), (81, 39), (31, 26), (58, 96), (36, 16), (67, 7), (10, 86), (57, 17), (65, 89), (39, 78), (9, 79), (81, 51), (53, 61), (66, 25), (87, 64)]

# distance between two cities
def dist(a, b):
  return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

# distance of an entire path
def dist_path(path, cities):
  s = 0
  for i, c in enumerate(path[1:]):
    s += dist(cities[path[i]], cities[c])
  return s

# random initial population
def gen_initial_population(size, cities=None):
  pop = []
  for i in range(size):
    chromosome = range(0, len(cities))
    random.shuffle(chromosome)
    pop.append(chromosome)
  return pop

# tournament selection with negative feedback. this is some black magic.
# the negative feedback punishes individuals that are similar to try and
# prevent crowding - the whole population converging on some local maxima.
def tournament_selection(k, pop, cities):
  sample = random.sample(pop, k)
  fns = [dist_path(x, cities) for x in sample]
  mode = max(set(fns), key=fns.count)
  best = sample[0]
  best_f = fns[0]
  for i, ind in enumerate(sample):
    ind_fitness = fns[i]
    diff = abs(mode - ind_fitness)
    if diff > 0:
      ind_fitness += diff*2
    if ind_fitness < best_f:
      best = ind
      best_f = ind_fitness
  return best
  # or regular tornament selection in one line. i own
  # return min(random.sample(pop, k), key=functools.partial(dist_path, cities=cities))

# ordered crossover
# regular crossover doesnt care any which way so you can duplicate chromosomes
# in the children - no good for travelling salesman.
# ordered crossover:
#   take a subsection from parent a
#   fill in the gaps with elements from parent b if they are not already in the
#     child
# means we get a lil of parent a's ordering a lil of parent b's and no repeats.
def ordered_crossover(a, b):
  # select subsection from parent a
  s = random.randrange(len(a)-1)
  e = random.randrange(len(a)-1)
  if s > e: s, e = e, s
  sub = a[s:e]

  child = []
  pp = 0
  for i in range(len(a)):
    if i >= s and i < e:
      child.append(sub[i-s])
    else:
      while b[pp] in sub:
        pp += 1
      child.append(b[pp])
      pp += 1
  return child

# regular mutation could also be bad for tsp
# this mutation just swaps two chromosomes
def mutate(a):
  if random.random() > 0.92:
    f = random.randrange(len(a))
    t = random.randrange(len(a))
    a[f], a[t] = a[t], a[f]
  return a

# population size
size = 50
pop = gen_initial_population(size, cities)

# number of iterations
gens = 3000
best_so_far = min(pop, key=functools.partial(dist_path, cities=cities))
for i in range(gens):
  best = min(pop, key=functools.partial(dist_path, cities=cities))
  if dist_path(best, cities) < best_so_far:
    best_so_far = best
  # elitism - always make the sure best individual (so far) is in the
  # population
  npop = [best_so_far]

  if i %  10 == 0 or i == gens-1:
    sys.stdout.write('\r' + str(i) + '   ' + str(dist_path(best, cities)))
    sys.stdout.flush()

  for i in range(size-1):
    # select and mutate
    a = mutate(tournament_selection(3, pop, cities))
    b = mutate(tournament_selection(3, pop, cities))
    # crossover
    npop.append(ordered_crossover(a, b))
  pop = npop

best = min(pop, key=functools.partial(dist_path, cities=cities))

print
print '{} {:3.3f}'.format(best, dist_path(best, cities))

# stuff for plotting the route, can be commented out
import matplotlib.path as mpath
import matplotlib.patches as mpatches
import matplotlib.pyplot as plt
fig, ax = plt.subplots()
Path = mpath.Path

path_data = [(Path.MOVETO, cities[best[0]])]
for city in best[1:-1]:
  path_data.append((Path.LINETO, cities[city]))
path_data.append((Path.CLOSEPOLY, cities[best[-1]]))

codes, verts = zip(*path_data)
path = mpath.Path(verts, codes)

x, y = zip(*path.vertices)
line, = ax.plot(x, y, 'go-')

ax.grid()
ax.axis('equal')

plt.show()