For now, let\'s just think about how to set up such a problem. One of the most c
ID: 3738029 • Letter: F
Question
For now, let's just think about how to set up such a problem. One of the most challenging aspects of the Traveling Salesperson Problem is that there are many steps involved and you will need to break it down into pieces. For now, here are your tasks: Write a function that takes as input the number of cities, N. For now we will not use real cities, so within the function create the locations of N cities using random numbers. For convenience, you can just assume that the cities fall on a map in the rangex E [0, 1] and y E [0,1. Every city will have a random (x, y) location in that range Return from the function the coordinates of the N cities as two arrays (x values and y values) Call the function and store those returned array in some variables. Then, Make a plot to be sure it is working. You should get something that looks like this (with points in different locations, of course): 10 0.8 0.6 0.41 0.2 0.0 0.0 020.4 0.6 0.8Explanation / Answer
here is the code for the above stated problem, travelling salesman problem in python,
import random
import math
import getopt
import sys
import GeneticAlgorithm
#........ Number of cities.............
citiesN = 10
# ........................x & y range for positions.........................
width = 250
height = 250
# .........................Config for Generic Algorithm.........................
population = 3
generations = 150
crossoverChance = 0.7
mutationChance = 0.5
class Route(GeneticAlgorithm.SolutionCandidate):
def __init__(self, cities):
self.cities = cities
def _distance(self, city1, city2):
""".....................Calculate the distance between two cities......................"""
return math.hypot(city2[0] - city1[0],
city2[1] - city1[1])
def getLen(self):
"""...................Calculate the length of the route.................."""
return sum([self._distance(self.cities[i-1],self.cities[i])
for i in range(len(self.cities))])
def getFitness(self):
return 1 / pow(self.getLen(), 2)
def crossover(self, route):
"""Take a cross-section of this instance and swap it with a cross-section of route."""
x1 = len(self.cities) / 3
x2 = x1 * 2
routes = [self.cities, route.cities]
crossParts = [r[x1:x2] for r in routes]
crossParts.reverse()
for i in range(len(routes)):
route = routes[i]
cross = crossParts[i]
for j in range(x1) + range(x2, len(route)):
while route[j] in cross:
route[j] = crossParts[i-1][cross.index(route[j])]
for j in range(x1,x2):
route[j] = cross[j-x1]
def mutate(self):
"""........................Swap two cities......................"""
index1 = random.randint(0, len(self.cities) - 1)
index2 = random.randint(0, len(self.cities) - 1)
n = self.cities[index1]
self.cities[index1] = self.cities[index2]
self.cities[index2] = n
def copy(self):
return Route(self.cities[:])
def createMap(self):
""".......................Generate a svg image with the given route......................"""
left = min([pos[0] for pos in self.cities]) - 5
right = max([pos[0] for pos in self.cities])
top = min([pos[1] for pos in self.cities]) - 5
bottom = max([pos[1] for pos in self.cities])
width = right - left + 5
height = bottom - top + 5
ret += '<polygon fill="none" stroke="currentColor" points="' +
" ".join([str(pos[0] - left) + "," + str(pos[1] - top)
for pos in self.cities]) +
'"/>' + " "
ret += '<g fill="#f00">' + " "
for pos in self.cities:
ret += ' <circle cx="' +
str(pos[0] - left) + '" cy="' +
str(pos[1] - top) + '" r="5"/>' + " "
ret += "</g></svg> "
return ret
class RandomRouteFactory(GeneticAlgorithm.SolutionCandidateFactory):
def __init__(self, cities):
self.cities = cities
def generate(self):
cities = self.cities[:]
random.shuffle(cities)
return Route(cities)
def usage ():
print "Usage tsp.py [-h -r -i image.svg]"
def generateRandomCities(n, width, height):
return [[random.randint(0,width),
random.randint(0,height)] for x in range(n)]
def parseCities(args):
cities = []
for arg in args:
arg = arg.split(',')
if len(arg) == 2:
cities.append([int(arg[0]), int(arg[1])])
return cities
def writeMap(mapFile, route):
f = open(mapFile, 'w')
f.write(route.createMap())
f.close()
cityPositions = []
mapFile = False
opts, args = getopt.getopt(sys.argv[1:], "hri:")
for opt, value in opts:
if opt == '-h':
usage()
exit()
elif opt == '-r':
cityPositions = generateRandomCities(citiesN, width, height)
elif opt == '-i':
mapFile = value
if cityPositions == []:
cityPositions = parseCities(args)
if cityPositions == []:
usage()
exit(1)
generator = RandomRouteFactory(cityPositions)
ga = GeneticAlgorithm.GeneticAlgorithm(generator,
crossoverChance,
mutationChance,
population)
print "Gen. Avg. Best"
for i in range(generations):
ga.evolve()
lengths = [route.getLen() for route in ga.getSolutions()]
print i + 1," ",
int(sum(lengths) / len(lengths))," ",
int(min(lengths))
shortest = ga.getBestSolution()
print "Shortest route: " + " ".join([str(pos[0]) + "," + str(pos[1])
for pos in shortest.cities])
if mapFile != False:
writeMap(mapFile, shortest)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.