cursesTSP.py

##Brendan Benshoof
##12/14/2011
##Copyleft 2011

import random, pygame, sys, math
import pygcurse as pygcurse
from pygame.locals import *

##window setup
win = pygcurse.PygcurseWindow(40, 40)

#genetic algorithim speedcode TSP 38 minutes long

#assumption 1 input graph is a clique

#cities x,y coords
cities = []
mapsize = 40 #sidelength of a square map
num_of_cities = 15

gen_size = 50 #divisable by parents
parentsl = 10 #number of parents for each generation
game_length = 100 # number of generations

def get_dist(a,b):
    return math.sqrt((a[0]-b[0])**2.0+(a[1]-b[1])**2.0)

#now the fun really starts
def Grade(order):
    total = 0.0
    for i in range(0,num_of_cities-1):
        total += get_dist(order[i],order[i+1])
    return total

def Mutate(order):
    copy = order[:]
    a = random.randint(0,num_of_cities-1)
    b = random.randint(0,num_of_cities-1)
    aa = copy[a]
    bb = copy[b]
    copy[a]=bb
    copy[b]=aa
    return copy




#make a list of 20 random cities
for i in range(0,num_of_cities):
    x = random.random()*mapsize
    y = random.random()*mapsize
    cities.append((x,y))
#print(cities)

#populate
generation = []
for i in range(0,gen_size):
    copy = cities[:]
    random.shuffle(copy)
    generation.append(copy)

def render(order):
    global win
    pi = math.pi
    for i in range(0,num_of_cities):

        #walk to the next city
        char = "|"
            ##up,down,left,right
        resolution = 100 #more then high enough
        slope = math.fabs((order[i][1]*1.0-order[(i+1)%num_of_cities][1]*1.0)/(order[i][0]*1.0-order[(i+1)%num_of_cities][0]*1.0))
        if(slope<0.4):
            char = "-"
        elif(slope<100):
            char = "/"
        for j in range(0,resolution):
            stepx = int((order[(i+1)%num_of_cities][0]-order[i][0]*1.0)*1.0*j/(resolution*1.0)+order[i][0])
            stepy = int((order[(i+1)%num_of_cities][1]-order[i][1]*1.0)*1.0*j/(resolution*1.0)+order[i][1])
            if(stepx>=0 and stepy>=0):
                win.write(char,x=stepx,y=stepy)

    for i in range(0,num_of_cities):
        win.write("#",x=order[i][0],y=order[i][1])

    pygcurse.waitforkeypress()
#mainloop
for k in range(0,game_length):
    parents = []
    for i in range(0,parentsl): #this is horrible I know, no time to think
        bestscore = 999999999.9
        bestid = -1
        for j in range(0,len(generation)):
            s = Grade(generation[j])
            if(s<bestscore):
                bestscore = s
                bestid = j
        parents.append(generation[bestid])
        generation.pop(bestid)


    #make more kids
    generation = []
    for i in range(0,parentsl): #this is horrible I know, no time to think
        kids = gen_size/parentsl-1
        generation.append(parents[i])
        for j in range(0,kids):
            generation.append(Mutate(parents[i]))
    #repeat while time remains
render(generation[0])