Optimització
Codi: 42250 Crèdits: 6| Titulació | Tipus | Curs | Semestre |
|---|---|---|---|
| 4313136 Modelització per a la Ciència i l'Enginyeria / Modelling for Science and Engineering | OB | 0 | 1 |
Professor/a de contacte
- Nom:
- Lluís Alseda Soler
- Correu electrònic:
- Lluis.Alseda@uab.cat
Utilització d'idiomes a l'assignatura
- Llengua vehicular majoritària:
- anglès (eng)
Equip docent
- Albert Ruíz Cirera
Prerequisits
-
Coneixement de matemàtiques a nivell d'un grau de ciències
-
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’encaminament, el gràfic, l’optimització de la xarxa i la planificació.
Les conferències es basen en presentacions de diapositives i en material d'Internet.
El material teòric es complementarà amb algunes tasques (a la primera) per a que cada alumne pugui desenvolupar cada tema. Aquesta és una part crítica del procés d’aprenentatge.
[Traduït de la versió anglesa per Google translator]
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
Algorismes combinatoris per a gràfics i enrutaments: algorismes Dijstra i A *. Optimització de gràfics.
Optimització determinista per a problemes no lineals (restringida i no limitada)
Algorismes genètics
Simulació d'anàlisi
Algorismes d’optimització de colònies de formigues
Optimització de eixam de partícules
Xarxes neuronals en optimització
Programació
Aprenentatge automàtic a través de xarxes neuronals
[Traduït de la versió anglesa per Google translator]
Metodologia
La metodologia es basa en classes magistrals que consisteixen en la presentació de la teoria, exemples i alguns casos pràctics per a cada algorisme del programa.
Els estudiants hauran d'aplicar de forma independent els algorismes estudiats en situacions realistes com a part crucial del procés d'aprenentatge.
[Traduït de la versió anglesa per Google translator]
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.
Activitats formatives
| 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 |
| Evaluation of the teaching performance and evaluation of the subject or module | 0,25 | 0,01 | |
| Tipus: Autònomes | |||
| Treas (implementación de los algoritmos – actividad individual) | 42 | 1,68 | 1, 2, 3, 4, 6, 7 |
Avaluació
Hi ha set tasques realistes pràctiques que consisteixen en un informe i un programa en funcionament. Tres d'elles seran obligatoris i quatre seran opcionals.
Les tasques opcionals s'han de fer de manera individual i poden incrementar la nota final fins al 20%.
Activitats d'avaluació
| Títol | Pes | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|---|
| Implementació d'algorismes en casos realistes en projectes d'equip | 50% | 35 | 1,4 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |
| Implementació d'algorismes en casos realistes en projectes individuals | 50% | 35 | 1,4 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 |
Bibliografia
All the necessary bibliography is and will be on the course's web page https://mat.uab.cat/~alseda/MasterOpt/
Combinatorial Algorithms
Judea Pearl, A* Algorithms and such: Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
Deterministic optimization for nonlinear problems
Numerical Mathematics, Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Texts in Applied Mathematicsm 37, Springer, 1991.
Convex Optimization (Notes of Lieven Vandenberghe)
Karush-Kuhn-Tucker conditions (Notes of Geoff Gordon & Ryan Tibshirani)
Penalty and Barrier Methods for constrained optimization
Genetic Algorithms
Sean Luke,Essentials of Metaheuristics, 2009.
http://cs.gmu.edu/∼sean/book/metaheuristics/
Melanie Mitchell, An Introduction to Genetic Algorithms, A Bradford Book, The MIT Press, Cambridge Massachusetts, 1999.
David Beasley, David R. Bully and Ralph R. Martinz, An Overview of Genetic Algorithms (Part 1: Fundamentals and Part 2: Research Topics)
Simulated Annealing algorithm
S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by Simulated Annealing, Science, May 1983, Vol. 220, no. 4598, pp. 671-680.
François Bergeret and Philippe Besse, Simulated Annealing, weighted simulated annealing and genetic algorithm at work.
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.
Ant colony algorithms
Marco Dorigoa and Christian Blum, Ant colony optimizationtheory: A survey, Theoretical Computer Science 344 (2005) 243 – 278.
Scheduling
Ronald L. Graham, Combinatorial Scheduling Theory
R. Gary Parker, Deterministic Scheduling Theory, Chapman Hall.
Peter Brucker, Scheduling Algorithms, Fourth Edition, Springer
R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Khan, Optimization and approximation in deterministic sequencing and scheduling: a survey
Peter Brucker, Scheduling Algorithms, Springer-Verlag, 2007, Berlin Heidelberg New York (ISBN 978-3-540-69515-8).
Neural Networks for Combinatorial Optimization
Jean-Yves Potvin, Kate A. Smith, Artificial Neural Networks for Combinatorial Optimization
Kate Smith, Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research 1999.
Kate Smith, Marimuthu Palaniswami and Mohan Krishnamoorthy. Neural Techniques for Combinatorial Optimization with Applications
The originals of some of these references as presentation slides and other bibliography can be found in the web page of the subject:
http://mat.uab.cat/~alseda/MasterOpt/
Programari
All programs used in the subject are "do it yourself"