Expand description
This module contains the TabuSearchSolver
implementing the
tabu search metaheuristic.
There are several tabu_improvers
(neighborhood exploration stategies)
to choose from.
- This solver requires a
TabuNeighborhood
, which, in comparison to a regularNeighborhood
, requires a tabu list as an additional argument and returns in addition to the neighbors a list of tabus that should be added to the tabu list. - Starts with an initial solution and iteratively explores the neighborhood of the current solution, while ignoring tabu solutions.
- The best non-tabu neighbor, even if it is worse than the current solution, is chosen.
- Each neighbor is paired with a list of tabus that should be added to the tabu list.
- A good tabu should forbid to return to the previous solution.
- The list of tabus is limited in size, and the oldest tabus are removed when the list is full.
- The search stops after a certain number of iterations, after a certain time limit, or if no global improvement is found after a certain number of iterations.
- The best solution seen is returned.
For examples, see the tabu search solver for the TSP.
Modules§
- This module contains several
TabuImprover
implementation, which define the strategy to explore the neighborhood of a solution in each iteration of theTabuSearchSolver
.
Structs§
- A tabu search solver that uses a
TabuNeighborhood
, anObjective
, a tabu list size, as well as a termination criterion to find a good solution.
Traits§
- Defines a neighborhood for a tabu search. Compared to a regular neighborhood, a tabu neighborhood takes a tabu list as an additional argument and returns in addition to the neighbors a list of tabus that should be added to the tabu list.