nach oben

Soft Computing

Erschienen in:

01.11.2014 | Methodologies and Application

On the sensitivity of reactive tabu search to its meta-parameters

verfasst von: Paola Pellegrini, Franco Mascia, Thomas Stützle, Mauro Birattari

Erschienen in: Soft Computing | Ausgabe 11/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we assess the sensitivity of reactive tabu search to its meta-parameters. Based on a thorough experimental analysis of reactive tabu search applications to the quadratic assignment and the maximum clique problem, we show that its performance is relatively insensitive to its meta-parameters. This is particularly evident when compared to the sensitivity of tabu search to its parameters: tabu search is rather penalized if used with sub-optimal parameter settings. Reactive tabu search does not strongly pay its high parameter robustness in terms of performance, although it does not improve the peak performance of tabu search.

Vorheriger Artikel Global migration strategy with moving colony for hierarchical distributed evolutionary algorithms

Nächster Artikel Solving nonlinear fuzzy differential equations by using fuzzy variational iteration method

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

For a general discussion of parameter adaptation methods in evolutionary computation, we refer the interested reader to Eiben et al. (2007).

Arntzen H, Hvattum LM, Lokketangen A (2006) Adaptive memory search for multidemand multidimensional knapsack problems. Comput Oper Res 33:2508–2525MathSciNetCrossRefMATH

Battiti R (1996) Reactive-search: toward self-tuning heuristics. In: Rayward-Smith VJ (ed) Modern heuristic search methods. Wiley, Chichester, pp 61–83

Battiti R, Bertossi A (2010) Greedy, prohibition, and reactive heuristics for graph-partitioning. IEEE Trans Comput 48(4):361–385CrossRef

Battiti R, Brunato M (2005) Reactive search: machine learning for memory-based heuristics. In: Gonzalez TF (ed) Approximation algorithms and metaheuristics. Taylor & Francis Books (CRC Press), Washington, pp 21-1–21-17

Battiti R, Brunato M, Mascia F (2008) Reactive search and intelligent optimization. Operations research/computer science interfaces, vol 45. Springer, Berlin

Battiti R, Mascia F (2010) Reactive and dynamic local search for max-clique: engineering effective building blocks. Comput Oper Res 37(3):534–542MathSciNetCrossRefMATH

Battiti R, Protasi M (1999) Reactive local search techniques for the maximum k-conjunctive constraint satisfaction problem (MAX-k-CCSP). Discrete Appl Math 96–97:3–27MathSciNetCrossRef

Battiti R, Tecchiolli G (1994) The reactive tabu search. ORSA J Comput 6(2):126–140CrossRefMATH

Birattari M (2004) On the estimation of the expected performance of a metaheuristic on a class of instances. How many instances, how many runs? Tech. Rep. 2004–01, IRIDIA, Université Libre de Bruxelles, Brussels

Birattari M, Stützle T, Paquete L, Varrentrapp K et al (2002) A racing algorithm for configuring metaheuristics. In: Langdon W (ed) Proceedings of the genetic and evolutionary computation conference 2002 (GECCO’02). Morgan Kaufmann, San Francisco, pp 11–18

Chiang W, Russell R (1997) A reactive tabu search metaheuristic for the vehicle routing problem with time windows. INFORMS J Comput 9(4):417–930CrossRefMATH

DaCosta L, Fialho Á, Schoenauer M, Sebag M (2008) Adaptive operator selection with dynamic multi-armed bandits. In: Ryan C, Keijzer M (eds) Proceedings of genetic and evolutionary computation conference 2008 (GECCO’08). ACM, Atlanta, pp 913–920

Datta T, Srinidhi N, Chockalingam A, Rajan B (2010) Random-restart reactive tabu search algorithm for detection in large-MIMO systems. IEEE Commun Lett 14(12):1107–1109CrossRef

DIMACS Center (2011) DIMACS implementation challenges. http://dimacs.rutgers.edu/Challenges/

Eiben AE, Michalewicz Z, Schoenauer M, Smith JE et al (2007) Parameter control in evolutionary algorithms. In: Lobo F (ed) Parameter setting in evolutionary algorithms. Springer, Berlin, pp 19–46CrossRef

Fialho Á, DaCosta L, Schoenauer M, Sebag M (2010) Analyzing bandit-based adaptive operator selection mechanisms. Ann Math Artif Intell 60(1–2):25–64

Fink A, Voß S (2003) Solving the continuous flow-shop scheduling problem by metaheuristics. Eur J Oper Res 151(2):400–414CrossRefMATH

Hoos HH (2012) Automated algorithm configuration and parameter tuning. In: Hammadi Y, Monfroy E, Saubion F (eds) Autonomous search. Springer, Berlin, pp 37–71

Hussin M, Stützle T (2010) Tabu search vs. simulated annealing for solving large quadratic assignment instances. Tech. Rep. 2010–20, IRIDIA, Université Libre de Bruxelles, Brussels

Johnson DS, Trick MA (eds) (1993) Cliques, coloring and satisfiability: second DIMACS implementation challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol 28. American Mathematical Society, Providence

Mascia F, Pellegrini P, Stützle T, Birattari M (2013) An analysis of parameter adaptation in reactive tabu search. Int Trans Oper Res (to appear)

Maturana J, Fialho Á, Saubion F, Schoenauer M, Lardeux F, Sebag M (2012) Adaptive operator selection and management in evolutionary algorithms. In: Hammadi Y, Monfroy E, Saubion F (eds) Autonomous search. Springer, Berlin, pp 161–189

Nanry W, Barnes J (2000) Solving the pickup and delivery problem with time windows using reactive tabu search. Transp Res Part B Methodol 34(2):107–121CrossRef

Osman I, Wassan N (2002) A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. J Schedul 5(4):263–285MathSciNetCrossRefMATH

Pellegrini P, Mascia F, Stützle T, Birattari M (2011) Companion of: on the sensitivity of reactive tabu search to its meta-parameters. http://iridia.ulb.ac.be/supp/IridiaSupp2011-026/, IRIDIA Supplementary page

Pellegrini P, Stützle T, Birattari M (2012) A critical analysis of parameter adaptation in ant colony optimization. Swarm Intell 6(1):23–48CrossRef

Russell R, Chiang W, Zepeda D (2008) Integrating multi-product production and distribution in newspaper logistics. Comput Oper Res 35(5):1576–1588CrossRefMATH

Stützle T (2006) Iterated local search for the quadratic assignment problem. Eur J Oper Res 174(3):1519–1539CrossRefMATH

Stützle T, López-Ibáñez M, Pellegrini P, Maur M, Montes de Oca MA, Birattari M, Dorigo M (2012) Parameter adaptation in ant colony optimization. In: Hammadi Y, Monfroy E, Saubion F (eds) Autonomous search. Springer, Berlin, pp 191–215

Titel: On the sensitivity of reactive tabu search to its meta-parameters
verfasst von: Paola Pellegrini
Franco Mascia
Thomas Stützle
Mauro Birattari
Publikationsdatum: 01.11.2014
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 11/2014
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-013-1192-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 11/2014

Uncertain minimum cost flow problem

Global migration strategy with moving colony for hierarchical distributed evolutionary algorithms

Localized biogeography-based optimization

A revised discrete particle swarm optimization algorithm for permutation flow-shop scheduling problem

Enhancing differential evolution with role assignment scheme

Multilevel RBF to resolve classification problems with large training sets: new pseudo-exact procedure