fork download
copy 
  1. ###############################################################################
  2. ##                   TSP SOLUTION WITH GENETIC ALGORITHM                     ##
  3. ##                    Luke Collins ~ ICS2207 Assignment                      ##
  4. ###############################################################################
  5.  
  6. import sys, math, random
  7. import numpy as np
  8. import matplotlib.pyplot as plt
  9.  
  10. class Graph:
  11.     """Graph data structure"""
  12.  
  13.     def __init__(self, vertices):
  14.         self.vertices = vertices
  15.         self.n = len(vertices)
  16.  
  17.         # Weighted adjacency matrix
  18.         self.a = np.empty((self.n, self.n))
  19.         self.a[:] = np.nan
  20.  
  21.     def d(self, i, j):
  22.         """Euclidean Metric d_2((x1, y1), (x2, y2))"""
  23.  
  24.         # Check if the distance was computed before
  25.         if not np.isnan(self.a[i][j]):
  26.             return self.a[i][j]
  27.  
  28.         _x1 = self.vertices[i][0]
  29.         _x2 = self.vertices[j][0]
  30.         _y1 = self.vertices[i][1]
  31.         _y2 = self.vertices[j][1]
  32.  
  33.         # Otherwise compute it
  34.         _distance = math.sqrt((_x1 - _x2)**2 + (_y1 - _y2)**2)
  35.  
  36.         # Add to matrix
  37.         self.a[i][j], self.a[j][i] = _distance, _distance
  38.         return _distance
  39.  
  40.     def plot(self, tour=None):
  41.         """Plots the cities and superimposes given tour"""
  42.  
  43.         if tour is None:
  44.             tour = Tour(self, [])
  45.  
  46.         _vertices = [self.vertices[0]]
  47.  
  48.         for i in tour.vertices:
  49.             _vertices.append(self.vertices[i])
  50.  
  51.         _vertices.append(self.vertices[0])
  52.  
  53.         plt.title("Cost = " + str(tour.cost()))
  54.         plt.plot(*zip(*_vertices), '-r')
  55.         plt.scatter(*zip(*self.vertices), c="b", s=10, marker="s")
  56.         plt.show()
  57.  
  58. class Tour:
  59.     """Tour data structure"""
  60.  
  61.     def __init__(self, g, vertices = None):
  62.         """Generate random tour in given graph g"""
  63.  
  64.         self.g = g
  65.  
  66.         if vertices is None:
  67.             self.vertices = list(range(1, g.n))
  68.             random.shuffle(self.vertices)
  69.         else:
  70.             self.vertices = vertices
  71.  
  72.         self.__cost = None
  73.  
  74.     def cost(self):
  75.         """Return total edge-cost of tour"""
  76.         if self.__cost is None:
  77.             self.__cost = self.g.d(0, self.vertices[0]) + \
  78.                           sum(map(self.g.d, self.vertices, self.vertices[1:])) + \
  79.                           self.g.d(self.vertices[-1], 0)
  80.         return self.__cost
  81.  
  82.  
  83. class GeneticAlgorithm:
  84.     """Implements instance of genetic algorithm"""
  85.  
  86.     def __init__(self, g, population_size, k=3, elite_mating_rate=0.3,
  87.                  mutation_rate=0.1, mutation_swap_rate=0.5,
  88.                  random_least_fit=0.1):
  89.         """Initialises algorithm parameters"""
  90.  
  91.         self.g = g
  92.         self.n = g.n
  93.  
  94.         self.population = []
  95.         for _ in range(population_size):
  96.             self.population.append(Tour(g))
  97.  
  98.         self.population_size = population_size
  99.         self.k = k
  100.         self.elite_mating_rate = elite_mating_rate
  101.         self.mutation_rate = mutation_rate
  102.         self.mutation_swap_rate = mutation_swap_rate
  103.         self.random_least_fit = random_least_fit
  104.  
  105.     def crossover(self, mum, dad):
  106.         """Implements ordered crossover"""
  107.  
  108.         size = self.n - 1
  109.  
  110.         # Choose random start/end position for crossover
  111.         start, end = sorted([random.randrange(size) for _ in range(2)])
  112.  
  113.         # Identify the elements from mum's sequence which end up in alice,
  114.         # and from dad's which end up in bob
  115.         mumxo = set(mum.vertices[start:end + 1])
  116.         dadxo = set(dad.vertices[start:end + 1])
  117.  
  118.         # Take the other elements in their original order
  119.         alice = [i for i in dad.vertices if not i in mumxo]
  120.         bob = [i for i in mum.vertices if not i in dadxo]
  121.  
  122.         # Insert selected elements of mum's sequence for alice, dad's for bob
  123.         alice[start:start] = mum.vertices[start:end + 1]
  124.         bob[start:start] = dad.vertices[start:end + 1]
  125.  
  126.         # Return twins
  127.         return Tour(self.g, alice), Tour(self.g, bob)
  128.  
  129.     def mutate(self, tour):
  130.         """Randomly swaps pairs of cities in a given tour according to mutation rate"""
  131.  
  132.         # Decide whether to mutate
  133.         if random.random() < self.mutation_rate:
  134.  
  135.             # For each vertex
  136.             for i in range(self.n - 1):
  137.  
  138.                 # Randomly decide whether to swap
  139.                 if random.random() < self.mutation_swap_rate:
  140.  
  141.                     # Randomly choose other city position
  142.                     j = random.randrange(self.n - 1)
  143.  
  144.                     # Swap
  145.                     tour.vertices[i], tour.vertices[j] = tour.vertices[j], tour.vertices[i]
  146.  
  147.     def select_parent(self, k):
  148.         """Implements k-tournament selection to choose parents"""
  149.         tournament = random.sample(self.population, k)
  150.         return max(tournament, key=lambda t: t.cost())
  151.  
  152.     def evolve(self):
  153.         """Executes one iteration of the genetic algorithm to obtain a new generation"""
  154.  
  155.         new_population = []
  156.  
  157.         for _ in range(self.population_size):
  158.  
  159.             # K-tournament for parents
  160.             mum, dad = self.select_parent(self.k), self.select_parent(self.k)
  161.             alice, bob = self.crossover(mum, dad)
  162.  
  163.             # Mate in an elite fashion according to the elitism_rate
  164.             if random.random() < self.elite_mating_rate:
  165.                 if alice.cost() < mum.cost() or alice.cost() < dad.cost():
  166.                     new_population.append(alice)
  167.                 if bob.cost() < mum.cost() or bob.cost() < dad.cost():
  168.                     new_population.append(bob)
  169.  
  170.             else:
  171.                 self.mutate(alice)
  172.                 self.mutate(bob)
  173.                 new_population += [alice, bob]
  174.  
  175.         # Add new population to old
  176.         self.population += new_population
  177.  
  178.         # Retain fittest
  179.         self.population = sorted(self.population, key=lambda t: t.cost())[0:self.population_size]
  180.  
  181.     def run(self, iterations):
  182.         """Runs the GA until a pair of consecutive tours differ in cost by epsilon"""
  183.         for _ in range(iterations):
  184.             self.evolve()
  185.  
  186.             # Replace least fit of population and replace with new random generated
  187.             # tours
  188.             retain = int((1-self.random_least_fit) * self.population_size)
  189.             to_add = self.population_size - retain
  190.             self.population = self.population[0:retain]
  191.             for _ in range(to_add):
  192.                 self.population.append(Tour(self.g))
  193.  
  194.     def best(self):
  195.         return min(self.population, key=lambda t: t.cost())
  196.  
  197. # Test on berlin52: http://e...content-available-to-author-only...b.de/pub/mp-testdata/tsp/tsplib/tsp/berlin52.tsp
  198. g = Graph([(565.0, 575.0), (25.0, 185.0), (345.0, 750.0), (945.0, 685.0), 
  199.            (845.0, 655.0), (880.0, 660.0), (25.0, 230.0), (525.0, 1000.0), 
  200.            (580.0, 1175.0), (650.0, 1130.0), (1605.0, 620.0), (1220.0, 580.0), 
  201.            (1465.0, 200.0), (1530.0, 5.0), (845.0, 680.0), (725.0, 370.0), 
  202.            (145.0, 665.0), (415.0, 635.0), (510.0, 875.0), (560.0, 365.0), 
  203.            (300.0, 465.0), (520.0, 585.0), (480.0, 415.0), (835.0, 625.0), 
  204.            (975.0, 580.0), (1215.0, 245.0), (1320.0, 315.0), (1250.0, 400.0), 
  205.            (660.0, 180.0), (410.0, 250.0), (420.0, 555.0), (575.0, 665.0), 
  206.            (1150.0, 1160.0), (700.0, 580.0), (685.0, 595.0), (685.0, 610.0), 
  207.            (770.0, 610.0), (795.0, 645.0), (720.0, 635.0), (760.0, 650.0), 
  208.            (475.0, 960.0), (95.0, 260.0), (875.0, 920.0), (700.0, 500.0), 
  209.            (555.0, 815.0), (830.0, 485.0), (1170.0, 65.0), (830.0, 610.0), 
  210.            (605.0, 625.0), (595.0, 360.0), (1340.0, 725.0), (1740.0, 245.0)])
  211.  
  212. # Population size 200, 8000 iterations
  213. ga = GeneticAlgorithm(g, 200)
  214. ga.run(8000)
  215.  
  216. best_tour = ga.best()
  217. g.plot(best_tour)
Time limit exceeded #stdin #stdout 15s 50184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oedbmG
language:
Python 3 nbc (python 3.7.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!