Metaheurísticas

Curso 2016-2017

La asignatura Metaheurísticas, impartida en el grado en Ingeniería Informática (especialidad en Computación y Sistemas Inteligentes), comprende el análisis de algoritmos avanzados de optimización y búsqueda, así como el estudio de técnicas de diseño de metaheurísticas basadas en trayectorias, poblaciones, y paralelas.

Teoría

El horario de clases de teoría durante este curso es el siguiente:

Día Horario Aula Profesor
Lunes 15:30-17:30 1.1 F. Herrera

 

Transparencias de la asignatura:

  • Planificación de la asignatura  Pdf
  • Presentación de la asignatura Pdf
  • Tema 1. Introducción a las metaheurísticas.Pdf
  • Tema 2. Modelos de Búsqueda: Entornos y Trayectorias vs. Poblaciones.Pdf
  • Tema 3. Metaheurísticas basadas en Poblaciones.PdfPdf
  • Tema 4. Algoritmos Meméticos.Pdf
  • Tema 5. Metaheurísticas basadas en Trayectorias.Pdf
  • Tema 6. Metaheurísticas basadas en adaptación social.Pdf
  • Tema 7. Aspectos Avanzados en Metaheurísticas.
    • Diversidad vs. Convergencia, múltiples soluciones (nichos y MOO), nuevos algoritmos Pdf
  • Tema 8. Metaheurísticas paralelasPdf
  • Relaciones de problemas
    • Relación 1 (Abril 2013)      Solución de tres de los problemas Pdf
    • Relación 2 (Junio 2015) Pdf
  • Relación de cuestiones (Junio 2015) Pdf

 

  • Trabajo alternativo a la teoría (por actualizar para el curso 2016-2017)
    • Definición de las funciones del CEC2014 (Utilizar Part A, Funciones 1-20, Dim. 20 y 30) Pdf
      • LInk al código para las funciones (directorio CEC-2014). Link
      • Información sobre la competición CEC2014. Link
    • Resultados de la competición CEC2014
    • Comparaciones del algorithm L-SHADE:   (JADE, iCMAES-ILS, SaDE, dynNP-jDE, CoDE, ...)
    • Resultados del algoritmo básico de Diferential Evolution

Prácticas

El horario de clases prácticas durante este curso es el siguiente:

Grupo Día Horario Laboratorio Profesor
1

Viernes

17:30-19:30 3.3 O. Cordón
2

Viernes

17:30-19:30 3.2 S. García
3

Lunes

17:30-19:30 3.2 S. García

 

Material de prácticas:

  • Práctica 1. Búsquedas basadas en Poblaciones y Trayectorias simples: Búsqueda Local, Algoritmos Genéticos y Algoritmos Meméticos
    • Guión A: QAPPdf
    • Guión B: APCPdf
  • Práctica 2. Búsquedas por Trayectorias.
    • Guión A: QAP Pdf Pdf
    • Guión B: APC Pdf Pdf

 

  • Materiales de apoyo a las prácticas
    • Tablas e instancias para el Probrema de Asignación Cuadrática (QAP) Zip
    • Tablas e instancias para el problema del Aprendizaje de Pesos en Características (APC) Zip
  • Codigos fuente:
    • Generador de números pseudoaletarios    H
    • Temporizador    Zip
    • Algoritmo genético binario    Zip
    • Algoritmo ACO para TSP    Zip

Seminarios

  • Seminario 1. Ejemplos de resolución de problemas con metaheurísticas: problemas clásicos y reales. Software de metaheurísticas. Pdf
    • Artículo complementario: Comparativa de frameworks de metaheurísticas. Pdf
    • Tutorial de ParadisEO Pdf
    • Otro tutorial de ParadisEO
  • Seminario 2. Problemas de optimización con técnicas basadas en trayectorias simples: Búsqueda Local.Pdf
  • Seminario 3. Problemas de optimización con técnicas basadas en poblaciones.Pdf
  • Seminario 4. Problemas de optimización con técnicas basadas en trayectorias simples y multiples (Apoyo de prácticas). Pdf Pdf
  • Seminario 5. Manejo de restricciones en metaheurísticas. Pdf
  • Seminario 6. Metaheurísticas Multiobjetivo. Pdf

