Tabu Search

Tabu Search (TS) is a heuristic method originally proposed by Glover in 1986. TS has been proposed and developed for combinatorial optimization problems. However, there is a very limit number of TS contributions in continuous optimization problems. The main feature of TS is its use of an adaptive memory and responsive exploration. A simple TS combines a local search procedure with anti-cycling memory-based rules to prevent the search from getting trapped in local minima. Specifically, TS restricts returning to recently visited solutions by constructing a list of them called Tabu List (TL). In each iteration of the simple TS illustrated in the following Algorithm, TS generates many trial solutions in a neighborhood of the current solution. The trial solutions generation process is composed to avoid generating any trial solution that is already recently visited. The best trial solution found among the generated solutions will become the next solution. Therefore, TS can accept uphill movements to avoid getting trapped in local minima. TS can be terminated if the number of iterations without any improvement exceeds a predetermined maximum number.

Simple Tabu Search Algorithm.

1. Choose an initial solution x₀. Set the Tabu List (TL) to be empty, and set the counter k := 0.

2. Generate neighborhood moves list M(x_k ) = {x′ : x′ ∈ N(x_k )}, based on tabu restrictions, where N(x_k) is a neighborhood of x_k.

3. Set x_k+1 equal to the best trial solution in M(x_k ), and update TL.

4. If stopping conditions are satisfied, terminate. Otherwise, go to Step 2.

A simple TS structure given in the above Algorithm is called short-term memory TS. Updating the memory-based TL can be modified and controlled by the following concepts:

· Tabu tenure: number of iterations in which a tabu move is considered to remain tabu or forbidden;

· Aspiration criteria: accepting an improving solution even if generated by a tabu move.

The short-term memory is built to keep the recency only. In order to achieve better performance, long-term memory has been proposed to keep more important search features besides the recency, such as the quality and the frequency [32]. Specifically, long-term memory in high-level TS records attributes of special characters like elite and frequently visited solutions. Then, the search process of TS can adapt itself by using these special types of solutions in:

· Intensification: giving priority to elite solutions in order to obtain much better solutions in their vicinity.

· Diversification: discouraging attributes of frequently visited solutions in new move selection functions in order to diversify the search to other areas of solution space.