some TSM genetic algo stuff - crappy mate function currently

genetic.py

import random
import bisect
import math
from matplotlib import pyplot


def points(n):
    return [(random.random(), random.random()) for _ in range(n)]

def random_path(n):
    path = range(n)
    random.shuffle(path)
    return path

def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def evaluate(path, points):
    total = 0
    for i1, i2 in zip(path[:-1], path[1:]):
        total += dist(points[i1], points[i2])
    return total

def display_points(points):
    print ["(%.2f, %.2f)" % p for p in points]

def best_of_random(n, points):
    return min([random_path(len(points)) for _ in range(n)],
               key=lambda x: evaluate(x, points))

def mate(path1, path2):
    assert len(path1) == len(path2)
    new_path = path1[:len(path1)/2] + [p for p in path2 if p not in path1[:len(path1)/2]]
    return new_path

def gen(paths, mate_func):
    random.shuffle(paths)
    return [mate_func(x, y) for x, y in zip(paths, paths[1:] + paths[0:1])]

def multiply(paths, n, mate_func):
    return sum([gen(paths, mate_func) for _ in range(n)], [])

def select(paths, points):
    return sorted(paths, key=lambda x: evaluate(x, points))[:len(paths)/2]

def ave(paths, points):
    return sum(evaluate(p, points) for p in paths) / len(paths)

def mutate(path, n):
    path = path[:]
    for _ in range(int(n*len(path))):
        i, j = [random.randint(0, len(path)-1) for _ in range(2)]
        path[i], path[j] = path[j], path[i]
    return path

def mutate_some(paths, percent_to_mutate, mutation_strength):
    return [path if random.random() > percent_to_mutate else mutate(path, mutation_strength)
            for path in paths]

def percentilize(values, points, resolution=100):
    sample = sorted([evaluate(random_path(len(points)), points) for _ in range(resolution)])
    return [round((1 - (bisect.bisect_left(sample, v) / float(resolution))) * 100, 3) for v in values]

def plot(paths, points):
    xs = [points[i][0] for i in paths[0]]
    ys = [points[i][1] for i in paths[0]]
    pyplot.plot(xs, ys)

def try_params(mate_func=mate,
               num_points=100,
               generation_size=50,
               num_generations=50,
               mutation_strength=.2,
               percent_to_mutate=.2,
               interactive=False):
    pts = points(num_points)
    paths = [random_path(num_points) for _ in range(generation_size)]
    aves = []
    for round in range(num_generations):
        paths = select(paths, pts)
        paths = multiply(paths, 2, mate_func)
        paths = mutate_some(paths, .2, .2)
        a = ave(paths, pts)
        aves.append(a)
    return aves, percentilize(aves, pts)

def compare(args1, args2, n=3):
    print 'mutation rate .2:'
    for i in range(n):
        aves, percentiles = try_params(**args1)
        pyplot.plot(aves, 'r-', label=str(args1))
        print percentiles[-1]
    print 'mutation rate .03:'
    for i in range(n):
        aves, percentiles = try_params(**args2)
        pyplot.plot(aves, 'b-', label=str(args2))
        print percentiles[-1]
    pyplot.legend()
    pyplot.show()

if __name__ == '__main__':
    compare({'percent_to_mutate':.20}, {'percent_to_mutate':.03})