.. index:: single: tabu_search(Problem,RandomAlgorithm)
.. _tabu_search/2:

.. rst-class:: right

**object**

``tabu_search(Problem,RandomAlgorithm)``
========================================

* ``Problem`` - Problem object implementing ``tabu_search_protocol``.
* ``RandomAlgorithm`` - Random number generator algorithm for the ``fast_random`` library (e.g. ``xoshiro128pp``, ``xoshiro256ss``, ``well512a``, ...).


Tabu search optimization algorithm. Parameterized by a problem object implementing the ``tabu_search_protocol`` protocol and by a random number generator algorithm for the ``fast_random`` library. The algorithm minimizes the energy (cost) function defined by the problem. Custom stop conditions, delta-energy neighbor generation, full neighborhood enumeration, progress reporting, and restarts can be defined by the problem object or configured via options; suitable defaults are used otherwise.

| **Availability:** 
|    ``logtalk_load(tabu_search(loader))``

| **Author:** Paulo Moura
| **Version:** 1:0:0
| **Date:** 2026-08-15

| **Compilation flags:**
|    ``static, context_switching_calls``


| **Imports:**
|    ``public`` :ref:`options <options/0>`
| **Uses:**
|    :ref:`fast_random(Algorithm) <fast_random/1>`
|    :ref:`list <list/0>`
|    :ref:`type <type/0>`

| **Remarks:**

   - Algorithm: Tabu search is a metaheuristic that guides a local search procedure using a short-term memory structure (the tabu list) to avoid cycling and to escape local minima. At each iteration a set of candidate neighbors is examined and the best admissible (non-tabu or aspiration-allowed) neighbor is selected.
   - Tabu list: A list of recently visited states paired with expiration steps. With fixed tenure the list behaves as a FIFO of maximum length ``tabu_tenure``. With ``tabu_tenure_range(Min, Max)`` each accepted move is assigned a random tenure drawn uniformly from the inclusive range.
   - Aspiration criterion: A tabu candidate is accepted when its energy is strictly better than the best energy found so far. This is the classic "best-so-far" aspiration criterion.
   - Candidate generation: By default the algorithm samples ``candidates(N)`` neighbors using ``neighbor_state/2`` (or ``neighbor_state/3`` when defined). If the problem defines ``neighbors/2``, that complete list is used instead (or a random sample of it when larger than the candidate limit).
   - Delta-energy optimization: If the problem object defines ``neighbor_state/3``, the algorithm uses the returned delta energy directly instead of calling ``state_energy/2`` on the neighbor. This is useful when computing the energy change is cheaper than recomputing the full energy.
   - 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. The reporting interval is controlled by the ``updates(N)`` option. A final report is always produced when the loop terminates.
   - Best state tracking: The algorithm tracks the best state found across all iterations and across all restart cycles, not just the final state.
   - 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.

| **Inherited public predicates:**
|     :ref:`options_protocol/0::check_option/1`  :ref:`options_protocol/0::check_options/1`  :ref:`options_protocol/0::default_option/1`  :ref:`options_protocol/0::default_options/1`  :ref:`options_protocol/0::option/2`  :ref:`options_protocol/0::option/3`  :ref:`options_protocol/0::valid_option/1`  :ref:`options_protocol/0::valid_options/1`  

.. contents::
   :local:
   :backlinks: top

Public predicates
-----------------

.. index:: run/2
.. _tabu_search/2::run/2:

``run/2``
^^^^^^^^^

Runs the tabu search algorithm using default options and returns the best state found and its energy.

| **Compilation flags:**
|    ``static``

| **Template:**
|    ``run(BestState,BestEnergy)``
| **Mode and number of proofs:**
|    ``run(-nonvar,-number)`` - ``one``


------------

.. index:: run/3
.. _tabu_search/2::run/3:

``run/3``
^^^^^^^^^

Runs the tabu search algorithm using the given options and returns the best state found and its energy.

| **Compilation flags:**
|    ``static``

| **Template:**
|    ``run(BestState,BestEnergy,Options)``
| **Mode and number of proofs:**
|    ``run(-nonvar,-number,+list(compound))`` - ``one``

| **Remarks:**

    - ``max_steps(N)`` option: Maximum number of iterations per cycle (default: ``10000``).
    - ``tabu_tenure(T)`` option: Fixed tabu tenure: maximum lifetime (in steps) of each tabu entry (default: ``7``). Ignored when ``tabu_tenure_range/2`` is also present.
    - ``tabu_tenure_range(Min, Max)`` option: 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)`` option: Number of candidate neighbors examined per iteration (default: ``20``).
    - ``updates(N)`` option: Number of progress reports during the run. Set to ``0`` to disable. Progress is reported by calling ``progress/5`` on the problem object (default: ``0``).
    - ``seed(S)`` option: Positive integer seed for the random number generator, enabling reproducible runs (default: none).
    - ``restarts(N)`` option: 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``).


------------

.. index:: run/4
.. _tabu_search/2::run/4:

``run/4``
^^^^^^^^^

Runs the tabu search algorithm using the given options, returns the best state found and its energy, and returns run statistics.

| **Compilation flags:**
|    ``static``

| **Template:**
|    ``run(BestState,BestEnergy,Statistics,Options)``
| **Mode and number of proofs:**
|    ``run(-nonvar,-number,-list(compound),+list(compound))`` - ``one``

| **Remarks:**

    - Statistics list: A list of ``Key(Value)`` pairs: ``steps(N)`` is the number of steps executed, ``acceptances(A)`` is the number of accepted moves, ``improvements(I)`` is the number of moves that improved the best energy, and ``final_tabu_size(S)`` is the number of non-expired tabu entries at termination.


------------

Protected predicates
--------------------

(no local declarations; see entity ancestors if any)

Private predicates
------------------

(no local declarations; see entity ancestors if any)

Operators
---------

(none)

.. seealso::

   :ref:`tabu_search(Problem) <tabu_search/1>`, :ref:`tabu_search_problem_protocol <tabu_search_problem_protocol/0>`

