.. _library_tabu_search:

``tabu_search``
===============

Tabu search is a metaheuristic that guides a local-search procedure by
using a short-term memory structure (the *tabu list*) to avoid
revisiting recently explored solutions and to escape local minima. It is
particularly useful for combinatorial optimization problems such as the
Traveling Salesman Problem (TSP), graph coloring, and scheduling.

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

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

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

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

Loading
-------

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

::

   | ?- logtalk_load(tabu_search(loader)).

Testing
-------

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

::

   | ?- logtalk_load(tabu_search(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 ``tabu_search(Problem)`` defaults to
  ``xoshiro128pp``.
- **Tabu list (short-term memory)** - recently visited states are stored
  with an expiration step. With fixed tenure (``tabu_tenure(T)``) the
  list behaves as a FIFO of maximum length ``T``. With
  ``tabu_tenure_range(Min, Max)`` each accepted move receives a random
  tenure drawn uniformly from the inclusive range. Candidates that
  appear in the active (non-expired) list are forbidden unless the
  aspiration criterion is met.
- **Aspiration criterion** - a tabu candidate is accepted when its
  energy is strictly better than the best energy found so far (classic
  “best-so-far” aspiration).
- **Candidate sampling** - by default the algorithm samples
  ``candidates(N)`` neighbors per iteration using ``neighbor_state/2``
  (or ``neighbor_state/3``). If the problem defines ``neighbors/2``,
  that complete list is used (or a random sample of it when larger than
  the candidate limit).
- **Delta-energy optimization** - when the problem object defines
  ``neighbor_state/3``, the algorithm uses the returned energy delta
  directly instead of recomputing the full energy.
- **Best state tracking** - the algorithm tracks the best state found
  across all iterations and across all restart cycles, not just the
  final state.
- **Progress reporting** - if the problem object defines ``progress/5``,
  it is called periodically with the current step, best energy, current
  energy, acceptance rate, and improvement rate. A final report is
  always produced when the loop terminates.
- **Run statistics** - the ``run/4`` predicate returns a list of
  statistics including the number of steps, acceptances, improvements,
  and the final tabu-list size.
- **Seed control** - the ``seed(S)`` option initializes the random
  number generator for reproducible runs.
- **Restarts** - the ``restarts(N)`` option runs N additional
  tabu-search cycles after the first. Each restart begins from the best
  state found so far with a cleared tabu list, allowing the search to
  escape deep local minima. Statistics accumulate across all cycles.

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

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

- ``initial_state(-State)`` - returns the starting state.
- ``neighbor_state(+State, -Neighbor)`` - generates a neighboring state.
- ``state_energy(+State, -Energy)`` - computes the cost of a state (to
  be minimized).

Optionally, the problem object may also define:

- ``neighbor_state(+State, -Neighbor, -DeltaEnergy)`` - generates a
  neighboring state and returns the energy change directly, avoiding a
  full energy recomputation.
- ``neighbors(+State, -Neighbors)`` - returns the complete list of
  neighboring states. When defined, the algorithm uses this list (or a
  random sample controlled by ``candidates(N)``) instead of repeated
  calls to ``neighbor_state/2``.
- ``stop_condition(+Step, +BestEnergy, +CurrentEnergy)`` - succeeds when
  the search should terminate early.
- ``progress(+Step, +BestEnergy, +CurrentEnergy, +AcceptanceRate, +ImprovementRate)``

  - called periodically during the optimization to report progress.

Options
-------

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

- ``max_steps(N)`` - maximum number of iterations per cycle (default:
  ``10000``).
- ``tabu_tenure(T)`` - fixed tabu tenure: lifetime in steps of each tabu
  entry (default: ``7``). Ignored when ``tabu_tenure_range/2`` is also
  present.
- ``tabu_tenure_range(Min, Max)`` - random tabu tenure: on each accepted
  move a tenure is drawn uniformly from the inclusive integer range
  ``Min..Max``. Overrides ``tabu_tenure/1`` when present.
- ``candidates(N)`` - number of candidate neighbors examined per
  iteration (default: ``20``).
- ``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).
- ``restarts(N)`` - number of additional tabu-search cycles after the
  first. Each restart begins from the best state found so far with a
  cleared tabu list (default: ``0``).

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

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

- ``steps(N)`` - total number of steps executed.
- ``acceptances(A)`` - number of accepted moves.
- ``improvements(I)`` - number of moves that strictly improved the best
  energy found.
- ``final_tabu_size(S)`` - size of the tabu list at termination.

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

- **Solution-based tabu memory only** - the tabu list stores complete
  states rather than move attributes. This is simple and
  problem-agnostic, but can be memory-intensive for large or richly
  structured states, and is often less effective than attribute-based
  tabu for problems where the relevant forbidden features are local
  (e.g. edges in TSP, variable assignments in scheduling).

- **Limited tenure schedules** - fixed tenure and uniform random tenure
  in a static range are supported. Reactive or adaptive tenure schedules
  (e.g. tenure that grows after repeated cycling) are not implemented.

- **Single aspiration criterion** - only the classic "best-so-far" rule
  is implemented (a tabu candidate is accepted when it improves the
  global best energy). Other aspiration strategies are not supported.

- **Neighborhood exploration** - when the problem does not define
  ``neighbors/2``, the algorithm samples a fixed number of candidates
  via repeated calls to ``neighbor_state/2``. Systematic or exhaustive
  enumeration of large neighborhoods is left to the problem object.

- **Short-term memory only** - there is no intermediate-term or
  long-term memory (frequency-based or elite-set structures) and
  therefore no built-in intensification or diversification beyond the
  optional ``restarts(N)`` mechanism, which simply clears the tabu list
  and resumes from the best state found so far.

- **State identity** - tabu membership is decided by ordinary term
  equality (``member/2``). States that are semantically equivalent but
  not term-identical (e.g. rotations or reflections of a tour) are
  treated as distinct unless the problem normalizes them.

- **Single trajectory** - the search follows one solution path at a
  time; population-based or multi-threaded variants are not currently
  implemented.

Usage
-----

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

Define an object implementing the ``tabu_search_problem_protocol``
protocol. For example, a simple quadratic minimization problem:

::

   :- object(quadratic,
       implements(tabu_search_problem_protocol)).

       initial_state(50.0).
       neighbor_state(X, Y) :-
           random::random(-5.0, 5.0, Delta),
           Y is X + Delta.
       state_energy(X, E) :-
           E is (X - 3.0) * (X - 3.0).

   :- end_object.

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

::

   | ?- tabu_search(quadratic)::run(State, Energy).
   State = 3.00..., Energy = 0.000...

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

::

   | ?- tabu_search(quadratic)::run(State, Energy, [max_steps(5000), tabu_tenure(10), candidates(30)]).
   State = 3.00..., Energy = 0.000...

Random tabu tenure
~~~~~~~~~~~~~~~~~~

::

   | ?- tabu_search(quadratic)::run(State, Energy, [tabu_tenure_range(5, 12), max_steps(5000)]).
   State = 3.00..., Energy = 0.000...

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

::

   | ?- tabu_search(quadratic)::run(State, Energy, Stats, []).
   State = 3.00..., Energy = 0.000...,
   Stats = [steps(10000), acceptances(...), improvements(...), final_tabu_size(...)]

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

::

   | ?- tabu_search(quadratic)::run(S1, E1, [seed(42)]),
        tabu_search(quadratic)::run(S2, E2, [seed(42)]).
   S1 = S2, E1 = E2.

Restarts
~~~~~~~~

Run 3 tabu-search cycles (1 initial + 2 restarts). Each restart clears
the tabu list and begins from the best state found so far:

::

   | ?- tabu_search(quadratic)::run(State, Energy, [restarts(2)]).
   State = 3.00..., Energy = 0.000...

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

Use the two-parameter version to select a specific ``fast_random``
algorithm:

::

   | ?- tabu_search(quadratic, well512a)::run(State, Energy).
   State = 3.00..., Energy = 0.000...

   | ?- tabu_search(quadratic, xoshiro256ss)::run(State, Energy, [seed(42)]).
   State = 3.00..., Energy = 0.000...
