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

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.

Irakasgaiko materiala apunte eta diapositibak eGela bitartez emango dira. Horrez gain, irakasleak hainbat artikulu zientifiko gomendatuko dio irakaslegoari. Azkenik, lan praktikoak Python lengoaian programatuko dira, Jupyter Notebooks edo Google Colab tresnak erabiliz.

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