The Genetic Algorithm and The Travelling Salesman Problem

So far all of my blog posts have revolved around widgets, flutter, Open Source, and software development. But this time I am taking a different direction, it's about an algorithm I studied as part of my master's course work Artificial Intelligence. I have had the privilege to study many different algorithms throughout my academics and work and have used them day in and day out, But I find this algorithm fascinating, and interesting for its nature, It is inspired by the phenomenon of Natural selection. The same phenomenon on which evolution is based. Brace yourself because this will be a lengthy blog post and probably difficult to understand, But I will try my best to keep things simple.

Introduction

Genetic Algorithm is a problem-solving strategy inspired by the way living things evolve and adapt over time. It's a computer-based method used to find good solutions to HARD problems, especially when finding the very best answer is really hard. Going forward I will clarify what exactly I meant by HARD problems.

We have all heard the popular phrase "Survival of the Fittest"

species of animals and plants that are best adapted to their environment survive and reproduce, while those that are less well adapted die out.

We understand this fittest theory in terms of evolution and you will see this behavior being perfectly applied in the genetic algorithm for the Travelling Salesman problem. The concept will evolve as you read along and everything will start to make sense, This is not Philosophy this is Evolution.

The Problem

So what exactly is The Traveling Salesman Problem (TSP)?

The problem states

Given a list of cities 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?

This problem is not as straightforward as it sounds, This is an NP-hard problem meaning there is no standard polynomial time algorithm that would solve every instance of this problem. In simple terms, as the number of cities increases it gets exponentially difficult and time-consuming to find a solution to this problem. Hence the Genetic Algorithm (A solution to this Optimization Problem).

The Algorithm

The above problem described can be solved using the genetic algorithm, This algorithm guarantees a solution that is close to the optimal but not necessarily optimal. It uses a stochastic approach to reach the near-optimal solution. I found a simple yet easy-to-understand analogy to understand this algorithm. I confess this analogy is not mine but it helps explain genetic algorithms in simple words.

"Finding the Best Recipe Imagine you're trying to find the best recipe to make a delicious sandwich. You have lots of ingredients (like bread, cheese, meat, veggies), but you're not sure which combination is the tastiest.

Here's how a genetic algorithm could help:

1. Create Recipes: First, you make a bunch of different sandwich recipes by randomly mixing ingredients. These recipes are like solutions to your sandwich problem.

2. Taste Test: You taste each sandwich and give them a score based on how yummy they are. Higher scores mean better-tasting sandwiches.

3. Mix Recipes: Now, you take the recipes (sandwiches) with the best scores and mix them together. You combine the recipes to create new ones.

4. Add a Twist: Sometimes, you make tiny changes in the new recipes to keep things interesting. This is like adding a pinch of creativity or randomness.

5. Repeat: You repeat these steps many times, keeping the best recipes and making new ones. Over time, the sandwiches get tastier and tastier because you're always choosing the best ones and mixing them.

6. Yummiest Sandwich: After doing this for a while, you end up with a super yummy sandwich recipe because the genetic algorithm keeps improving the recipes based on what tastes best."

Similarly, we apply the GA to the Travelling Salesman problem. Let's understand the algorithm steps before we dive into solving the problem. Before that, it is important to clarify some of the terms that might be confusing.

'Population' denotes the collection of paths (with a size of populationSize), and terms such as 'parent' and 'offspring' refer to individual elements within this population, specifically referring to a path of cities, And genes refer to each individual city within this path.

1. Initialization: Create an initial set of population(paths) of possible solutions. Each population(path) represents a possible route that visits all cities exactly once with the start and end city being the same.
2. Fitness Calculation: Evaluate the fitness of each path. The fitness is determined by the total distance of the route. Shorter routes have higher fitness.
3. Selection: Select parents from the current population based on their fitness. The higher-fitness population should have a higher chance of being selected.
4. Crossover: Apply crossover (recombination) to the selected parents to create offspring. This can be done using various crossover techniques such as order crossover, partially mapped crossover, or cycle crossover.
5. Mutation: Apply mutation to the offspring. This involves making small random changes to some of the genes (cities) in the population.
6. Replacement: Replace the old population with the combined population of parents and offspring.
7. Termination: We repeat steps 2–6 for a certain number of generations or until a stopping criterion is met (e.g. a sufficiently good solution is found or if we have iterated the number of generations).

