The Travelling Salesperson Problem

This notebook has been adapted from a Pyevolve example.

The travelling salesperson problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city. It is a special case of the travelling purchaser problem.

The code below shows the use of Pyevolve to solve the TSP. Images of the intermediate and final solutions are stored in the 'tspimg' folder.

Your tasks are:

Add the necessary statements for storing the results in a database named 'tsp.db' with identifier 'ex1'.
For the maximum grade: modify the code to solve the problem with the ATT 48 dataset, a set of 48 cities (US state capitals) from TSPLIB. Store the results in a database named 'tsp_att48.db' with identifier 'ex1'. For your information, the optimal cost is 10648.



In [ ]:

    
from pyevolve import G1DList
from pyevolve import GSimpleGA
from pyevolve import Crossovers
from pyevolve import Consts

import random
from math import sqrt
from PIL import Image, ImageDraw, ImageFont



In [ ]:

    
cm     = []
coords = []
CITIES = 30
WIDTH   = 600
HEIGHT  = 400
LAST_SCORE = -1



In [ ]:

    
def cartesian_matrix(coords):
    """ A distance matrix """
    matrix={}
    for i,(x1,y1) in enumerate(coords):
        for j,(x2,y2) in enumerate(coords):
            dx, dy = x1-x2, y1-y2
            dist=sqrt(dx*dx + dy*dy)
            matrix[i,j] = dist
    return matrix



In [ ]:

    
def tour_length(matrix, tour):
    """ Returns the total length of the tour """
    total = 0
    t = tour.getInternalList()
    for i in range(CITIES):
        j      = (i+1)%CITIES
        total += matrix[t[i], t[j]]
    return total



In [ ]:

    
def write_tour_to_img(coords, tour, img_file):
    """ The function to plot the graph """
    padding=20
    coords=[(x+padding,y+padding) for (x,y) in coords]
    maxx,maxy=0,0
    for x,y in coords:
        maxx, maxy = max(x,maxx), max(y,maxy)
    maxx+=padding
    maxy+=padding
    img=Image.new("RGB",(int(maxx),int(maxy)),color=(255,255,255))
    font=ImageFont.load_default()
    d=ImageDraw.Draw(img);
    num_cities=len(tour)
    for i in range(num_cities):
        j=(i+1)%num_cities
        city_i=tour[i]
        city_j=tour[j]
        x1,y1=coords[city_i]
        x2,y2=coords[city_j]
        d.line((int(x1),int(y1),int(x2),int(y2)),fill=(0,0,0))
        d.text((int(x1)+7,int(y1)-5),str(i),font=font,fill=(32,32,32))

    for x,y in coords:
        x,y=int(x),int(y)
        d.ellipse((x-5,y-5,x+5,y+5),outline=(0,0,0),fill=(196,196,196))
    del d
    img.save(img_file, "PNG")
    print "The plot was saved into the %s file." % (img_file,)



In [ ]:

    
def G1DListTSPInitializator(genome, **args):
    """ The initializator for the TSP """
    lst = [i for i in xrange(genome.getListSize())]
    random.shuffle(lst)
    genome.setInternalList(lst)



In [ ]:

    
def evolve_callback(ga_engine):
    global LAST_SCORE
    if ga_engine.getCurrentGeneration() % 100 == 0:
        best = ga_engine.bestIndividual()
        if LAST_SCORE != best.getRawScore():
            write_tour_to_img( coords, best, "tspimg/tsp_result_%05d.png" % ga_engine.getCurrentGeneration())
            LAST_SCORE = best.getRawScore()
    return False



In [ ]:

    
coords = [(random.randint(0, WIDTH), random.randint(0, HEIGHT))
             for i in xrange(CITIES)]
cm     = cartesian_matrix(coords)



In [ ]:

    
genome = G1DList.G1DList(len(coords))
genome.evaluator.set(lambda chromosome: tour_length(cm, chromosome))
genome.crossover.set(Crossovers.G1DListCrossoverEdge)
genome.initializator.set(G1DListTSPInitializator)



In [ ]:

    
ga = GSimpleGA.GSimpleGA(genome)
ga.setGenerations(2000)
ga.setMinimax(Consts.minimaxType["minimize"])
ga.setCrossoverRate(1.0)
ga.setMutationRate(0.02)
ga.setPopulationSize(80)
ga.stepCallback.set(evolve_callback)



In [ ]:

    
ga.evolve(freq_stats=200)
best = ga.bestIndividual()
write_tour_to_img(coords, best, "tspimg/tsp_result.png")

You can check now the results by plotting some graphs of the evolution process in this notebook.