TSP Genetic Algorithm

import numpy as np, random, operator, math
import matplotlib.pyplot as plt

'''
  class City: representa cada cidade com suas localizações
descritas pelas coordenadas (x, y).
  - Método __init__(self, x, y): inicializa objeto da classe com as coordenadas x e y;
  - Método distance(self, city): calcula a distância entre o objeto e outro da classe City;
  - Método __init__(self): reproduz em coordenadas cartesianas a localização da cidade.
'''
class City:
  def __init__(self, x, y):
    self.x = x
    self.y = y

  def distance(self, city):
    xDis = abs(self.x - city.x)
    yDis = abs(self.y - city.y)
    return xDis + yDis

  def __repr__(self):
    return "(" + str(self.x) + "," + str(self.y) + ")"
'''
  class Fitness: calcula o valor de Fitness de um caminho passando por uma sequência de cidades. Quanto menor a extensão do caminho, maior o valor de Fitness.
   - Método __init__(self, route): inicializa um objeto da classe Fitness;
   - Método routeDistance(self): calcula a distância total percorrida na sequência de cidades dada;
   - Método routeFitness(self): calcula o valor do Fitness do caminho a partir do valor obtido no método routeDistance().
'''
class Fitness:
  def __init__(self, route):
    self.route = route
    self.distance = 0
    self.fitness = 0.0

  def routeDistance(self):
    if self.distance == 0:
      pathDistance = 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]
        pathDistance += fromCity.distance(toCity)
      self.distance = pathDistance
    return self.distance

  def routeFitness(self):
    if self.fitness == 0.0:
      self.fitness = 1/float(self.routeDistance())
    return self.fitness

random.seed('seed fixa') #seed usada para os métodos do módulo random

'''
  Método  inicializeCities(cityPoints): recebe uma sequência de pontos como parâmetro que representam coordenadas de cidades e retorna uma lista de objetos da classe City localizados nos pontos dados como parâmetro.
'''
def initializeCities(cityPoints):
  cityList = []
  for i in range(0, int(len(cityPoints)/2)):
    cityList.append(City(cityPoints[2*i],cityPoints[2*i+1]))
  return cityList

'''
  Método createRoute(cityList): recebe uma lista de objetos da classe City como parâmetro e os retorna em ordem aletória.
  *Cada lista com as Cidades dispostas em uma ordem é considera um Indivíduo. Cada Indivíduo é considerada uma possível solução para o TSP.
'''
def createRoute(cityList):
  route = random.sample(cityList,len(cityList))
  return route

'''
  Método createPopulation(cityList, popSize): recebe uma lista de objetos da classe City (cityList) e um int que reprezenta o tamanho da população (popSize) como parâmetros. Este método retorna uma lista de Indivíduos, sendo uma sequência de cidades. O conjunto desses indiíduos é chamado População e o tamanho da lista retornada é o tamanho da Poupulação.
'''
def createPopulation(cityList, popSize):
  firstPop = []
  for i in range(0, popSize):
    firstPop.append(createRoute(cityList))
  return firstPop

'''
  Método rankRoutes(population): recebe uma População (population) como parâmetro e retorna um dicionário com os mesmos indivíduos, porém ordenados pelo valor de Fitness de cada um em ordem decrescente. Ou seja, os indivíduos com distância total do caminho menores ficam nas posições iniciais da lista. As chaves do dicionário retornado são as posições (índices) de cada objeto na lista de cidades (population) e os valores são os seus respectivos valores de Fitness.
'''
def rankRoutes(population):
  fitnessResults = {}
  for i in range(0, len(population)):
    fitnessResults[i] = Fitness(population[i]).routeFitness()
  return sorted(fitnessResults.items(), key = operator.itemgetter(1), reverse = True)


