Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Unified Approach for Domination Problems on Different Network Topologies Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Tabu Search∗

verfasst von : Fred Glover, Manuel Laguna

Erschienen in: Handbook of Combinatorial Optimization

Verlag: Springer New York

Einloggen

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

search-config
loading …

Abstract

Tabu search, also called adaptive memory programming, is a method for solving challenging problems in the field of optimization. The goal is to identify the best decisions or actions in order to maximize some measure of merit (such as maximizing profit, effectiveness, quality, and social or scientific benefit) or to minimize some measure of demerit (cost, inefficiency, waste, and social or scientific loss).
Practical applications in optimization addressed by tabu search are exceedingly challenging and pervade the fields of business, engineering, economics, and science. Everyday examples include problems in resource management, financial and investment planning, healthcare systems, energy and environmental policy, pattern classification, biotechnology, and a host of other areas. The complexity and importance of such problems has motivated a wealth of academic and practical research throughout the past several decades, in an effort to discover methods that are able to find solutions of higher quality than many found in the past and capable of producing such solutions within feasible time limits or at reduced computational cost.
Tabu search has emerged as one of the leading technologies for handling optimization problems that have proved difficult or impossible to solve with classical procedures that dominated the attention of textbooks and were considered the mainstays of available alternatives until recent times. A key feature of tabu search, underscored by its adaptive memory programming alias, is the use of special strategies designed to exploit adaptive memory. The idea is that an effective search for optimal solutions should involve a process of flexibly responding to the solution landscape in a manner that permits it to learn appropriate directions to take along with appropriate departures to explore new terrain. The adaptive memory feature of tabu search allows the implementation of procedures that are capable of searching this terrain economically and effectively.

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 "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

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
Vorheriges Kapitel Steiner Minimum Trees in E3: Theory, Algorithms, and Applications
Nächstes Kapitel Variations of Dominating Set Problem
Literatur
1.
D. Ackley, A Connectionist Model for Genetic Hillclimbing (Kluwer Academic Publishers, Dordrecht, 1987)CrossRef
2.
T. Bäck, F. Hoffmeister, H. Schwefel, A survey of evolution strategies, in Proceedings of the Fourth International Conference on Genetic Algorithms, San Diego, ed. by R. Belew, L. Booker (1991), pp. 2–9
3.
R. Battiti, G. Tecchiolli, Parallel based search for combinatorial optimization: genetic algorithms and tabu search. Microprocess. Microsyst. 16, 351–367 (1992)CrossRef
4.
R. Battiti, G. Tecchiolli, The reactive tabu search. ORSA J. Comput. 6(2), 126–140 (1994)CrossRefMATH
5.
D. Beyer, R. Ogier, Tabu learning: a neural network search method for solving nonconvex optimization problems, in Proceedings of the International Conference in Neural Networks (IEEE/INNS, Singapore, 1991)
6.
A. Consiglio, S.A. Zenios, Designing portfolios of financial products via integrated simulation and optimization models. Oper. Res. 47(2), 195–208 (1999)CrossRefMATH
7.
V.-D. Cung, T. Mautor, P. Michelon, A. Tavares, Scatter search for the Quadratic assignment problem, Laboratoire PRiSM-CNRS URA 1525, 1996
8.
L. Davis, Adapting operator probabilities in genetic algorithms, in Proceedings of the Third International Conference on Genetic Algorithms (Morgan Kaufmann, San Mateo, 1989), pp. 61–69
9.
D. De Werra, A. Hertz, Tabu search techniques: a tutorial and applications to neural networks. OR Spectrum 11, 131–141 (1989)CrossRefMATH
10.
A.E. Eiben, P.-E. Raue, Z. Ruttkay, Genetic algorithms with multi-parent recombination, in Proceedings of the third international conference on parallel problem solving from nature (PPSN), ed. by Y. Davidor, H.-P. Schwefel, R. Manner (Springer, New York, 1994), pp. 78–87
11.
L.J. Eschelman, J.D. Schaffer, Real-coded genetic algorithms and interval-schemata, Technical report, Phillips Laboratories, 1992
12.
T. Feo, M.G.C. Resende, A probabilistic Heuristic for a computationally difficult set covering problem Oper. Res. Lett. 8, 67–71 (1989)MathSciNetMATH
13.
T. Feo, M.G.C. Resende, Greedy randomized adaptive search procedures. J. Global Opt. 2, 1–27 (1995)MathSciNet
14.
C. Fleurent, F. Glover, P. Michelon, Z. Valli, A scatter search approach for unconstrained continuous optimization, in Proceedings of the 1996 IEEE International Conference on Evolutionary Computation (1996), pp. 643–648
15.
A. Freville, G. Plateau, Heuristics and reduction methods for multiple constraint 0-1 linear programming problems. Eur. J. Oper. Res. 24, 206–215 (1986)MathSciNetCrossRefMATH
16.
A. Freville, G. Plateau, An exact search for the solution of the surrogate dual of the 0-1 bidimensional Knapsack problem. Eur. J. Oper. Res. 68, 413–421 (1993)CrossRefMATH
17.
F. Glover, D. Klingman, N Phillips, Netform modeling and applications, Special issue on the practice of mathematical programming. Interfaces 20(1), 7–27 (1990)MathSciNetCrossRef
18.
F. Glover, Parametric combinations of local job shop rules. Chapter IV, ONR Research Memorandum no. 117, GSIA, Carnegie Mellon University, Pittsburgh, PA, 1963
19.
20.
21.
22.
F. Glover, Heuristics for integer programming using surrogate constraints. Decis. Sci. 8(1), 156–166 (1977)CrossRef
23.
24.
F. Glover, Ejection chains, reference structures and alternating path methods for traveling salesman problems. University of Colorado. Shortened version published in Discret. Appl. Math. 65(1996), 223–253 (1992)MathSciNet
25.
F. Glover, Genetic algorithms and scatter search: unsuspected potentials. Stat. Comput. 4, 131–140 (1994)
26.
F. Glover, Scatter search and star-paths: beyond the genetic metaphor. OR Spektrum 17, 125–137 (1995)CrossRefMATH
27.
F. Glover, A template for scatter search and path relinking, in Artificial Evolution, ed. by J.K. Hao, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers. Lecture Notes in Computer Science, vol. 1363 (Springer, Berlin, 1997), pp. 13–54
28.
29.
F. Glover, H. Greenberg, New approaches for Heuristic search: a bilateral linkage with artificial intelligence. Eur. J. Oper. Res. 39(2), 119–130 (1989)MathSciNetCrossRefMATH
30.
F. Glover, G. Kochenberger, Critical event Tabu search for multidimensional Knapsack problems, in Meta-Heuristics: Theory and Applications, ed. by I.H. Osman, J.P. Kelly (Kluwer Academic Publishers, Boston, 1996), pp. 407–427CrossRef
31.
32.
F. Glover, J.P. Kelly, M. Laguna, New advances and applications of combining simulation and optimization, in Proceedings of the 1996 Winter Simulation Conference, Coronado, ed. by J.M. Charnes, D.J. Morrice, D.T. Brunner, J.J. Swain (1996), pp. 144–152
33.
F. Glover, G. Kochenberger, B. Alidaee, Adaptive memory Tabu search for binary quadratic programs. Manag. Sci. 44(3), 336–345 (1998)CrossRefMATH
34.
F. Glover, J. Mulvey, D. Bai, M. Tapia, Integrative population analysis for better solutions to large-scale mathematical programs, Industrial Applications of Combinatorial Optimization, ed. by G. Yu (Kluwer Academic Publishers, Boston, 1998), pp. 212–237
35.
F. Glover, M. Laguna, R. Marti, Fundamentals of scatter search and path relinking. Control Cybern. 29(3), 653–684 (2000)MathSciNetMATH
36.
37.
H.J. Greenberg, W.P. Pierskalla, Quasi-conjugate functions and surrogate duality. Cahiers du Centre d’Etudes de Recherche Operationelle 15, 437–448 (1973)MathSciNetMATH
38.
J.H. Holland, Adaptation in natural and artificial systems (University of Michigan Press, Ann Arbor, 1975)
39.
D.S. Johnson, Local optimization and the traveling salesman problem, in Proceedings of the 17th International Colloquium on Automata, Languages and Programming (1990), pp. 446–460
40.
M.H. Karwan, R.L. Rardin, Surrogate dual multiplier search procedures in integer programming. School of Industrial Systems Engineering, Report series no. J-77-13, Georgia Institute of Technology, 1976
41.
M.H. Karwan, R.L. Rardin, Some relationships between lagrangian and surrogate duality in integer programming. Math. Program. 17, 230–334 (1979)MathSciNet
42.
J. Kelly, B. Rangaswamy, J. Xu, A scatter search-based learning algorithm for neural network training. J. Heuristics 2, 129–146 (1996)MATH
43.
M. Laguna, Optimizing complex systems with OptQuest. Research report, University of Colorado, 1997
44.
M. Laguna, T. Feo, H. Elrod, A greedy randomized adaptive search procedure for the 2-partition problem. Oper. Res. 42(4), 677–687 (1994)CrossRefMATH
45.
M. Laguna, F. Glover, Integrating target analysis and Tabu search for improved scheduling systems. Expert Syst. Appl. 6, 287–297 (1993)CrossRef
46.
M. Laguna, R. Marti, GRASP and Path Relinking for 2-Layer straight line crossing minimization. INFORMS J. Comput. 11(1), 44–52 (1999)CrossRefMATH
47.
M. Laguna, R. Martí, V. Campos, Tabu search with path relinking for the linear ordering problem. Research report, University of Colorado, 1997
48.
M. Laguna, R. Marti, V. Valls, Arc crossing minimization in hierarchical digraphs with Tabu search. Comput. Oper. Res. 24(12), 1175–1186 (1997)MathSciNetCrossRefMATH
49.
A. Lokketangen, K. Jornsten, S. Storoy, Tabu search within a pivot and complement framework. Int. Trans. Oper. Res. 1(3), 305–316 (1994)CrossRef
50.
A. Lokketangen, F. Glover, Probabilistic move selection in Tabu search for 0/1 mixed integer programming problems, in Meta-Heuristics: Theory and Applications, ed. by I.H. Osman, J.P. Kelly (Kluwer Academic Publishers, Boston, 1996), pp. 467–488
51.
A. Lokketangen, F. Glover, Surrogate constraint analysis—new heuristics and learning schemes for satisfiability problems, in Proceedings of the DIMACS workshop on Satisfiability Problems: Theory and Applications, Providence, ed. by D.-Z. Du, J. Gu, P. Pardalos (1997)
52.
H.R. Lourenco, M. Zwijnenburg, Combining the large-step optimization with Tabu search: application to the job shop scheduling problem, in Meta-Heuristics: Theory and Applications, ed. by I.H. Osman, J.P. Kelly (Kluwer Academic Publishers, Boston, 1996), pp. 219–236CrossRef
53.
O. Martin, S.W. Otto, E.W. Felten, Large-step Markov chains for the traveling salesman problem. Complex Syst. 5(3), 299–326 (1991)MathSciNetMATH
54.
O. Martin, S.W. Otto, E.W. Felten, Large-step Markov chains for TSP incorporating local search heuristics. Oper. Res. Lett. 11(4), 219–224 (1992)MathSciNetCrossRefMATH
55.
Z. Michalewicz, C. Janikow, Genetic algorithms for numerical optimization. Stat. Comput. 1, 75–91 (1991)CrossRef
56.
H. Mühlenbein, D. Schlierkamp-Voosen, The science of breeding and its application to the Breeder genetic algorithm. Evolut. Computat. 1, 335–360 (1994)CrossRef
57.
H. Mühlenbein, H.-M. Voigt, Gene pool recombination in genetic algorithms, Meta-Heurisitics: Theory and Applications, ed. by I.H. Osman, J.P. Kelly (Kluwer Academic Publishers, Boston, 1996), 53–62
58.
H. Mühlenbein, M. Gorges-Schleuter, O. Krämer, Evolution algorithms in combinatorial optimization. Parallel Comput. 7, 65–88 (1988)CrossRefMATH
59.
K. Nonobe, T. Ibaraki, A Tabu search approach for the constraint satisfaction problem as a general problem solver. Eur. J. Oper. Res. 106, 599–623 (1998)CrossRefMATH
60.
K. Nonobe, T. Ibaraki, An improved tabu search method for the weighted constraint satisfaction problem. INFOR 39, 131–151 (2001)
61.
A.P. Punnen, F. Glover, Ejection chains with combinatorial leverage for the traveling salesman problem, Graduate School of Business, University of Colorado at Boulder, 1997
62.
S. Rana, D. Whitley, Bit representations with a twist, in Proceedings of the 7th International Conference on Genetic Algorithms, ed. by T. Baeck (Morgan Kaufman, San Francisco, 1997), pp. 188–196
63.
C. Rego, F. Glover, Ejection chain and filter-and-fan methods in combinatorial optimization. Ann. Oper. Res. (2009). Springer Science+Business Media, LLC, doi:10.1007/s10479-009-0656-7
64.
Y. Rochat, É.D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995)CrossRefMATH
65.
W.M. Spears, K.A. DeJong, On the virtues of uniform crossover, in Proceedings of the 4th International Conference on Genetic Algorithms, La Jolla, CA, 1991
66.
É.D. Taillard, A heuristic column generation method for the heterogeneous VRP. Publication CRT-96-03, Centre de recherche sur les transports, Université de Montréal. To appear in RAIRO-OR, 1996
67.
T. Trafalis, I. Al-Harkan, A continuous scatter search approach for Global optimization. Extended abstract in Conference in Applied Mathematical Programming and Modeling (APMOD’95), London, UK, 1995
68.
N.L.J. Ulder, E. Pech, P.J.M. van Laarhoven, H.J. Bandelt, E.H.L. Aarts, Genetic local search algorithm for the traveling salesman problem, in Parallel Problem Solving from Nature, ed. by R. Maenner, H.P. Schwefel (Springer, Berlin, 1991), pp. 109–116CrossRef
69.
D. Whitley, V.S. Gordon, K. Mathias, Lamarckian evolution, the Baldwin effect and function optimization, in Proceedings of the Parallel Problem Solving from Nature, vol. 3 (Springer, New York, 1994) pp. 6–15
70.
A.H. Wright, Genetic algorithms for real parameter optimization, Foundations of Genetic Algorithms, ed. by G. Rawlins, (Morgan Kaufmann, Los Altos, CA, 1990) pp. 205–218
71.
T. Yamada, R. Nakano, Scheduling by Genetic local search with multi-step crossover, in Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, Berlin (1996), pp. 960–969
72.
T. Yamada, C. Reeves, Permutation flowshop scheduling by genetic local search, in Proceedings of the 2nd IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems (GALESIA ’97), Glasglow, UK (1997), pp. 232–238
73.
S. Zenios, Dynamic financial modeling and optimizing the design of financial products, Presented at the National INFORMS Meeting, Washington, DC, 1996
Metadaten
Titel
Tabu Search∗
verfasst von
Fred Glover
Manuel Laguna
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Handbook of Combinatorial Optimization

Print ISBN: 978-1-4419-7996-4

Electronic ISBN: 978-1-4419-7997-1

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4419-7997-1_17