Concentric Tabu Search

Concentric Tabu Search

Zvi Drezner

Concentric tabu search (Drezner, 2002) was designed for the solution of the Quadratic Assignment Problem (QAP). The idea is to force the search to regions of the solution space which are “far” from the starting solution hoping to find a better local optimum. It can be adapted to any tabu search algorithm once a “distance” between two solutions is defined. For example, if a solution consists of a string of binary variables, the distance between two solutions is the number of variables with different values. The QAP seeks the best permutation of assigning facilities to sites. For the QAP, the distance is the number of facilities that are assigned to different sites (or the number of sites that are assigned different facilities).

The basic principle of the concentric tabu search is as follows: A solution called “the center solution” is the starting solution of the search. The neighborhood of each solution is defined in the same manner as in standard tabu search. The search is performed in “rings” around the center solution. Suppose that a solution at distance D from the center solution is part of the current iteration. All solutions in the neighborhood which are not farther than D are in the tabu list (there is no tabu tenure). If a solution better than the best found solution is encountered, it replaces the center solution and the search is restarted from that solution. Otherwise, the search proceeds to evaluate solutions that are farther and farther away from the center solution. For any problem there is a maximum possible distance, and once this distance is reached, the algorithm terminates.

Concentric Tabu Search fits into the general framework of tabu search first introduced by Glover (1977) as the strategic oscillation, or oscillating assignment, approach. See also chapter 10.5 in Glover and Laguna (1997). This approach evolved to multi-neighborhood setting in Glover (1996) and to the variable neighborhood search (Hansen and Mladenovic, 2001).

In the specific case of the QAP, the neighborhood consists of all possible exchanges between two facilities. Suppose the iteration is at a solution which is at distance D from the center solution. The distance between a solution in the neighborhood and the center solution can only be D-2, D-1, D, D+1, D+2 because only two facilities are located at different sites. Solutions whose distance is D-2, D-1 or D are tabu. We maintain the best K solutions (K is a parameter of the search) found for every D and once the neighborhoods of the K solutions at distance D are evaluated and no solution better than the best found solution is observed, the neighborhoods of the best K solutions at a distance D+1 are evaluated, and so on.

The concentric tabu search is used as an improvement algorithm in a hybrid genetic algorithm (Drezner, 2003). Many extensions were also proposed. In Drezner (2005), two different tabu rules are defined. In the “ring moves” all solutions at distance D are also compared with the K solutions (at distance D) and if a better solution at distance D is found, the neighborhood of the improved solution is evaluated. Otherwise, the search moves to the best K solutions at distance D+1. In the “all moves” rule the search is allowed to proceed to a lower distance solution under certain conditions. For details see Drezner (2005). In Drezner (2005) the concept of “levels” L is defined. If the search fails to find an improved solution while scanning all rings, the best solution at the maximum distance (a different rule can be applied) becomes the center solution. The search is repeated L times before terminating the algorithm unless a solution which is better than the best found solution is encountered.

The best results for the QAP employing a hybrid genetic algorithm with various versions of concentric tabu or other tabu searches, such as robust tabu (Taillard, 1991), are reported in Drezner (2008a) and in the book chapter by Drezner (2008b) which is available on line for free. The book chapter by Drezner (2008b) also describes various programming “tricks” that enhance the performance of tabu algorithms. One such issue, which arises in every tabu search approach, is breaking ties between equally valued solutions. When several solutions competing for the “best one” for the next iteration exist, one of them is randomly selected by a trick described in Drezner (2010).

References

Drezner Z. (2002) “A New heuristic for the Quadratic Assignment Problem,” Journal of Applied Mathematics and Decision Sciences, 6, 163-173.

Drezner Z. (2003) "A New Genetic Algorithm for the Quadratic Assignment Problem," INFORMS Journal of Computing, 15, 320-330.

Drezner Z. (2005) "Extended Concentric Tabu for the Quadratic Assignment Problem," European Journal of Operational Research, 160, 416-422.

Drezner Z. (2008a) “Extensive Experiments with Hybrid Genetic Algorithms for the Solution of the Quadratic Assignment Problem,” Computers and Operations Research, 35, 717-736.

Drezner Z. (2008b) “Tabu Search and Hybrid Genetic Algorithms for Quadratic Assignment Problems” in W. Jaziri (ed.) Local Search Techniques: Focus on Tabu Search, IN-TECH Publishing, Chapter 5, 89-108. Available at http://sciyo.com/articles/show/title/tabu_search_and_hybrid_genetic_algorithms_for_quadratic_assignment_problems

Drezner Z. (2010) “Random Selection from a Stream of Events,” Communications of the ACM, 53, 158-159.

Glover F. (1977) “Heuristics for integer programming using surrogate constraints,” Decision Sciences, 8, 156-166.

Glover (1996) "Tabu Search and Adaptive Memory Programming - Advances, Applications and Challenges," in Interfaces in Computer Science and Operations Research, Barr, Helgason and Kennington (eds.) Kluwer Academic Publishers, 1-75.

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

Hansen, P. and Mladenovic, N. (2001) “Variable neighborhood search: Principles and applications,” European Journal of Operational Research, 130, 449–467.

Taillard, E.D. (1991) “Robust Tabu Search for the Quadratic Assignment Problem,” Parallel Computing, 17, 443-455.