Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ##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])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement