Tabu Search

Ref1 - Link 

Notes

• Iterative procedure 
• Initial feasible solution to next solution in the current neighbourhood

Ref2 - Link

Notes

• The basic form of Tabu Search (TS) is founded on ideas proposed by Fred Glover (1977, 1986).
• Ordinary local or neighborhood search, proceeding iteratively from one point (solution) to another until a chosen termination criterion is satisfied.
• The most common attributive memory approaches are recency based memory and frequency-based memory
• Recency-based memory is the most common memory structure used in TS implementations.
• A key element of the adaptive memory framework of tabu search is to create a balance between search intensification and diversification.

Ref3 - Link

• A Comparative Study of Tabu Search and Simulated Annealing for Traveling Salesman Problem 
• Tabu List: To prevent the process from cycling in a small set of solutions, some attribute of recently visited solutions is stored in a Tabu List, which prevents their occurrence for a limited period.
• Diversification: The use of frequency information is used to penalize nonimproving moves by assigning a larger penalty
• Neighborhood: A neighborhood to a given solution is defined as any other solution that is obtained by a pair wise exchange of any two nodes in the solution

Book - Algorithms For Dummies

Notes

AVOIDING REPEATS USING TABU SEARCH

Tabu Search does the following

• Allows use of a pejorative solution for a few times to see whether moving away from the local solution can help the search find a better path to the best solution
• Remembers the solutions that the search tries and forbids it from using them anymore
• Creates a long-term or short-term memory of Tabu solutions by modifying the length of the queue used to store past solutions. 

Book - Metaheuristics and Evolutionary Algorithms

The TS is an enhancement of local search (LS) methods.

• TS solved the problem of convergence to local optima experienced with LS methods by allowing movements to non‐improving solutions when there is no better solution near the current solution. 
• Unlike the LS, in the TS the best neighboring point replaces the searching point even if it is worse than the current searching point
• The previous searching point is memorized as tabu
• If the new searching point is better than the best point, the new point replaces the best point; otherwise the best point remains unchanged.
• Neighboring points near the new searching point are generated. 

More Reads

• tabuSearch - R
• Ref4 - Link
• Code example - Link
• A Tabu Search-Based Algorithm for Airport Gate Assignment: A Case Study in Kunming, China
• Optimization Techniques — Tabu Search
• Code link 

Keep Thinking!!!