.. 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 ` | **Uses:** | :ref:`fast_random(Algorithm) ` | :ref:`list ` | :ref:`type ` | **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) `, :ref:`tabu_search_problem_protocol `