#!/usr/bin/env python3

# tsp-ga-start.py
# A baseline genetic algorithm for the TSP.

import math, turtle, random

def distance(p, q):
	"""Return the distance between points p and q."""
	
	pass
	
def tourLength(tour):
	"""Return the total length of a tour."""
	
	pass
	
def readPoints(filename):
	"""Read points from a file and return a list of tuples."""
	
	inputFile = open(filename, 'r')
	points = []
	for line in inputFile:
		values = line.split()
		points.append((float(values[0]), float(values[1])))
	return points
	
def drawTour(tour):
	"""Draw a tour expressed as a list of (x,y) coordinates."""
	
	pass
	
# ********************* GENETIC ALGORITHM FOR TSP ***********************

GENERATIONS = 100000     # number of generations to evolve
SIZE = 50                # size of the population
CROSSOVER_RATE = 0.90    # probability that a crossover happens
MUTATION_RATE = 0.20     # probability that a mutation happens
MATING_FRACTION = 0.5    # top fraction of population that mates
	
def makePopulation(cities):
	"""Create a population consisting of random permutations of the cities."""
	
	population = []
	for i in range(SIZE):
		population.append(cities[:])       # add a copy of cities to population
		random.shuffle(population[i])      # shuffle the new list randomly
	return population
		
def crossover(mom, pop):
	"""Perform a single point crossover operation."""
	
	mid = random.randrange(0, len(mom) - 1)       # randomly choose crossover point
	
	# Make child1 a copy of mom but with cities in the second "half" of pop removed.
	child1 = [city for city in mom if city not in pop[mid:]]
			
	# Add the second half of pop to the end of child1.
	child1.extend(pop[mid:])
	
	# Make child2 a copy of pop but with cities in the second "half" of mom removed.
	child2 = [city for city in pop if city not in mom[mid:]]
	
	# Add the second half of mom to the end of child1.
	child2.extend(mom[mid:])
	
	return (child1, child2)
	
def swap(L, i, j):
	"""Swap two elements in a list (used by mutate)."""
	
	temp = L[i]
	L[i] = L[j]
	L[j] = temp

def mutate(individual):
	"""Mutate an individual by randomly swapping two cities."""
	
	if random.random() < MUTATION_RATE:
		i = random.randrange(0, len(individual))
		j = random.randrange(0, len(individual))
		swap(individual, i, j)
		
def newGeneration(population):
	"""Crossover two individuals, mutate them, and replace the two least fit individuals."""
	
	mate1 = random.choice(population[:int(SIZE * MATING_FRACTION)])     # randomly choose a tour to crossover
	if random.random() < CROSSOVER_RATE:                                # crossover with pobability CROSSOVER_RATE
		mate2 = random.choice(population[:int(SIZE * MATING_FRACTION)])  # randomly choose a second tour
		(child1, child2) = crossover(mate1, mate2)                       # cross the two tours
		mutate(child1)                                                   # mutate the children
		mutate(child2)                                                   
		population[SIZE - 2] = child1                                    # replace the two least fit
		population[SIZE - 1] = child2
	else:
		mutate(population[random.randrange(SIZE)])                       # otherwise just mutate a random tour
	
def histogram(population):
	"""Print a frequency chart of the current population diversity."""
	
	pass
	
def report(population, generation, minLength):
	"""Periodically display information about the current population."""
	
	if generation % 100 == 0:                      # display the generation number every 100
		print("GENERATION", generation)
			
	if generation % 1000 == 0:                     # display population diversity every 1000
		histogram(population)
		
	currentBest = tourLength(population[0])        # get the best tour length in this population
	if currentBest < minLength:                    # if it is the best so far, then print it
		print(currentBest)
		minLength = currentBest
		
	return minLength                               # return the best tour length so far
	
def tspGA(filename):
	"""Genetic algorithm for TSP."""
	
	# Get the city coordinates from a file.
	points = readPoints(filename)
	
	# Create an initial population of random tours.
	population = makePopulation(points) 
	
	# Sort the initial population by tour length using the TourLength function.
	population.sort(key = tourLength)
	
	# Initialize the shortest tour length.
	bestSoFar = tourLength(population[0])            
	
	# Evolve over GENERATIONS generations.
	for g in range(GENERATIONS):
	
		# Print stats on the current population and update the shorest tour length.
		bestSoFar = report(population, g, bestSoFar)  
		
		# Update the population via crossover and mutation.
		newGeneration(population)                     
		
		# Sort the population by tour length using the TourLength function.
		population.sort(key = tourLength)               
	
	tour = population[0]              # the best tour in the final generation
	
	drawTour(tour)                    # draw the tour
	
	return tourLength(tour)           # return the tour's length
	
def main():
	tspGA('africa.tsp')
	
main()