Skip to content

README.md

Latest commit

 

History

History
205 lines (153 loc) · 8.38 KB

README.md

File metadata and controls

205 lines (153 loc) · 8.38 KB
Raw

Ant Colony Optimization

Python License: MIT CI Dependencies

Ant Colony Optimization (ACO) applied to five problems — four discrete and one continuous — built on one shared engine.

Ant Colony Optimization is a metaheuristic based on the foraging behaviour of ants. Many agents ("ants") build solutions step by step. They leave a chemical trail (pheromone) on the choices they make. Over iterations the colony concentrates on the lower-cost regions of the search space. This repository solves four discrete problems and one continuous problem with the same core engine.

What is Ant Colony Optimization?

Each ant builds a solution one component at a time. At every step it picks the next component with a probability that mixes two signals:

  • Pheromone $\tau$ — how good this choice was for past ants (learned).
  • Heuristic $\eta$ — a fixed problem hint, such as "closer cities are better".

$$ p_{ij} ;=; \frac{\tau_{ij}^{\alpha},\eta_{ij}^{\beta}} {\sum_{l \in \text{allowed}} \tau_{il}^{\alpha},\eta_{il}^{\beta}} $$

After all ants finish an iteration, the pheromone is updated. Good (low-cost) solutions add pheromone; then every trail evaporates a little so old choices fade:

$$ \tau_{ij} ;\leftarrow; \tau_{ij} + \sum_{k}\frac{Q}{C_k} \qquad\text{then}\qquad \tau_{ij} ;\leftarrow; (1-\rho),\tau_{ij} $$

where $C_k$ is the cost of ant $k$'s solution. The exponents $\alpha,\beta$ balance learned pheromone against the fixed heuristic; $\rho$ is the evaporation rate and $Q$ the deposit constant.

The continuous problem (sphere) uses ACO_R (Socha & Dorigo, 2008), which replaces the pheromone matrix with a ranked archive of solutions and samples new points from Gaussian kernels. See its README.

Problems

Problem Type Instance Pheromone structure Heuristic $\eta$ Local search Reference result
Traveling Salesman permutation 50 cities $n\times n$ edge matrix $1/\text{distance}$ 2-opt tour length 588.97
Quadratic Assignment permutation 20 locations, 10 facilities $n\times n$ matrix $1/\text{distance}$ — cost 22 669
Binary Knapsack binary 0/1 30 items $2\times n$ matrix value/weight — value 2941, feasible
Integer Knapsack bounded integer 30 items per-item arrays value/weight — value 19 240, feasible
Sphere (ACO_R) continuous 5 dimensions Gaussian archive — — cost $\approx 0$

All reference results above are produced by the default seed (--seed 1).

Results

TSP — best tour
 TSP — convergence
QAP — facility assignment
 Sphere (ACO_R) — convergence

The sphere curve uses a logarithmic axis: ACO_R drives the cost down by hundreds of orders of magnitude, reaching the global optimum at the origin.

Installation

Requires Python 3.10 or newer.

git clone https://github.com/hajibabaie/ant_colony_optimization.git
cd ant_colony_optimization
pip install -e .            # add ".[dev]" to also install pytest and ruff

The editable install puts the aco package on your path and registers the command-line tools below, so everything runs from any directory.

Usage

Each problem has a console command and an equivalent module entry point:

Problem Console command Module form
Traveling Salesman aco-tsp python -m aco.problems.tsp
Quadratic Assignment aco-qap python -m aco.problems.qap
Binary Knapsack aco-binary-knapsack python -m aco.problems.binary_knapsack
Integer Knapsack aco-integer-knapsack python -m aco.problems.integer_knapsack
Sphere (ACO_R) aco-sphere python -m aco.problems.sphere

Common options: --seed (reproducibility), --iterations, and --no-plot.

aco-tsp                       # solve the default 50-city instance, save figures
aco-tsp --seed 7              # a different run
aco-sphere --dim 10           # minimize the 10-dimensional sphere

Figures are written to results/<problem>/.

Project structure

aco/
├── core/                 # the shared engine (no problem code here)
│   ├── base.py           # DiscreteACO: the template-method run loop
│   ├── continuous.py     # ContinuousACO: the ACO_R archive engine
│   ├── selection.py      # roulette-wheel selection (shared)
│   └── plotting.py       # convergence figure (shared)
└── problems/             # one package per problem
    ├── tsp/  qap/  binary_knapsack/  integer_knapsack/  sphere/
    │   ├── instance.py   # data model (load / random / save)
    │   ├── cost.py       # objective function
    │   ├── solver.py     # the five hooks that specialize the engine
    │   └── cli.py        # command-line entry point
tests/                    # pytest suite
results/                  # generated figures (committed for the README)
docs/references/          # the ACO_R paper

The four discrete problems share one run loop. Each problem only implements how to build a solution, score it, and deposit/evaporate pheromone — the iteration order, best-tracking, timing, and plotting live once in the base class.

Algorithm design notes

  • Template method for the discrete engine. DiscreteACO fixes the loop and exposes four required hooks (construct_solution, evaluate, deposit, evaporate) plus two optional ones (local_search, plot_solution). Adding a new discrete problem means writing one small solver class, not a new loop.
  • ACO_R is a separate engine. The continuous algorithm has a different shape (a ranked archive and Gaussian sampling instead of a pheromone matrix), so it is its own class rather than a forced subclass with empty methods.
  • Reproducible runs. Every engine takes a numpy.random.Generator, so a seed reproduces a run exactly. This also makes the test suite deterministic.
  • Data is loaded once. Each problem reads its instance into a small dataclass and the cost function is a pure function of (solution, instance) — no file is read during the search.

Parameter reference

The engines use the standard ACO symbols.

Symbol Name Meaning
$\alpha$ alpha pheromone exponent (weight of learned trails)
$\beta$ beta heuristic exponent (weight of the fixed hint)
$\rho$ rho evaporation rate
$Q$ q pheromone deposit constant

Values used by each discrete problem:

Problem ants iterations $\alpha$ $\beta$ $\rho$ $Q$
Traveling Salesman 150 100 2.7 1.2 0.04 1
Quadratic Assignment 40 100 2.7 1.02 0.04 1
Binary Knapsack 200 100 2.0 1.5 0.04 1
Integer Knapsack 120 100 3.2 1.2 0.04 1

ACO_R (sphere) uses an archive of 20, 50 samples per iteration, intensification $q = 0.5$ and deviation scale $\zeta = 1$ over 1000 iterations.

References

  1. M. Dorigo, V. Maniezzo, A. Colorni (1996). Ant System: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 26(1), 29–41.
  2. M. Dorigo, T. Stützle (2004). Ant Colony Optimization. MIT Press.
  3. K. Socha, M. Dorigo (2008). Ant colony optimization for continuous domains. European Journal of Operational Research, 185(3), 1155–1173. (local copy)

License

Released under the MIT License.