Ant Colony Optimization

Swarm Intelligence

Ant Colony Optimization (ACO) algorithm for continuous optimization.

Algorithm Overview

This module implements the Ant Colony Optimization (ACO) algorithm. ACO is a population-based metaheuristic that can be used to find approximate solutions to difficult optimization problems.

In ACO, a set of software agents called artificial ants search for good solutions to a given optimization problem. To apply ACO, the optimization problem is transformed into the problem of finding the best path on a weighted graph. The artificial ants incrementally build solutions by moving on the graph. The solution construction process is stochastic and is biased by a pheromone model, that is, a set of parameters associated with graph components (either nodes or edges) whose values are modified at runtime by the ants.

ACO is particularly useful for problems that can be reduced to finding paths on weighted graphs, like the traveling salesman problem, the vehicle routing problem, and the quadratic assignment problem.

Usage

from opt.swarm_intelligence.ant_colony import AntColony
from opt.benchmark.functions import sphere

optimizer = AntColony(
    func=sphere,
    lower_bound=-5.12,
    upper_bound=5.12,
    dim=10,
    max_iter=500,
    population_size=50,
)

best_solution, best_fitness = optimizer.search()
print(f"Best solution: {best_solution}")
print(f"Best fitness: {best_fitness:.6e}")

Parameters

Parameter	Type	Default	Description
func	Callable	Required	Objective function to minimize.
lower_bound	float	Required	Lower bound of search space.
upper_bound	float	Required	Upper bound of search space.
dim	int	Required	Problem dimensionality.
max_iter	int	1000	Maximum iterations.
population_size	int	100	Number of ants in colony.
seed	int | None	None	Random seed for reproducibility.
alpha	float	1	Pheromone influence exponent.
beta	float	1	Heuristic information weight (not used in basic continuous ACO).
rho	float	0.5	Pheromone evaporation rate in [0, 1].
q	float	1	Pheromone deposit constant.
track_history	bool	False	Track optimization history for visualization

Algorithm Metadata

Property	Value
Algorithm Name	Ant Colony Optimization
Acronym	ACO
Year Introduced	1992
Authors	Dorigo, Marco; Stützle, Thomas
Algorithm Class	Swarm Intelligence
Complexity	O(population_size $\times$ dim $\times$ max_iter)
Properties	Population-based, Derivative-free, Stochastic
Implementation	Python 3.10+
COCO Compatible	Yes

Mathematical Formulation

