ACOAgent

A Python implementation of Ant Colony Optimization (ACO) algorithms, featuring the Ant Colony System (ACS) variant.

Overview

ACOAgent provides a clean, well-documented implementation of ACO algorithms for solving combinatorial optimization problems. The library is designed with modularity and extensibility in mind, making it easy to experiment with different ACO variants and apply them to various problems.

Features

• Ant Colony System (ACS): Full implementation with pseudo-random proportional rule, local and global pheromone updates
• Modular Design: Separate components for graph representation, pheromone management, and ant agents
• Type Hints: Full type annotations for better IDE support and code clarity
• Extensible: Easy to add new ACO variants by extending the base class
• Well Tested: Comprehensive test suite with good coverage

Installation

# Clone the repository
git clone https://github.com/bayazknn/ACOAgent.git
cd ACOAgent

# Create virtual environment
python -m venv venv
source venv/bin/activate  # On Windows: venv\Scripts\activate

# Install in development mode
pip install -e ".[dev]"

Quick Start

from aco import Graph, AntColonySystem

# Create a graph from coordinates (e.g., city locations)
coordinates = [
    (0, 0), (10, 0), (10, 10), (0, 10), (5, 5)
]
graph = Graph.from_coordinates(coordinates)

# Or create a random graph
graph = Graph.random(num_nodes=20, seed=42)

# Initialize and run ACS
acs = AntColonySystem(
    graph=graph,
    num_ants=20,
    alpha=1.0,      # Pheromone importance
    beta=2.0,       # Heuristic importance
    q0=0.9,         # Exploitation probability
    max_iterations=100,
    seed=42,
)

# Solve and get results
result = acs.solve()

print(f"Best tour length: {result.best_length:.2f}")
print(f"Best tour: {result.best_path}")
print(f"Iterations: {result.total_iterations}")

Running the Examples

# Run the TSP example
python examples/tsp.py

Running Tests

# Run all tests
pytest

# Run with coverage
pytest --cov=src/aco

# Run specific test file
pytest tests/test_acs.py -v

Project Structure

ACOAgent/
├── src/aco/
│   ├── __init__.py         # Package exports
│   ├── graph.py            # Graph representation
│   ├── pheromone.py        # Pheromone matrix management
│   ├── agent.py            # Ant agent implementation
│   └── algorithms/
│       ├── __init__.py
│       ├── base.py         # Abstract base class for ACO
│       └── acs.py          # Ant Colony System
├── tests/                  # Test suite
├── examples/               # Usage examples
└── CLAUDE.md              # AI assistant guide

Algorithm Details

Ant Colony System (ACS)

ACS introduces several improvements over the basic ACO:

1. Pseudo-random Proportional Rule: With probability q0, the ant chooses the best next node (exploitation); otherwise, it uses probabilistic selection (exploration).

2. Local Pheromone Update: After each move, the ant decreases pheromone on the traversed edge to encourage exploration of different paths.

3. Global Pheromone Update: Only the best-so-far ant deposits pheromone, concentrating the search around the best solution.

Parameters

Parameter	Description	Typical Value
alpha	Pheromone importance	1.0
beta	Heuristic importance	2.0 - 5.0
q0	Exploitation probability	0.9
xi	Local evaporation rate	0.1
rho	Global evaporation rate	0.1

References

• Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.

License

MIT License