TSP.py

import random
import time
import timeit
from math import floor

import matplotlib.pyplot as draw
import scipy.io
import numpy as np
import cProfile

mat = scipy.io.loadmat('xy.mat')
cities_location = mat["xy"]
list_of_chromosomes = []
generation_history=[]
flatten = lambda l: [item for sublist in l for item in sublist]



def draw_city_positions():
    A = np.matrix(cities_location)

    # scatter plot x - column 0, y - column 1, shown with marker o
    draw.plot(A[:, 0], A[:, 1], 'o', label='Cities Location')
    draw.legend()
    draw.show()


def create_cities_list():
    cities_list = []
    for x in cities_location:
        cities_list.append(City(x[0], x[1]))
    #print("chromosomes", cities_list)
    #print("length" , len(cities_list))
    return cities_list


def create_chromosomes():
    population_size = len(cities_location)
    for x in range(100):
        list_of_chromosomes.append(random.sample(create_cities_list(),len(cities_location)))
    #print(list_of_chromosomes)

class Matlab : pass

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

    def distance(self, other_city):
        x_dist = abs(self.x - other_city.x)
        y_dist = abs(self.y - other_city.y)
        distance = np.sqrt((x_dist ** 2) + (y_dist ** 2))
        return distance

    def __repr__(self):
        return "(" + str(self.x) + "," + str(self.y) + ")"
    def getCords(self):
        return self.x,self.y


class Fitness:
    def __init__(self, route):
        self.route = route
        self.distance = 0
        self.fitness = 0.0

    def route_dist(self):
        if self.distance == 0:
            path_distance = 0

            for i in range(0, len(self.route)):
                fromCity = self.route[i]
                toCity = None
                if i + 1 < len(self.route):
                    toCity = self.route[i + 1]
                else:
                    toCity = self.route[0]
                path_distance += fromCity.distance(toCity)
            self.distance = path_distance
        return self.route_fitness(self.distance), self.distance

    def route_fitness(self,route_dist):
        if self.fitness == 0:
            try:
                self.fitness = float(1) / float(route_dist)
            except Exception :
                print("something went wrong")

        return self.fitness


class Roullete_selection:
    def __init__(self,generation):


        self.mating_pool = []
        self.post_crossover =[]
        self.post_mutation=[]

    def select_candidate(self):
        global list_of_chromosomes

        fitnesses = [Fitness(c) for c in list_of_chromosomes]
        distances = [x.route_dist()[0] for x in fitnesses]
        fitness_sum = sum(distances)
        uniform = random.uniform(0,fitness_sum)
        current = 0
        for chromosome, distance in zip(list_of_chromosomes, distances):
            current+=distance
            if(current>uniform):

                return chromosome

    def get_mating_pool(self):
        return self.mating_pool

    def new_population(self):
        global list_of_chromosomes

        self.mating_pool = []
        self.post_crossover = []
        self.post_mutation = []

        for x in range(len(cities_location)):
            champion = self.select_candidate()
            self.mating_pool.append(champion)
        #print(len(self.mating_pool),self.mating_pool)

        while len(self.post_crossover)<len(list_of_chromosomes):
            self.crossover()
        #print("that's what I gave",len(self.post_crossover))

        self.mutation()

        list_of_chromosomes=self.post_mutation
        #print("mutation",len(self.post_mutation),self.post_mutation)
        generation_history.append(evaluate_fitness(self.post_mutation))
        #print("post-cross", len(self.post_crossover), self.post_crossover)
        """print("initial",list_of_chromosomes)
        print("mutation",self.post_mutation)
        print("cross",self.post_crossover)
        print("mating",self.mating_pool)"""




    def crossover(self):
        father=random.sample(self.mating_pool,1)
        mother=random.sample(self.mating_pool,1)

        index1 = random.randint(1, len(self.mating_pool) - 2)
        index2 = random.randint(1, len(self.mating_pool) - 2)
        if index1 > index2: index1, index2 = index2, index1
        child1 = father[:index1] + mother[index1:index2] + father[index2:]
        child2 = mother[:index1] + father[index1:index2] + mother[index2:]

        self.post_crossover.append(flatten(child1))
        self.post_crossover.append(flatten(child2))


        return self.post_crossover

    def mutation(self):
#        print(len(self.post_crossover))
        for chromosome in self.post_crossover:

            for chrom in range(len(chromosome)):
                r=random.uniform(0,100)
                #print("Mutation rate",r)
                if(r<=2):
                    #print("MUTATION")
                    #random.shuffle(chromosome)

                    swapWith = int(random.random() * len(chromosome))
                    index1 = random.randint(1, len(self.mating_pool) - 1)
                    index2 = random.randint(1, len(self.mating_pool) - 1)

                    city1=chromosome[chrom]
                    city2=chromosome[swapWith]

                    chromosome[chrom]=city2
                    chromosome[swapWith]=city1


                    if index1>index2:

                        chromosome[index2:index1]=chromosome[index2:index1][::-1]
                    else:
                        chromosome[index1:index2]=chromosome[index1:index2][::-1]

                    temp = chromosome[index1]
                    del chromosome[index1]
                    chromosome.insert(index2,temp)


            self.post_mutation.append(chromosome)



#                print("oh boi",x[random.randint(0,100)].getCords()[random.randint(0,1)])

    def calculate_average(self):
        sum=0
        for x in self.post_mutation:
            sum += Fitness(x).route_dist()[0]
        mean = sum/len(self.post_mutation)
        return mean




def evaluate_fitness(x):
    fit=[]
    for chromosome in range(len(x)):
        route = Fitness(x[chromosome])


        fit.append(route.route_dist()[0])
    return max(fit)
"""

def roullete_new_population():
    roullete = Roullete_selection(list_of_chromosomes)
    for x in range(len(list_of_chromosomes)):
        pass
"""

start = time.time()
def main():
    create_chromosomes()
    #print("eval old",sum(evaluate_fitness(list_of_chromosomes)))
    roullete = Roullete_selection(list_of_chromosomes)
    #print(list_of_chromosomes)

    i=0
    while(i<500):
        roullete.new_population()
        print("new generation..")
        i+=1

cProfile.run('main()')
# main()
#    print(len(list_of_chromosomes)0)
end = time.time()
print (end - start)
A = np.matrix(generation_history)
print(generation_history)
draw.plot(generation_history)





draw.ylabel('MAX Finess in generation')
draw.xlabel('Generation')
draw.show()
#print(len(roullete.get_mating_pool()))