1 """TravelingSalesmanProblem solving using GeneticAlgorithm
   2 """
   3 
   4 import random, math
   5 
   6 class Map:
   7     def __init__(self):
   8         self.distanceMap = \
   9                 [[ 0, 10, 20, 30, 40, 50], 
  10                  [10,  0,  9, 40, 25, 15], 
  11                  [20,  9,  0, 32,  9, 41], 
  12                  [30, 40, 32,  0, 39,  5],  
  13                  [40, 25,  9, 39,  0, 27], 
  14                  [50, 15, 41,  5, 27,  0]]
  15 
  16     def getDistanceBetweenTwoCities(self, aCity1, aCity2):
  17         return self.distanceMap[aCity1-1][aCity2-1]
  18 
  19     def getDistance(self, aPath):
  20         i = 0
  21         sum = 0
  22         for eachCity in aPath:
  23             if i == len(aPath)-1:
  24                 break
  25 	    city1 = aPath[i]
  26 	    city2 = aPath[i+1]
  27             sum += self.getDistanceBetweenTwoCities(city1, city2)
  28             i += 1
  29         return sum
  30 
  31 class RealMap(Map):
  32     def __init__(self, numOfCities=6):
  33         self.addressOfCities = {}
  34         for eachCityNum in range(numOfCities):
  35             cityname = eachCityNum + 1
  36 	    xpos = random.uniform(0,100)
  37 	    ypos = random.uniform(0,100)
  38 	    self.addressOfCities[cityname] = (xpos, ypos)
  39 
  40     def getCities(self):
  41         return self.addressOfCities
  42 
  43     def getAddressOfCity(self, aCityName):
  44     	return self.addressOfCities[aCityName]
  45 
  46     def getDistanceBetweenTwoCities(self, aCity1, aCity2):
  47         ad1 = self.getAddressOfCity(aCity1)
  48 	ad2 = self.getAddressOfCity(aCity2)
  49         return math.sqrt((ad1[0] - ad2[0])**2 + (ad1[1] - ad2[1])**2)
  50 
  51     def loadMap(self, aMapOfDict):
  52         self.addressOfCities = aMapOfDict
  53     	
  54 
  55 def encode(aCityPath):
  56     ordinalrep = []
  57     aPathcopy = range(1,100)
  58     for eachCity in aCityPath:
  59         index = aPathcopy.index(eachCity) + 1
  60         aPathcopy.remove(eachCity)
  61         ordinalrep.append(index)
  62     return ordinalrep
  63 
  64 def decode(aOrdinalRep):
  65     citypath = []
  66     replist = range(1,100)
  67     for eachIndex in aOrdinalRep:
  68         eachCity = replist[eachIndex - 1]
  69         citypath.append(eachCity)
  70         replist.remove(eachCity)
  71     return citypath
  72 	
  73 def crossover(p1, p2, xpoint):
  74     encodedp1, encodedp2 = encode(p1), encode(p2)
  75     newep1 = encodedp1[:xpoint] + encodedp2[xpoint:]
  76     newep2 = encodedp2[:xpoint] + encodedp1[xpoint:]
  77     return decode(newep1), decode(newep2)
  78 
  79 def getPermutation(aList):
  80     if len(aList)<=1:
  81             return [aList]
  82     p=[]
  83     for eachElement in aList:
  84             theRest=aList[:]
  85             theRest.remove(eachElement)
  86             for eachPerm in getPermutation(theRest):
  87                     p.append([eachElement]+eachPerm)
  88     return p
  89     
  90 def perms(list): 
  91     if not list: return [[]] 
  92     return [[list[i]] + p for i in range(len(list)) 
  93         for p in perms(list[:i] + list[i+1:])] 
  94         
  95 def getOptima():
  96     cities=[1,2,3,4,5,6]
  97     allRoutes=getPermutation(cities)
  98     myMap = Map()
  99     l=[]
 100     for eachRoute in allRoutes:
 101         l.append(myMap.getDistance(eachRoute))
 102     return max(l),min(l),allRoutes[l.index(max(l))],allRoutes[l.index(min(l))]