Traveling Salesperson Problem

Some days ago, I wrote blog about knapsack problem.
Next I tried to solve traveling salesperson problem(TSP).

The problem is : “Given a list of cites and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city ?”. It is an NP-hard problem. -from wiki-
Following code uses genetic algorithm to solve it.
Each cities positions(X,Y) are represented as complex. And define some function for calculation.
All tours are permutation of possible combination. It will be huge number if I use large number of cities.

import matplotlib.pyplot as plt
import matplotlib.colors as colors
import matplotlib.cm as cmx
import itertools, operator
import time
import random
import numpy, math
random.seed( 789 )
def exact_TSP( cities ):
    return shortest( alltours( cities ) )
def shortest( tours ):
    return min( tours, key = total_distance )
alltours = itertools.permutations
def total_distance( tour ):
    return sum( distance( tour[i], tour[i-1] ) for i in range( len(tour) ) )
City = complex
def generate_cities( n ):
    return set( City( random.randrange(10,890),
                                 random.randrange( 10,590) ) for i in range( n) )

Next I defined parameters for GA.
numpy.random.permutation returns random order permutation of given length.
Initial individual has random order for traveling.
Evaluate function calculate total distance of travel and GA will minimize the distance.

from deap import algorithms, base, creator, tools
from deap.tools import initIterate
num_cities  = 30
cities = generate_cities( num_cities )
toolbox = base.Toolbox()
creator.create( "FitnessMin", base.Fitness, weights=( -1.0, ) )
creator.create( "Individual", list, fitness = creator.FitnessMin )
toolbox.register( "indices", numpy.random.permutation, len( cities ) )
toolbox.register( "individual", initIterate, creator.Individual, toolbox.indices )
toolbox.register( "population", tools.initRepeat, list, toolbox.individual )
toolbox.register( "mate", tools.cxOrdered )
toolbox.register( "mutate", tools.mutShuffleIndexes, indpb=0.05 )
def create_tour( individual ):
    return [ list(cities) [e] for e in individual ]
def evaluation( individual ):
    return ( total_distance( create_tour( individual ) ), )

Next step. Set evaluator and selector, run code.

toolbox.register("evaluate", evaluation)
toolbox.register("select", tools.selTournament, tournsize=3)
%%time
res, log = algorithms.eaSimple( pop, toolbox,
                                                        cxpb = 0.8,
                                                        mutpb=0.2,
                                                        ngen=400, verbose=False)
>>> CPU times: user 5.38 s, sys: 9.52 ms, total: 5.39 s
>>>Wall time: 5.39 s

best_individual = tools.selBest(res, k=1)[0]
print('Fitness of the best individual: ', evaluation(best_individual)[0])
>>>Fitness of the best individual:  3558.4312378302448

The route seems cross. But better route than my choice.
Next, I will try to multi knapsack problem.
fig

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s