Coders Packet

Travelling Salesperson Problem using Genetic Algorithm in Python

By Rhushabh Gedam

Travelling Salesperson Problem is a NP-Hard problem. Genetic Algorithms attempt to solve this problem using the Darwin's law of natural selection and survival of the fittest.

Installation:

$> pip install -r requirements.txt

How to run:

$> python3 main.py [--city_count ] [--population_size ] [--survival_rate ] [--mating_rate ] [--gene_mutation_rate ]

where cnt = number of cities in the problem,
pop_size = population size of the salespersons (individuals),
survive = fraction of the fittest population to survive till the next generation,
mate = fraction of population to mate and create new child offsprings,
mutate = fraction to mutation introduced in the gene of the offspring while mating individuals

Algorithm Details:

After generating the city map and setting up the hyperparameters, the algorithm starts off by generating a random population of salespersons. Each salesperson is modelled as an individual with a genomic sequence or gene. This sequence denotes the order in which the individual visits the cities. Fitness of the individual is the distance travelled by the individual. Lesser the distance travelled, more fit the individual is.

To generate a new population out of the current one, we select top fittest individuals (based on SURVIVAL_RATE) to survive till the next generation and fill up the rest of the population by mating among the remaining individuals. Mutations are introduced randomly during mating based on the GENE_MUTATION_RATE.

Once we find the most fittest individual (one who finds the optimal solution to the problem), we stop iterating over generations and the program terminates. If we don't find the optimal solution within 300 generations, we terminate prematurely.

Download project

Reviews Report

Submitted by Rhushabh Gedam (Rhushabh1)

Download packets of source code on Coders Packet