Pheromone update equation (inspired by Dorigo's Ant System):

$${\tau }_i(t+1)=(1-\rho )\cdot {\tau }_i(t)+\rho \cdot \frac{Q}{f(x_i)}$$

where:

• ${\tau }_i$ is the pheromone trail for ant $i$
• $\rho \in [0,1]$ is the evaporation rate
• $Q$ is a constant controlling pheromone deposition
• $f(x_i)$ is the fitness value at position $x_i$

Solution construction:

$$x_i^{new}=x_i+{\tau }_i^{\alpha }\cdot r$$

where:

• $\alpha$ controls pheromone influence
• $r$ is a random perturbation vector from uniform distribution $[-1,1]$

Constraint handling:

• Boundary conditions: Clamping to [lower_bound, upper_bound]
• Feasibility enforcement: Direct clipping after each position update

Hyperparameters

Parameter	Default	BBOB Recommended	Description
population_size	100	10*dim	Number of ants
max_iter	1000	10000	Maximum iterations
alpha	1.0	0.5-2.0	Pheromone influence exponent
beta	1.0	0.5-2.0	Heuristic information weight
rho	0.5	0.1-0.9	Pheromone evaporation rate
q	1.0	0.1-10.0	Pheromone deposit constant

Sensitivity Analysis:

• rho: High impact on convergence - controls exploration vs exploitation balance
• alpha: Medium impact - balances pheromone influence on solution construction
• Recommended tuning ranges: $\text{rho}\in [0.1,0.9]$, $\text{alpha}\in [0.5,2.0]$

COCO/BBOB Benchmark Settings

Search Space:

• Dimensions tested: 2, 3, 5, 10, 20, 40
• Bounds: Function-specific (typically [-5, 5] or [-100, 100])
• Instances: 15 per function (BBOB standard)

Evaluation Budget:

• Budget: $\text{dim}\times 10000$ function evaluations
• Independent runs: 15 (for statistical significance)
• Seeds: 0-14 (reproducibility requirement)

Performance Metrics:

• Target precision: 1e-8 (BBOB default)
• Success rate at precision thresholds: [1e-8, 1e-6, 1e-4, 1e-2]
• Expected Running Time (ERT) tracking

Raises

ValueError: If search space is invalid or function evaluation fails.

Notes

• Uses self.seed for all random number generation
• BBOB: Returns final best solution after max_iter or convergence

Computational Complexity:

• Time per iteration: $O(\text{population\_size}\times \text{dim})$
• Space complexity: $O(\text{population\_size}\times \text{dim})$
• BBOB budget usage: Typically uses 60-80% of dim $\times$ 10000 budget for convergence

BBOB Performance Characteristics:

• Best function classes: Multimodal functions with local optima
• Weak function classes: Highly ill-conditioned or very high-dimensional problems
• Typical success rate at 1e-8 precision: 20-40% (dim=5)
• Expected Running Time (ERT): Moderate, slower than gradient-based but robust

Convergence Properties:

• Convergence rate: Sublinear (depends on pheromone evaporation)
• Local vs Global: Balanced search with tunable exploration/exploitation via rho
• Premature convergence risk: Medium - can be mitigated by tuning evaporation rate

Reproducibility:

• Deterministic: Yes - Same seed guarantees same results
• BBOB compliance: seed parameter required for 15 independent runs
• Initialization: Uniform random sampling in [lower_bound, upper_bound]
• RNG usage: numpy.random.default_rng(self.seed) throughout

Implementation Details:

• Parallelization: Not supported in this implementation
• Constraint handling: Clamping to bounds via np.clip
• Numerical stability: Pheromone values kept positive via Q/fitness formulation

Known Limitations:

• Adapted from combinatorial to continuous optimization
• Local search component uses simple random walk
• No adaptive parameter tuning in this basic implementation
• BBOB known issues: May struggle with very high dimensions (dim>40)

Version History:

• v0.1.0: Initial implementation
• v0.1.2: COCO/BBOB compliant docstring added

References

[1] Dorigo, M., & Stützle, T. (2004). "Ant Colony Optimization." MIT Press, Cambridge, MA. https://doi.org/10.7551/mitpress/1290.001.0001

[2] Dorigo, M., Birattari, M., & Stutzle, T. (2006). "Ant colony optimization." IEEE Computational Intelligence Magazine, 1(4), 28-39. https://doi.org/10.1109/MCI.2006.329691

[3] Hansen, N., Auger, A., Ros, R., Mersmann, O., Tušar, T., Brockhoff, D. (2021). "COCO: A platform for comparing continuous optimizers in a black-box setting." Optimization Methods and Software, 36(1), 114-144. https://doi.org/10.1080/10556788.2020.1808977

COCO Data Archive:

• Benchmark results: https://coco-platform.org/testsuites/bbob/data-archive.html
• Code repository: https://github.com/Anselmoo/useful-optimizer

Implementation:

• This implementation: Adapted for continuous optimization with modifications for BBOB compliance. Original ACO was designed for combinatorial problems.

See Also

ParticleSwarm: Similar swarm-based algorithm with velocity updates BBOB Comparison: Generally faster convergence on unimodal functions

GeneticAlgorithm: Evolutionary approach with crossover and mutation BBOB Comparison: ACO often more exploratory on multimodal landscapes

AbstractOptimizer: Base class for all optimizers opt.benchmark.functions: BBOB-compatible test functions

Related BBOB Algorithm Classes:

• Evolutionary: GeneticAlgorithm, DifferentialEvolution
• Swarm: ParticleSwarm, BatAlgorithm, FireflyAlgorithm
• Gradient: AdamW, SGDMomentum

Benchmark Performance

Interactive fitness landscape of a representative multimodal benchmark function (drag to rotate, scroll to zoom):

Convergence, final-fitness distribution and performance profile on rastrigin (5D), averaged over independent runs (compared against representative baselines):

Related Pages

• Swarm Intelligence Algorithms
• All Algorithms
• Benchmark Functions

---

Source Code

View the implementation: ant_colony.py