Tabu search

Like simulated annealing, tabu search is a technique designed to avoid the problem of becoming trapped in local optima. The procedure is basically hill-climbing, which commences at an initial solution and searches the neighbourhood for a better solution. However, the process will recognize, and avoid areas of the solution space that it has already encountered, thus making these areas tabu . The tabu moves are kept in a finite list, which is updated as the search proceeds. 

Performance of tabu search on a five-batch sequencing problem... 

Genetic algorithms Scatter search Simulated annealing Tabu search... 

Glover, F. and M. Laguna. Tabu Search. Kluwer Academic Publishers, Norwell, MA (1997). 

Laguna, M. J. W. Barnes and F. Glover. Tabu Search Methods for a Single Machine Scheduling Problem. J Intell Manufact 2 63 (1991). 

This problem can also be solved by a search method (see Chapter 10). Because the order of products cannot be changed once they start through the sequence of units, we need only determine the order in which the products are processed. This is the same problem as considered in Section 10.5.2, to illustrate the workings of tabu search. Using the notation of that section, let... 

Heuristic Search / 10.5.2 Tabu Search / 10.5.3 Simulated Annealing / 10.5.4 Genetic and Evolutionary Algorithms /... 

II with a new chapter (for the second edition) on global optimization methods, such as tabu search, simulated annealing, and genetic algorithms. Only deterministic optimization problems are treated throughout the book because lack of space precludes discussing stochastic variables, constraints, and coefficients. 

Since scope economies are especially hard to quantify, a separate class of optimization models solely dealing with plant loading decisions can be found. For example, Mazzola and Schantz (1997) propose a non-linear mixed integer program that combines a fixed cost charge for each plant-product allocation, a fixed capacity consumption to reflect plant setup and a non-linear capacity-consumption function of the total product portfolio allocated to the plant. To develop the capacity consumption function the authors build product families with similar processing requirements and consider effects from intra- and inter-product family interactions. Based on a linear relaxation the authors explore both tabu-search heuristics and branch-and-bound algorithms to obtain solutions. 

Lin, B., Chavali, S., Camarda, K. and Miller, D.C. (2005) Computer-aided molecular design using Tabu search. Comp. Chem. Eng., 29, 337. 

C. A. Baxter, C. W. Murray, D. E. Clark, D. R. Westhead, and M. D. Eldridge, Proteins Struct., Fund., Genet., 33, 367 (1998). Flexible Docking Using Tabu Search and an Empirical Estimate of Binding Affinity. 

The dumbest of these search methods by some distance is one in which colours are chosen for matching completely at random. In a random search (Fig. 2a) a colour is chosen blindly from the wheel for comparison with the paint chip. If the colours match, the search is over, but if there is no match, another colour is chosen at random and the process is repeated. This kind of search has almost no merit beyond simplicity. Even in the small search space of this problem it is inefficient, while for large spaces the probability of success falls to near zero. Furthermore, the search may revisit points it has already checked, which is unproductive. (This is avoided in a TABU search, in which a tally is kept of points previously visited, but maintaining a TABU list adds computational overhead which becomes increasingly onerous as the search progresses and cannot pretend to rescue what is a very poor method.)... 

Struct., Fund., Genet., 33, 367 (1998). Flexible Docking Using Tabu Search and an Empirical Estimate of Binding Affinity. 

Baxter, C.A. Murray, C.W. Clark, D.E. Westhead, D.R. Eldridge, M.D. Flexible docking using tabu search and an empirical estimate of binding affinity. Proteins 1998,33 (3), 367-382. 

---