Tabu Search

class TabuSearch(domain: Domain, fitness_function: Callable[[Solution], float], population_size: int = 10, warmup_iterations: int = 5, max_iterations: int = 20, tabu_size: int = 5, alteration_limit: float = 1.0, gamma_config: GammaConfig | None = None, distributed=False, log_dir: str = 'logs/TS')

Bases: Metaheuristic

Tabu Search Algorithm for optimization problems.

This class implements the Tabu Search metaheuristic which uses a memory structure (tabu list) to avoid revisiting recently explored solutions. The algorithm explores the neighborhood of the current solution while maintaining a list of forbidden (tabu) solutions.

Parameters:

• domain (Domain) – The problem’s domain to explore

• fitness_function (Callable[[Solution], float]) – Function to evaluate solutions

• population_size (int, optional) – Size of the population (neighborhood) to maintain, defaults to 10

• max_iterations (int, optional) – Maximum number of iterations to run, defaults to 10

• tabu_size (int, optional) – Maximum size of the tabu list, defaults to 5

• alteration_limit (float, optional) – Maximum proportion of solution to alter in local search, defaults to 1.0

• distributed (bool, optional) – Whether to use distributed computation, defaults to False

• log_dir (str, optional) – Directory for logging, defaults to “logs/TS”

Variables:

• max_iterations (int) – Maximum number of iterations to run

• tabu_size (int) – Maximum size of the tabu list

• tabu_list (Deque[Solution]) – List of recently visited solutions that are forbidden

• alteration_limit (float) – Maximum proportion of solution to alter in local search

Initialize the Tabu Search algorithm.

Parameters:

• domain (Domain) – The problem’s domain to explore

• fitness_function (Callable[[Solution], float]) – Function to evaluate solutions

• population_size (int, optional) – Size of the population (neighborhood) to maintain, defaults to 10

• max_iterations (int, optional) – Maximum number of iterations to run, defaults to 10

• tabu_size (int, optional) – Maximum size of the tabu list, defaults to 5

• alteration_limit (float, optional) – Maximum proportion of solution to alter in local search, defaults to 1.0

• distributed (bool, optional) – Whether to use distributed computation, defaults to False

• log_dir (str, optional) – Directory for logging, defaults to “logs/TS”

initialize(num_solutions: int = 10) → Tuple[List[Solution], Solution]

Initializes the Tabu Search algorithm.

Creates an initial solution and explores its neighborhood while respecting the tabu list constraints.

iterate(solutions: List[Solution]) → Tuple[List[Solution], Solution]

Execute one iteration of the Tabu Search algorithm.

Explores the neighborhood of the current best solution while respecting the tabu list constraints. The best solution found is added to the tabu list to prevent cycling.

Parameters:

solutions (List[Solution]) – Current population of solutions

Returns:

A tuple containing the new neighborhood solutions and the best solution found

Return type:

Tuple[List[Solution], Solution]

stopping_criterion() → bool

Check if the algorithm should stop.

The algorithm stops when the current iteration reaches the maximum number of iterations.

Returns:

True if the maximum number of iterations is reached, False otherwise

Return type:

bool