Irakasgai honen aztergaia optimizazio problemen ebazpena da. Problema baterako soluziorik onena topatzea erabaki-hartzearen elementu garrantzitsuenetako bat da. Prozesuen plangintza optimoa, garraio-enpresa batean ibilbide motzena topatzea optimizazioa edota baliabideen esleipena, bizitza errealean horrenbestetan agertzen diren optimization problemen adibide dira.



Ikerkuntza Operatiboa irakasgaian optimizazio problemak ebazteko teknika klasikoak azaltzen dira, esaterako Simplex, Branch & Bound edota metodo Hungariarra. Algoritmo horiek aplikatzeko, problemek ezaugarri zehatzak izan behar dituzte (normalean problema sinpleak dira). Errealitatean aurkezten diren problema asko ordea, oso konplexuak dira (NP-hard) eta beraz, aipatu ditugun algoritmo horiek erabiltzea ezinezkoa da. Bilaketa Heuristikoak irakasgaian ikasiko ditugun algoritmoek, denbora gutxian, ahalik eta soluziorik hoberenak lortzen saiatuko dira. Noski, optimoa lortzeko bermerik gabe. Algoritmo heuristikoak bezela ezagutzen dira, eta intuizioa dute oinarritzat. Irakasgaian zehar, optimizazio konbinatorioko problemak izango ditugu aztergai, eta horiek nola formalizatu, eta eurak ebazteko algoritmoak diseinatu eta inplementatzen ikasiko dugu. Ez hori bakarrik, proposatutako algoritmoen artean eraginkorrenak nola aukeratu ikasiko dugu.

- Konbinatoriako optimizazio problemak formalizatzeko, euren soluzioak egoki errepresentatzeko, eta bilaketa espazioa definitzeko gaitasuna eskuratzea.



- Algoritmo eraikitzaileak, soluzio bakarrean oinarritutako algoritmoak, eta algoritmo poblazionalak diseinatu eta aplikatzen jakitea.



- Helburu anizkoitzeko edota kontextu dinamikoetako problemak atzemateko gaitasuna eskuratzea, eta bibliografia zientifikoa aztertuz, algoritmo egokiak aplikatzeko gaitasuna izatea.



- Diseinu esperimental bat definitu eta aplikatzen jakitea algoritmo estokastikoen konparaketa aurrera eramateko. Emaitzak bistaratzeko teknikak dominatzea, eta ondorio sendoak ateratzeko analisi estatistikoko metodoak aplikatzeko ahalmena edukitzea.

* 1. Gaia - Bilaketa heuristikoei sarrera.

1.1. Optimizazio konbinatorioko problemak.

1.2. Soluzioen kodeketa eta bilaketa espazioa.

1.2. Konplexutasuna.

1.3. Metodo klasikoen berrikuspena.

1.4. Algoritmo eraikitzaileak.



* 2. Gaia - Bilaketa lokaleko algoritmo heuristikoak.

2.1. Ingurune funtzioa

2.2. Bilaketa lokaleko algoritmoak

2.3. Aukeraketa irizpideak.

2.4. Maximo eta minimo lokalak eta euren estimazioa

2.5. Atrakzio baseak



* 3. Gaia - Bilaketa lokal aurreratuak.

3.1. Multi-start metodoak (MLS, GRASP, ILS,...)

3.2. Ingurune funtzioen aldaketa metodoak (VNS, VND...)

3.3. Soluzio txarrak onartzeko metodoak (SA, TS,...)



* 4. Gaia - Populazioetan oinarritutako algoritmoak

4.1. Sarrera.

4.2. Algoritmo genetikoak

4.3. Estimation of Distribution Algorithms

4.4. Swarm Intelligence algoritmoak (ACO, PSO)



* 5. Gaia. Optimizazio problemen aldaerak

5.1. Helburu anizkoitzeko optimizazioa

5.2. Optimizazio dinamikoa

5.3. Murriztapenak dituzten problemen optimizazioa



* 6. Gaia: Beste paradigma batzuk

6.1. Bayesian Optimization

6.2. Reinforcement Learning to learn heuristics

6.3. Evolving with NNs



* 7. Gaia. Diseinu esperimentala eta algoritmoen konparaketa.

7.1. Esperimentazioaren diseinua.

7.2. Algoritmoen exekuzioa.

