XIII Conferencia de la Asociación Española para la Inteligencia Artificial Sevilla (España)

Francisco Herrera (Universidad de Granada)

Tutorial: Introducción a los Algoritmos Metaheurísticos

El objetivo de este tutorial presentar las líneas básicas de desarrollo de algoritmos metaheurísticos y su aplicabilidad en el ámbito de la Inteligencia Artificial.

Los algoritmos metaheurísticos son algoritmos aproximados de optimización y búsqueda de propósito general.

Son procedimientos iterativos que guían una heurística subordinada combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda.

El tutorial está organizado de la siguiente manera:

1. Introducción a las Metaheurísticas. Resolución de Problemas Mediante Algoritmos de Búsqueda.
2. MH I: Búsqueda Basada Trayectorias.
3. MH II: Swarm Intelligence.
4. MH III: Algoritmos Evolutivos.
5. Limitaciones de los Algoritmos MH: Teorema NFL.
6. MH IV: Algoritmos Híbridos: Poblaciones vs. Trayectorias.
7. Consideraciones Sobre el Uso de las Metaheurísticas.
8. Algunos Estudios/Extensiones de Interés.
9. Comentarios Finales.

Documentación

• El tutorial completo se puede descargar desde el siguiente enlace:

Bibliografía Complementaria

• Introducción a las Metaheurísticas. Resolución de Problemas Mediante Algoritmos de Búsqueda.
  • B. Melián, J.A. Moreno Pérez, J.M. Moreno Vega. Metaheurísticas: un visión global. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 7-28
  • C. Blum, A. Roli. Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35:3 (2003) 268-308.
  • Colin G. Johnson A design framework for metaheuristics. Artif Intell Rev (2008) 29:163-178
  • Metaheuristics: From Design to Implementation, El-Ghazali Talbi, ISBN: 978-0-470-27858-1, 593 pages, July 2009
• MH I: Búsqueda Basada Trayectorias.
  • F. Glover, G.A. Kochenberger (Eds.). Handbook of Metaheuristics. Kluwer Academic Press, 2003.
  • H.H. Hoos, T. Stützle. Stochastic Local Search. Morgan Kaufmann, 2004
  • K.A. Dowsland, B.A. Díaz. Diseño de Heurísticas y Fundamentos del Recocido Simulado. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 93-102.
  • B. Suman, P. Kumar. A survey of simulated annealing as a tool for single and multiobjective optimization. Journal of the Operational Research Society 57:10 (2006) 1143-1160.
  • F. Glover, B. Melián. Búsqueda Tabú. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 29-48.
  • M. Gendreau. Chapter 2: An Introduction to Tabu Search. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 37-54.
  • M.G.C. Resende, C.S. Ribeiro. Chapter 8: Greedy Randomized Adaptive Search Procedure. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 221-249.
  • R. Martí. Chapter 12: Multi-Start Methods. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 355-368.
  • H.L. Lourenço, O.C. Martin, T. Stützle. Chapter 11: Iterated Local Search. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 321-353.
  • P. Hansen, N. Mladenovic. Chapter 6: Variable Neighborhood Search. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 145-184.
  • T. Stützle, 1998. Local Search Algorithms for Combinatorial Problems-Analysis, Improvements and New Applications. PhD Thesis, Darmstadt,University of Technology, Department of Computer Science.
  • H.H. Hoos, T. Stützle. Stochastic Local Search. Morgan Kaufmann, 2004.
