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.
$> pip install -r requirements.txt
How to run:
$> python3 main.py [--city_count ] [--population_size ] [--survival_rate ] [--mating_rate ] [--gene_mutation_rate ]
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
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
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.
Submitted by Rhushabh Gedam (Rhushabh1)
Download packets of source code on Coders Packet