Ant Colony Optimization in Action
Welcome back! In my previous post, I introduced the fundamentals of Ant Colony Optimization (ACO). In this installment, we'll delve into implementing the ACO algorithm from scratch to tackle two distinct problem types.
The problems we'll be addressing are the Traveling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP). Why these two? Well, the TSP is a classic challenge, and ACO happens to be an effective algorithm for finding the most cost-efficient path through a graph. On the other hand, the Quadratic Assignment Problem represents a different class of problems related to optimizing the arrangement of items, and in this post, I aim to demonstrate that ACO can be a valuable tool for solving such assignment-related problems as well. This versatility makes the ACO algorithm applicable to a wide range of problems. Finally, I'll share some tips for achieving improved solutions more rapidly.
Traveling Salesman Problem
TSP is straightforward to describe but can pose a significant challenge in finding a solution. Here's the basic definition: you're tasked with discovering the shortest route that visits all nodes in a graph. This problem falls into the category of NP-hard problems, which implies that if you attempt to explore all possible routes, it can take an impractical amount of time to find the solution. Instead, a more effective approach is to seek a high-quality solution within a reasonable timeframe, and that's precisely what we'll accomplish using ACO.
Problem Definition
With the following code, we can create a TSP instance with a given number of nodes:
import itertools
import math
import random
from typing import Tuple
import networkx as nx
import networkx.algorithms.shortest_paths.dense as nxalg
class TSP:
"""
Creates a TSP problem with a certain number of nodes
"""
def __init__(self, nodes: int = 30, dimensions: Tuple[int, int] = (1000, 1000), seed: int = 5):
if seed:
random.seed(seed)
graph = nx.Graph()
nodes_dict = dict()
for i in range(nodes):
nodes_dict[i] = (random.randint(0, dimensions[0]), random.randint(0, dimensions[1]))
graph.add_node(i)
for i, j in itertools.permutations(range(nodes), 2):
graph.add_edge(i, j, weight=self.calculate_distance(nodes_dict[i], nodes_dict[j]))
self.graph = graph
self.nodes = nodes_dict
self.distance_matrix = nxalg.floyd_warshall_numpy(graph)
@staticmethod
def calculate_distance(i, j):
"""
Calculate the Euclidian distance between two nodes
"""
return int(math.sqrt((i[0] - j[0])**2 + (i[1] - j[1])**2))The TSP example we will use for demonstrating ACO is the following (default settings):
The optimal solution for this problem (calculated with mixed integer programming) looks like this:
The distance of this path is 4897.
Solving TSP with ACO
The next step is to solve this problem with ant colony optimization to see how close we can get to the optimal solution. If you are unfamiliar with ACO and you want to learn how the algorithm works, you can read my previous post. Then you can return here to see ACO in action.
The code for ACO:
import datetime
import json
import logging
import random
import time
import matplotlib.pyplot as plt
import numpy as np
from problem import TSP
class AntColonyOptimization:
"""
Ant colony optimization algorithm for finding the shortest route in a graph.
Parameters:
m = number of ants
k_max = number of iterations
alpha = pheromone importance
beta = distance importance
rho = pheromone evaporation rate
Q = pheromone deposit
tau = pheromone
eta = distance
"""
def __init__(self, problem, **kwargs):
self.graph = problem.graph
self.nodes = list(problem.nodes)
self.coordinates = list(problem.nodes.values())
self.n = len(self.nodes)
self.distance_matrix = problem.distance_matrix
self.m = kwargs.get("m", 100)
self.k_max = kwargs.get("k_max", 50)
self.alpha = kwargs.get("alpha", 1)
self.beta = kwargs.get("beta", 5)
self.rho = kwargs.get("rho", 0.9)
self.Q = kwargs.get("Q", 1)
self.time_limit = kwargs.get("time_limit", 5)
# initialization of tau and eta
self.tau = np.full(self.distance_matrix.shape, 0.1)
self.eta = 1 / (self.distance_matrix + 1e-10)
self.history = []
def ant_colony_optimization(self):
"""
Ant colony optimization algorithm
"""
start_time = time.time()
x_best, y_best = [], float("inf")
for _ in range(self.k_max):
self.edge_attractiveness()
self.tau *= (1-self.rho)
for _ in range(self.m):
x_best, y_best = self.ant_walk(x_best, y_best)
if time.time() - start_time > self.time_limit:
logging.info("Time limit reached. Stopping ACO.")
return x_best, y_best
return x_best, y_best
def edge_attractiveness(self, plot: bool = False):
"""
Calculate edge attractiveness
tau = pheromone
eta = distance
alpha = pheromone importance
beta = distance importance
"""
self.A = (self.tau ** self.alpha) * (self.eta ** self.beta)
def ant_walk(self, x_best, y_best, plot: bool = True):
"""
Ant walk
"""
x = [0] # Start at first node
while len(x) < self.n:
i = x[-1]
neighbors = [j for j in range(self.n) if j not in x and self.distance_matrix[i][j] > 0]
if len(neighbors) == 0:
return x_best, y_best
p = [self.A[(i, j)] for j in neighbors]
sampled_neighbor = random.choices(neighbors, weights=p)[0]
x.append(sampled_neighbor)
x.append(0)
y = self.score(x)
self.history.append(y)
for i in range(1, self.n):
self.tau[(x[i-1], x[i])] += self.Q / y
if y < y_best:
logging.info("Better ACO solution found. Score: %.2f", y)
return x, y
return x_best, y_best
def score(self, x):
"""
Score a solution
"""
y = 0
for i in range(len(x) - 1):
y += self.distance_matrix[x[i]][x[i + 1]]
return yLet's break down the crucial parts of the code step by step:
- The first step is initialization
__init__. We define the problem, which, in this case, is a TSP instance, and optionally provide hyperparameters if needed. - The
ant_colony_optimizationsection contains the core execution. Over a specified number of iterationsk_max, the algorithm strives to enhance the current best solution. It involves deploying multiple antsm, and each ant traverses the graph. - The
ant_walkprovides the simulation of the journey of a single ant. In the while loop, the ant's path is constructed by choosing the next edge based on its attractivenessA. The edge attractiveness is computed using theedge_attractivenessmethod, which takes into account factors like the pheromone matrixtau, alpha, the distance matrix, and beta. The pheromone matrix is updated after each ant's walk.
To run the algorithm for a problem instance, all you have to do is the following:
problem = TSP()
aco = AntColonyOptimization(problem)
best_solution, best_score = aco.ant_colony_optimization()Now, how does ACO perform compared to the optimal solution? You can visualize the progress with a GIF that displays the evolving solution. Each image in the GIF shows the current best route, allowing you to observe the improvement over time.
The score of the final solution is equal to 4944, really close to the optimal solution (the gap is less than 1%)! It's also interesting to take a look at the solving process:
In this graph, the x-axis represents the ant number, while the y-axis indicates the distance covered during the ant's journey. The horizontal red line shows the score of the optimal solution, and the red dots symbolize instances where ants have found a new, improved solution. It's worth noting that it often takes several ants to discover a better solution. However, the last red dot is remarkably close to the optimal solution. There are strategies available to enhance the performance of ACO, which I'll elaborate on in the following section.
Assignment Problems
TSP is a routing problem, and ACO was originally designed to address routing problems. That's already a long time ago, and in the meantime people found ways to solve different types of challenges using ACO. One such example worth highlighting is its application to assignment problems.
Assignment problems are problems in which you assign ‘something' to ‘something else'. One example is the quadratic assignment problem (QAP). Imagine you have a set of locations, and you want to assign a set of facilities to these locations. The goal is to determine the best assignment that minimizes the total cost. The cost of assigning facility f to location l is determined by:
- The flow between facilities: Facilities have a certain flow or interaction between them. This represents how much "stuff" or "activity" is transferred between facilities.
- The distance between locations: Each pair of locations has a corresponding distance, which represents the cost or effort required to transport or operate between those locations.
The cost of assigning a particular facility to a specific location is determined by the flow between facilities and the distance between locations. Specifically, the cost for a pair of facilities is computed as the product of their flow and the distance between the locations to which they are assigned.
To find the total cost of a particular assignment, you sum up the pairwise costs for all possible pairs of facilities based on their assignments to locations.
How does the problem formulation changes when you want to apply ACO to an assignment problem instead of a routing problem? I'll leave the coding up to you, but I will provide an intuitive understanding of the difference between a routing and an assignment problem, looking at it from an ant perspective.
The TSP is all about finding the optimal sequence in which to visit various locations. On the other hand, the QAP shifts the focus to deciding where to place items or facilities. In ACO for TSP, the ants learn to favor specific visitation sequences over others. In contrast, when tackling the QAP, the ants lean towards selecting particular facilities for specific locations. In this scenario, the pheromone trails represent how desirable it is to assign a facility to a specific location.
You can imagine it like this: each ant has a list of available places (locations in QAP) where they can allocate items (facilities in QAP). The ants proceed through these steps repeatedly until they've determined the optimal arrangement of all items.
In simpler terms, think of it as ants collaboratively determining the most efficient way to allocate items, drawing from the knowledge they've acquired about what works best in terms of item-to-location assignments.
Improve Solution Quality
There are several strategies to achieve better solutions in a shorter timeframe. Here are three valuable tips that can significantly impact your results:
Hyperparameter Search
If you're dealing with multiple problems of the same type, it's highly advisable to conduct a hyperparameter search. Parameters such as the number of iterations, the quantity of ants, alpha, beta, rho, and Q can exert a substantial influence on algorithm performance.
Let's examine an example. In the plot below, we test two different values of alpha, while the other parameters stay the same. The line plots depict the moving average over 100 ant runs, while the dots represent the best solution found for a certain run.
The algorithm with the orange settings (alpha = 2) not only discovers a superior solution (indicated by the orange dot) but also accomplishes this more rapidly compared to the algorithm with the blue settings (alpha = 1).
To emphasize the impact of hyperparameter tuning further, consider a TSP problem with 100 nodes. If we conduct a random search (10 iterations) across the hyperparameters and plot the moving average, we observe significant variations in performance.
At the top, the orange and yellow lines yield suboptimal results, while others come remarkably close to the optimal solution. For context, it's worth noting that the OR tools solver took 5 minutes to find the optimum, whereas the ACO algorithms completed their runs in a maximum of 5 seconds.
Warm Up Procedure
Before setting the ants in motion, you have the option to initiate a warm-up for the pheromone matrix. This preparatory step often reduces the number of iterations needed to find the best solution. In this paper, a warm-up procedure is proposed and its effects are compared.
Exploration and Exploitation
Similar to many algorithms, they can encounter stagnation if they don't explore sufficiently. To address this, you can use the Max-Min Ant System. MMAS encourages ants to venture into unexplored paths by assigning a high pheromone value to these paths. When stagnation occurs, the trails are reset to this elevated value. An additional advantage of MMAS over the original algorithm is that only the global best tour or the iteration's best tour are permitted to enhance their trails with pheromone. These adjustments promote a more effective balance between exploration and exploitation.
Conclusion
Ant colony optimization is a fun algorithm to play around with. It can find high quality solutions to routing and assignment problems, even if the problem size increases. This makes it a powerful algorithm.
To further enhance the algorithm's performance and uncover superior solutions, consider incorporating essential strategies such as hyperparameter search, a warm-up procedure, and techniques for balancing exploration and exploitation. These adjustments can lead to significant improvements in your results.
If you became curious and want to read more on ACO, I can recommend this work. One of the authors is the one who proposed ACO in 1992. It offers valuable insights and a comprehensive understanding of this remarkable optimization technique.
Related
Optimizing Connections: Mathematical Optimization within Graphs
An Introduction to a Powerful Optimization Technique: Simulated Annealing
