Search Heuristics26222
- Centre
- Faculty of Informatics
- Degree
- Bachelor's Degree in Informatics Engineering
- Academic course
- 2023/24
- Academic year
- 4
- No. of credits
- 6
- Languages
- Spanish
- Basque
- Code
- 26222
TeachingToggle Navigation
Teaching guideToggle Navigation
Description and Contextualization of the SubjectToggle Navigation
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.
Skills/Learning outcomes of the subjectToggle Navigation
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
Theoretical and practical contentToggle Navigation
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
MethodologyToggle Navigation
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.
Assessment systemsToggle Navigation
- Continuous Assessment System
- Final Assessment System
- Tools and qualification percentages:
- Los porcentajes y tipos de evaluaciones se especifícan en apartados posteriores (%): 100
Ordinary Call: Orientations and DisclaimerToggle Navigation
Ebaluazio jarraituan zein globalean hauek izango dira azken notan proba bakoitzak izango duen pisua:
Azterketa(k) - %20
Praktikak - %60
Taldeko lana - %20
Extraordinary Call: Orientations and DisclaimerToggle Navigation
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.
Compulsory materialsToggle Navigation
Irakasgaiaren apunteak: https://github.com/b0rxa/metaheuR/tree/master/Dokumentazioa
BibliographyToggle Navigation
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/
GroupsToggle Navigation
01 Teórico (Spanish - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 10:30-12:00 (1) | 09:00-10:30 (2) |
Teaching staff
01 Applied laboratory-based groups-1 (Spanish - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 12:00-13:30 (1) |
Teaching staff
46 Teórico (Basque - Tarde)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 15:30-17:00 (1) | 14:00-15:30 (2) |
Teaching staff
46 Applied laboratory-based groups-1 (Basque - Tarde)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
1-15 | 17:00-18:30 (1) |