.. _library_ant_colony:

``ant_colony``
==============

Ant Colony Optimization (ACO) is a constructive metaheuristic inspired
by the foraging behaviour of real ants. Artificial ants build candidate
solutions component-by-component on a construction graph, guided by
pheromone trails and problem-specific heuristic information. After each
iteration the pheromone is evaporated and reinforced according to the
quality of the constructed solutions. ACO is particularly effective for
combinatorial problems that can be stated as finding good paths or
permutations on a graph, such as the Traveling Salesman Problem (TSP),
vehicle routing, and scheduling.

The library provides the parametric object
``ant_colony(Problem, RandomAlgorithm)`` where ``Problem`` is an object
implementing the ``ant_colony_problem_protocol`` protocol and
``RandomAlgorithm`` is one of the algorithms supported by the
``fast_random`` library. The algorithm minimizes the solution cost
defined by the problem.

A convenience object ``ant_colony(Problem)`` is also provided, using the
Xoshiro128++ random number generator (``xoshiro128pp``) as the default.

API documentation
-----------------

Open the
`../../apis/library_index.html#ant-colony <../../apis/library_index.html#ant-colony>`__
link in a web browser.

Loading
-------

To load all entities in this library, load the ``loader.lgt`` file:

::

   | ?- logtalk_load(ant_colony(loader)).

Testing
-------

To test this library predicates, load the ``tester.lgt`` file:

::

   | ?- logtalk_load(ant_colony(tester)).

Features
--------

- **Configurable random number generator** - the algorithm is
  parameterized by a ``fast_random`` algorithm. Available algorithms
  include ``xoshiro128pp``, ``xoshiro128ss``, ``xoshiro256pp``,
  ``xoshiro256ss``, ``well512a``, ``splitmix64``, and ``as183``. The
  convenience object ``ant_colony(Problem)`` defaults to
  ``xoshiro128pp``.
- **Classic Ant System pheromone update** - every edge evaporates by
  factor ``(1-Rho)``; each ant then deposits ``Q / Cost`` on the edges
  of its tour.
- **MAX-MIN pheromone bounds** - optional ``tau_min(T)`` and
  ``tau_max(T)`` clamp every trail into a closed interval after each
  update (MMAS-style), preventing trail collapse or domination. Defaults
  are a tiny positive floor and a very large ceiling.
- **Elitist reinforcement** - the optional ``elite(E)`` option adds an
  extra ``E * Q / BestCost`` deposit on the edges of the global-best
  tour.
- **Probabilistic construction** - each ant builds a complete tour by
  starting at a random node and selecting successive unvisited nodes
  with probability proportional to ``Tau^Alpha * Eta^Beta``
  (roulette-wheel selection).
- **Best solution tracking** - the algorithm retains the best solution
  found across all iterations.
- **Progress reporting** - if the problem object defines ``progress/5``,
  it is called periodically with the current iteration, best cost,
  iteration-best cost, and rate statistics.
- **Run statistics** - the ``run/4`` predicate returns the number of
  iterations, total solutions constructed, number of global-best
  improvements, and the final best cost.
- **Seed control** - the ``seed(S)`` option initializes the random
  number generator for reproducible runs.

Defining a problem
------------------

A problem object must implement the ``ant_colony_problem_protocol``
protocol by defining (at least) the following three predicates:

- ``nodes(-Nodes)`` - returns the list of nodes of the construction
  graph.
- ``heuristic(+From, +To, -Eta)`` - returns the heuristic desirability
  of the directed edge from ``From`` to ``To`` (typically the reciprocal
  of distance or cost; must be strictly positive).
- ``solution_cost(+Tour, -Cost)`` - computes the cost of a complete tour
  (the algorithm minimizes this value). The tour is a list of nodes; the
  cost predicate is responsible for adding the closing edge back to the
  first node when required (as in TSP).

Optionally, the problem object may also define:

- ``stop_condition(+Iteration, +BestCost, +IterationBestCost)`` -
  succeeds when the search should terminate early.
- ``progress(+Iteration, +BestCost, +IterationBestCost, +AcceptanceRate, +ImprovementRate)``

  - called periodically during the optimization to report progress.