Implementation

Now that we have these steps to solve this problem in place, Let's take a problem instance to understand this better. Do not worry if the above steps do not make any sense. The problem instance we will discuss will help us go through each step in detail and make things clear. This problem instance is from my coursework assignment. (I swear this blog is being posted after the assignment's due date 🙂.)

Our Goal here is to find the shortest path among these 10 cities such that we start from City A, visit every city exactly once, and return back to City A with the shortest path.

Screenshot of the deployed app

A graph of 10 Cities along with their coordinatesWe are given with coordinates of these 10 cities as shown on the above scale e.g. A (X: 100, Y: 300) B (X: 200, Y: 130) C (X: 300, Y: 500), and so on.

We will start by implementing a Graph data structure to store this data and some helper functions that will help us along the way.

In the above Graph class following are the class members

• nodes_len is the number of nodes that will be stored in a graph

• roots is a dictionary that acts as an adjacency matrix to store the connections of nodes in a graph.

• nodes is a dictionary that stores the coordinates of the node

• start_city a configurable field to choose the start city in our TSP

• directed decides whether the graph is directed or not.

  and the member functions

• addEdge: is a function that takes two nodes and a weight (distance) between two nodes

• addNode: is a function that takes a node and the coordinates of the node (x,y)

• distance: A helper function to calculate the distance between two nodes

• vertices: A helper function to return the list of nodes in the graph Note that addEdge and addNode both are only added for convenience if we have distance between each pair of cities we can directly use addEdge.

  Now let's implement the Genetic Algorithm Class

I will explain these class members in short here, if you find difficulty understanding the below terms that's totally fine. It is not uncommon to not understand them at this point, it will only get clearer when we look at each step of the algorithm in detail.

• population_size: Determines the possible number of solutions to the problem in each generation which will be optimized further to obtain a near-optimal solution.
• generations: The number of generations/iterations the algorithm should go through. Each generation involves the evaluation of the fitness of individuals in the population, the selection of parents for reproduction, crossover, mutation, and the creation of a new population.
• tournamentSize: The tournament size is the number of individuals participating in each tournament during tournament selection during the crossover.
• mutationRate: The mutation rate is a parameter that determines the likelihood of mutation occurring for each gene.
• fit_selection_rate: This parameter represents the rate or proportion of the fittest individuals(shortest path is fittest) in the population that will be directly carried over to the next generation without undergoing crossover or mutation. It's a form of elitism, preserving some of the best solutions.

The program begins here in find_fittest_path we will leave this method here for our reference and go through this method one step at a time to get a clear picture.

we start by first generating a list of random cities (The list of possible solutions) for our TSP. Note that I am calling it a possible solution, As I mentioned above this is an optimization problem, generation 1 may/may not have the near-optimal solution. If it does, then it will be carried forward (Survival of the fittest) to newPopulation and if it doesn't then the new offspring generated from the fittest parents will give rise to the near-optimal solution. Let's go through the steps of the algorithm we defined above

Initialization

The randomizeCities method is responsible for generating a list of initial populations. It works in a way that it randomizes all the vertices except the start*city and then appends the start_city at the beginning and end of the generated population. Remember in TSP the salesman must return to the _original city (start city).

The output at the end of the code shows the output generated by this function

The output at the end of the code shows the output generated by this functionOnce we have generated the initial population, Our next work would be to select the fittest population and retain them as part of Generation 1. Each generation must have a population of population_size

But the question is

How many fits to select from the population and What exactly do we mean by fit?

In the context of the Travelling Salesman problem, fitness is basically the distance of the path (in other problems it would mean different e.g. in the Sandwich recipe the taste score given to each sandwich implies the fitness value). We intend to achieve the shortest path in TSP. So, the population with the shortest path would be deemed fit. And to select the number of fits we have already defined a fit factor called fit_selection_rate (in the range 0-1) to avoid overflow).

Fitness Calculation

So we calculate the fitness of our entire population using computeFitness and add the number_of_fits_to_carryover number of population from the current generation to newPopulation.  But the newPopulation we generate in each generation must have a population of size population_size. So the remaining population (population_size - number_of_fits_to_carryover) will be generated in our next step of the algorithm using crossover and mutation.

