Question

How does the memory structure used in Tabu Search prevent the algorithm from entering an infinite loop when it reaches a local optimum?

Accepted Answer

Tabu Search prevents infinite loops at local optima by utilizing a short-term memory structure called a tabu list. A local optimum is a solution that appears better than its immediate neighbors but is not the best possible solution globally. When the algorithm reaches this point, it would normally cycle back and forth between two solutions because every available move leads to a worse state. The tabu list records the attributes of recently visited solutions or the specific moves made to reach them. By marking these moves as tabu, or forbidden, for a set number of iterations, the algorithm is forced to explore new areas of the search space rather than reversing its last action. For example, if the algorithm swaps two numbers to arrive at a solution, the tabu list prevents it from swapping those same two numbers back for a fixed duration. This restriction compels the algorithm to accept a move that may temporarily worsen the objective function value, effectively allowing it to escape the local optimum. Once the tabu tenure, or the duration a move remains forbidden, expires, the move becomes eligible again. This combination of forcing movement toward unexplored regions and allowing moves that decrease solution quality ensures the search continues to traverse the landscape instead of becoming trapped in a repeating cycle.

Home → All Courses → Science and Mathematics Courses → Decision Science and Optimization → Flashcard

How does the memory structure used in Tabu Search prevent the algorithm from entering an infinite loop when it reaches a local optimum?