## 3 Tabu Search Approach
### An Overview  
Tabu Search is a meta-heuristic approach devoted to the solution of optimization problems. It uses a guided local-search procedure to explore the entire solution space in a way that makes it difficult to be entrapped in local optima and prevents solution cycling. The strategy incorporates adaptive memory that allows local searches being guided by the information collected previously, which is presented in the form of Tabu lists [11].  
Given a current solution **q**, a neighbourhood of possible solutions, N(**q**), is defined at each iteration by modifying **q** through an operation called move, whose definition is highly problem-dependent. A modified neighbourhood N'(**q**) is obtained from N(**q**), as result of maintaining a selective history of the recent states encountered during the search. The neighbours in N'(**q**) are inspected to select the best one that becomes the starting point for the new iteration (**q**'), even if it is worse than **q**. Furthermore the best solution ever found (**q***) is saved. Aspiration criteria are applied to determine when the Tabu lists can be overridden to avoid missing good solutions.  
Tabu Search makes use of short-term and long-term memory. The first one prevents solution cycling and being entrapped in local optima. It identifies the elements of N(**q**) excluded from N'(**q**) because they correspond to solutions recently visited. Short-term knowledge is provided by means of a Recency based Tabu List, where new solutions are incorporated at each iteration, and remained there as forbidden moves during the Tabu Tenure Period, _pt_.  
The use of long-term memory allows the inclusion of solutions not ordinarily found in N(**q**), because it penalizes the elements of N'(**q**) associated to moves that have been done more often. These are contained in the Frequency based Tabu list that represents the long-term memory of the technique.  
Within the framework of TS, other procedures are incorporated for search intensification and diversification such as SO and PR. The first one consists of a sequence of destructive and constructive phases. Given a feasible solution, the search is strategically driven to cross the feasibility boundary and to continue in the infeasible region (destructive phase) until certain depth is reached, then the search changes the direction towards the feasible region where it continues until the same depth (constructive phase). The process of repeatedly crossing the feasibility boundary from different directions originates an oscillatory behaviour. Standard TS mechanisms are applied to avoid going back over previous trajectories.  
Path relinking consists in selecting two components of a reference set \(R\) which is made up of high quality solutions. They are called Initiating Solution (_IS_) and Guiding Solution (_GS_) respectively. A path is generated in the neighbourhood space from the _IS_ to the _GS_ selecting moves that introduce attributes contained in _GS_. The rationale behind the strategy is that high quality solutions share certain attributes, and their combinations produce other solutions that could be better than those contained in \(R\) and even better than the best current one. The strategy performance depends on the rules adopted togenerate the reference set \(R\), select _IS_ and _GS_ and identify the neighbour structure and the guiding attributes.