'''
  Método selection(popRanked): recebe uma lista com Indivíduos ordenados em ordem decrescente de Fitness (popRanked) como parâmetro e retorna os índices dos Indivíduos que farão Mutação e Cruzamento para formar a próxima Geração.
'''
def selection(popRanked):
  selectionResults = [] #inicializa a lista dos Indivíduos da próxima Geração

  '''
    Soma os valores de Fitness de todos os Indivíduos (totalSum) e faz uma lista com as somas cumulativas dos Fitness até a posição de cada Indivíduo na lista Indivíduos ordenados por seus Fitness (cumSum[]).
  '''
  totalSum = 0
  cumSum = []
  for i in range(0, len(popRanked)):
    totalSum += popRanked[i][1]
    cumSum.append(totalSum)

  '''
    Faz uma lista que representa o percentual de Fitness de cada Indivíduo (perc[]) sobre a soma dos Fitness de todos da População (totalSum) e outra com a soma cumulativa de seus percentuais (percSum[]).
  '''
  perc = []
  percSum = []
  for i in range(0, len(popRanked)):
    perc.append(popRanked[i][1]/totalSum)
    percSum.append(cumSum[i]/totalSum)

  '''
    Decide quantas vezes cada Indivíduo vai aparecer na lista dos Indivíduos que vão gerar a próxima Geração (selectionResults[]).
    Considerando que perc[i]*len(popRanked) = n*1% + r, sendo n um número inteiro >= 0 e r um número decimal menor que 1, o número de vezes que um Indivíduo vai aparecer (selQuan[i]) na lista é n. Para todas as vezes em que n for igual a zero, o Indivíduo será selecionado aleatoriamente com chances proporcionais ao valor de seus Fitness (perc[i]).
  '''
  rest = 0
  selQuant = []
  for i in range(0, len(popRanked)):
    selQuant.append(math.floor(perc[i]*len(popRanked)))
    if selQuant[i] == 0:
      rest += 1

  '''
    Se n >= 1, coloca os Indivíduos n vezes na lista da próxima Geração (selectionResults[]).
  '''
  for i in range(0, len(popRanked) - rest):
    for j in range(0, selQuant[i]):
      selectionResults.append(popRanked[i][0])

  '''
    Seleciona os indivíduos que vão gerar a próxima Geração (selectionResults[]) que faltam aleatoriamente, com o chances proporcionais aos valores de seus Fitness.
  '''
  for i in range(len(popRanked) - rest, len(popRanked)):
    pick = random.random()
    for i in range(0, len(perc)):
      if pick < percSum[i]:
        selectionResults.append(popRanked[i][0])
        break
  return selectionResults #retorna os índices dos Indivíduos que vão ser Cruzados e Mutados para formar a próxima Geração.

'''
  Método matingPool(population, selectionResults): dados os índices de cada elemento na lista da População atual (selectionResults[i]) e a própria População atual (population[]), retorna a lista com os Índivíduos que formarão a próxima Geração.
'''
def matingPool(population, selectionResults):
  matingPool = []
  for i in range(0, len(selectionResults)):
    index = selectionResults[i]
    matingPool.append(population[index])
  return matingPool

'''
  Método breed(parent1, parent2): Recebe dois Indivíduos (parent1[] & parent2[]) como parâmetros e retorna um terceiro Indivíduo considerado filho dos dois anteriores (child[]). Este método é chamado de Cruzamento. É importante ressaltar que nenhuma cidade (objeto da classe City) presente nas listas de parent[1] e parent[2] é excluído da lista de child[], de mesma forma, nenhum objeto aparece mais de uma vez em child[].
'''
def breed(parent1, parent2):
  '''
    Inicializa a lista do Indivíduo filho (child[]), dos elementos de parent1 que vão ser herdados pelo filho (childP1[]) e dos elementos de parent2 que serão herdados pelo filho (childP2[]).
  '''
  child = []
  childP1 = []
  childP2 = []

  '''
    Seleciona de forma aleatória os elementos de início (startGene) e de fim (endGene) na lista de elementos de parent1 que serão herdados pelo filho e os coloca na lista que o filho herdará de parent1[] (childP1[])
  '''
  geneA = int(random.random()*len(parent1))
  geneB = int(random.random()*len(parent1))
  startGene = min(geneA, geneB)
  endGene = max(geneA, geneB)
  for i in range(startGene, endGene):
    childP1.append(parent1[i])

  '''
    Adiciona na lista dos elementos herdados de parent2[] (childP2[]) todos os elementos que estão em parent2[] e não estão em parent1[]
  '''
  childP2 = [item for item in parent2 if item not in childP1]

  '''
    Forma e retorna a lista do Indivíduo filho (child[])
  '''
  child = childP1 + childP2
  return child

