×

General local search methods. (English) Zbl 0914.90227

Summary: This paper is a tutorial introduction to three recent yet widely used general heuristics: simulated annealing, tabu search, and genetic algorithms. A relatively precise description and an example of application are provided for each of the methods, as well as a tentative evaluation and comparison from a pragmatic point of view.

MSC:

90C27 Combinatorial optimization

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Azencott, R., Simulated Annealing. Parallelization Techniques (1992), Wiley: Wiley New York) · Zbl 0746.00020
[2] (Belew, R. K.; Booker, L. B., Proceedings of the Fourth International Conference on Genetic Algorithms (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
[3] Cerny, V., A thermodynamical approach to the traveling salesman problem: An efficient simulated algorithm, Journal of Optimization Theory and Applications, 45, 41-51 (1985) · Zbl 0534.90091
[4] Chams, M.; Hertz, A.; de Werra, D., Some experiments with simulated annealing for coloring graphs, European Journal of Operational Research, 32, 260-266 (1987) · Zbl 0626.90067
[5] Charon, I.; Hudry, O., La méthode du bruitage: Application au problème du voyageur de commerce, (Report 93D003 (1993), TELECOM: TELECOM Paris)
[6] Collins, N. E.; Eglese, R. W.; Golden, B. L., Simulated annealing: An annotated bibliography, (Report No. 88-019 (1988), College of Business and Management, University of Maryland: College of Business and Management, University of Maryland College Park, MD) · Zbl 0669.65047
[7] Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M., Ant system for jobshop scheduling, JORBEL. Belgian Journal of Operations Research, 34, 1, 39-54 (1994) · Zbl 0814.90047
[8] De Jong, K. A., An analysis of the behaviour of a class of genetic adaptive systems, (doctoral Thesis (1975), University of Michigan: University of Michigan Ann Arbor, MI)
[9] De Jong, K. A., Are genetic algorithms function optimizers?, (Männer, R.; Manderick, B., Parallel Problem Solving from Nature, 2 (1992), North-Holland: North-Holland Amsterdam), 3-14
[10] Dueck, G., New optimization heuristics. The Great Deluge algorithm and the Record-to-Record travel, Journal of Computational Physics, 104, 86-92 (1993) · Zbl 0773.65042
[11] Faigle, U.; Kern, W., Some convergence results for probabilistic Tabu Search, ORSA Journal on Computing, 4, 1, 32-37 (1992) · Zbl 0767.90069
[12] Falkenauer, E., The grouping genetic algorithms: Widening the scope of the GAs, JORBEL. Belgian Journal of Operations Research, 33, 79-102 (1993) · Zbl 0803.68037
[13] Gidas, B., Non-stationary Markov chains and convergence of the annealing algorithm, Journal of Statistical Physics, 39, 73-131 (1985) · Zbl 0642.60049
[14] Glover, F., Heuristics for integer programming using surrogate constraints, Decision Sciences, 8, 1, 156-166 (1977)
[15] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 5, 533-549 (1986) · Zbl 0615.90083
[16] Glover, F., Tabu search — Part I, ORSA Journal on Computing, 1, 190-206 (1989) · Zbl 0753.90054
[17] Glover, F., Tabu search — Part II, ORSA Journal on Computing, 2, 4-32 (1990) · Zbl 0771.90084
[18] Glover, F., Genetic Algorithms and Scatter Search: Unsuspected potentials, Statistics and Computing, 4, 131-140 (1994)
[19] Glover, F.; Greenberg, H. J., New approaches for heuristic search: A bilateral linkage with artificial intelligence, European Journal of Operational Research, 39, 119-130 (1989) · Zbl 0658.90079
[20] Glover, F.; Laguna, M., Tabu Search, (Reeves, C. R., Modern Heuristic Techniques for Combinatorial Problems (1993), Blackwell Scientific Publications: Blackwell Scientific Publications Oxford), 70-150 · Zbl 0942.90500
[21] Glover, F.; Taillard, E.; de Werra, D., A user’s guide to tabu search, Annals of Operations Research, 41, 3-28 (1993) · Zbl 0772.90063
[22] Glover, F.; Laguna, M.; Taillard, E.; de Werra, D., Tabu Search. Tabu Search, Annals of Operations Research, 41 (1993), Special Issue · Zbl 0772.90063
[23] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[24] Goldberg, D. E.; Lingle, R., Alleles, loci and the traveling salesman problem, (Grefenstette, J. J., Proceedings of an International Conference on Genetic Algorithms and their Applications (1985), Lawrence Erlbaum: Lawrence Erlbaum Hillsdale, NJ), 154-159 · Zbl 0674.90095
[25] (Grefenstette, J. J., Proceedings of an International Conference on Genetic Algorithms and their Applications (1985), Lawrence Erlbaum: Lawrence Erlbaum Hillsdale, NJ)
[26] (Grefenstette, J. J., Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms (1987), Lawrence Erlbaum: Lawrence Erlbaum Hillsdale, NJ)
[27] Grefenstette, J. J.; Gopal, R.; Rosmalta, B. J.; Van Gucht, D., Genetic algorithms for the traveling salesman problem, (Grefenstette, J. J., Proceedings of an International Cofference on Genetic Algorithms and their Applications (1985), Lawrence Erlbaum: Lawrence Erlbaum Hillsdale, NJ), 160-168 · Zbl 0674.90096
[28] Hajek, B., Cooling schedules for optimal annealing, Mathematics of Operations Research, 13, 311-329 (1988) · Zbl 0652.65050
[29] Hansen, P., The steepest ascent mildest descent heuristic for combinatorial programming, (presented at the Congress on Numerical Methods in Combinatorial Optimization. presented at the Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy (1986))
[30] Hertz, A.; de Werra, D., Using tabu search techniques for graph coloring, Computing, 29, 345-351 (1987) · Zbl 0626.68051
[31] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), The University of Michigan Press: The University of Michigan Press Ann Arbor, MI · Zbl 0317.68006
[32] Johnson, D. S.; Aragon, C. R.; McGeoch, L. A.; Schevon, C., Optimization by simulated annealing: An experimental evaluation - Part I (graph partitioning), Operations Research, 37, 6, 865-892 (1989) · Zbl 0698.90065
[33] Johnson, D. S.; Aragon, C. R.; McGeoch, L. A.; Schevon, C., Optimization by simulated annealing: An experimental evaluation - Part II (graph coloring and number partitioning), Operations Research, 39, 3, 378-406 (1991) · Zbl 0739.90055
[34] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[35] Männer, R.; Manderick, B., (Parallel Problem Solving from Nature, 2 (1992), North-Holland: North-Holland Amsterdam)
[36] Mathias, K.; Whitley, D., Genetic operators, the fitness landscape and the traveling salesman problem, (Männer, R.; Manderick, B., Parallel Problem Solving from Nature, 2 (1992), North-Holland: North-Holland Amsterdam), 219-228
[37] Mezard, M.; Parisi, G.; Virasoro, M. A., Spin Glass Theory and Beyond, (Lecture Notes in Physics, 9 (1987), World Scientific) · Zbl 0992.82500
[38] Montgomery, D., Design and Analysis of Experiments (1976), Wiley: Wiley New York
[39] Moscato, P., An introduction to population approaches for optimization and hierarchical objective function: A discussion on the role of tabu search, Annals of Operations Research, 41, 85-122 (1993) · Zbl 0775.90292
[40] Mühlenbein, H., Parallel genetic algorithms, population genetics and combinatorial optimization, (Schaffer, F. D., Proceedings of the Third International Conference on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 416-421 · Zbl 0722.92010
[41] Mühlenbein, H., Parallel genetic algorithms in combinatorial optimization, (Balci, O., Computer Science and Operations Research (1991), Pergamon: Pergamon Oxford), to appear in: · Zbl 0722.92010
[42] Nowicki, E.; Smutnicki, C., A fast Taboo Search algorithm for the Job Shop problem, (Report 8/93 (1993), Institute of Engineering Cybernetics: Institute of Engineering Cybernetics Technical University of Wroclaw), to appear in ORSA Journal on Computing · Zbl 0880.90079
[43] Nowicki, E.; Smutnicki, C., A fast Tabu Search algorithm for the Flow Shop problem, (European Journal of Operational Research (1994), Institute of Engineering Cybernetics, Technical University of Wroclaw), to appear in · Zbl 0814.90050
[44] Osman, I., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problems, Annals of Operations Research, 41, 405-421 (1993) · Zbl 0775.90153
[45] Pirlot, M., General local search heuristics in combinatorial optimization: A tutorial, JORBEL. Belgian Journal of Operations Research, 32, 1-2, 7-67 (1992) · Zbl 0768.90062
[46] Rochat, Y.; Taillard, E., Probabilistic diversification and intensification in local search for vehicle routing (1994), Centre de Recherche sur les Transports, University of Montreal · Zbl 0857.90032
[47] (Schaffer, F. D., Proceedings of the Third International Conference on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
[48] (Schwefel, H. P., Parallel Problem Solving from Nature, 1. Parallel Problem Solving from Nature, 1, Lecture Notes in Computer Science, 496 (1991), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0875.00115
[49] Siarry, J.; Dreyfus, G., La Méthode du Recuit Simulé (1989), IDSET: IDSET Paris
[50] Teghem, J.; Pirlot, M.; Antoniadis, C., Embedding of linear programming in a simulated annealing algorithm for solving a mixed integer production planning problem, Journal of Computational and Applied Mathematics (1994), to appear in · Zbl 0864.65037
[51] Tuyttens, D.; Pirlot, M.; Teghem, J.; Trauwaert, E.; Liégeois, B., Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search, Annals of Operations Research, 50, 575-607 (1994) · Zbl 0812.90111
[52] van Laarhoven, P. J.M.; Aarts, E. H.L., Simulated Annealing: Theory and Practice (1987), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0643.65028
[53] van Laarhoven, P. J.M.; Aarts, E. H.L.; Lenstra, J. K., Jobshop scheduling by simulated annealing, Operations Research, 40, 113-125 (1992) · Zbl 0819.90040
[54] (Vidal, R. V.V., Applied Simulated Annealing. Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems (1992), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0789.90064
[55] Yamada, T.; Nakano, R., A genetic algorithm applicable to large-scale Jobshop problems, (Männer, R.; Manderick, B., Parallel Problem Solving from Nature, 2 (1992), North-Holland: North-Holland Amsterdam), 281-290
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.