Metaheuristics in combinatorial optimization

ABSTRACT

The field of metaheuristics for the application to combinatorial optimization problems is a rapidly growing field of research. This is due to the importance of combinatorial optimization problems for the scientific as well as the industrial world. We give a survey of the nowadays most important metaheuristics from a conceptual point of view. We outline the different components and concepts that are used in the different metaheuristics in order to analyze their similarities and differences. Two very important concepts in metaheuristics are intensification and diversification. These are the two forces that largely determine the behavior of a metaheuristic. They are in some way contrary but also complementary to each other. We introduce a framework, that we call the I&D frame, in order to put different intensification and diversification components into relation with each other. Outlining the advantages and disadvantages of different metaheuristic approaches we conclude by pointing out the importance of hybridization of metaheuristics as well as the integration of metaheuristics and other methods for optimization.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Aarts, E. H. L., Korst, J. H. M., and Laarhoven, P. J. M. v. 1997. Simulated annealing. In Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra, Eds. Wiley-Interscience, Chichester, England, 91--120.
	2	Emile Aarts , Jan K. Lenstra, Local Search in Combinatorial Optimization, John Wiley & Sons, Inc., New York, NY, 1997
	3	R. M. Aiex , S. Binato , M. G. C. Resende, Parallel GRASP with path-relinking for job shop scheduling, Parallel Computing, v.29 n.4, p.393-430, 01 April 2003 [doi>10.1016/S0167-8191(03)00014-0]
	4	Bachelet, V. and Talbi, E. 2000. Cosearch: A co-evolutionary metaheuritics. In Proceedings of Congress on Evolutionary Computation---CEC'2000. 1550--1557.
	5	Thomas Bäck, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, Oxford University Press, Oxford, 1996
	6	Thomas Back , David B. Fogel , Zbigniew Michalewicz, Handbook of Evolutionary Computation, IOP Publishing Ltd., Bristol, UK, 1997
	7	Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
	8	Baluja, S. and Caruana, R. 1995. Removing the genetics from the standard genetic algorithm. In The International Conference on Machine Learning 1995, A. Prieditis and S. Russel, Eds. Morgan-Kaufmann Publishers, San Mateo, Calif., 38--46.
	9	Yaneer Bar-Yam, Dynamics of complex systems, Perseus Books, Cambridge, MA, 1997
	10	Battiti, R. 1996. Reactive search: Toward self-tuning heuristics. In Modern Heuristic Search Methods, V. J. Rayward-Smith, I. H. Osman, C. R. Reeves, and G. D. Smith, Eds. Wiley, Chichester, UK, 61--83.
	11	Roberto Battiti , Marco Protasi, Reactive search, a history-sensitive heuristic for MAX-SAT, Journal of Experimental Algorithmics (JEA), 2, p.2-es, 1997 [doi>10.1145/264216.264220]
	12	Battiti, R. and Tecchiolli, G. 1994. The reactive tabu search. ORSA J. Comput. 6, 2, 126--140.
	13	Binato, S., Hery, W. J., Loewenstern, D., and Resende, M. G. C. 2001. A greedy randomized adaptive search procedure for job shop scheduling. In Essays and Surveys on Metaheuristics, P. Hansen and C. C. Ribeiro, Eds. Kluwer Academic Publishers.
	14	Christian Blum, ACO Applied to Group Shop Scheduling: A Case Study on Intensification and Diversification, Proceedings of the Third International Workshop on Ant Algorithms, p.14-27, September 12-14, 2002
	15	Christian Blum, Ant Colony Optimization For The Edge-weighted k-cardinality Tree Problem, Proceedings of the Genetic and Evolutionary Computation Conference, p.27-34, July 09-13, 2002
	16	Blum, C., Roli, A., and Dorigo, M. 2001. HC--ACO: The hyper-cube framework for ant colony optimization. In Proceedings of MIC'2001---Meta--heuristics International Conference. Vol. 2. Porto, Portugal, 399--403.
	17	Patrice Calégari , Giovanni Coray , Alain Hertz , Daniel Kobler , Pierre Kuonen, A Taxonomy of Evolutionary Algorithms in Combinatorial Optimization, Journal of Heuristics, v.5 n.2, p.145-158, July 1999 [doi>10.1023/A:1009625526657]
	18	Vicente Campos , Fred Glover , Manuel Laguna , Rafael Martí, An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem, Journal of Global Optimization, v.21 n.4, p.397-414, December 2001 [doi>10.1023/A:1012793906010]
	19	Caseau, Y. and Laburthe, F. 1999. Effective forget-and-extend heuristics for scheduling problems. In Proceedings of CP-AI-OR'02---Fourth Int. Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems. Ferrara (Italy). Also available at: www.deis.unibo.it/Events/Deis/Workshops/Proceedings.html.
	20	Cerny, V. 1985. A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm. J. Optim. Theory Appl. 45, 41--51.
	21	Chardaire, P., Lutton, J. L., and Sutter, A. 1995. Thermostatistical persistency: A powerful improving concept for simulated annealing algorithms. Europ. J. Oper. Res. 86, 565--579.
	22	Carlos A. Coello, An updated survey of GA-based multiobjective optimization techniques, ACM Computing Surveys (CSUR), v.32 n.2, p.109-143, June 2000 [doi>10.1145/358923.358929]
	23	Connolly, D. T. 1990. An improved annealing scheme for the QAP. Europ. J. Oper. Res. 46, 93--100.
	24	Teodor Gabriel Crainic , Michel Toulouse, Introduction to the Special Issue on Parallel Meta-Heuristics, Journal of Heuristics, v.8 n.3, p.247-249, May 2002 [doi>10.1023/A:1015084116772]
	25	Crainic, T. G. and Toulouse, M. 2002b. Parallel strategies for meta-heuristics. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds. International Series in Operations Research & Management Science, vol. 57. Kluwer Academic Publishers, Norwell, MA.
	26	Bruno De Backer , Vincent Furnon , Paul Shaw , Philip Kilby , Patrick Prosser, Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics, Journal of Heuristics, v.6 n.4, p.501-523, September 2000 [doi>10.1023/A:1009621410177]
	27	de Bonet, J. S., Isbell Jr., C. L., and Viola, P. 1997. MIMIC: Finding optima by estimating probability densities. In Proceedings of the 1997 Conference on Advances in Neural Information Processing Systems (NIPS'97), M. C. Mozer, M. I. Jordan, and T. Petsche, Eds. MIT Press, Cambridge, MA, 424--431.
	28	Kenneth Alan De Jong, An analysis of the behavior of a class of genetic adaptive systems., 1975
	29	Della Croce, F. and T'kindt, V. 2003. A Recovering Beam Search algorithm for the one machine dynamic total completion time scheduling problem. J. Oper. Res. Soc. To appear.
	30	Dell'Amico, M. and Lodi, A. 2002. On the integration of metaheuristic strategies in constraint programming. In Adaptive Memory and Evolution: Tabu Search and Scatter Search, C. Rego and B. Alidaee, Eds. Kluwer Academic Publishers, Boston, MA.
	31	Mauro Dell‘amico , Andrea Lodi , Francesco Maffioli, Solution of the Cumulative Assignment Problem With a Well-Structured TabuSearch Method, Journal of Heuristics, v.5 n.2, p.123-143, July 1999 [doi>10.1023/A:1009647225748]
	32	Matthijs den Besten , Thomas Stützle , Marco Dorigo, Design of Iterated Local Search Algorithms, Proceedings of the EvoWorkshops on Applications of Evolutionary Computing, p.441-451, April 18-20, 2001
	33	Deneubourg, J.-L., Aron, S., Goss, S., and Pasteels, J.-M. 1990. The self-organizing exploratory pattern of the argentine ant. J. Insect Behav. 3, 159--168.
	34	Denzinger, J. and Offerman, T. 1999. On cooperation between evolutionary algorithms and other search paradigms. In Proceedings of Congress on Evolutionary Computation---CEC'1999. 2317--2324.
	35	Devaney, R. L. 1989. An introduction to chaotic dynamical systems, second ed. Addison--Wesley, Reading, Mass.
	36	Di Caro, G. and Dorigo, M. 1998. AntNet: Distributed stigmergetic control for communication networks. J. Artif. Int. Res. 9, 317--365.
	37	Dorigo, M. 1992. Optimization, learning and natural algorithms (in italian). Ph.D. thesis, DEI, Politecnico di Milano, Italy. pp. 140.
	38	Marco Dorigo , Gianni Di Caro, The ant colony optimization meta-heuristic, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
	39	Marco Dorigo , Gianni Di Caro , Luca M. Gambardella, Ant algorithms for discrete optimization, Artificial Life, v.5 n.2, p.137-172, April 1999 [doi>10.1162/106454699568728]
	40	Dorigo, M. and Gambardella, L. M. 1997. Ant colony system: A cooperative learning approach to the travelling salesman problem. IEEE Trans. Evolution. Comput. 1, 1 (Apr.), 53--66.
	41	Dorigo, M., Maniezzo, V., and Colorni, A. 1996. Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybernet.---Part B 26, 1, 29--41.
	42	Dorigo, M. and Stützle, T. 2002. The ant colony optimization metaheuristic: Algorithms, applications and advances. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds. International Series in Operations Research & Management Science, vol. 57. Kluwer Academic Publishers, Norwell, MA, 251--285.
	43	Marco Dorigo , Thomas Stützle, Ant Colony Optimization, Bradford Book, 2004
	44	Gunter Dueck, New optimization heuristics, Journal of Computational Physics, v.104 n.1, p.86-92, Jan. 1993 [doi>10.1006/jcph.1993.1010]
	45	Gunter Dueck , Tobias Scheuer, Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, v.90 n.1, p.161-175, Sept. 1990 [doi>10.1016/0021-9991(90)90201-B]
	46	A. E. Eiben , Paul-Erik Raué , Zsófia Ruttkay, Genetic algorithms with multi-parent recombination, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.78-87, October 09-14, 1994
	47	Eiben, A. E. and Ruttkay, Z. 1997. Constraint satisfaction problems. In Handbook of Evolutionary Computation, T. Bäck, D. Fogel, and M. Michalewicz, Eds. Institute of Physics Publishing Ltd, Bristol, UK.
	48	A. E. Eiben , C. A. Schippers, On evolutionary exploration and exploitation, Fundamenta Informaticae, v.35 n.1-4, p.35-50, Aug. 1998
	49	Feller, W. 1968. An Introduction to Probability Theory and Its Applications. Wiley, New York.
	50	Feo, T. A. and Resende, M. G. C. 1995. Greedy randomized adaptive search procedures. J. Global Optim. 6, 109--133.
	51	Festa, P. and Resende, M. G. C. 2002. GRASP: An annotated bibliography. In Essays and Surveys on Metaheuristics, C. C. Ribeiro and P. Hansen, Eds. Kluwer Academic Publishers, 325--367.
	52	Andreas Fink , Stefan Voß, Generic metaheuristics application to industrial engineering problems, Computers and Industrial Engineering, v.37 n.1-2, p.281-284, Oct. 1999 [doi>10.1016/S0360-8352(99)00074-1]
	53	Mark Fleischer, Simulated annealing: past, present, and future, Proceedings of the 27th conference on Winter simulation, p.155-161, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224457]
	54	Focacci, F., Laburthe, F., and Lodi, A. 2002. Local search and constraint programming. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds. International Series in Operations Research & Management Science, vol. 57. Kluwer Academic Publishers, Norwell, MA.
	55	Fogel, D. B. 1994. An introduction to simulated evolutionary optimization. IEEE Trans. Neural Netw. 5, 1 (Jan.), 3--14.
	56	Fogel, G. B., Porto, V. W., Weekes, D. G., Fogel, D. B., Griffey, R. H., McNeil, J. A., Lesnik, E., Ecker, D. J., and Sampath, R. 2002. Discovery of RNA structural elements using evolutionary computation. Nucleic Acids Res. 30, 23, 5310--5317.
	57	Fogel, L. J. 1962. Toward inductive inference automata. In Proceedings of the International Federation for Information Processing Congress. Munich, 395--399.
	58	Fogel, L. J., Owens, A. J., and Walsh, M. J. 1966. Artificial Intelligence through Simulated Evolution. Wiley, New York.
	59	Fonlupt, C., Robilliard, D., Preux, P., and Talbi, E. 1999. Fitness landscapes and performance of meta-heuristics. In Meta-heuristics: advances and trends in local search paradigms for optimization, S. Voβ, S. Martello, I. Osman, and C. Roucairol, Eds. Kluwer Academic.
	60	Freisleben, B. and Merz, P. 1996. A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In International Conference on Evolutionary Computation. 616--621.
	61	Freuder, E. C., Dechter, R., Ginsberg, M. L., Selman, B., and Tsang, E. P. K. 1995. Systematic versus stochastic constraint satisfaction. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI 1995. Vol. 2. Morgan-Kaufmann, 2027--2032.
	62	Luca Maria Gambardella , Marco Dorigo, An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem, INFORMS Journal on Computing, v.12 n.3, p.237-255, July 2000 [doi>10.1287/ijoc.12.3.237.12636]
	63	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	64	M. Gendreau , G. Laporte , J.-Y. Potvin, Metaheuristics for the capacitated VRP, The vehicle routing problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, 01
	65	Ginsberg, M. L. 1993. Dynamic backtracking. J. Artif. Int. Res. 1, 25--46.
	66	Glover, F. 1977. Heuristics for integer programming using surrogate constraints. Dec. Sci. 8, 156--166.
	67	Fred Glover, Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, v.13 n.5, p.533-549, May 1986 [doi>10.1016/0305-0548(86)90048-1]
	68	Glover, F. 1990. Tabu search Part II. ORSA J. Comput. 2, 1, 4--32.
	69	Fred Glover, Scatter search and path relinking, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
	70	Fred Glover , Fred Laguna, Tabu Search, Kluwer Academic Publishers, Norwell, MA, 1997
	71	Glover, F., Laguna, M., and Martí, R. 2000. Fundamentals of scatter search and path relinking. Control, 29, 3, 653--684.
	72	Glover, F., Laguna, M., and Martí, R. 2002. Scatter search and path relinking: Advances and applications. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds. International Series in Operations Research & Management Science, vol. 57. Kluwer Academic Publishers, Norwell, MA.
	73	David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	74	Goldberg, D. E., Deb, K., and Korb, B. 1991. Don't worry, be messy. In Proceedings of the 4th International Conference on Genetic Algorithms. Morgan-Kaufmann, La Jolla, CA.
	75	David E. Goldberg , Jon Richardson, Genetic algorithms with sharing for multimodal function optimization, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.41-49, October 1987, Cambridge, Massachusetts, United States
	76	Carla P. Gomes , Bart Selman , Nuno Crato , Henry Kautz, Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems, Journal of Automated Reasoning, v.24 n.1-2, p.67-100, February 2000 [doi>10.1023/A:1006314320276]
	77	Grefenstette, J. J. 1987. Incorporating problem specific knowledge into genetic algorithms. In Genetic Algorithms and Simulated Annealing, L. Davis, Ed. Morgan-Kaufmann, 42--60.
	78	Grefenstette, J. J. 1990. A user's guide to GENESIS 5.0. Tech. rep., Navy Centre for Applied Research in Artificial Intelligence, Washington, D.C.
	79	Hansen, P. 1986. The steepest ascent mildest descent heuristic for combinatorial programming. In Congress on Numerical Methods in Combinatorial Optimization. Capri, Italy.
	80	Hansen, P. and Mladenović, N. 1997. Variable neighborhood search for the p-median. Loc. Sci. 5, 207--226.
	81	Hansen, P. and Mladenović, N. 1999. An introduction to variable neighborhood search. In Meta-heuristics: Advances and trends in local search paradigms for optimization, S. Voβ, S. Martello, I. Osman, and C. Roucairol, Eds. Kluwer Academic Publishers, Chapter 30, 433--458.
	82	Hansen, P. and Mladenović, N. 2001. Variable neighborhood search: Principles and applications. Europ. J. Oper. Res. 130, 449--467.
	83	Harik, G. 1999. Linkage learning via probabilistic modeling in the ECGA. Tech. Rep. No. 99010, IlliGAL, University of Illinois.
	84	William David Harvey, Nonsystematic backtracking search, Stanford University, Stanford, CA, 1995
	85	Harvey, W. D. and Ginsberg, M. L. 1995. Limited discrepancy search. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI 1995 (Montréal, Qué, Canada). C. S. Mellish, Ed. Vol. 1. Morgan-Kaufmann, 607--615.
	86	Hertz, A. and Kobler, D. 2000. A framework for the description of evolutionary algorithms. Europ. J. Oper. Res. 126, 1--12.
	87	Hogg, T. and Huberman, A. 1993. Better than the best: The power of cooperation. In SFI 1992 Lectures in Complex Systems. Addison-Wesley, 163--184.
	88	Hogg, T. and Williams, C. 1993. Solving the really hard problems with cooperative search. In Proceedings of AAAI93. AAAI Press, 213--235.
	89	John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
	90	Hordijk, W. 1996. A measure of landscapes. Evolut. Comput. 4, 4, 335--360.
	91	Ingber, L. 1996. Adaptive simulated annealing (ASA): Lessons learned. Cont. Cybernet.---Special Issue on Simulated Annealing Applied to Combinatorial Optimization 25, 1, 33--54.
	92	Johnson, D. S. and McGeoch, L. A. 1997. The traveling salesman problem: a case study. In Local Search in Combinatorial Optimization, E. Aarts and J. Lenstra, Eds. Wiley, New York, 215--310.
	93	Jones, T. 1995a. Evolutionary algorithms, fitness landscapes and search. Ph.D. thesis, Univ. of New Mexico, Albuquerque, NM.
	94	Jones, T. 1995b. One operator, one landscape. Santa Fe Institute Tech. Rep. 95-02-025, Santa Fe Institute.
	95	Joslin, D. E. and Clements, D. P. 1999. "Squeaky Wheel" Optimization. J. Artif. Int. Res. 10, 353--373.
	96	Narendra Jussien , Olivier Lhomme, Local search with constraint propagation and conflict-based heuristics, Artificial Intelligence, v.139 n.1, p.21-45, July 2002 [doi>10.1016/S0004-3702(02)00221-7]
	97	Kauffman, S. A. 1993. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press.
	98	Kilby, P., Prosser, P., and Shaw, P. 1999. Guided Local Search for the Vehicle Routing Problem with time windows. In Meta-heuristics: Advances and trends in local search paradigms for optimization, S. Voβ, S. Martello, I. Osman, and C. Roucairol, Eds. Kluwer Academic, 473--486.
	99	Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science, 13 May 1983 220, 4598, 671--680.
	100	Laguna, M., Lourenço, H., and Martí, R. 2000. Assigning Proctors to Exams with Scatter Search. In Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, M. Laguna and J. L. González-Velarde, Eds. Kluwer Academic Publishers, Boston, MA, 215--227.
	101	Manuel Laguna , Rafael Marti, Grasp and Path Relinking for 2-Layer Straight Line Crossing Minimization, INFORMS Journal on Computing, v.11 n.1, p.44-52, January 1999 [doi>10.1287/ijoc.11.1.44]
	102	Manuel Laguna , Rafael Marti , Vicente Campos, Intensification and diversification with elite tabu search solutions for the linear ordering problem, Computers and Operations Research, v.26 n.12, p.1217-1230, Oct. 1999 [doi>10.1016/S0305-0548(98)00104-X]
	103	Larrañaga, P. and Lozano, J. A., Eds. 2002. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, Boston, MA.
	104	Lourenço, H. R., Martin, O., and Stützle, T. 2001. A beginner's introduction to Iterated Local Search. In Proceedings of MIC'2001---Meta--heuristics International Conference. Vol. 1. Porto---Portugal, 1--6.
	105	Lourenço, H. R., Martin, O., and Stützle, T. 2002. Iterated local search. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds. International Series in Operations Research & Management Science, vol. 57. Kluwer Academic Publishers, Norwell, MA, 321--353.
	106	M Lundy , A Mees, Convergence of an annealing algorithm, Mathematical Programming: Series A and B, v.34 n.1, p.111-124, Jan. 1986 [doi>10.1007/BF01582166]
	107	Martin, O. and Otto, S. W. 1996. Combining simulated annealing with local search heuristics. Ann. Oper. Res. 63, 57--75.
	108	Martin, O., Otto, S. W., and Felten, E. W. 1991. Large-step Markov chains for the traveling salesman problem. Complex Syst. 5, 3, 299--326.
	109	Merkle, D., Middendorf, M., and Schmeck, H. 2002. Ant colony optimization for resource-constrained project scheduling. IEEE Trans. Evolut. Comput. 6, 4, 333--346.
	110	Metaheuristics Network Website 2000. http://www.metaheuristics.net/. Visited in January 2003.
	111	Nicolas Meuleau , Marco Dorigo, Ant colony optimization and stochastic gradient descent, Artificial Life, v.8 n.2, p.103-121, July 2002 [doi>10.1162/106454602320184202]
	112	Michalewicz, Z. and Michalewicz, M. 1997. Evolutionary computation techniques and their applications. In Proceedings of the IEEE International Conference on Intelligent Processing Systems, (Beijing, China). Institute of Electrical & Electronics Engineers, Incorporated, 14--24.
	113	Milano, M. and Roli, A. 2002. On the relation between complete and incomplete search: An informal discussion. In Proceedings of CP-AI-OR'02---Fourth Int. Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (Le Croisic, France). 237--250.
	114	Mills, P. and Tsang, E. 2000. Guided local search for solving SAT and weighted MAX-SAT Problems. In SAT2000, I. Gent, H. van Maaren, and T. Walsh, Eds. IOS Press, 89--106.
	115	Melanie Mitchell, An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA, 1998
	116	Mladenović, N. and Urošević, D. 2001. Variable neighborhood search for the k-cardinality tree. In Proceedings of MIC'2001---Meta--heuristics International Conference. Vol. 2. Porto, Portugal, 743--747.
	117	Moscato, P. 1989. On evolution, search, optimization, genetic algorithms and martial arts: Toward memetic algorithms. Tech. Rep. Caltech Concurrent Computation Program 826, California Institute of Technology,Pasadena, Calif.
	118	Pablo Moscato, Memetic algorithms: a short introduction, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
	119	Mühlenbein, H. 1991. Evolution in time and space---The parallel genetic algorithm. In Foundations of Genetic Algorithms, G. J. E. Rawlins, Ed. Morgan-Kaufmann, San Mateo, Calif.
	120	Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
	121	Mühlenbein, H. and Voigt, H.-M. 1995. Gene pool recombination in genetic algorithms. In Proc. of the Metaheuristics Conference, I. H. Osman and J. P. Kelly, Eds. Kluwer Academic Publishers, Norwell, USA.
	122	George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
	123	Eugeniusz Nowicki , Czeslaw Smutnicki, A fast taboo search algorithm for the job shop problem, Management Science, v.42 n.6, p.797-813, June 1996 [doi>10.1287/mnsc.42.6.797]
	124	Ibrahim Hassan Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, v.41 n.1-4, p.421-451, 1993
	125	Osman, I. H. and Laporte, G. 1996. Metaheuristics: A bibliography. Ann. Oper. Res. 63, 513--623.
	126	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	127	Pelikan, M., Goldberg, D. E., and Cantú-Paz, E. 1999a. BOA: The Bayesian optimization algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99 (Orlando, Fla.). W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, Eds. Vol. I. Morgan-Kaufmann Publishers, San Fransisco, CA, 525--532.
	128	Pelikan, M., Goldberg, D. E., and Lobo, F. 1999b. A survey of optimization by building and using probabilistic models. Tech. Rep. No. 99018, IlliGAL, University of Illinois.
	129	Pesant, G. and Gendreau, M. 1996. A view of local search in Constraint Programming. In Principles and Practice of Constraint Programming---CP'96. Lecture Notes in Computer Science, vol. 1118. Springer-Verlag, 353--366.
	130	Gilles Pesant , Michel Gendreau, A Constraint Programming Framework for Local Search Methods, Journal of Heuristics, v.5 n.3, p.255-279, October 1999 [doi>10.1023/A:1009694016861]
	131	Pitsoulis, L. S. and Resende, M. G. C. 2002. Greedy randomized adaptive search procedure. In Handbook of Applied Optimization, P. Pardalos and M. Resende, Eds. Oxford University Press, 168--183.
	132	Marcelo Prais , Celso C. Ribeiro, Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment, INFORMS Journal on Computing, v.12 n.3, p.164-176, July 2000 [doi>10.1287/ijoc.12.3.164.12639]
	133	Prestwich, S. 2002. Combining the scalability of local search with the pruning techniques of systematic search. Ann. Oper. Res. 115, 51--72.
	134	Radcliffe, N. J. 1991. Forma Analysis and Random Respectful Recombination. In Proceedings of the Fourth International Conference on Genetic Algorithms, ICGA 1991. Morgan-Kaufmann, San Mateo, Calif., 222--229.
	135	Rayward-Smith, V. J. 1994. A unified approach to tabu search, simulated annealing and genetic algorithms. In Applications of Modern Heuristics, V. J. Rayward-Smith, Ed. Alfred Waller Limited, Publishers.
	136	Rechenberg, I. 1973. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog.
	137	Colin R. Reeves, Modern heuristic techniques for combinatorial problems, John Wiley & Sons, Inc., New York, NY, 1993
	138	Reeves, C. R. 1999. Landscapes, operators and heuristic search. Ann. Oper. Res. 86, 473--490.
	139	Colin R. Reeves , Jonathan E. Rowe, Genetic Algorithms: Principles and Perspectives: A Guide to GA Theory, Kluwer Academic Publishers, Norwell, MA, 2002
	140	Rego, C. 1998. Relaxed Tours and Path Ejections for the Traveling Salesman Problem. Europ. J. Oper. Res. 106, 522--538.
	141	César Rego, Node-ejection chains for the vehicle routing problem: sequential and parallel algorithms, Parallel Computing, v.27 n.3, p.201-222, February 1, 2001 [doi>10.1016/S0167-8191(00)00102-2]
	142	Resende, M. G. C. and Ribeiro, C. C. 1997. A GRASP for graph planarization. Networks 29, 173--189.
	143	Celso C. Ribeiro , Maurício C. Souza, Variable neighborhood search for the degree-constrained minimum spanning tree problem, Discrete Applied Mathematics, v.118 n.1-2, p.43-54, 15 April 2002 [doi>10.1016/S0166-218X(01)00255-4]
	144	Schaerf, A. 1997. Combining local search and look-ahead for scheduling and constraint satisfaction problems. In Proceedings of the 15th International Joint Conference on Artificial Intelligence, IJCAI 1997. Morgan-Kaufmann Publishers, San Mateo, CA, 1254--1259.
	145	Andrea Schaerf , Marco Cadoli , Maurizio Lenzerini, LOCAL ++: A C++ framework for local search algorithms, Software—Practice & Experience, v.30 n.3, p.233-257, Mar.1.2000 [doi>10.1002/(SICI)1097-024X(200003)30:3<233::AID-SPE297>3.3.CO;2-B]
	146	Paul Shaw, Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems, Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming, p.417-431, October 26-30, 1998
	147	Sipper, M., Sanchez, E., Mange, D., Tomassini, M., Pérez-Uribe, A., and Stauffer, A. 1997. A phylogenetic, ontogenetic, and epigenetic view of bio-inspired hardware systems. IEEE Trans. Evolut. Comput. 1, 1, 83--97.
	148	Sondergeld, L. and Voβ, S. 1999. Cooperative intelligent search using adaptive memory techniques. In Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, S. Voss, S. Martello, I. Osman, and C. Roucairol, Eds. Kluwer Academic Publishers, Chapter 21, 297--312.
	149	William M. Spears , Kenneth A. De Jong , Thomas Bäck , David B. Fogel , Hugo de Garis, An Overview of Evolutionary Computation, Proceedings of the European Conference on Machine Learning, p.442-459, April 05-07, 1993
	150	Stadler, P. F. 1995. Towards a theory of landscapes. In Complex Systems and Binary Networks, R. Lopéz-Peña, R. Capovilla, R. García-Pelayo, H. Waelbroeck, and F. Zertuche, Eds. Lecture Notes in Physics, vol. 461. Springer-Verlag, Berlin, New York, 77--163. Also available as SFI preprint 95-03-030.
	151	Stadler, P. F. 1996. Landscapes and their correlation functions. J. Math. Chem. 20, 1--45. Also available as SFI preprint 95-07-067.
	152	Stützle, T. 1999a. Iterated local search for the quadratic assignment problem. Tech. rep. aida-99-03, FG Intellektik, TU Darmstadt.
	153	Stützle, T. 1999b. Local Search Algorithms for Combinatorial Problems---Analysis, Algorithms and New Applications. DISKI---Dissertationen zur Künstliken Intelligenz. infix, Sankt Augustin, Germany.
	154	Thomas Stützle , Holger H. Hoos, MAX-MIN Ant system, Future Generation Computer Systems, v.16 n.9, p.889-914, June 2000
	155	Syswerda, G. 1993. Simulated Crossover in Genetic Algorithms. In Proceedings of the 2nd Workshop on Foundations of Genetic Algorithms, L. Whitley, Ed. Morgan-Kaufmann Publishers, San Mateo, Calif., 239--255.
	156	Tabu Search Website. 2003. http://www.tabusearch.net. Visited in January 2003.
	157	Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. Paral. Comput. 17, 443--455.
	158	E.-G. Talbi, A Taxonomy of Hybrid Metaheuristics, Journal of Heuristics, v.8 n.5, p.541-564, September 2002 [doi>10.1023/A:1016540724870]
	159	Toulouse, M., Crainic, T., and Sansò, B. 1999a. An experimental study of the systemic behavior of cooperative search algorithms. In Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, S. Voβ, S. Martello, I. Osman, and C. Roucairol, Eds. Kluwer Academic Publishers, Chapter 26, 373--392.
	160	Michel Toulouse , Krishnaiyan Thulasiraman , Fred Glover, Multi-level Cooperative Search: A New Paradigm for Combinatorial Optimization and an Application to Graph Partitioning, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.533-542, August 31-September 03, 1999
	161	Cees H. M. van Kemenade, Explicit Filtering of Building Blocks for Genetic Algorithms, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.494-503, September 22-26, 1996
	162	Peter J. M. van Laarhoven , Emile H. L. Aarts , Jan Karel Lenstra, Job shop scheduling by simulated annealing, Operations Research, v.40 n.1, p.113-125, Jan.–Feb. 1992 [doi>10.1287/opre.40.1.113]
	163	Michael D. Vose, The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA, 1998
	164	Voβ, S., Martello, S., Osman, I. H., and Roucairol, C., Eds. 1999. Meta-Heuristics---Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands.
	165	Voβ, S. and Woodruff, D., Eds. 2002. Optimization Software Class Libraries. Kluwer Academic Publishers, Dordrecht, The Netherlands.
	166	Voudouris, C. 1997. Guided local search for combinatorial optimization problems. Ph.D. dissertation, Department of Computer Science, University of Essex. pp. 166.
	167	Voudouris, C. and Tsang, E. 1999. Guided local search. Europ. J. Oper. Res. 113, 2, 469--499.
	168	Wade, A. S. and Rayward-Smith, V. J. 1997. Effective local search for the steiner tree problem. Studies in Locational Analysis 11, 219--241. Also in Advances in Steiner Trees, ed. by Ding-Zhu Du, J. M.Smith and J.H. Rubinstein, Kluwer, 2000.
	169	Watson, R. A., Hornby, G. S., and Pollack, J. B. 1998. Modeling building-block interdependency. In Late Breaking Papers at the Genetic Programming 1998 Conference, J. R. Koza, Ed. Stanford University Bookstore, University of Wisconsin, Madison, Wisconsin, USA.
	170	Darrell Whitley, The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best, Proceedings of the third international conference on Genetic algorithms, p.116-121, December 1989, George Mason University, United States
	171	Yagiura, M. and Ibaraki, T. 2001. On metaheuristic algorithms for combinatorial optimization problems. Syst. Comput. Japan 32, 3, 33--55.
	172	Zlochin, M., Birattari, M., Meuleau, N., and Dorigo, M. 2004. Model-based search for combinatorial optimization: A critical survey. Ann. Oper. Res. To appear.