TSP

tsp.png

tsp.py

#/usr/bin/env python
import matplotlib.pyplot as plt
import numpy as np
import numpy.random as random
from itertools import imap, islice

class City:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    @classmethod
    def distance(cls, a, b):
        return np.sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2)

    def getx(self):
        return self.x

    def gety(self):
        return self.y


class Cycle:
    def __init__(self, cities):
        self.cities = list(cities)
        self.cycle = self.cities + [self.cities[0]]
        self.score = 0
        c = self.cycle[0]
        for n in self.cycle[1:]:
            self.score += City.distance(c, n)
            c = n

    def plot(self, *opt):
        xs = map(City.getx, self.cycle)
        ys = map(City.gety, self.cycle)
        plt.xlim((0, 1))
        plt.ylim((0, 1))
        plt.plot(xs, ys, *opt)
        plt.scatter(xs, ys)

    def shuffle(self):
        cities = self.cities[:]
        random.shuffle(cities)
        return Cycle(cities)

    @classmethod
    def cross(cls, parent1, parent2):
        p1, p2 = map(lambda p: p.cities, (parent1, parent2))
        point = random.randint(1, len(p1))
        def tail(p): return p[point:]
        def head(p): return p[:point]
        c1, c2 = map(tail, (p2, p1))

        c1 = [e if not e in c1 else c2[c1.index(e)] for e in head(p2)] + c1
        c2 = [e if not e in c2 else c1[c2.index(e)] for e in head(p1)] + c2
        return map(Cycle, (c1, c2))

    def swap(self):
        cities = self.cities[:]
        p1, p2 = random.randint(len(cities), size = 2)
        cities[p1], cities[p2] = cities[p2], cities[p1]
        return Cycle(cities)

    def opt2(self):
        p1, p2 = sorted(random.randint(len(self.cities), size = 2))
        return Cycle(self.cities[:p1] + self.cities[p1:p2][::-1] + self.cities[p2:])


def ga(init, population = 10, mutation = 0.1):
    genes = [init] + [init.shuffle() for _ in range(population)]
    while True:
        random.shuffle(genes)
        pairs = zip(genes[0::2], genes[1::2])
        children = reduce(lambda r, e: r + e, map(lambda p: Cycle.cross(*p), pairs), [])
        mutations = [children[index].opt2() for index, p in enumerate(random.random(len(children))) if p < mutation]
        genes = genes + children + mutations
        genes.sort(key = lambda g: g.score)
        genes = genes[:population]
        yield genes[0]


def sa(init, temp = 1, accept = lambda e1, e2, t: np.exp((e1 - e2)/t), next_temp = lambda t: 0.99 * t):
    c = init
    while True:
        n = c.opt2()
        if c.score - n.score >= 0 or accept(c.score, n.score, temp) > random.random():
            c = n
        temp = next_temp(temp)
        yield c

if __name__ == '__main__':
    itrs = 1000
    cycle = Cycle(map(lambda e: City(*e), random.random((30, 2))))
    plt.figure(figsize = (12, 8))
    plt.subplot(2, 3, 1)
    cycle.plot()
    plt.title('init, score = %0.2f' % cycle.score)

    plt.subplot(2, 3, 2)
    randoms = [cycle.shuffle() for _ in range(itrs)]
    best = min(randoms, key = lambda x: x.score)
    best.plot()
    plt.title('random (%d), score = %0.2f' % (itrs, best.score))

    plt.subplot(2, 3, 3)
    ga_results = list(islice(ga(cycle), itrs))
    ga_results[-1].plot()
    plt.title('GA (%d), score = %0.2f' % (itrs, ga_results[-1].score))

    plt.subplot(2, 3, 4)
    hc_results = list(islice(sa(cycle, accept = lambda e1, e2, t: 0.0), itrs))
    hc_results[-1].plot()
    plt.title('HC (%d), score = %0.2f' % (itrs, hc_results[-1].score))

    plt.subplot(2, 3, 5)
    sa_results = list(islice(sa(cycle), itrs))
    sa_results[-1].plot()
    plt.title('SA (%d), score = %0.2f' % (itrs, sa_results[-1].score))

    plt.subplot(2, 3, 6)
    plt.title('score')
    xs = range(itrs)
    plt.plot(xs, map(lambda x: x.score, randoms), label = 'random')
    plt.plot(xs, map(lambda x: x.score, ga_results), label = 'GA')
    plt.plot(xs, map(lambda x: x.score, hc_results), label = 'HC')
    plt.plot(xs, map(lambda x: x.score, sa_results), label = 'SA')
    plt.legend(loc = 'best')

    plt.savefig('tsp.png')