Traveling Salesman Problem (TSP) using Genetic Algorithm (Python)
Traveling Salesman Problem
For decades, the Traveling Salesman Problem (TSP) has been an intriguing challenge for mathematicians, computer scientists, and operations researchers. It involves determining the shortest route for a salesman to take to visit a set of cities and return to the starting point. As the number of cities increases, the complexity of the problem grows exponentially, which is known as a combinatorial explosion. Solutions for the TSP have been attempted through a variety of algorithms and techniques, such as dynamic programming, branch-and-bound, genetic algorithms, and simulated annealing.
The computational complexity of algorithms for solving the Traveling Salesman Problem (TSP) can vary significantly depending on the approach used. Here’s a brief overview of some common algorithms and their complexities:
| Algorithm | Approach | Complexity |
|-----------------------|--------------------------|--------------------|
| Brute Force | Exact | O(n!) |
| Dynamic Programming | Exact | O(n^2 * 2^n) |
| Branch and Bound | Exact | O(n!) |
| Genetic Algorithms | Heuristic | Depends on params |The brute-force approach exhaustively explores all possible permutations of cities to find the optimal solution.
For a TSP with “n” cities, there are (n-1) choices for the second city, (n-2) choices for the third city, and so on until there is only one choice left for the last city. The total number of permutations is calculated as the factorial of (n-1), denoted as (n-1)!. For example, if there are 5 cities (n=5), the number of permutations is (5–1)! = 4! = 4 x 3 x 2 x 1 = 24. Since the salesman must return to the starting city to complete the tour. Therefore, after calculating the number of permutations, we multiply it by “n” to account for starting the tour from each of the “n” cities. In the example with 5 cities, we have 24 permutations for each starting city, resulting in a total of 24 x 5 = 120 possible tours to evaluate.
The time complexity is determined by the total number of permutations. Since the number of permutations is (n-1)! * n, the time complexity of the brute force method to solve the TSP is O((n-1)! * n) which can be simplified to O(n!).
Genetic Algorithms involve a heuristic process based on the concept of natural selection. These algorithms may not deliver the best possible solution, but they can quickly identify good approximations. It is difficult to estimate the amount of time it takes to complete a genetic algorithm since it is dependent on population size, number of generations, and other factors.
It is important to be aware that the Traveling Salesman Problem is an NP-hard problem, meaning no algorithm that is polynomial-time has been found to solve it. This is why the algorithms discussed above are either exact yet slow for larger instances or heuristic, providing close-to-accurate solutions quickly. This has caused the TSP to be a very interesting and difficult issue in the realm of computational optimization, causing scientists to keep on developing more effective and precise algorithms.
In this article, we shall discuss the solution of the TSP using genetic algorithms in detail.
Genetic Algorithms (GAs):
Genetic algorithms are a type of evolutionary algorithm inspired by the processes of natural selection and genetics. They are widely used for optimization and search problems. The main components of a genetic algorithm include:
Population
The optimization problem is composed of an array of possible solutions, known as a “population”. Every single solution is symbolized as a “chromosome” or “individual”. The population changes over time, and its quantity and variety can affect the effectiveness of the algorithm.
def initial_population(cities_list, n_population = 250):
"""
Generating initial population of cities randomly selected from all
possible permutations of the given cities
Input:
1- Cities list
2. Number of population
Output:
Generated lists of cities
"""
population_perms = []
possible_perms = list(permutations(cities_list))
random_ids = random.sample(range(0,len(possible_perms)),n_population))
for i in random_ids:
population_perms.append(list(possible_perms[i]))
return population_permsThe above function would initialize the required number of individuals, which together form the algorithm's initial population. Please note that each individual in our case is a probable solution, which means that each individual is a sequence of cities without any repetition, as the traveling salesman should not pass any city twice while completing his or her journey. One individual example could be: [Gliwice, Cairo, Rome, Krakow, Paris, Alexandria, Berlin, Tokyo, Hong Kong, Rio]
As each individual is a probable solution, we need to evaluate this solution’s performance by measuring the total distance traveled by the salesman, as the distance traveled is the only metric that undergoes optimization in our example under the assumption that the lines or edges connecting the cities are straight lines and there are no better roads than the others. In real life, roads are not built in straight lines; some are wider than others, and some have traffic. These restrictions can be translated into time or the duration of the journey, but for simplicity, the only metric we’re optimizing for here is the total distance.
def dist_two_cities(city_1, city_2):
"""
Calculating the distance between two cities
Input:
1- City one name
2- City two name
Output:
Calculated Euclidean distance between two cities
"""
city_1_coords = city_coords[city_1]
city_2_coords = city_coords[city_2]
return np.sqrt(np.sum((np.array(city_1_coords) - np.array(city_2_coords))**2))The above function calculates the Euclidean distance between two cities, which is the length of the edge connecting the two cities together.
def total_dist_individual(individual):
"""
Calculating the total distance traveled by individual,
one individual means one possible solution (1 permutation)
Input:
1- Individual list of cities
Output:
Total distance traveled
"""
total_dist = 0
for i in range(0, len(individual)):
if(i == len(individual) - 1):
total_dist += dist_two_cities(individual[i], individual[0])
else:
total_dist += dist_two_cities(individual[i], individual[i+1])
return total_distThis function calculates the total distance traveled by a single individual by utilizing the function that calculates the distance between two cities.
As of now, we can assess the performance of each individual, which is a potential solution to the problem. If we generate all the probable solutions to the problem and measure the total distance traveled by each solution (individual), we then have a winner which is the individual with the least traveled distance. However, we would need enormous computational power and time as the complexity of the problem increases significantly as the number of cities increases. This approach of assessing the performance of all the potential solutions is called the brute force approach. In our example, we only generated a few individuals to start our GA optimization with.
Fitness Function
The fitness function assesses the quality of each individual in the population, assessing how well each potential solution solves the problem. This function guides the search process by giving higher scores to better solutions.
def fitness_prob(population):
"""
Calculating the fitness probability
Input:
1- Population
Output:
Population fitness probability
"""
total_dist_all_individuals = []
for i in range (0, len(population)):
total_dist_all_individuals.append(total_dist_individual(population[i]))
max_population_cost = max(total_dist_all_individuals)
population_fitness = max_population_cost - total_dist_all_individuals
population_fitness_sum = sum(population_fitness)
population_fitness_probs = population_fitness / population_fitness_sum
return population_fitness_probsThis function converts the total distance traveled by an individual in the population into a probability. This can facilitate the next step of selecting the best-fit individuals.
Selection
In the selection process, individuals with higher fitness values have a higher probability of being chosen for reproduction. This is an emulation of the concept of “the strong prevail” from natural selection, where those with beneficial features have a greater likelihood of passing down their genes to the next generation. The selection approach used in this example is Roullette Wheel Selection.
def roulette_wheel(population, fitness_probs):
"""
Implement a selection strategy based on proportionate roulette wheel
Selection.
Input:
1- population
2: fitness probabilities
Output:
selected individual
"""
population_fitness_probs_cumsum = fitness_probs.cumsum()
bool_prob_array = population_fitness_probs_cumsum < np.random.uniform(0,1,1)
selected_individual_index = len(bool_prob_array[bool_prob_array == True]) - 1
return population[selected_individual_index]
When selecting an individual based on its fitness, a random number between 0 and 1 is generated from a uniform distribution and this generated number will be used to select a certain individual. If the individual has a higher fitness, then it’s more likely to cover a bigger area as shown in the above circle. The uniform distribution to draw a number is used because, at this point, we don’t want to favor one individual over another but rather let their fitness probabilities give them a higher or lower chance of being chosen. In the above animation, it is clear that those with greater fitness are more likely to be selected. However, that does not mean that those who are less fit will never be chosen.
Crossover
Crossover is the process of creating new individuals by combining genetic information from two or more parent individuals. It emulates the genetic recombination that occurs during sexual reproduction in biology. Crossover points are selected on the parent chromosomes, and the genetic material is exchanged to create new offspring.
def crossover(parent_1, parent_2):
"""
Implement mating strategy using simple crossover between two parents
Input:
1- parent 1
2- parent 2
Output:
1- offspring 1
2- offspring 2
"""
n_cities_cut = len(cities_names) - 1
cut = round(random.uniform(1, n_cities_cut))
offspring_1 = []
offspring_2 = []
offspring_1 = parent_1 [0:cut]
offspring_1 += [city for city in parent_2 if city is not in offspring_1]
offspring_2 = parent_2 [0:cut]
offspring_2 += [city for city in parent_1 if city is not in offspring_2]
return offspring_1, offspring_2Here is the part where the selected individuals are mating or mixing to generate new ones (offspring). For example, if we have two individuals with 10 elements each, we can take the first 3 elements from the first individual and the last 7 elements from the second individual. Generally Selecting a subset of elements from one individual and the remaining elements from the other, ensuring that no duplicate elements are taken from the first individual. Choosing the number of offspring produced by each pair of parents can be considered part of the population management process. Additionally, the selection of how many elements to take from the first individual can be randomized using a uniform distribution. Although this choice might not have a specific philosophy behind it, using the uniform distribution ensures higher variability in the selection process, enabling the genetic algorithm to explore a more diverse set of solutions.
Mutation
Mutation introduces small random changes to the genetic information of individuals. It helps introduce new genetic material into the population, promoting exploration of the search space and preventing premature convergence to suboptimal solutions.
def mutation(offspring):
"""
Implement mutation strategy in a single offspring
Input:
1- offspring individual
Output:
1- mutated offspring individual
"""
n_cities_cut = len(cities_names) - 1
index_1 = round(random.uniform(0,n_cities_cut))
index_2 = round(random.uniform(0,n_cities_cut))
temp = offspring [index_1]
offspring[index_1] = offspring[index_2]
offspring[index_2] = temp
return(offspring)In this code snippet, the mutation process is implemented using a straightforward switching step. A random element is selected, and it is swapped with another element which is also chosen randomly. This simple switching process enables the genetic algorithm to introduce mutation to selected individuals.
The mutation rate (The percentage of individuals that will experience mutation) can have a huge influence on the outcome and the optimization procedure. The two animations featured above demonstrate the impact of a high and low mutation rate before optimization is applied. In this case, what is happening is the sole influence of mutation, without taking into account the rest of the optimization process.
Replacement
Once selection, crossover, and mutation have occurred, the newly generated individuals (offspring) replace some of the original population. This replacement tactic ensures the population is maintained at a fixed size between generations, which is also a component of population management techniques.
By iteratively applying these components, genetic algorithms explore the search space, gradually improving the quality of solutions over generations. Through selection, crossover, and mutation, the algorithm can efficiently converge towards optimal or near-optimal solutions.
GA Algorithm Parameters
Population Size: The population size defines the number of candidate solutions (individuals) present in each generation. A larger population size increases the diversity of the population, promoting exploration of the search space. However, it also leads to increased computation time. Finding the right balance is essential to striking a trade-off between exploration and exploitation.
Crossover Rate: The crossover rate defines the probability of applying crossover (recombination) to create new offspring from selected parent individuals. Crossover helps combine beneficial traits from different parents and is crucial for exploration and maintaining diversity in the population.
Mutation Rate: The mutation rate determines the probability of introducing random changes to the genetic information of individual chromosomes. Mutation aids in exploration, allowing the algorithm to escape local optima. However, setting a mutation rate too high can lead to excessive exploration and divergence from good solutions.
Number of Generations: The number of generations determines how many iterations or cycles the genetic algorithm will run. Each generation produces a new set of individuals through selection, crossover, and mutation. A higher number of generations generally allows more time for the algorithm to explore the search space thoroughly.
Termination Criteria: The termination criteria determine when the genetic algorithm stops running. Common termination criteria include reaching a maximum number of generations, finding a satisfactory solution, or reaching a predefined fitness level. Proper termination criteria help avoid unnecessary computation and improve efficiency.
n_population = 250
crossover_per = 0.8
mutation_per = 0.2
n_generations = 200In the given code snippet, the algorithm parameters are specified as follows: The population size is set to 250 individuals. After the selection process, 80% of the selected individuals will undergo crossover, while only 20% of the resulting offspring will undergo mutation. The algorithm is set to terminate after 200 generations, meaning that the entire process, including selection, crossover, and mutation, will be repeated 200 times in an attempt to achieve convergence.
Cities Coordinates
x = [0,3,6,7,15,10,16,5,8,1.5]
y = [1,2,1,4.5,-1,2.5,11,6,9,12]
cities_names = ["Gliwice", "Cairo", "Rome", "Krakow", "Paris",
"Alexandria", "Berlin", "Tokyo", "Hong Kong", "Rio"]
city_coords = dict(zip(cities_names, zip(x, y)))In the above code snippet, the cities are represented using (x, y) coordinates, where each pair (x, y) corresponds to a point on the Cartesian plane. It’s important to note that in real-world applications, cities are typically represented using longitude and latitude coordinates. Also, the city names used in this example are for illustration purposes only and do not reflect the actual distances between these cities but were chosen purely for the convenience of this demonstration. The last line of code creates a dictionary where each city name is the dictionary key and the corresponding (x, y) coordinates are the dictionary value.
Putting it all together
import matplotlib.pyplot as plt
from itertools import permutations and combinations
from random import shuffle
import random
import numpy as np
import statistics
import pandas as pd
import seaborn as SNs
These are the important libraries used in this example.
def run_ga(cities_names, n_population, n_generations,
crossover_per, mutation_per):
population = initial_population(cities_names, n_population)
fitness_probs = fitness_prob(population)
parents_list = []
for i in range(0, int(crossover_per * n_population)):
parents_list.append(roulette_wheel(population,
fitness_probs))
offspring_list = []
for i in range(0,len(parents_list), 2):
offspring_1, offspring_2 = crossover(parents_list[i],
parents_list[i+1])
# print(offspring_1)
# print(offspring_2)
# print()
mutate_threashold = random.random()
if(mutate_threashold > (1-mutation_per)):
offspring_1 = mutation(offspring_1)
# print("Offspring 1 mutated", offspring_1)
mutate_threashold = random.random()
if(mutate_threashold > (1-mutation_per)):
offspring_2 = mutation(offspring_2)
# print("Offspring 2 mutated", offspring_2)
offspring_list.append(offspring_1)
offspring_list.append(offspring_2)
mixed_offspring = parents_list + offspring_list
fitness_probs = fitness_prob(mixed_offspring)
sorted_fitness_indices = np.argsort(fitness_probs)[::-1]
best_fitness_indices = sorted_fitness_indices[0:n_population]
best_mixed_offsrping = []
for i in best_fitness_indices:
best_mixed_offsrping.append(mixed_offspring[i])
for i in range(0, n_generations):
# if (i%10 == 0):
# print("Generation: ", i)
fitness_probs = fitness_prob(best_mixed_offsrping)
parents_list = []
for i in range(0, int(crossover_per * n_population)):
parents_list.append(roulette_wheel(best_mixed_offsrping,
fitness_probs))
offspring_list = []
for i in range(0,len(parents_list), 2):
offspring_1, offspring_2 = crossover(parents_list[i],
parents_list[i+1])
mutate_threashold = random.random()
if(mutate_threashold > (1-mutation_per)):
offspring_1 = mutation(offspring_1)
mutate_threashold = random.random()
if(mutate_threashold > (1-mutation_per)):
offspring_2 = mutation(offspring_2)
offspring_list.append(offspring_1)
offspring_list.append(offspring_2)
mixed_offspring = parents_list + offspring_list
fitness_probs = fitness_prob(mixed_offspring)
sorted_fitness_indices = np.argsort(fitness_probs)[::-1]
best_fitness_indices = sorted_fitness_indices[0:int(0.8*n_population)]
best_mixed_offsrping = []
for i in best_fitness_indices:
best_mixed_offsrping.append(mixed_offspring[i])
old_population_indices = [random.randint(0, (n_population - 1))
for j in range(int(0.2*n_population))]
for i in old_population_indices:
# print(i)
best_mixed_offsrping.append(population[i])
random.shuffle(best_mixed_offsrping)
return best_mixed_offsrpingThe above function performs the algorithm’s steps in the following order:
- Initialize the population
- Calculates fitness of individuals
- Applies Roullette Wheel selection method to individuals
- Performs crossover between selected individuals
- Performs mutation on the resulting offspring
- Replaces a subset of the old population with new offspring (Replacement)
- Shuffles the new population and returns it
- Repeat for number of generations and terminate
best_mixed_offsrping = run_ga(cities_names, n_population,
n_generations, crossover_per, mutation_per)
total_dist_all_individuals = []
for i in range(0, n_population):
total_dist_all_individuals.append(total_dist_individual(best_mixed_offsrping[i]))
index_minimum = np.argmin(total_dist_all_individuals)
minimum_distance = min(total_dist_all_individuals)
shortest_path = best_mixed_offsrping[index_minimum]
In the above code snippet, the algorithm is being executed with the specified inputs, the least distance that an individual has traveled is set in the minimum_distance variable as well as the path traversed to reach this distance.
The minimum_distance and the optimal solution is 61.137
The shortest path is: Cairo → Gliwice → Tokyo → Rio → Hong Kong → Berlin → Paris → Alexandria → Krakow → Rome → Cairo
Optimum Solution Visualization
x_shortest = []
y_shortest = []
for city in shortest_path:
x_value, y_value = city_coords[city]
x_shortest.append(x_value)
y_shortest.append(y_value)
x_shortest.append(x_shortest[0])
y_shortest.append(y_shortest[0])
fig, ax = plt.subplots()
ax.plot(x_shortest, y_shortest, '--go', label='Best Route', linewidth=2.5)
plt.legend()
for i in range(len(x)):
for j in range(i + 1, len(x)):
ax.plot([x[i], x[j]], [y[i], y[j]], 'k-', alpha=0.09, linewidth=1)
plt.title(label="TSP Best Route Using GA",
fontsize=25,
color="k")
str_params = '\n'+str(n_generations)+' Generations\n'+str(n_population)+' Population Size\n'+str(crossover_per)+' Crossover\n'+str(mutation_per)+' Mutation'
plt.suptitle("Total Distance Travelled: "+
str(round(minimum_distance, 3)) +
str_params, fontsize=18, y = 1.047)
for i, txt in enumerate(shortest_path):
ax.annotate(str(i+1)+ "- " + txt, (x_shortest[i], y_shortest[i]), fontsize= 20)
fig.set_size_inches(16, 12)
# plt.grid(color='k', linestyle='dotted')
plt.savefig('solution.png')
plt.show()
Convergence Analysis
As demonstrated in the animation, the GA achieved convergence in far fewer generations than expected, as 200 generations was the initial assumed maximum. However, it is essential to adjust the number of generations to reach the best and most speedy outcomes.
In some situations, a genetic algorithm can become trapped in a local minimum, hindering its ability to find the global optimum. To address this, the mutation rate becomes a valuable parameter as it introduces random changes that aid in escaping local minima. However, while mutation can be effective in exploring new areas, excessive mutation can lead to divergence, as seen in the above animation, even after reaching a promising solution. Consequently, the selection of algorithm parameters becomes crucial in dealing with such challenges. Finding the right set of parameters is essential for achieving a stable, fast, and near-optimal solution. This process of searching for the best parameter configuration is vital to maximizing the algorithm’s performance and ensuring it converges efficiently towards the global minimum.
Conclusion
In conclusion, the application of genetic algorithms to solve the Traveling Salesman Problem (TSP) has proven to be a powerful and flexible approach. The algorithm operates by mimicking the principles of natural selection, employing components such as population, fitness evaluation, selection, crossover, and mutation. These mechanisms enable the genetic algorithm to explore the vast search space efficiently and gradually converge towards optimal or near-optimal solutions.
However, the success of a genetic algorithm in solving the TSP heavily depends on the careful selection of its parameters. The most critical parameters include population size, mutation rate, crossover rate, and the number of generations. Each of these parameters influences the algorithm’s behavior and performance in distinctive ways. For instance, a larger population size promotes exploration but increases computation time, while a higher mutation rate helps escape local minima but might lead to divergence if set excessively.
Finding the right balance among these parameters becomes critical to achieving the best performance. An unsuitable parameter configuration can lead to bad performance, trapping the algorithm in suboptimal solutions, or excessive exploration that prolongs the optimization process unnecessarily.
Hence, researchers and practitioners must conduct thorough parameter tuning to identify the optimal combination for their specific GA instances. This process often involves experimentation and iterative refinement to strike a balance between exploration and exploitation. By selecting appropriate parameters, the genetic algorithm can efficiently explore the search space, escape local minima, and converge towards a stable, near-optimal solution in a timely manner.
GAs provide a robust and adaptable approach for solving the TSP, and their effectiveness is highly dependent on skillful parameter selection. By understanding the impact of each parameter, researchers can control the algorithm’s potential to tackle complex real-world traveling salesman scenarios effectively. As the field of optimization continues to evolve, refining genetic algorithms’ parameters will remain a critical aspect of maximizing their performance and relevance in solving a wide range of combinatorial optimization problems.
Please find the full code here:
👏 Clap for the story if you liked it.
❓ Feel free to drop your question in the comments.
