Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Applying a genetic algorithm to the travelling salesman problem
#!/usr/bin/env python
"""
This Python code is based on Java code by Lee Jacobson found in an article
entitled "Applying a genetic algorithm to the travelling salesman problem"
that can be found at: http://goo.gl/cJEY1
"""
import math
import random
class City:
def __init__(self, x=None, y=None):
self.x = None
self.y = None
if x is not None:
self.x = x
else:
self.x = int(random.random() * 200)
if y is not None:
self.y = y
else:
self.y = int(random.random() * 200)
def getX(self):
return self.x
def getY(self):
return self.y
def distanceTo(self, city):
xDistance = abs(self.getX() - city.getX())
yDistance = abs(self.getY() - city.getY())
distance = math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) )
return distance
def __repr__(self):
return str(self.getX()) + ", " + str(self.getY())
class TourManager:
destinationCities = []
def addCity(self, city):
self.destinationCities.append(city)
def getCity(self, index):
return self.destinationCities[index]
def numberOfCities(self):
return len(self.destinationCities)
class Tour:
def __init__(self, tourmanager, tour=None):
self.tourmanager = tourmanager
self.tour = []
self.fitness = 0.0
self.distance = 0
if tour is not None:
self.tour = tour
else:
for i in range(0, self.tourmanager.numberOfCities()):
self.tour.append(None)
def __len__(self):
return len(self.tour)
def __getitem__(self, index):
return self.tour[index]
def __setitem__(self, key, value):
self.tour[key] = value
def __repr__(self):
geneString = "|"
for i in range(0, self.tourSize()):
geneString += str(self.getCity(i)) + "|"
return geneString
def generateIndividual(self):
for cityIndex in range(0, self.tourmanager.numberOfCities()):
self.setCity(cityIndex, self.tourmanager.getCity(cityIndex))
random.shuffle(self.tour)
def getCity(self, tourPosition):
return self.tour[tourPosition]
def setCity(self, tourPosition, city):
self.tour[tourPosition] = city
self.fitness = 0.0
self.distance = 0
def getFitness(self):
if self.fitness == 0:
self.fitness = 1/float(self.getDistance())
return self.fitness
def getDistance(self):
if self.distance == 0:
tourDistance = 0
for cityIndex in range(0, self.tourSize()):
fromCity = self.getCity(cityIndex)
destinationCity = None
if cityIndex+1 < self.tourSize():
destinationCity = self.getCity(cityIndex+1)
else:
destinationCity = self.getCity(0)
tourDistance += fromCity.distanceTo(destinationCity)
self.distance = tourDistance
return self.distance
def tourSize(self):
return len(self.tour)
def containsCity(self, city):
return city in self.tour
class Population:
def __init__(self, tourmanager, populationSize, initialise):
self.tours = []
for i in range(0, populationSize):
self.tours.append(None)
if initialise:
for i in range(0, populationSize):
newTour = Tour(tourmanager)
newTour.generateIndividual()
self.saveTour(i, newTour)
def __setitem__(self, key, value):
self.tours[key] = value
def __getitem__(self, index):
return self.tours[index]
def saveTour(self, index, tour):
self.tours[index] = tour
def getTour(self, index):
return self.tours[index]
def getFittest(self):
fittest = self.tours[0]
for i in range(0, self.populationSize()):
if fittest.getFitness() <= self.getTour(i).getFitness():
fittest = self.getTour(i)
return fittest
def populationSize(self):
return len(self.tours)
class GA:
def __init__(self, tourmanager):
self.tourmanager = tourmanager
self.mutationRate = 0.015
self.tournamentSize = 5
self.elitism = True
def evolvePopulation(self, pop):
newPopulation = Population(self.tourmanager, pop.populationSize(), False)
elitismOffset = 0
if self.elitism:
newPopulation.saveTour(0, pop.getFittest())
elitismOffset = 1
for i in range(elitismOffset, newPopulation.populationSize()):
parent1 = self.tournamentSelection(pop)
parent2 = self.tournamentSelection(pop)
child = self.crossover(parent1, parent2)
newPopulation.saveTour(i, child)
for i in range(elitismOffset, newPopulation.populationSize()):
self.mutate(newPopulation.getTour(i))
return newPopulation
def crossover(self, parent1, parent2):
child = Tour(self.tourmanager)
startPos = int(random.random() * parent1.tourSize())
endPos = int(random.random() * parent1.tourSize())
for i in range(0, child.tourSize()):
if startPos < endPos and i > startPos and i < endPos:
child.setCity(i, parent1.getCity(i))
elif startPos > endPos:
if not (i < startPos and i > endPos):
child.setCity(i, parent1.getCity(i))
for i in range(0, parent2.tourSize()):
if not child.containsCity(parent2.getCity(i)):
for ii in range(0, child.tourSize()):
if child.getCity(ii) == None:
child.setCity(ii, parent2.getCity(i))
break
return child
def mutate(self, tour):
for tourPos1 in range(0, tour.tourSize()):
if random.random() < self.mutationRate:
tourPos2 = int(tour.tourSize() * random.random())
city1 = tour.getCity(tourPos1)
city2 = tour.getCity(tourPos2)
tour.setCity(tourPos2, city1)
tour.setCity(tourPos1, city2)
def tournamentSelection(self, pop):
tournament = Population(self.tourmanager, self.tournamentSize, False)
for i in range(0, self.tournamentSize):
randomId = int(random.random() * pop.populationSize())
tournament.saveTour(i, pop.getTour(randomId))
fittest = tournament.getFittest()
return fittest
if __name__ == '__main__':
tourmanager = TourManager()
# Create and add our cities
city = City(60, 200)
tourmanager.addCity(city)
city2 = City(180, 200)
tourmanager.addCity(city2)
city3 = City(80, 180)
tourmanager.addCity(city3)
city4 = City(140, 180)
tourmanager.addCity(city4)
city5 = City(20, 160)
tourmanager.addCity(city5)
city6 = City(100, 160)
tourmanager.addCity(city6)
city7 = City(200, 160)
tourmanager.addCity(city7)
city8 = City(140, 140)
tourmanager.addCity(city8)
city9 = City(40, 120)
tourmanager.addCity(city9)
city10 = City(100, 120)
tourmanager.addCity(city10)
city11 = City(180, 100)
tourmanager.addCity(city11)
city12 = City(60, 80)
tourmanager.addCity(city12)
city13 = City(120, 80)
tourmanager.addCity(city13)
city14 = City(180, 60)
tourmanager.addCity(city14)
city15 = City(20, 40)
tourmanager.addCity(city15)
city16 = City(100, 40)
tourmanager.addCity(city16)
city17 = City(200, 40)
tourmanager.addCity(city17)
city18 = City(20, 20)
tourmanager.addCity(city18)
city19 = City(60, 20)
tourmanager.addCity(city19)
city20 = City(160, 20)
tourmanager.addCity(city20)
# Initialize population
pop = Population(tourmanager, 50, True);
print "Initial distance: " + str(pop.getFittest().getDistance())
# Evolve population for 50 generations
ga = GA(tourmanager)
pop = ga.evolvePopulation(pop)
for i in range(0, 100):
pop = ga.evolvePopulation(pop)
# Print final results
print "Finished"
print "Final distance: " + str(pop.getFittest().getDistance())
print "Solution:"
print pop.getFittest()
@khadijahsaleh

