Ant Colony Optimization¶

Ant colony optimization is a class of optimization algorithm that uses a probabilistic way of finding shortest paths. It seeks to replicate the behaviour of real-world ant navigation, where ants leave pheremones when returning from food-gathering trips.

Because these pheremones evaporate over time, shorter paths tend to maintain stronger pheremone traces, and thus are favoured by outbound ants looking for food. As more and more ants use these shorter paths, the pheremone trace becomes stronger. This produces a reinforcing effect favouring optimal solutions.

import osmnx
from smart_mobility_utilities.common import Node, cost
from smart_mobility_utilities.viz import draw_route
import random
from tqdm.notebook import tqdm
import matplotlib.pyplot as plt

reference = (43.661667, -79.395)

G = osmnx.graph_from_point(reference, dist=300, clean_periphery=True, simplify=True)

origin = Node(graph=G, osmid=55808290)
destination = Node(graph=G, osmid=389677909)

highlighted = [389677909, 55808290]

# marking both the source and destination node

nc = ['red' if node in highlighted else '#336699' for node in G.nodes()]
ns = [50 if node in highlighted else 8 for node in G.nodes()]
fig, ax = osmnx.plot_graph(G, node_size=ns, node_color=nc, node_zorder=2)


Our Ant Colony algorithm will follow these steps:

1. We generate $$n$$ number of ants to fill our population, and place them all at the origin point (the colony).

2. We initialize the pheromone concentrations to random values, to seed the graph.

3. For each ant, the following procedures are followed:

• The ant examines all the edges leading to neighbouring nodes, and probabilistically chooses an edge to travel based on pheromone levels. If one of the neighbouring nodes is the destination (the food source), the ant overrides this probability and goes straight for the destination.

• If the ant is stuck, it retraces its steps back to a previous node with unexplored neighbours.

• The ant now retraces its route, and deposits pheromone on the route, weighted inversely to the edge length.

• If the route is a newly discovered route, we add it to our list of all known routes.

4. The route that is most frequented by the ants is selected as the “best” solution.

# Initialize the parameter

# Alpha and Beta are used in the pheremone calculation
alpha = 2
beta = 2

n = 500
Q = 1 # factor for post-route pheremone increase

pheremone_concentrations = dict()
known_routes = dict()

# randomize the pheromones
pheremone_concentrations = {(u,v):random.uniform(0,0.5) for [u,v] in G.edges()}

# a function to calculate pheremone levels
def pheremone(level, distance, alpha, beta):
return level ** alpha * ((1/distance)) ** beta

for ant in tqdm(range(n)):
# Place the ant at the colony
frontier = [origin]
explored = set()
route = []
found = False

parent = frontier.pop(0)

children = []
children_pheremones = []
for child in parent.expand():
# If we see the destination, ignore all pheremones
if child == destination:
found = True
route = child.path()
continue
if child not in explored:
children.append(child)
children_pheremones.append(
pheremone(
pheremone_concentrations[(parent.osmid, child.osmid)],
child.distance,
alpha,
beta,
)
)

if len(children) == 0:
continue  # The ant is stuck, go back.

transition_probability = [
children_pheremones[i] / sum(children_pheremones)
for i in range(len(children_pheremones))
]

# Probabilistically choose a child to explore based weighted by transition probability
chosen = random.choices(children, weights=transition_probability, k=1)[0]

# Add all the non-explored children in case we need to explore them later
children.pop(children.index(chosen))
frontier.extend(children)

# Set the chosen child to be the next node to explore
frontier.insert(0, chosen)

# We now have a completed route, we can increase pheremone levels
# on that route for the next ant to detect.

for u, v in zip(route[:-1], route[1:]):
length_of_edge = G[u][v][0]['length']
pheremone_concentrations[(u,v)] += Q/length_of_edge

# If the route is newly discovered, add it to the list
route = tuple(route)
if route in known_routes:
known_routes[route] += 1
else:
known_routes[route] = 1

best_route = max(known_routes, key=known_routes.get)
times_used = known_routes[best_route]

route = list(best_route)
print("Cost:", cost(G,route))
print("Times used:",times_used)
draw_route(G,route)

Cost: 1241.759
Times used: 350

costs = [cost(G,r) for r in known_routes]
used = list(known_routes.values())

costs, used = zip(*sorted(zip(costs,used)))

plt.plot(costs, used)
plt.xlabel('Solution cost')
plt.ylabel('Times travelled')
plt.show()


As we can see, the most travelled route has a lower cost, as the pheremones from that route are reinforced by each subsequent ant.