The Travelling Salesman Problem (TSP) is one of the most famous problems in computer science for studying optimization, the objective is to find a complete route that connects all the nodes of a network, visiting them only once and returning to the starting point while minimizing the total distance of the route.
The problem of the traveling agent has an important variation, and this depends on whether the distances between one node and another are symmetric or not, that is, that the distance between A and B is equal to the distance between B and A, since in practice is very unlikely to be so.
The number of possible routes in a network is determined by the equation: (𝒏−𝟏)!
This means that in a network of 5 nodes the number of probable routes is equal to (5-1)! = 24, and as the number of nodes increases, the number of possible routes grows factorially.
In the case that the problem is symmetrical the number of possible routes is reduced to half:
( (𝒏−𝟏)! ) / 𝟐
The complexity of calculating the traveler's problem has sparked multiple initiatives to improve efficiency in route calculation. The most basic method is the one known by the name of ‘brute force’, which consists of the calculation of all possible routes, which becomes extremely inefficient and almost impossible in large networks. There are also heuristics that have been developed by the complexity in the calculation of optimal solutions in robust networks, that is why there are methods such as the nearest neighbor and the cheapest insertion.
Finally, we find algorithms that provide optimal solutions such as ACO algorithm. The basic idea underlying all the ant-based algorithm is to use a positive feedback mechanism based on the laying pheromone. The pheromone component allows the best solutions found to be kept in memory, which can be used to make up better solutions. To avoid stagnation of the algorithm a form of negative feedback is implemented through pheromone evaporation, but it must not evaporate too fast in order to make cooperation behavior emerge. In the TSP the goal is to find the tour with minimal length connecting 𝑛 given cities, and each city must be visited only once. The distance between cities can be defined by Euclidean distance or other distance functions. In the graph the cities would be the nodes and the connections between the cities are the edges of the graph. The graph does not need to be fully connected, all the nodes may not be connected to all the other nodes. And the distances may not be symmetric, distance 𝑖𝑗 may be different that distance 𝑗𝑖.
In order to solve the TSP using ACO the transitions of the ants from city to city depends on the following premises:
▪ Whether or not the city has already been visited. Each ant has a memory or tabu list to make sure each city is visited once per tour.
▪ The inverse of the distance between two nodes (visibility). Visibility is based on local information and represents the heuristic desirability of choosing city 𝑗 when in city 𝑖.
▪ The amount of virtual pheromone on the edges. It is a global type of information, represents the learned desirability of choosing city 𝑗 when in city 𝑖.
Other things to take into account are:
▪ The transition rule: the probability for an ant to go from city 𝑖 to city 𝑗 while building a tour.
▪ Pheromone decay: Without pheromone decay the algorithm would lead to amplification of the initial random fluctuation, that will produce not optimal solutions.
▪ Total number of ants: It is an important parameter since too many ants will reinforce not optimal solutions, while too few ants would not produce cooperative effect due to pheromone decay. It is suggested to use a number of ants equal to the number of cities in the graph.
CODE using Jupyter Notebook:
The problem of the traveling agent has an important variation, and this depends on whether the distances between one node and another are symmetric or not, that is, that the distance between A and B is equal to the distance between B and A, since in practice is very unlikely to be so.
The number of possible routes in a network is determined by the equation: (𝒏−𝟏)!
This means that in a network of 5 nodes the number of probable routes is equal to (5-1)! = 24, and as the number of nodes increases, the number of possible routes grows factorially.
In the case that the problem is symmetrical the number of possible routes is reduced to half:
( (𝒏−𝟏)! ) / 𝟐
The complexity of calculating the traveler's problem has sparked multiple initiatives to improve efficiency in route calculation. The most basic method is the one known by the name of ‘brute force’, which consists of the calculation of all possible routes, which becomes extremely inefficient and almost impossible in large networks. There are also heuristics that have been developed by the complexity in the calculation of optimal solutions in robust networks, that is why there are methods such as the nearest neighbor and the cheapest insertion.
Finally, we find algorithms that provide optimal solutions such as ACO algorithm. The basic idea underlying all the ant-based algorithm is to use a positive feedback mechanism based on the laying pheromone. The pheromone component allows the best solutions found to be kept in memory, which can be used to make up better solutions. To avoid stagnation of the algorithm a form of negative feedback is implemented through pheromone evaporation, but it must not evaporate too fast in order to make cooperation behavior emerge. In the TSP the goal is to find the tour with minimal length connecting 𝑛 given cities, and each city must be visited only once. The distance between cities can be defined by Euclidean distance or other distance functions. In the graph the cities would be the nodes and the connections between the cities are the edges of the graph. The graph does not need to be fully connected, all the nodes may not be connected to all the other nodes. And the distances may not be symmetric, distance 𝑖𝑗 may be different that distance 𝑗𝑖.
In order to solve the TSP using ACO the transitions of the ants from city to city depends on the following premises:
▪ Whether or not the city has already been visited. Each ant has a memory or tabu list to make sure each city is visited once per tour.
▪ The inverse of the distance between two nodes (visibility). Visibility is based on local information and represents the heuristic desirability of choosing city 𝑗 when in city 𝑖.
▪ The amount of virtual pheromone on the edges. It is a global type of information, represents the learned desirability of choosing city 𝑗 when in city 𝑖.
Other things to take into account are:
▪ The transition rule: the probability for an ant to go from city 𝑖 to city 𝑗 while building a tour.
▪ Pheromone decay: Without pheromone decay the algorithm would lead to amplification of the initial random fluctuation, that will produce not optimal solutions.
▪ Total number of ants: It is an important parameter since too many ants will reinforce not optimal solutions, while too few ants would not produce cooperative effect due to pheromone decay. It is suggested to use a number of ants equal to the number of cities in the graph.
CODE using Jupyter Notebook:
!pip install ACO-Pants
import pants
import math
import random
import pandas as pd
import numpy as np
cities = pd.read_csv('C:/Desktop/BLOG/worldcities.csv', decimal=".")
USAcities = cities.loc[cities['country'] == 'United States of America'] #only the cities that belong to USA
print('Dimention USAcities:', UScities.shape) #dimention of USAcities dataset
UScities = USAcities.sample(100) #to get a sample of 100 rows to work with
print('Dimention UScities:', UScities.shape) #dimention UScities dataset
UScities.head() #fisrt rows from the new dataset
def euclidean(a, b):
return math.sqrt(pow(a[1] - b[1], 2) + pow(a[0] - b[0], 2))
x = UScities['lat']
y = UScities['lng']
DD = list(zip(x,y)) #UScities represented in decimal degrees
print(DD)
#Here we will use a number of ants less than number of nodes (N= 5).
#Number of iterations L = 5 instead of 100.
#Alpha and beta with the same relative importance (A, B = 1)
world = pants.World(DD, euclidean, N = 5, L = 5 , A = 1, B = 1)
solver = pants.Solver()
solution = solver.solve(world)
print('DISTANCE:', solution.distance) #total distance of the tour performed
tour = solution.tour #nodes visited in order
print(tour)
UScities.set_index(['lat','lng'])['city'].loc[tour].tolist()
#Here we will use a number of ants bigger than the number of nodes (N= 100).
#Number of iterations L = 150.
#Alpha and beta with the different relative importance, distance (beta) will be more importat. (A = 2, B = 3)
world = pants.World(DD, euclidean, N = 150, L = 150 , A = 2, B = 3)
solver = pants.Solver()
solution = solver.solve(world)
print('DISTANCE:', solution.distance) #total distance of the tour performed
tour1 = solution.tour #nodes visited in order
print(tour1)
UScities.set_index(['lat','lng'])['city'].loc[tour1].tolist()