main.py

# -*- coding: utf-8 -*-
"""GeneticAlgorithmForTSP.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/17lhnkDCZtWyCoFsKOwoa5jUi9QUTs5qv

**Genetic algorithm for Traveling Salesman Problem - TSP**

1. Load Data
"""

def read_file(file_name:str):
  file = open(file_name)

  num_of_points = int(file.readline())

  distance_matrix = [[0 for _ in range(num_of_points)] for _ in range(num_of_points)]

  for i_row in range(num_of_points):
    dist_list = file.readline().split()
    dist_list = list(map(int, dist_list))

    for i_col in range(len(dist_list)):
      distance_matrix[i_row][i_col] = dist_list[i_col]
      distance_matrix[i_col][i_row] = dist_list[i_col]

  file.close()
  return distance_matrix

"""2. Create and manage the population"""

from random import shuffle

def new_individual(m:int) -> list:
  ind = list(range(m))
  shuffle(ind)
  return ind

def new_population(n:int, m:int) -> list:
  pop = []
  for _ in range(n):
    pop.append(new_individual(m))

  return pop

def print_individual(ind, fit):
  print("-".join(map(str, ind)), fit)

def print_population(pop, fitness=None):
  if not fitness:
    fitness = ["none" for _ in range(len(pop))]

  for ind, fit in zip(pop, fitness):
    print_individual(ind, fit)

def evaluate_individual(ind,dm):
  m = len(ind)
  fit = 0

  for i_gene in range(m-1):
    gene_1 = ind[i_gene]
    gene_2 = ind[i_gene+1]
    fit += dm[gene_1][gene_2]

  gene_1 = ind[-1]
  gene_2 = ind[0]
  fit += dm[gene_1][gene_2]

  return fit

def evaluate_population(pop, dm):
  fitness = []

  for ind in pop:
    eval_ind = evaluate_individual(ind, dm)
    fitness.append(eval_ind)

  return fitness

def find_best_individual_index(fitness):
  index = 0
  for i in range(1,len(fitness)):
    if fitness[i] < fitness[index]:
      index = i

  return index

"""3. Tournament selection and crossover"""

from random import randint

def tournament_selection(pop, fitness, k):
    n = len(pop)
    new_pop = []

    for _ in range(n):
        best_ind_index = randint(0,n-1)

        for _ in range(k):
            random_ind_index = randint(0,n-1)
            if fitness[random_ind_index] < fitness[best_ind_index]:
                best_ind_index = random_ind_index

        new_pop.append(pop[best_ind_index][:])

    return new_pop

from random import random

def fix_PMX(parent, self_mid, second_mid):
  fix = []

  for gene in parent:
    while gene in self_mid:
      pos = self_mid.index(gene)
      gene = second_mid[pos]

    fix.append(gene)

  return fix

def crossover_PMX(parent_1, parent_2):
  m = len(parent_1)

  cut_1 = randint(0,m)
  cut_2 = randint(cut_1+1,m+1)
  cut_2 += 1

  child_1_middle = parent_1[cut_1:cut_2]
  child_2_middle = parent_2[cut_1:cut_2]

  child_1_prefix = fix_PMX(parent_2[:cut_1], child_1_middle, child_2_middle)
  child_2_prefix = fix_PMX(parent_1[:cut_1], child_2_middle, child_1_middle)

  child_1_sufix = fix_PMX(parent_2[cut_2:], child_1_middle, child_2_middle)
  child_2_sufix = fix_PMX(parent_1[cut_2:], child_2_middle, child_1_middle)

  child_1 = child_1_prefix + child_1_middle + child_1_sufix
  child_2 = child_2_prefix + child_2_middle + child_2_sufix

  return child_1, child_2


def crossover(pop, pc):
  new_population = []

  for i in range(0,len(pop),2):
    parent_1 = pop[i]
    parent_2 = pop[i+1]

    if pc > random():
      child_1, child_2 = crossover_PMX(parent_1, parent_2)
    else:
      child_1, child_2 = parent_1, parent_2

    new_population.append(child_1)
    new_population.append(child_2)

  return new_population

"""4. Mutation"""

from random import randint

def inv_mutation(ind):
  m = len(ind)

  cut_1 = randint(0,m)
  cut_2 = randint(cut_1+1,m+1)
  cut_2 += 1

  mid = ind[cut_1:cut_2]
  ind[cut_1:cut_2] = mid[::-1]

def mutation(pop, pm):
  for ind in pop:
    if pm > random():
      inv_mutation(ind)

"""5. Results graphical presentation"""

import matplotlib.pyplot as plt

def draw_graph(best_results,best_in_population,avg_pop,worst_pop):
  plt.plot(best_results)
  plt.plot(best_in_population)
  plt.plot(avg_pop)
  plt.plot(worst_pop)

  plt.show()

"""6. Algorithm exec"""

#parameters
problem = "problems/pr107.txt"
num_of_eras = 2 #parameters
num_of_generations = 2700
all_time_best_result_score = 100000000
debug_print = False
m = None

n = 500 #population size
k = 3 #tournament selection comparisons for each individual
pc = 0.7 #crossover chance in percentage for each (two at once) individual
pm = 0.05 #mutation chance in percentage for each individual

bcc = 2 #break condition count

#exec
distance_matrix = read_file(problem)
m = len(distance_matrix)

for _ in range(num_of_eras):
  pop_P = new_population(n,m)
  fitness = evaluate_population(pop_P, distance_matrix)

  best_index = find_best_individual_index(fitness)
  best_ind = (pop_P[best_index][:], fitness[best_index])

  print("Initial path length: " + str(best_ind[1]))
  best_results = [best_ind[1]]
  best_in_population = [best_ind[1]]
  avg_pop = [sum(fitness)/len(fitness)]
  worst_pop = [max(fitness)]

  #additional variables for break conditions
  last_result_score = 0;
  current_result_count = 0;

  for i in range(num_of_generations):
      pop_T = tournament_selection(pop_P, fitness, k)

      pop_O = crossover(pop_T, pc)

      mutation(pop_O, pm)

      fitness = evaluate_population(pop_O, distance_matrix)

      best_index = find_best_individual_index(fitness)

      if fitness[best_index] < best_ind[1]:
          best_ind = (pop_O[best_index][:], fitness[best_index])

      best_results.append(best_ind[1])
      best_in_population.append(fitness[best_index])
      avg_pop.append(sum(fitness)/len(fitness))
      worst_pop.append(max(fitness))

      pop_P = pop_O

      if i % 200 == 0:
        if best_ind[1] == last_result_score:
          current_result_count += 1
        else:
          last_result_score = best_ind[1]
          current_result_count = 0

        if(current_result_count > bcc-1):
          break

        if(best_ind[1] < all_time_best_result_score):
          all_time_best_result_score = best_ind[1]

        if(debug_print):
          print(best_ind[1], end='\n')
          print_individual(best_ind[0],best_ind[1])
          print(" ", end='\n')

        #progressbar
        print("=", end="")

  print("\n" + "Final path length: " + str(best_ind[1]))
  print_individual(best_ind[0],best_ind[1])
  print("All time best result: " + str(all_time_best_result_score), end='\n\n')
  draw_graph(best_results,best_in_population,avg_pop,worst_pop)