Implementing Tabu Search: Tabu List and Aspiration Criteria

1. The Philosophy of Tabu Search

At its core, Tabu Search is an enhanced form of local search. A simple local search algorithm (like hill climbing) often gets stuck because it will only accept improving moves. Once it reaches a local optimum, where all neighboring solutions are worse, the search stops.

Tabu Search overcomes this by a simple but profound rule: at each step, it moves to the best available neighbor, even if that neighbor is worse than the current solution. This allows it to "walk away" from local optima.

However, this raises a new problem: if you just moved from solution A to a worse solution B, the best move from B might be to go right back to A, creating a simple 2-move cycle. To prevent this, TS introduces memory.

Let's watch a short video that introduces this core concept.

This brings us to the central components of the algorithm: the mechanisms that implement this "memory".

2. The Core Components: Short-Term Memory

The intelligence of Tabu Search resides in its use of memory structures. The most fundamental of these is the short-term memory, which is composed of a tabu list and a tabu tenure.

2.1. The Tabu List: Remembering What to Forbid

The tabu list is the mechanism that prevents cycling. However, storing a list of entire solutions that have been recently visited is computationally expensive and memory-intensive. Instead, TS stores attributes of the moves that were made.

For a scheduling problem, a "move" might be swapping the positions of job A and job B on machine M1. The attribute stored in the tabu list could be:

• The pair of jobs (A, B).
• The specific operation that was moved.
• The position that an operation was moved out of.

By making an attribute tabu, TS forbids any move that possesses that attribute for a certain period. For example, if we swap A and B, we might forbid swapping B and A for the next few iterations.

2.2. Tabu Tenure: The Duration of Memory

An attribute doesn't stay tabu forever. The tabu tenure defines how many iterations an attribute remains on the tabu list. It is a critical parameter that balances preventing short-term cycles with allowing the search to revisit promising areas later on.

• A short tenure might not be enough to prevent cycling.
• A long tenure can be too restrictive, preventing the search from making good moves and overly constraining its exploration.

The tenure can be a fixed number (e.g., 7 iterations) or it can be dynamic, changing as the search progresses. For your thesis work, experimenting with different tenure strategies is a common part of algorithm design.

3. Aspiration Criteria: When to Break the Rules

Forbidding moves is a powerful strategy, but what if a tabu move leads to an outstanding new solution? It would be unwise to ignore it simply because it's on the forbidden list. This is where aspiration criteria come in.

An aspiration criterion is a rule that allows a tabu status to be overridden. The most common and intuitive aspiration criterion is:

If a tabu move results in a solution with a better objective value than any solution found so far in the entire search (the "best-so-far" solution), its tabu status is ignored, and the move is allowed.

This ensures that the search doesn't miss out on discovering a new global best solution because of its own rules.

4. Applying Tabu Search to Scheduling

Now, let's connect these concepts directly to your thesis topic. How would you apply TS to a Job Shop or Flexible Job Shop problem? The GERAD paper you just looked at provides an excellent, detailed example.

For a job shop problem, the key design choices are:

• Solution Representation: A feasible ordering of operations on each machine.
• Neighborhood Move: A common and effective move is to take an operation on a critical path (a sequence of operations that determines the makespan) and move it. For example, swapping two adjacent critical operations on the same machine.
• Tabu Attribute: When two operations, i and j, are swapped, the pair (i, j) or simply operation i could be added to the tabu list to prevent it from being moved back immediately.
• Objective Function: The makespan, $C_{max}$.

This example demonstrates how the general framework of Tabu Search can be tailored with problem-specific knowledge (like critical paths and specialized neighborhood structures) to create a high-performing algorithm for a difficult, real-world problem.

Conclusion

In this lesson, we have unpacked the core mechanisms of Tabu Search, a metaheuristic that uses memory to navigate complex search spaces with remarkable effectiveness.

Key Takeaways:

• Tabu Search (TS) is a local search method that always moves to the best neighboring solution, even if it's non-improving.
• It uses a tabu list, a short-term memory of move attributes, to forbid recent moves and prevent cycling.
• The tabu tenure determines how long an attribute remains forbidden and is a key parameter for tuning the algorithm's performance.
• Aspiration criteria provide a mechanism to override a tabu status, ensuring that exceptionally good moves are not missed. The most common criterion is aspirating to a new best-so-far solution.
• For scheduling problems, TS is applied by defining a neighborhood structure (e.g., swapping critical operations) and corresponding tabu attributes.

Preview of the Next Lesson:

So far in this module, we have covered three powerful metaheuristics: Genetic Algorithms, Simulated Annealing, and now Tabu Search. These are all heuristic methods, designed to find very good, but not necessarily optimal, solutions in a reasonable amount of time.

In the next module, we will shift gears and begin our study of Constraint Programming (CP). CP is an exact optimization paradigm. Instead of searching for solutions via neighborhood moves, it works by systematically reducing the set of possible solutions through logical inference and propagation. This will provide you with a powerful new way to model and solve scheduling problems, which can also be combined with metaheuristics to create even more powerful hybrid methods.