Optimització
Codi: 42250 Crèdits: 62024/2025
| Titulació | Tipus | Curs |
|---|---|---|
| 4313136 Modelització per a la Ciència i l'Enginyeria / Modelling for Science and Engineering | OB | 0 |
Professor/a de contacte
- Nom:
- Albert Ruiz Cirera
- Correu electrònic:
- albert.ruiz@uab.cat
Equip docent
- Albert Ruiz Cirera
- Judit Chamorro Servent
Idiomes dels grups
Podeu consultar aquesta informació al final del document.
Prerequisits
- Coneixement de matemàtiques a nivell d'un grau de ciències o d'enginyeria.
- Saber programar.
Objectius
El curs està dedicat a estudiar i practicar diversos algorismes d’optimització heurística i combinatòria, fent especial èmfasi en l’enrutament i l'optimització convexa. El curs tractarà també altres temes d'optimització.
Aquest curs pretèn donar a l'alumnat els coneixements necessaris i eines bàsiques per a programar algorismes que puguin resoldre problemes d'optimització actuals.
Competències
- "Aplicar el pensamiento lógico/matemático: el proceso analítico a partir de principios generales para llegar a casos particulares; y el sintético, para a partir de diversos ejemplos extraer una regla general."
- Analitzar, sintetitzar, organitzar i planificar projectes del seu camp d'estudi.
- Aplicar la metodologia de recerca, tècniques i recursos específics per investigar en un determinat àmbit d'especialització.
- Aplicar les tècniques de resolució dels models matemàtics i els seus problemes reals d'implementació.
- Comunicar en llengua anglesa els resultats dels treballs de l'àmbit d'estudi.
- Concebre i dissenyar solucions eficients, aplicant tècniques computacionals, que permetin resoldre models matemàtics de sistemes complexos.
- Extreure d'un problema complex la dificultat principal, separada d'altres qüestions d'índole menor.
- Formular, analitzar i validar models matemàtics de problemes pràctics de diferents camps.
- Usar mètodes numèrics apropiats per solucionar problemes específics.
Resultats d'aprenentatge
- "Aplicar el pensament lògic/matemàtic: el procés analític a partir de principis generals per arribar a casos particulars; i el sintètic, para a partir de diversos exemples extreure una regla general."
- Analitzar, sintetitzar, organitzar i planificar projectes del seu camp d'estudi.
- Aplicar la metodologia de recerca, tècniques i recursos específics per investigar en un determinat àmbit d'especialització.
- Aplicar tècniques d'optimització per estudiar models associats a problemes pràctics.
- Comunicar en llengua anglesa els resultats dels treballs de l'àmbit d'estudi.
- Extreure d'un problema complex la dificultat principal, separada d'altres qüestions d'índole menor.
- Identificar problemes que requereixin aplicar tècniques d'optimització per construir models associats a problemes pràctics.
- Implementar els algorismes que consten al programa
- Implementar les solucions proposades de forma fiable i eficient.
- Usar programaris específics per a la resolució de problemes d'optimització.
Continguts
Continguts principals:
- Algorismes combinatoris per a grafs i enrutaments: algorismes Dijkstra i A *. Optimització sobre grafs.
- Optimització determinista (problemes amb restriccions i sense).
- Algorismes genètics.
- Simulated annealing.
- Algorismes de colònies de formigues.
- Altres.
Activitats formatives i Metodologia
| Títol | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|
| Tipus: Dirigides | |||
| Assistir a classe i activitats relacionades | 37,75 | 1,51 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |
| Avaluació del professorat i de l'assignatura | 0,25 | 0,01 | |
| Tipus: Autònomes | |||
| Tasques (implementació dels algorismes activitat individual i en grup) | 42 | 1,68 | 1, 2, 3, 4, 6, 7 |
La metodologia consisteix en classes teòriques (presentacions amb transparències i pissarra), i sessions pràctiques.
Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, per a la complementació per part de l'alumnat de les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura/mòdul.
Avaluació
Activitats d'avaluació continuada
| Títol | Pes | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|---|
| Lliurament i exposició del treball final (grups de 4) | 30% | 21 | 0,84 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |
| Projectes de casos realistes de forma individual | 30% | 21 | 0,84 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |
| Projectes en casos realistes en grups de 2 (excepcionalment 3) | 40% | 28 | 1,12 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |
Hi ha tres tipus d'avaluació:
- Treballs individuals: informe resumit i codi resolent el problema plantejat.
- Treballs en grups de 2: informe resumit i codi resolent el problema plantejat.
- Treball en grups de 4: informe, (pot incloure codi) i presentació oral.
Bibliografia
- David Beasley, David R. Bully and Ralph R. Martinz, An Overview of Genetic Algorithms (Part 1: Fundamentals and Part 2: Research Topics).
- Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for industrial and applied mathematics.
- Borwein, J., & Lewis, A. (2006). Convex Analysis and Nonlinear Optimization. CMS Books in Mathematics. Springer, New York, NY.
- Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
- Marco Dorigoa and Christian Blum, Ant colony optimization theory: A survey, Theoretical Computer Science 344 (2005) 243 - 278.
- Hansen, P. C. (2010). Discrete inverse problems: insight and algorithms. Society for Industrial and Applied Mathematics.
- S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by Simulated Annealing, Science, May 1983, Vol. 220, no. 4598, 671-680.
- Melanie Mitchell, An Introduction to Genetic Algorithms, A Bradford Book, The MIT Press, Cambridge Massachusetts, 1999.
- Nocedal, J., & Wright, S. J. (2006). Quadratic programming. Numerical optimization, 448-492.
- Nocedal, J., & Wright, S. J. (2006). Sequential Quadratic Programming. Numerical Optimization, 529-562.
- Judea Pearl, A* Algorithms and such: Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
- William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, Numerical Recipes in C. The Art of Scientific Computing (second edition), Cambridge University Press.
- Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Numerical Mathematics, Texts in Applied Mathematics 37, Springer, 1991.
Programari
Programari recomanat:
- C
- MATLAB
Llista d'idiomes
| Nom | Grup | Idioma | Semestre | Torn |
|---|---|---|---|---|
| (TEm) Teoria (màster) | 1 | Anglès | primer quadrimestre | tarda |