'''
  Método breedPopulation(matingpool, breedingRate, eliteSize): recebe a lista de Indivíduos que serão cruzados para formar a prócima Geração (matingpool), a Taxa de Cruzamento (breedingRate) e o tamanho da Elite (eliteSize) como parâmetros e retorna a lista com os Indivíduos filhos (children[]). Taxa de Cruzamento representa as chances de haver Cruzamento entre dois Indivídos. Se não houver cruzamento, o Indivíduo aparecerá idêntico na lista dos filhos (children[]). Tamanho da Elite representa o número de elementos da lista de Indivíduos que não serão cruzados e serão passados diretamente para a próxima Geração. Isso acontece com os indivíduos com os melhores valores de Fitness.
'''
def breedPopulation(matingpool, breedingRate, eliteSize):
  children = [] #inicializa a lista dos Indivíduos filhos

  '''
    Insere os Indivíduos mais bem qualificados da População atual na lista dos filhos
  '''
  for i in range(0, eliteSize):
    children.append(matingpool[i])

  pool = random.sample(matingpool, len(matingpool)) #coloca os Indivíduos da População atual em ordem aleatória.

  '''
    Faz o Cruzamento dos Indivíduos de acordo com as chances previstas na Taxa de Cruzamento (breedingRate) e retorna a População dos filhos completa (children[])
  '''
  length = len(matingpool) - eliteSize
  for i in range(0, length):
    if random.random() < breedingRate:
      child = breed(pool[i], pool[len(matingpool) - i - 1])
    else:
      child = pool[i]
    children.append(child)
  return children

'''
  Método mutate(individual, mutationRate): recebe um objeto da classe City (individual) e a Taxa de Mutação (mutationRate) como parâmetros e retorna o Indivíduo (individual), tendo este sofrido a Mutação ou não. As chances de ele sofrer a Mutação são definidas pela Taxa de Mutação. Neste processo, dois Genes (objetos na classe City) aleatórios são trocados de lugar.
'''
def mutate(individual, mutationRate):
  if random.random() < mutationRate:
    swapped = int(random.random()*len(individual))
    swapWith = int(random.random()*len(individual))

    city1 = individual[swapped]
    city2 = individual[swapWith]

    individual[swapped] = city2
    individual[swapWith] = city1
  return individual

'''
  Método mutatePopulation(population, mutationRate, eliteSize): recebe a População atual (population), a Taxa de Mutação (mutationRate) e o Tamanho da Elite (eliteSize) como parâmetros e realiza o processo de Mutação em toda a População de acordo com a Taxa de Mutação (mutationRate) e o tamanho da Elite (eliteSize), até retornar a nova População com os Genes trocados de lugar nos Indivíduos que sofreram a Mutação (mutatedPop[]). Taxa de Mutação representa as chances de havar Mutação em cada Indivíduo e Tamanho da Elite represente a quantidade de Indivíduos, os quais possuem os valores de Fitness mais altos da População atual, que não têm chances de sofrer Mutação.
'''
def mutatePopulation(population, mutationRate, eliteSize):
  mutatedPop = []

  for i in range(0, eliteSize):
    mutatedPop.append(population[i])

  for i in range(eliteSize, len(population)):
    mutatedInd = mutate(population[i], mutationRate)
    mutatedPop.append(mutatedInd)
  return mutatedPop

'''
  Método nextGeneration(currentGen, breedingRate, mutationRate, eliteSize): recebe a Geração Atual (currentGen), Taxa de Cruzamento (breedingRate), Taxa de Mutação (mutationRate) e tamanho da Elite (eliteSize) como parâmetros e aplica os métodos descritos acima para retornar a próxima Geração (nextGeneration)
'''
def nextGeneration(currentGen, breedingRate, mutationRate, eliteSize):
  popRanked = rankRoutes(currentGen)
  selectionResults = selection(popRanked)
  matingpool = matingPool(currentGen, selectionResults)
  children = breedPopulation(matingpool, breedingRate, eliteSize)
  nextGeneration = mutatePopulation(children, mutationRate, eliteSize)
  return nextGeneration

