turbofart · August 22, 2012 20:06 · Aug 23, 2012 · Aug 23, 2012 · Aug 22, 2012
diff --git a/tsp.py b/tsp.py
@@ -14,11 +14,11 @@ class City:
    def __init__(self, x=None, y=None):
       self.x = None
       self.y = None
-      if x:
+      if x is not None:
          self.x = x
       else:
          self.x = int(random.random() * 200)
-      if y:
+      if y is not None:
          self.y = y
       else:
          self.y = int(random.random() * 200)
@@ -58,7 +58,7 @@ def __init__(self, tourmanager, tour=None):
       self.tour = []
       self.fitness = 0.0
       self.distance = 0
-      if tour:
+      if tour is not None:
          self.tour = tour
       else:
          for i in range(0, self.tourmanager.numberOfCities()):

diff --git a/tsp.py b/tsp.py
@@ -11,9 +11,6 @@
 
 
 class City:
-   x = None
-   y = None
-
    def __init__(self, x=None, y=None):
       self.x = None
       self.y = None
@@ -56,11 +53,6 @@ def numberOfCities(self):
 
 
 class Tour:
-   tourmanager = None
-   tour = []
-   fitness = 0.0
-   distance = 0
-
    def __init__(self, tourmanager, tour=None):
       self.tourmanager = tourmanager
       self.tour = []
@@ -127,8 +119,6 @@ def containsCity(self, city):
 
 
 class Population:
-   tours = []
-
    def __init__(self, tourmanager, populationSize, initialise):
       self.tours = []
       for i in range(0, populationSize):
@@ -164,11 +154,6 @@ def populationSize(self):
 
 
 class GA:
-   tourmanager = None
-   mutationRate = 0.015
-   tournamentSize = 5
-   elitism = True
-
    def __init__(self, tourmanager):
       self.tourmanager = tourmanager
       self.mutationRate = 0.015

diff --git a/tsp.py b/tsp.py
@@ -0,0 +1,300 @@
+#!/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:
+   x = None
+   y = None
+
+   def __init__(self, x=None, y=None):
+      self.x = None
+      self.y = None
+      if x:
+         self.x = x
+      else:
+         self.x = int(random.random() * 200)
+      if y:
+         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:
+   tourmanager = None
+   tour = []
+   fitness = 0.0
+   distance = 0
+
+   def __init__(self, tourmanager, tour=None):
+      self.tourmanager = tourmanager
+      self.tour = []
+      self.fitness = 0.0
+      self.distance = 0
+      if tour:
+         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:
+   tours = []
+
+   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:
+   tourmanager = None
+   mutationRate = 0.015
+   tournamentSize = 5
+   elitism = True
+
+   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()
+
No results found