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:
:param float alpha: relative importance of pheromone (default=1)
:param float beta: relative importance of distance (default=3)
:param float rho: percent evaporation of pheromone (0..1, default=0.8)
:param float q: total pheromone deposited by each :class:`Ant` after
each iteration is complete (>0, default=1)
:param float t0: initial pheromone level along each :class:`Edge` of the
:class:`World` (>0, default=0.01)
:param int limit: number of iterations to perform (default=100)
:param float ant_count: how many :class:`Ant`\s will be used
(default=10)
:param float 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)]