'''
  Método geneticAlgotithm(cityList, popSize, breedingRate, mutationRate, eliteSize, generations): recebe uma lista de objetos da classe City (cityList), o número de Indivíduos de cada Geração (popSize), a Taxa de Cruzamento em cada Geração (breedingRate), a Taxa de Mutação em cada Geração (mutationRate), o tamanho da Elite de cada Geração (eliteSize) e o número de Gerações (generations) da execução do Algoritmo Genético como parâmetros e executa o Algoritmo em si. O Algoritmo Genético retorna o melhor caminho encontrado em todas as iterações realizadas (bestRoute). O melhor caminho é a sequência de cidades que obtiveram o maior valor de Fitness e portanto, a menor distância total entre elas.
'''
def geneticAlgotithm(cityList, popSize, breedingRate, mutationRate, eliteSize, generations):
  pop = createPopulation(cityList, popSize) # Iicializa uma população com as cidades dadas
  shortest = [] # Inicializa a lista das menores distâncias obtidas em cada geração
  mean = [] # Inicializa lista da média das distâncias obtidas em cada geração
  startDistance = Fitness(pop[rankRoutes(pop)[0][0]]).routeDistance() # Calcula a menor distância da primeira Geração
  shortest.append(startDistance) # Insere o primeiro elemento na lista de menores distâncias de cada Geração
  v = [] # Inicializa a lista com as distâncias da primeira Geração, o loop abaixo a preenche
  for i in range(0, len(pop)):
    v.append(Fitness(pop[i]).routeDistance())
  mean.append(np.mean(v)) # Calcula a média das distâncias da primeira Geração e insere na lista das médias
  bestDistance = startDistance # Salva a menor distância obtida entre todos Indivíduos de todas as Gerações
  bestRoute = pop[rankRoutes(pop)[0][0]] # Salva o caminho

  gen = 0 # Inicializa a contagem de Gerações
  while gen <= generations: # Realiza o loop pelo número de Gerações determinado
    pop = nextGeneration(pop, breedingRate, mutationRate, eliteSize) # Obtém a próxima Geração
    rankedRoutes = rankRoutes(pop) # Coloca os Indivíduos da Geração atual em ordem decrescente de Fitness
    m = [] # Inicializa a lista com as distâncias da Geração atual, o loop abaixo a preenche
    for i in range(0, len(pop)):
      m.append(Fitness(pop[rankedRoutes[i][0]]).routeDistance())
    media = np.mean(m) # Calcula a média das distâncias da Geração atual
    distance = Fitness(pop[rankedRoutes[0][0]]).routeDistance() # Calcula a distância total do melhor Indivíduo da Geração atual
    print("Best Distance: " + str(distance) + "  Média: " + str(media)) # Imprime a menor distância total da Geração atual
    if distance < bestDistance: # Salva a melhor distância total e melhor caminho entre todas as Gerações, caso estes superem o melhor obtido até agora
      bestDistance = distance
      bestRoute = pop[rankRoutes(pop)[0][0]].copy()
    shortest.append(distance) # Insere a menor distância atual na lista de menores distâncias
    mean.append(media) # Insere a média das distâncias da Geração atual na lista das médias
    gen += 1 # Continua a contagem de Gerações
  '''
    Imprime os resultados do Algoritmo Genético e salva os de
  '''
  print("\nStart Distance: " + str(startDistance) + "\nFinal Distance: "
        + str(distance) + "\nBest Distance: " + str(bestDistance)
        + "\n" + str(generations) + " generations.\n")
  plt.plot(shortest)
  plt.ylabel('Distance')
  plt.xlabel('Generation')
  plt.grid(b = True, which = 'major', axis = 'both')
  plt.savefig("shortest_TC1TM1.png", quality = 95)
  plt.figure()
  plt.plot(mean)
  plt.ylabel('Média das Distâncias')
  plt.xlabel('Generation')
  plt.grid(b = True, which = 'major', axis = 'both')
  plt.savefig("mean_TC1TM1.png", quality = 95)
  return bestRoute

cityPoints = [19, 39, 9, 93, 35, 84, 14, 91, 66, 93, 3, 78,
          93, 72, 7, 40, 99, 79, 82, 12, 78, 91, 42, 44,
          97, 63, 93, 81, 61, 85, 87, 35, 22, 82, 11, 70,
          17, 4, 88, 16, 32, 8, 53, 64, 47, 28, 68, 83, 40,
          17, 93, 53, 47, 9, 63, 20, 66, 67, 63, 3, 78, 50,
          71, 33, 76, 64, 15, 18, 60, 8, 50, 77, 12, 80, 94,
          36, 2, 94, 65, 5, 86, 46, 46, 11, 39, 25, 80, 29,
          51, 31]

cities = initializeCities(cityPoints)

# Para rodar o segundo caso é necessário comentar a linha referente ao Caso 1 e descomentar a linha referente ao Caso 2
# Caso 1
bestRoute = geneticAlgotithm(cityList = cities, popSize = 100, breedingRate = 0.55, mutationRate = 0.12, eliteSize = 10, generations = 2000)

# Caso 2
# bestRoute = geneticAlgotithm(cityList = cities, popSize = 100, breedingRate = 0.43, mutationRate = 0.65, eliteSize = 10, generations = 2000)

print(bestRoute)