Irakasgai honen aztergaia optimizazio problemen ebazpena da. Problema baterako soluziorik onena topatzea erabaki hartzearen alde garrantztitsua da; prozesuen plangintza optimoa edo garraio-enpresa batean ibilibide motzena topatzea optimizazioaren adibideak dira.



Ikerkuntza Operatiboa irakasgaian optimizazio problemak ebazteko teknika klasikoak azaltzen dira. Alabaina, teknika horiek problema berezi batzuei bakarrik aplika diezaieke. Bilaketa Heuristikoak irakasgaian algoritmo orokorrak aztertzen dira, edozein optimizazion probleara egoki daitzekenak.

Introducción a la optimización mediante el uso de heurísticos. Partiendo de las deficiencias de los métodos clásicos de investigación se presentarán los métodos heurísticos. Inicialmente se presentarán los basados en búsqueda local para a continuación tocar los algoritmos poblacionales. Finalmente se presentarán aspectos de optimización multiobjetivo, optimización dinámica, paralelización de algoritmos y evaluación de algoritmos heurísticos

Tema 1 Introducción a la optimización heurística Los contenidos de este tema son los siguientes: planteamiento de los problemas de optimización combinatoria analizando su formalización y su complejidad, revisión de los métodos clásicos de optimización, introducción a las heurísticas de búsqueda y comparación entre ambos conjuntos de técnicas

Tema 2 Heurísticas basadas en búsqueda local Se presentará el algoritmo de búsqueda local básico, y tras ver sus deficiencias se propondrán alternativas de mejora basadas en: comenzar desde la búsqueda desde diferentes lugares, modificar el sistema de vecinos o aceptar soluciones que empeoren el valor de la solución actual. De esta forma se introducirán los siguientes métodos heurísticos de optimización: greddy randomized adaptive search (GRASP), algoritmo de vencidad variable, simulated annealing y búsqueda tabú

Tema 3 Heurísticas basadas en poblaciones El tema comenzará introduciendo la computación evolutiva para pasar a presentar los algoritmos genéticos. A continuación se verán los algoritmos de estimación de distribuciones y terminará el tema presentando los algoritmos basados en colonias de hormigas y la búsqueda dispersa

Tema 4 Optimización multiobjetivo Se presentára el problema de la optimización multiobjetivo, haciendo hincapié en las diferencias con la optimización monoobjetivo. Se presentarán medidas de evaluación de problemas de optimización multiobjetivo y a continuación se verán varios algoritmos heurísticos para resolver problemas multiobjetivo

Tema 5 Otros aspectos de la optimización heurística Este tema está principalmente dedicado a ver otros aspectos de la optimización, de esta forma se tocarán aspectos relacionados con el paralelismo de algoritmos heurísticos, la evaluación de algoritmos y otros problemas de optimización como son los problemas dinámicos o la optimización on-line

Irakasgaia hiru iharduera motatan banatuta dago:



Eskola Magistralak - Irakasgaiaren teoria azaltzeko



Banakako praktikak - Ikasleek, banaka, hainbat ariketa praktikoak jorratu beharko dute. Ariketa hauek R lengoaian egingo dira.



Taldeko praktika - Ikasleek, taldeka, optimizazio problema bat ebazteko algoritmoak diseinatu eta (R-n) inplementatu beharko dituzte.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • Los porcentajes y tipos de evaluaciones se especifícan en apartados posteriores (%): 100

Ebaluazio jarraituan zein globalean hauek izango dira azken notan proba bakoitzak izango duen pisua:



Azterketa(k) - %20

Praktikak - %60

Taldeko lana - %20

Ezohiko deiladian azterketa bakarra egongo da, teoria guztia ebaluatzeko (honen pisua %30 izango da). Horrez gain, ikasleak, azterketa data baino lehenago, klasean egindako ariketa praktikoak entregatu beharko ditu.



Taldeko lanaren ordez, ikasleak problema bat ebazteko algoritmo bat inplementatu beharko du.

Irakasgaiaren apunteak: https://github.com/b0rxa/metaheuR/tree/master/Dokumentazioa

Basic bibliography

*C.R. Reeves (Ed.), Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scienti¿c Publications, 1993.

*C. Blum, A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. 35,

3 (Sep. 2003), 268-308

*H.H Hoos, T. Stuztle, Stochastic local search.Foundationsandapplications.MorganKaufmann,2005.

* B. Melián, J.A. Moreno Pérez, J. Marcos Moreno-Vega, J.(Ed.) Revista Iberoamericana de Inteligencia Arti¿cial 19, 2, 2003.

* A.E. Eiben, J.E. Smith, Introduction to Evolutionary Computing. Springer, 2007.

* C.A. Coello, G.B. Lamont, D.A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems. Springer,

2007

In-depth bibliography

* A. Díaz (Ed.), Optimización Heurística y Redes Neuronales en Dirección de Operaciones e Ingeniería. Editorial Paraninfo, 1996. *F. Glover, M. Laguna, Tabu Search. Kluwer Academic Publishers, 1997. * M. Laguna and R. Martí, Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers, 2003. * P. Larrañaga & Jose A. Lozano (Ed.) Estimation of Distribution Algorithms. Kluwer Academic Publishers, 2002. * E. Aarts, J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization. John Wiley & Sons, 1997.

Journals

IEEE Trans. On Evolutionary Computation Evolutionary Computation Journal Journal of Heuristics Soft Computing Information Sciences

Web addresses

OR-Library http://people.brunel.ac.uk/~mastjjb/jeb/info.html . Repositorio de problemas de optimización. Red Española de Metaheurísticos. http://heur.uv.es/ Dirección de LIO una librería de algorimtos heurísticos http://www.dsi.uclm.es/investigacion/simd/SOFTWARE/LIO/