`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>`