**Ant Colony Optimization** is an old but still often applied **construction heuristic** to develop solutions using nature inspired behavior. The heuristic mimics the behavior of ants when finding shortest paths to between their nests and some kind of attraction, i.e. a food-source.

The main idea are the pheromone trails, which ants leave behind, when travelling a certain path. Shorter paths to the same source will show higher visiting frequencies and therefore show higher pheromone concentrations. If ants have to decide which way to take, they would most prbably choose one with a higher concentration than a lower one.

## What do I need?

**Here **we want to show** how to calculate a Minimim Spanning Tree (MST) **for a **TSP **problem instance **using Ant Colony Optimization **(ACO) in python. The only thing you need is a working python IDE – I’m using pyCharm from jetbrains – of your favour and the packages pants, math, random and pandas installed.

Here you can find some TSP problem instances to play around with the ACO heuristic.

```
import pants
import math
import random
import pandas as pd
# Ant colony optimization for TSP
# documentation see here: https://pypi.org/project/ACO-Pants/
def euclidean(a, b):
return math.sqrt(pow(a[1] - b[1], 2) + pow(a[0] - b[0], 2))
def main():
dat = pd.read_csv("./data/TSP_Instances/pr1002.tsp", sep='\t', skiprows=2, names=['nodeId', 'lat', 'lng'])
nodes = [tuple(x) for x in dat.to_numpy()]
# nodes.append((dat.lat.array, dat.lng.array, dat.nodeId.array))
world = pants.World(nodes, euclidean)
solver = pants.Solver()
solution = solver.solve(world)
print(solution.distance)
print(solution.tour) # Nodes visited in order
print(solution.path) # Edges taken in order
# Press the green button in the gutter to run the script.
if __name__ == '__main__':
main()
```

The script shows you how to construct the world based on the TSP instance loaded from the CSV. There are quite a lot of parameters you can submit to the pant – framework. The following list shows the params available for the pants.Solver() constructor:

:paramfloat alpha: relative importance of pheromone (default=1):paramfloat beta: relative importance of distance (default=3):paramfloat rho: percent evaporation of pheromone (0..1, default=0.8):paramfloat q: total pheromone deposited by each :class:`Ant` aftereach iteration is complete (>0, default=1):paramfloat t0: initial pheromone level along each :class:`Edge` of the:class:`World` (>0, default=0.01):paramint limit: number of iterations to perform (default=100):paramfloat ant_count: how many :class:`Ant`\s will be used(default=10):paramfloat elite: multiplier of the pheromone deposited by the elite:class:`Ant` (default=0.5)

By launching the ACO with the berlin52 TSP instance, I found the following solution for the Minimum Spanning Tree:

3763.2463665383325[(50, 1340, 725), (26, 1320, 315), (27, 1250, 400), (25, 1215, 245), (11, 1220, 580), (46, 1170, 65), (32, 1150, 1160), (42, 875, 920), (47, 830, 610), (45, 830, 485), (36, 770, 610), (39, 760, 650), (33, 700, 580), (43, 700, 500), (34, 685, 595), (35, 685, 610), (28, 660, 180), (9, 650, 1130), (48, 605, 625), (8, 580, 1175), (0, 565, 575), (19, 560, 365), (44, 555, 815), (18, 510, 875), (21, 520, 585), (7, 525, 1000), (30, 420, 555), (29, 410, 250), (17, 415, 635), (2, 345, 750), (20, 300, 465), (6, 25, 230), (1, 25, 185), (41, 95, 260), (16, 145, 665), (22, 480, 415), (40, 475, 960), (31, 575, 665), (49, 595, 360), (38, 720, 635), (15, 725, 370), (37, 795, 645), (23, 835, 625), (14, 845, 680), (4, 845, 655), (5, 880, 660), (3, 945, 685), (24, 975, 580), (51, 1740, 245), (10, 1605, 620), (13, 1530, 5), (12, 1465, 200)]