aco-tsp

ACO-TSP

Ant Colony Optimization for the Traveling Salesman Problem (TSP) implemented in Python.

This library provides a clean and configurable implementation of the Ant Colony Optimization (ACO) algorithm to solve the TSP.
It includes robust error handling, parameter customization, convergence tracking, and easy integration into Python projects.

---

Usage

Basic Example

from ACO_TSP import ACO_TSP

# Define your distance matrix (5x5 example)
distance_matrix = [
    [0, 10, 12, 11, 14],
    [10, 0, 13, 15, 8],
    [12, 13, 0, 9, 14],
    [11, 15, 9, 0, 16],
    [14, 8, 14, 16, 0]
]

# Initialize and run ACO
aco = ACO_TSP(
    distance_matrix,
    labels=['A', 'B', 'C', 'D', 'E'],
    num_ants=15,
    num_iterations=100,
    beta=3
)
path, length = aco.solve()

print(f"Optimal Path: {' → '.join(path)}")
print(f"Total Distance: {length:.2f}")

---

Advanced Usage

# Get full solution details
solution = aco.get_solution()

print(f"Best tour indices: {solution['tour']}")
print(f"Convergence history: {solution['convergence']}")

# Access algorithm parameters
print(f"Parameters used: {solution['parameters']}")

# Visualize pheromone matrix
import matplotlib.pyplot as plt
plt.imshow(solution['pheromones'], cmap='hot', interpolation='nearest')
plt.title("Pheromone Matrix")
plt.colorbar()
plt.show()

---

Parameters

All parameters are configurable when initializing the ACO_TSP class:

---

Error Handling

The library provides comprehensive error checking with meaningful messages:

try:
    aco = ACO_TSP(
        [[0, 10], [10, 0]],  # Invalid matrix size
        labels=['A', 'B', 'C'],
        evap_rate=1.5,
        num_ants=0
    )
except ValueError as e:
    print(f"Configuration error: {e}")

Common error scenarios:

• Non-square distance matrix
• Label size mismatch
• Parameter out of valid range
• Invalid start node index
• Calling get_solution() before solve()

---

Theory Overview

Ant Colony Optimization mimics how real ants find shortest paths:

1. Pheromone Initialization
   Equal pheromone on all paths.
2. Solution Construction
   Ants probabilistically choose paths based on:
   • Pheromone intensity (α)
   • Heuristic visibility (1 / distance, β)
3. Pheromone Update
   • Evaporation: All paths lose pheromone.
   • Deposition: Ants reinforce paths used in their solution.
4. Convergence
   Over iterations, better paths accumulate more pheromone.

---

Output

After running solve(), you can get:

• Best path (labels & indices)
• Total path length
• Convergence history
• Final pheromone matrix
• Parameters used

---