Glover, F. 1986. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research. Vol. 13, pp. 533-549

• Glover, F. 1986. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research. Vol. 13, pp. 533-549.

• Hansen, P. 1986. The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming. Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy.

3 main strategies [7]:

• 3 main strategies [7]:

• Forbidding strategy: control what enters the tabu list
• Freeing strategy: control what exits the tabu list and when
• Short-term strategy: manage interplay between the forbidding strategy and freeing strategy to select trial solutions

Local search procedure

• Local search procedure

• Neighborhood structure

• Aspiration conditions

• Form of tabu moves

• Addition of a tabu move

• Maximum size of tabu list

• Stopping rule

A chief way to exploit memory in tabu search is to classify a subset of the moves in a neighborhood as forbidden (or tabu) [1].

• A chief way to exploit memory in tabu search is to classify a subset of the moves in a neighborhood as forbidden (or tabu) [1].

• A neighborhood is constructed to identify adjacent solutions that can be reached from current solution [8].

• The classification depends on the history of the search, and particularly on the recency or frequency that certain move or solution components, called attributes, have participated in generating past solutions [1].

• A tabu list records forbidden moves, which are referred to as tabu moves [5].

• Tabu restrictions are subject to an important exception. When a tabu move has a sufficiently attractive evaluation where it would result in a solution better than any visited so far, then its tabu classification may be overridden. A condition that allows such an override to occur is called an aspiration criterion[1].

Step 1: Choose an initial solution i in S. Set i* = i and k=0.

• Step 1: Choose an initial solution i in S. Set i* = i and k=0.

• Step 2: Set k=k+1 and generate a subset V* of solution in N(i,k) such that neither one of the Tabu conditions is violated or at least one of the aspiration conditions holds.

• Step 3: Choose a best j in V* and set i=j.

• Step 4: If f(i) < f(i*) then set i* = i.

• Step 5: Update Tabu and aspiration conditions.

• Step 6: If a stopping condition is met then stop. Else go to Step 2.

Some immediate stopping conditions could be the following [4]:

• Some immediate stopping conditions could be the following [4]:

• N(i, K+1) = 0. (no feasible solution in the neighborhood of solution i)

• K is larger than the maximum number of iterations allowed.

• The number of iterations since the last improvement of i* is larger than a specified number.

• Evidence can be given that an optimum solution has been obtained.

Minimum spanning tree problem with constraints.

• Minimum spanning tree problem with constraints.
• Objective: Connects all nodes with minimum costs

New cost = 75 (iteration 2)

• New cost = 75 (iteration 2)

• ( new best so far solution)

* A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition)

• * A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition)

• Iteration 3 new cost = 85

* A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition)

• * A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition)

• Iteration 4 new cost = 70 Override tabu status

Optimal Solution

• Optimal Solution

• Cost = 70

• Additional iterations only find

• inferior solutions

Long term memory

• Long term memory

• We’ll see how this information is used in a minute

When search not going well; e.g., haven’t found an improving neighbor in some iterations

• When search not going well; e.g., haven’t found an improving neighbor in some iterations

• New best solutions become rare

Intensify search in promising regions

• Intensify search in promising regions

• When to intensify vs. diversify: interesting; further topic we will not cover

Pros:

• Pros:

• Allows non-improving solution to be accepted in order to escape from a local optimum (true too for GA, SimAnn, AntColOpt)
• The use of Tabu list (helps avoid cycles and move reversal)
• Can be applied to both discrete and continuous solution spaces
• For larger and more difficult problems (scheduling, quadratic assignment and vehicle routing), tabu search obtains solutions that rival and often surpass the best solutions previously found by other approaches [1].

• Cons:

• Too many parameters to be determined
• Number of iterations could be very large
• Global optimum may not be found, depends on parameter settings (also true of GA, SimAnn, AntColOpt)

[1] Glover, F., Kelly, J. P., and Laguna, M. 1995. Genetic Algorithms and Tabu Search: Hybrids for Optimization. Computers and Operations Research. Vol. 22, No. 1, pp. 111 – 134.

• [1] Glover, F., Kelly, J. P., and Laguna, M. 1995. Genetic Algorithms and Tabu Search: Hybrids for Optimization. Computers and Operations Research. Vol. 22, No. 1, pp. 111 – 134.

• [2] Glover, F. and Laguna, M. 1997. Tabu Search. Norwell, MA: Kluwer Academic Publishers.

• [3] Hanafi, S. 2001. On the Convergence of Tabu Search. Journal of Heuristics. Vol. 7, pp. 47 – 58.

• [4] Hertz, A., Taillard, E. and Werra, D. A Tutorial on Tabu Search. Accessed on April 14, 2005: http://www.cs.colostate.edu/~whitley/CS640/hertz92tutorial.pdf

• [5] Hillier, F.S. and Lieberman, G.J. 2005. Introduction to Operations Research. New York, NY: McGraw-Hill. 8th Ed.

• [6] Ji, M. and Tang, H. 2004. Global Optimizations and Tabu Search Based on Mamory. Applied Mathematics and Computation. Vol. 159, pp. 449 – 457.

• [7] Pham, D.T. and Karaboga, D. 2000. Intelligent Optimisation Techniques – Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks. London: Springer-Verlag.

• [8] Reeves, C.R. 1993. Modern Heuristic Techniques for Combinatorial Problems. John Wiley & Sons, Inc.