Genetic Algorithm

This notebook contains a simple implementation of a genetric algorithm (GA) to solve the Travelling Salesman Problem.

GAs belong to the family of evolutionary metaheuristics, which are based on the "survival of the fittest". Each solution is represented by a chromosome, which consists of a sequence of genes that represent a solution to the problem.

GAs operate upon a population of solutions, which are manipulated over several iterations, which are called generations.

Better solutions are progressively identified, as the algorithm pairs parent chromosomes to produce offspring, or applies random mutations on previously generated chromosomes.

There are 5 main steps to the GA process after we initialise the parameters:

  1. Population generation - where a randomised population of chromosomes (a one-dimensional string of real values) is generated.
  2. Fitness evaluation - where the fitness of all chromosomes in the population is calculated
  3. Parent selection - where certain chromosomes are selected to be carried over to the next generation based on elitism
  4. Crossover - where sections of the best parent chromosomes are combines to create offspring
  5. Mutation - where the chromosomes are tweaked to get a new solution

When the population has converged (where the offspring are not significantly different to the parents), the algorithm can be terminated.

We will be using Distributed Evolutionary Algorithms in Python (DEAP) library.

We will first create a map of the 15 homes with two centres using make_blobs. The function of make_blob from sklearn (or scikit-learn) allows to create spatially normally distributed points with given number of centres.

For this example, we will set two clusters and the standard deviation of the cluster to be 20 based on the random generator seed of 2. By setting a value for the random_state parameter, the results can be reproduced for future comparison of the results.

We will then calculate the distances between the homes within the created map. The Euclidean distance gives us the length of the line segment between two points. These distances will form as an input to our genetic algorithm.

We now have:

Using the DEAP library, we will solve our travelling salesman problem using genetic algorithm.

We will create the necessary functions to solve our problem.

Firstly, we will need to create our population of chromosomes. The function to achieve this, is the following:

We also need a generic function that will evaluate the overall distance the travelling salesperson will be covering based on the current route to be able to compare between each iteration.

The second step of GA is to evaluate the fitness of all chromosomes in the population. We can use the embedded functions from the DEAP library.

Now that we have set up the necessary functions, we will start with our solver.

Before we start, we need to initialise the parameters for the genetic algorithm to function. We are specifying the solution population size, number of generations, the crossover probability, and the mutation probability.

Step 1: We will generate our population. Using the function chromo_create we wrote above, we will create the population based on the home IDs we created in the beginning. We then will need to register all this information to our Toolbox.

Step 2: We will calculate the fitness of all chromosomes in the population.

We create a for-loop to iterate for the number of generations we set in our initialisation.

We will plot the fitness level for each generation to see if the population has converged after the limited number of generations we have set.

We can see the population has converged!

So we will now print the best solution for the tour route ofor Santa Claus to cover all 15 homes the quickest and return to his origin.

We will create a plot to see what such route would look like.