7.3. Emaitzen bisualizazioa.

7.4. Emaitzen azterketa estatistikoa (Uncertainty-aren azterketa)

Irakasgai honetan lau jarduera mota izango ditugu:



Saio magistralak - Eduki teorikoak aurkeztuko dira adibide sinpleekin ilustratuz. Ikaslegoaren partehartzea sustatuko da, hausnarketara bideratuta dauden ariketa-erronka txikiekin.



Laborategi praktika indibidualak - Ikasleek, indibidualki, optimizazio problementzako algoritmoa heuristikoak programatuko dituzte Python lengoaian. Helburua, eduki teorikoak ilustratzea izango da.



Taldekako proiektua - Taldeka, proiektu bat garatu beharko dute. Irakasleak, optimizazio problema bat planteatuko diete, eta problema formalizatu, eta hau optimizatzeko bi algoritmo planteatu beharko dituzte. Azkenik, bien errendimendua konparatzeko diseinu esperimental bat garatu beharko dute. Lan guztia, izaera zientifikoko 4 orriko artikulu batean idatzi beharko dute lauhilekoaren bukaeran.



Mintegiak - Saio berezi hauetan gaitegiari gehigarriak diren eduki konkretu batzuk landuko ditugu. Formatu erlaxatu bat erabiliz, hasiera batean edukiak landuko dituzte ikasleek, eta ondoren eztabaidarako tartea izango dugu.

• Ebaluazio Jarraituaren Sistema
• Azken Ebaluazioaren Sistema
• Kalifikazioko tresnak eta ehunekoak:
  • Jarraian azaltzen dira portzentaiak. (%): 100

Bi ebaluazio mota egongo dira eskuragarri: JARRAITUA eta FINALA.



Ebaluazio JARRAITUAN sei ataza bete beharko dituzue: 2 froga (praktiko bat eta teoriko bat), 2 proiektu-entrega eta 2 laborategi entrega. Defektuz ikasle guztiak ebaluazio mota honetatik joango dira. Ebaluazio mota honetan, nota ondorengo atazen ebaluazioaren bitartez kalkulatuko da:

- Proiektua - %20 (2 fasetan banatuta, bakoitza %10)

- Laborategi entregak - %20 (bi entrega, bakoitza % 10)

- 1. Froga teorikoa - %30

- 2. Froga praktikoa - % 30



Ebaluazio JARRAITUAN mantendu ahal izateko, froga bakoitzean 3.5-eko nota minimoa atera beharko da 10etik. Laborategi entregetan ere nota minimo bat gainditu beharko da. Minimoa gainditzen ez duenak, automatikoki ebaluazio FINALERA pasako da.



Ebaluazioan FINALA azterketa teoriko-praktiko bat eta proiektuaren entregaren bitartez ebaluatuko da:

- Proiektua - %20

- Froga teorikoa-praktikoa - %80



Ikasleak ez balu gaindituko, ez-ohiko deialdian froga teoriko-praktikoa egiteko beste aukera bat izango luke.



Nahi izanez gero, ikasleak amaierako ebaluaziora pasa ahal izango du, beti ere, bigarren azterketa baino lehen.



Irakasgaian emango diren edukiak eta honen izaera praktikoa ikusirik, ebaluazioa etengabeko bidetik egitea gomendatzen da.

Ezohiko deialdian froga teoriko-praktiko bakarra egongo da notaren %80a balio duena eta irakasgaiaren kontzeptu teoriko eta praktikoak jasoko dituena. Beste %20a proiektuaren entregarekin lortu ahal izango da.

Apuntes de la asignatura que se proporcionarán en eGela, así como numerosos artículos científicos que el profesor recomendará al alumnado. Por último, los ejercicios prácticos se programarán en Python e utilizando Jupyter Notebooks o Google Colab.

Oinarrizko bibliografia

* C.R. Reeves (Ed.), Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific 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 Artificial 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

Gehiago sakontzeko bibliografia

* 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.

Aldizkariak

IEEE Trans. On Evolutionary Computation
Evolutionary Computation Journal
European Journal of Operational Research
Computers and Operations Research
Journal of Heuristics
Journal of Machine Learning Research
Information Sciences

Web helbideak

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 algoritmos heurísticos http://www.dsi.uclm.es/investigacion/simd/SOFTWARE/LIO/