Metaheurísticas

Curso 2018-2019

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
Miércoles 15:30-17:30 0.4 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. Parte I.  Pdf Parte II. Pdf
  • 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 paralelas Pdf
  • Relaciones de problemas Pdf
    • Relación. Solución de tres de los problemas Pdf
  • Relación de cuestiones  Pdf

 

Prácticas

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

Grupo Día Horario Laboratorio Profesor
1 Martes 17:30-19:30 3.3 S. García
2 Miércoles 17:30-19:30 3.2 O. Cordón
3 Jueves 17:30-19:30 2.8 S. García

 

Material de prácticas:

  • Problema de la Máxima Diversidad (MDP)
    • Conjunto de datos.
    • Práctica 1. Pdf
    • Práctica 2. Pdf
    • Práctica 3. Pdf
  • Problema del aprendizaje de pesos en Características (APC)
    • Instancias y tablas.
    • Práctica 1. Pdf
    • Práctica 2. Pdf
    • Práctica 3. Pdf

 

  • Generador números aleatorios 
  • Código para contabilizar los tiempos 
  • Código Algoritmo Genetico Binario. Problema de la mochila
  • Código Algoritmo Enfriamiento Simulado

Seminarios

  • Seminario 1. Ejemplos de resolución de problemas con metaheurísticas: problemas clásicos y reales. Software de metaheurísticas. Pdf
  • Seminario 2. Problemas de optimización con técnicas basadas en búsqueda local. Pdf
  • Seminario 3. Problemas de optimización con técnicas basadas en poblaciones. Pdf
  • Seminario 4. Técnicas basadas en trayectorias. Pdf
  • -->
  • Seminario 5. Restricciones. Pdf
  • Seminario 7. Metaheurísticas multiobjetivo. 

     

    Otros documentos de apoyo

    • 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 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 4. Algoritmos Meméticos.
      • 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
    • Tema 5. Metaheurísticas basadas en Trayectorias.
      • 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
      • 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 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 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, S. González and J. Maillo