Options
-------

Options for the ``run/3-4`` predicates:

- ``max_iterations(N)`` - maximum number of iterations (default:
  ``100``).
- ``ants(N)`` - number of ants (solutions constructed) per iteration
  (default: ``10``).
- ``alpha(A)`` - pheromone importance exponent (default: ``1.0``).
- ``beta(B)`` - heuristic importance exponent (default: ``2.0``).
- ``rho(R)`` - evaporation rate in ``(0,1]`` (default: ``0.5``).
- ``q(Q)`` - pheromone deposit constant (default: ``100.0``).
- ``elite(E)`` - elitist weight: extra deposit factor for the
  global-best tour (default: ``0``).
- ``tau0(T)`` - initial pheromone level on every edge (default:
  ``1.0``). Clamped into ``[tau_min, tau_max]`` at initialization.
- ``tau_min(T)`` - lower bound on pheromone trails; must be strictly
  positive (default: ``1.0e-12``).
- ``tau_max(T)`` - upper bound on pheromone trails; must be strictly
  positive and at least ``tau_min`` (default: ``1.0e300``).
- ``updates(N)`` - number of progress reports during the run. Progress
  is reported by calling ``progress/5`` on the problem object. Set to
  ``0`` to disable (default: ``0``).
- ``seed(S)`` - positive integer seed for the random number generator,
  enabling reproducible runs (default: none).

Run statistics
--------------

The ``run/4`` predicate returns a list of statistics about the completed
run:

- ``iterations(N)`` - number of iterations executed.
- ``solutions(S)`` - total number of solutions constructed.
- ``improvements(I)`` - number of times the global best was strictly
  improved.
- ``final_best_cost(C)`` - cost of the best solution found.

**Limitations**
---------------

- **Solution-construction model only** - the library implements the
  classic constructive ACO paradigm (ants build complete solutions from
  components). Local-search improvement of constructed solutions is left
  to the problem object or a surrounding hybrid.
- **Edge-based pheromone** - pheromone is stored on directed edges of
  the complete graph induced by ``nodes/1``. Attribute-based or
  set-based pheromone models are not provided.
- **Single colony, single pheromone matrix** - multi-colony and
  multi-objective variants are not implemented.
- **TSP-oriented construction** - the built-in construction procedure
  assumes a Hamiltonian path/tour over the node set (every node visited
  exactly once). Problems with different feasibility rules need a custom
  construction strategy (future extension point).

Usage
-----

Example of a problem definiton
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Define an object implementing the ``ant_colony_problem_protocol``
protocol. For example, a small TSP instance:

::

   :- object(tsp6,
       implements(ant_colony_problem_protocol)).

       nodes([a,b,c,d,e,f]).

       heuristic(From, To, Eta) :-
           distance(From, To, D),
           Eta is 1.0 / D.

       solution_cost(Tour, Cost) :-
           % sum of successive distances plus the closing edge
           ...

   :- end_object.

Running the algorithm
~~~~~~~~~~~~~~~~~~~~~

::

   | ?- ant_colony(tsp6)::run(Tour, Cost).
   Tour = [a,b,c,...], Cost = ...

Running with custom options
~~~~~~~~~~~~~~~~~~~~~~~~~~~

::

   | ?- ant_colony(tsp6)::run(Tour, Cost, [
            max_iterations(200), ants(20), alpha(1.0), beta(5.0),
            rho(0.1), elite(2)
        ]).

Running with statistics
~~~~~~~~~~~~~~~~~~~~~~~

::

   | ?- ant_colony(tsp6)::run(Tour, Cost, Stats, []).
   Stats = [iterations(100), solutions(1000), improvements(...), final_best_cost(...)]

Reproducible runs with seed
~~~~~~~~~~~~~~~~~~~~~~~~~~~

::

   | ?- ant_colony(tsp6)::run(T1, C1, [seed(42)]),
        ant_colony(tsp6)::run(T2, C2, [seed(42)]).
   T1 = T2, C1 = C2.

Using a custom random number generator
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

::

   | ?- ant_colony(tsp6, well512a)::run(Tour, Cost).
