Abstract
Optimization methods based on complete neighborhood exploration such as Tabu Search are impractical against large neighborhood problems. Strategies of candidate list propose a solution to reduce the neighborhood exploration complexity. We propose in this paper a generic Tabu Search algorithm using adaptive candidate list strategy based on two alternate candidate lists. Each candidate list strategy corresponds to a given search phase: intensification or diversification. The optimization algorithm uses a Tabu list containing the variables causing loops. The paper proposes a classification of Tabu tenure managing in the literature and presents a new and original Tabu tenure adaptation mechanism. The generic method is tested on the k-coloring problem and compared with some best methods published in the literature. Obtained results show the competitiveness of the method.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bachelet, V., Talbi, E.-G.: COSEARCH: a co-evolutionary metaheuristic. In: Proceedings of the Congress on Evolutionary Computation CEC 2000, pp. 1550–1557 (2000)
Battiti, R., Tecchiolli, G.: The reactive Tabu search. ORSA Journal on Computing 6(2), 126–140 (1994)
Battiti, R.V.J., Rayward-Smith, I.O., Smith, G. (eds.): Reactive Search: Toward Self-Tuning Heuristics, pp. 61–83. John Wiley and Sons Ltd, Chichester (1996)
Blöchliger, I.: Suboptimal colorings and solution of large chromatic scheduling problems, Ph.D. thesis, Mathematics Department, Ecole polytechnique federale de Lausanne, Lausanne, Suisse, 20056
Chiarandini, M., Dumitrescu, I., Stutzle, T.: Stochastic Local Search for the Graph Colouring Problem, Technical Report AIDA-05-03 (2005)
Devarenne, I., Mabed, H., Caminada, A.: Intelligent neighborhood exploration in local search heuristics. In: 18th IEEE International Conference on Tools with Artificial Intelligence, Washington D.C. USA (2006)
Devarenne, I., Mabed, H., Caminada, A.: Self-adaptive Neighborhood Exploration Parameters in Local Search. In: 7th EU/MEeting on Adaptive, Self-Adaptive, and Multi-Level Metaheuristics, University of Málaga, Spain (2006)
Di Gaspero, L., Schaerf, A.: A Tabu Search Approach to the Traveling Tournament Problem. In: MIC 2005: The 6th Metaheuristics International Conference, Vienna, Austria (2005)
Dorne, R., Hao, J.K.: Tabu Search for graph coloring, T-coloring and Set T-colorings. In: Osman, I.H., et al. (eds.) Metaheuristics 1998: Theory and Applications, ch. 3, Kluver Academic Publishers (1998)
Dupont, A.: Étude d’une métaheuristique hybride pour l’affectation de fréquences dans les réseaux tactiques évolutifs, PhD thesis, Univ. Montpellier II, France (2005)
Galinier, P., Hao, J.-K.: Hybrid Evolutionary Algorithms for Graph Coloring. Journal of Combinatorial Optimization 3, 379–397 (1999)
Galinier, P., Hertz, A., Zufferey, N.: An Adaptive Memory Algorithm for the k-colouring problem. Les Cahiers du GERAD G-2003-35 (2004)
Glover, F.: Tabu Search - Part I. ORSA Journal on Computing 1(3), 190–206 (1989)
Glover, F.: Tabu Search - Part II. ORSA Journal on Computing 2(1), 4–32 (1990)
Hansen, P., Jaumard, B.: Algorithms for the maximum satisfiability problem. Computing 4(44), 279–303 (1990)
Hao, J.-K., Galinier, P.: Tabu search for maximal constraint satisfaction problems. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 196–208. Springer, Heidelberg (1997)
Hao, J.K., Dorne, R., Galinier, P.: Tabu search for frequency assignment in mobile radio networks. Journal of Heuristics 4(1), 47–62 (1998)
Leighton, F.: A graph coloring algorithm for large scheduling problems. Journal of research of the national bureau of standards, 489–505 (1979)
Mabed, H., Devarenne, I., Caminada, A., Defaix, T.: Frequency Planning for Military Slow Frequency Hopping System. In: International Network Optimization Conference 2007, Spa, Belgium (2007)
Montemanni, R., Smith, D.H.: A Tabu search Algorithm with a dynamic Tabu list for the Frequency Assignment Problem, Technical Report, University of Glamorgan (2001)
Taillard, E.: Robust taboo search for the quadratic assignment problem. Parallel Computing 17, 443–455 (1991)
Neveu, B., Trombettoni, G., Glover, F.: A Candidate List Strategy with a Simple Diversification Device. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 423–437. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Devarenne, I., Mabed, H., Caminada, A. (2008). Adaptive Tabu Tenure Computation in Local Search. In: van Hemert, J., Cotta, C. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2008. Lecture Notes in Computer Science, vol 4972. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78604-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-540-78604-7_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78603-0
Online ISBN: 978-3-540-78604-7
eBook Packages: Computer ScienceComputer Science (R0)