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 options
Uses:
fast_random(Algorithm)
list
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:
 check_option/1  check_options/1  default_option/1  default_options/1  option/2  option/3  valid_option/1  valid_options/1

Public predicates

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

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).

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)

See also

tabu_search(Problem), tabu_search_problem_protocol