Selection

CrossOver is a process to produce offspring by combining the traits of parents. But,

How do we decide which parents to select for crossover?

We do this with the help of Tournament selection, This is the selection step in GA that determines which parents to select from the existing population for reproduction, This is an important step since selecting the right parent ensures the fit traits/genes are passed on to the next generation. Tournament Selection is a commonly used method for selecting the parents who will participate in the tournament. 

This step is pretty much simple, we run a tournament among a subset of the population (of tournamentSize). This subset is randomly selected and the tournament selection is executed multiple times until the number of parents participating in the crossover are selected. The selection criteria is basically to select the most fit individual among the subset of the population.

Crossover

Now Once we have two parents participating in crossover we need to decide how the crossover takes place to produce the offspring that is as fit as its parents. The idea of crossover is to select genes from both parents and add them to the offspring ensuring the genes in the offspring are unique. The goal is to generate diverse offspring with a combination of genetic material from both parents, potentially leading to improved solutions in the search space. There are multiple methods of crossover such as partially mapped crossover, order crossover, etc with one-point and multiple-point crossovers.

1. Partially Mapped CrossOver (PMX)

Let's say we have these two parents from the Tournament selection

Parents participating in Crossover

Parents participating in Crossoverand we want them to cross over to produce offspring. The steps for this cross-over are

1. Select the points to cross over we can choose a single point or two points to divide the array into halves, let's select two points for our case the choice of selection is random (computed using computeTwoPointIndexes method in the source code)

Two-point indexes to copy the genes to offspring

2. Copy the genes between the two points from parent 1 to the offspring at the same location as the parent

genes copied from parent 1 to Offspring

3. Look for genes that have not been copied in the corresponding segment of parent 2, starting at the first position in the crossover point. Gene I is the first uncopied Gene from parent 2( …, I, B, F, …) Copy I to Offspring at the location where E appears in Parent 2.

The next gene in (… I, B, F … ) is B, but since it is already present in Offspring we will skip it,

The next gene is F, It should be copied to the position occupied by B in parent 2, But that position is already occupied by C in the Offspring, so F will be copied to the position occupied by C in parent 2.

With this change, our Offspring will be

4. The remaining elements of offspring are copied from parent 2 in the same order as they appear in parent 2.

The final Offspring generated after crossover is 'IGHECBFDJ'

2. Order Crossover (OX1) : The order crossover is simpler than partially mapped crossover we choose multipoint crossover indexes generally more than two. We will choose two cross-over indexes for simplicity and choose the same example as the previous

Parents Participating in Order Crossover

1. Select the points to cross over we must choose two or more points to divide the array into multiple halves. We will select the same indexes for simplicity, the choice of selection is random.

Two-point indexes to copy the genes to offspring

2. Copy the genes within the crossover indexes to Offspring in the same position as they appear in parent 1

3. Now for each element in Parent 2 copy the missing genes to Offspring in the same order as they appear. e.g. The first element not present in Offspring from parent 2 is G so G appears in the first position of Offspring, the second missing element is H so it appears next, and so on. So the newly generated Offspring is

Generated Offspring after Order Crossover

coming back to our implementation we will use Order Crossover to keep things simple.

Notice the crossover implementation we are keeping the Offspring_length short by 2 to eliminate start_city from the start and end of the path. And adding it back once the offspring is generated (before return).

Mutation

The last step of the Genetic Algorithm for the current generation is Mutation, The idea of mutation is to make some random changes in the genes of the new Offspring. The primary purpose of mutation is to maintain diversity in the population. Without mutation, the genetic algorithm might get stuck with a local optimum where all individuals are quite similar.

And then for each iteration, we replace our old population with newPopulation obtained to achieve a better solution with every iteration. But there will be a point where the algorithm will converge even after introducing randomness in mutation, meaning Further iterations/generations cannot give a better solution so we stop the generations with the converged solution.

Output

Putting it all together we will get the following output

The smaller values of population size and generations are only used to keep the output short

If you have made it to the end thank you so much for reading, hope this algorithm helped you understand the genetic algorithm and more importantly it gave you an idea of how it can be used to solve hard problems.

You can find the complete source code for this problem here.

Thanks for reading!