• MH II: Swarm Intelligence.
  • E. Bonabeau, M. Dorigo, G. Theraulaz Swarm Intelligence. From Nature to Artificial Systems. Oxford University Press, 1999.
  • M. Dorigo, T. Stuetzle. Ant Colony Optimization. MIT Press, 2004.
  • Kennedy, J., Eberhart, R. C., and Shi, Y.. Swarm intelligence. Morgan Kaufmann Publishers, 2001.
  • S. Garnier, J. Gautrais, G. Theraulaz. The biological principles of swarm intelligence. Swarm Intelligence 1 (2007) 3-31
  • O. Cordón, F. Herrera and T. Stützle. A Review on the Ant Colony Optimization Metaheuristic: Basis, Models and New Trends. Mathware and Soft Computing 9:2-3, 2002, pp. 141-175
  • M. Dorigo, T. Stützle. Chapter 9: The ant colony optimization metaheuristic: Algorithms, applications and advances. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics (2003) 251-285
  • A. Banks, J. Vincent, C. Anyakoha. A review of particle swarm optimization. Part I: background and development. Natural Computing 6 (2007) 467-484
  • A. Banks, J. Vincent, C. Anyakoha. A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications. Natural Computing 7 2008) 109-124
  • W.B. Langdon, R. Poli. Evolving Problems to Learn About Particle Swarm Optimizers and Other Search Algorithms. IEEE Transactions on Evolutionary Computation 11:5 (2007) 561-578
  • Y. del Valle, G.K. Venayagamoorthy, S. Mohagheghi, J.-C. Hernandez, R.G. Harley. Particle swarm optimization: basic concepts, variants and applications in power systems. IEEE Transactions on Evolutionary Computation 12:2 (2008) 171-195
• MH III: Algoritmos Evolutivos.
  • D.B. Fogel (Ed.) Evolutionary Computation. The Fossil Record. (Selected Readings on the History of Evolutionary Computation). IEEE Press, 1998.
  • A.E. Eiben, J.E. Smith. Introduction to Evolutionary Computation. Springer Verlag 2003. (Natural Computing Series)
  • Thomas Bäck, Ulrich Hammel, Hans-Paul Schwefel. Evolutionary Computation: Comments on the History and Current State. IEEE Transactions on Evolutionary Computation 1:1 (1997) 3-17
  • C. Reeves. Chapter 3: Genetic Algorithms. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 55-82
  • F. Herrera, M. Lozano, A.M. Sánchez. A Taxonomy for the Crossover Operator for Real-Coded Genetic Algorithms: An Experimental Study. International Journal of Intelligent Systems 18 (2003) 309-338
  • Storn, K. Price. Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization 11 (1997) 341-359
• Limitaciones de los Algoritmos MH: Teorema NFL.
  • Wolpert, D.H.; Macready, W.G.; No free lunch theorems for optimization. Evolutionary Computation, IEEE Transactions on 1:1, April 1997, 67-82
• MH IV: Algoritmos Híbridos: Poblaciones vs. Trayectorias.
  • N. Krasnogor and J.E. Smith. A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE Transactions on Evolutionary Computation 9(5):474- 488, 2005.
  • P. Moscato, C. Cotta, "Una Introducción a los Algoritmos Memeticos", Inteligencia Artificial. Revista Iberoamericana de IA, No. 19,2003, 131-148.
  • P. Moscato, C. Cotta. Chapter 5: Gentle Introduction to Memetic Algorithms. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 105-144
• Consideraciones Sobre el Uso de las Metaheurísticas.
  • A. Hertz, M. Widmer. Guidelines for the use of meta-heuristics in combinatorial optimization. European Journal of Operational Research 151 (2003) 247-252
• Algunos Estudios/Extensiones de Interés.
  • K. Deb, Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, 2001.
  • E. Alba (Ed.), Parallel Metaheuristics. A New Class of Algorithms. Wiley-Interscience, 2005.
  • B. Sareni, L. Krähenbühk, Fitness Sharing and Niching Methods Revisited. IEEE Transactions on Evolutionary Computation, Vol. 2, No. 3, Septiembre 1998, 97-106.
  • Pérez, E., Herrera, F. and Hernández, C. (2003). Finding multiple solutions in job shop scheduling by niching genetic algorithms. Journal of Intelligent Manufacturing, (14) Pp. 323-341.
  • C.A. Coello, D.A. Van Veldhuizen, G.B. Lamont, Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic Publishers, 2002.
  • K. Deb, Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, 2001
  • K. Deb, A. Pratap, S. Agarwal and T. Meyarivan. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6:2 (2002) 182-197.
  • E. Zitzler, L. Thiele, M. Laumanns, C.M. Fonseca, and V. Grunert da Fonseca. Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation 7:2, April, 2003, pp. 117 - 132.
  • M. Potter and K. D. Jong. Cooperative coevolution: an architecture for evolving coadapted subcomponents. Evolutionary Computation, 8(1):1-29, 2000