Otros documentos de apoyo (pendiente de actualización curso 2016-2017)

  • Tema 1. Introducción a las metaheurísticas
    • 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. Pdf
    • Xiong, N., Molina, D., Ortiz, M. L., & Herrera, F. (2015). A walk into metaheuristics for engineering optimization: principles, methods and recent trends. international journal of computational intelligence systems, 8(4), 606-636. Pdf
  • Tema 2. Algoritmos de búsqueda local básicos
    • P. Hansen, N. Mladenovic, J.A. Moreno Pérez. Búsqueda de Entorno Variable. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 77-92. Pdf
  • Tema 3. Metaheurísticas Basadas en Trayectorias Simples
    • S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing. Science 220:4598 (1983)671-680 Pdf
    • 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. Pdf
    • 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. Pdf
    • D. Henderson, S.H. Jacobson, A.W. Johnson. Chapter 10: The Theory and Practice of Simmulated Annealing. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 287-319. Pdf
    • F. Glover, B. Melián. Búsqueda Tabú. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 29-48. Pdf
    • M. Gendreau. Chapter 2: An Introduction to Tabu Search. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 37-54. Pdf
  • Tema 4. Métodos basados en trayectorias múltiples
    • R. Martí, J.M. Moreno Vega. Métodos Multiarranque. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 49-60. Pdf
    • T.A. Feo, M.G.C. Resende. Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization 6 (1995) 109-134. Pdf
    • 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. Pdf
    • R. Martí. Chapter 12: Multi-Start Methods. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 355-368. Pdf
    • P. Hansen, N. Mladenovic, J.A. Moreno Pérez. Búsqueda de Entorno Variable. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 77-92. Pdf
    • N. Mladenovic, P. Hansen. Variable Neighborhood Search. Computers and Operations Research 24(11) (1997) 1097-1100. Pdf
    • 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. Pdf
    • P. Hansen, N. Mladenovic. Chapter 6: Variable Neighborhood Search. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 145-184. Pdf
  • Tema 5. Metaheurísticas basadas en poblaciones
    • C. Reeves. Chapter 3: Genetic Algorithms. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 55-82. Pdf
    • D. Beasley, D. R. Bull, R. R. Martin. An Overview of Genetic Algorithms: Part 1, Fundamentals. University Computing 15:4 (1993) 170-181. Pdf
    • D. Beasley, D. R. Bull, R. R. Martin. An Overview of Genetic Algorithms: Part 2, Research Topics. University Computing 15:4 (1993) 170-181. Pdf
    • Darrell Whitley. A Genetic Algorithm Tutorial. Statistics and Computing 4 (1994) 65-85. Pdf
    • 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, doi: 10.1002/int.10091. Pdf
    • K. Deb. A population-based algorithm-generator for real-parameter optimization. Soft Computing 9:4 (2005) 236-253. Pdf
    • J. Smith. On Replacement Strategies in Steady State Evolutionary Algorithms. Evolutionary Computation 15:1 (2007) 29-59. Pdf
    • N. Hansen, A. Ostermeier. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation 9:2 (2001) 159-195. Pdf
    • N. Hansen, S.D. Müller, P. Koumoutsakos. Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES). Evolutionary Computation 11:1 (2003) 1-18. Pdf
    • C. Igel, N. Hansen, S. Roth. Covariance Matrix Adaptation for Multi-objective Optimization. Evolutionary Computation 15:1 (2007) 1-28. Pdf
    • R. Storn, K. Price. Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization 11 (1997) 341-359. Pdf
    • J. Brest, S. Greiner, B. Boskovic, M. Mernik, V. Zumer. Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems. IEEE Transactions on Evolutionary Computation 10:6 (2006) 646-657. Pdf
    • S. Rahnamayan, H.R. Tizhoosh, M.M.A. Salama. Opposition-Based Differential Evolution. IEEE Transactions on Evolutionary Computation 12:1 (2008) 64-79. Pdf
    • S. Das and P.N. Suganthan. Differential Evolution: A Survey of the State-of-the-Art, IEEE Transactions on Evolutionary Computation 15:1 (2011) 4-31. Pdf
  • Tema 6. Metaheurísticas basadas en adaptación social
    • S. Garnier, J. Gautrais, G. Theraulaz. The biological principles of swarm intelligence. Swarm Intelligence 1 (2007) 3-31. Pdf
    • Dervis Karaboga, Bahriye Akay. A survey: algorithms simulating bee swarm intelligence. Artificial Intelligence Review 31 (2009) 61-85. Pdf
    • Dervis Karaboga, Bahriye Basturk. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization 39 (2007) 459-471. Pdf
    • M. Dorigo, V. Maniezzo and A. Colorni. The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics 26:1, 1996, pp. 29-41. Pdf
    • M. Dorigo and L.M. Gambardella. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation 1:1, 1997, pp. 53-66. Pdf
    • 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. Pdf
    • 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. Pdf
    • S. Alonso, O. Cordón, I. Fernández de Viana y F. Herrera. La Metaheurística de Optimización Basada en Colonias de Hormigas: Modelos y Nuevos Enfoques. In: G. Joya, M.A. Atencia, A. Ochoa, S. Allende (Eds.), Optimizacion Inteligente: Técnicas de Inteligencia Computacional para Optimización, 2004, Servicio de Publicaciones de la Universidad de Málaga, 261-313. Pdf
    • K.E. Parsopoulos, M.N. Vrahatis. Recent approaches to global optimization problems through Particle Swarm Optimization. Natural Computing 1 (2002) 235-306. Pdf
    • R. Mendes, J. Kennedy, J. Neves. The fully informed particle swarm: simpler, maybe better. IEEE Transactions on Evolutionary Computation 8:3 (2004) 204-210. Pdf
    • V. Kadirkamanathan, K. Selvarajah, P.J. Fleming. Stability analysis of the particle dynamics in particle swarm optimizer. IEEE Transactions on Evolutionary Computation 10:3 (2006) 245-255. Pdf
    • R. Poli, J. Kennedy, T. Blackwell. Particle swarm optimization: An overview. Swarm Intelligence 1 (2007) 33-57. Pdf
    • A. Banks, J. Vincent, C. Anyakoha. A review of particle swarm optimization. Part I: background and development. Natural Computing 6 (2007) 467-484. Pdf
    • 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. Pdf
    • 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. Pdf
    • 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. Pdf
  • Tema 7. Metaheurísticas híbridas
    • P. Moscato, C. Cotta. Una Introducción a los Algoritmos Meméticos. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 131-148. Pdf
    • P. Moscato, C. Cotta. Chapter 5: A Gentle Introduction to Memetic Algorithms. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 105-144. Pdf
    • R. Martí, M. Laguna. Scatter Search: Diseño Básico y Estrategias Avanzadas. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 123-130. Pdf
    • Página Oficial sobre Scatter Search*
    • F. Glover, M. Laguna, R. Martí. Chapter 1: Scatter Search and Path Relinking: Advances and Applications. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 1-35. Pdf
  • Tema 8. Metaheurísticas paralelas
    • T.G. Crainic, M. Toulouse. Chapter 17: Parallel Strategies for Meta-heuristics. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 475-513. Pdf
    • T.G. Crainic, M. Toulouse. Parallel Meta-Heuristics (2009). Pdf
Page Maintained by S. García and S. González