This comment has been minimized.

Copy link

@khadijahsaleh khadijahsaleh commented May 27, 2014

may i use your code for my research? thank you very much if you allow me

@techniholic

This comment has been minimized.

Copy link

@techniholic techniholic commented Dec 13, 2014

I also feel happy to get a trial by this code, but I got an error with Anaconda (running with Python 2.7.8) at the initialization def init(self, x=None, y=None):

I am totally newbie, but need to compare two meta-heuristics, so any help is very very welcome.

@zhirzh

This comment has been minimized.

Copy link

@zhirzh zhirzh commented Dec 15, 2015

original post can be found here

@evanbrown88

This comment has been minimized.

Copy link

@evanbrown88 evanbrown88 commented Jun 28, 2016

I'm attempting to use this substituting geocodes for xy coordinates, and for a modified version of TSP where want the fastest tour but don't need to end up back at the starting node. Could this code be easily modified to achieve that?

@thiagomoretto

This comment has been minimized.

Copy link

@thiagomoretto thiagomoretto commented Aug 12, 2016

@evanbrown88 try adding a dummy node where the distance from/to starting node is 0 and the distance from/to for all other node (except the starting node one, of course) is infinity. Then, remove the dummy node.

@larsblumberg

This comment has been minimized.

Copy link

@larsblumberg larsblumberg commented Aug 1, 2017

@turbofart: The comment states # Evolve population for 50 generations but in fact, the population is evolving over 100 generations:

   for i in range(0, 100):
      pop = ga.evolvePopulation(pop)
@marleyas

This comment has been minimized.

Copy link

@marleyas marleyas commented Aug 3, 2018

Awesome solution!
This is a very nice code.

@zurimokato

This comment has been minimized.

Copy link

@zurimokato zurimokato commented Apr 18, 2019

very nice

@timtreis

This comment has been minimized.

Copy link

@timtreis timtreis commented May 3, 2019

Probably no longer relevant to @evanbrown88, but for others trying to achieve the same result:

Replace the getCity function (line 87,88) with the following:

   def getCity(self, tourPosition="last"):

      if tourPosition != "last":

         return self.tour[tourPosition]

      else:

         return self.tour[-1]

and then in line 109 call:

destinationCity = self.getCity("last")
@denizyigit

This comment has been minimized.

Copy link

@denizyigit denizyigit commented Mar 3, 2020

hello,
what if we wanted to make the maximum distance as a 9000, what should i change? thank you

@pablobarrios1

This comment has been minimized.

Copy link

@pablobarrios1 pablobarrios1 commented Mar 30, 2020

Hi! Im getting an invalid syntax on line 272

Initialize population

pop = Population (tourmanager, 50, True);
print "Initial distance: " + str(pop.getFittest().getDistance())

does anybody notice a mistake??

@Tayyab-Ilahi12

This comment has been minimized.

Copy link

@Tayyab-Ilahi12 Tayyab-Ilahi12 commented May 31, 2020

Hi! Im getting an invalid syntax on line 272

Initialize population

pop = Population (tourmanager, 50, True);
print "Initial distance: " + str(pop.getFittest().getDistance())

does anybody notice a mistake??

Hi, let me correct you that it is because of the python version difference. It is probably written in 2.7 version while you are trying to run it on 3.x .
So the code will be
print ("Initial distance: " + str(pop.getFittest().getDistance()))
The parentheses are mandatory in Python 3.x

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment