Optimización
Código: 42250 Créditos ECTS: 6| Titulación | Tipo | Curso | Semestre |
|---|---|---|---|
| 4313136 Modelización para la Ciencia y la Ingeniería / Modelling for Science and Engineering | OB | 0 | 1 |
Contacto
- Nombre:
- Lluís Alseda Soler
- Correo electrónico:
- Lluis.Alseda@uab.cat
Uso de idiomas
- Lengua vehicular mayoritaria:
- inglés (eng)
Equipo docente
- Albert Ruíz Cirera
Prerequisitos
-
Conocimiento de matemáticas a nivel de un grado en ciencias
-
Saber programar
Objetivos y contextualización
El curso está dedicado a estudiar y practicar varios algoritmos de optimización heurística y combinatoria con especial énfasis en enrutamiento, gráficos, optimización de redes y programación.
Las conferencias se basan en presentaciones de diapositivas y material de internet.
El material teórico se complementará con algunas tareas (al menos una) para cada asignatura que desarrollarán individualmente los alumnos. Esta es una parte crítica del proceso de aprendizaje.
[Traducido de la versión inglesa por Google translator]
Competencias
- "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."
- Analizar, sintetizar, organizar y planificar proyectos de su campo de estudio.
- Aplicar la metodología de investigación, técnicas y recursos específicos para investigar en un determinado ámbito de especialización.
- Aplicar las técnicas de resolución de los modelos matemáticos y sus problemas reales de implementación.
- Comunicar en lengua inglesa los resultados de los trabajos del ámbito de estudio.
- Concebir y diseñar soluciones eficientes, aplicando técnicas computacionales, que permitan resolver modelos matemáticos de sistemas complejos.
- Extraer de un problema complejo la dificultad principal, separada de otras cuestiones de índole menor.
- Formular, analizar y validar modelos matemáticos de problemas prácticos de distintos campos.
- Usar métodos numéricos apropiados para solucionar problemas específicos.
Resultados de aprendizaje
- "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."
- Analizar, sintetizar, organizar y planificar proyectos de su campo de estudio.
- Aplicar técnicas de optimización para estudiar modelos asociados a problemas prácticos.
- Aplicar la metodología de investigación, técnicas y recursos específicos para investigar en un determinado ámbito de especialización.
- Comunicar en lengua inglesa los resultados de los trabajos del ámbito de estudio.
- Extraer de un problema complejo la dificultad principal, separada de otras cuestiones de índole menor.
- Identificar problemas que requieran aplicar técnicas de optimización para construir modelos asociados a problemas prácticos.
- Implementar las soluciones propuestas de forma fiable y eficiente.
- Implementar los algoritmos que constan en el programa
- Usar softwares específicos para la resolución de problemas de optimización.
Contenido
Algoritmos combinatorios para gráficos y enrutamiento: algoritmos Dijstra y A *. Optimización en gráficos.
Optimización determinística para problemas no lineales (restringidos y no restringidos)
Algoritmos genéticos
Recocido Simulado
Algoritmos de optimización de colonias de hormigas
Optimización de enjambre de partículas.
Redes neuronales en optimización.
Programación
Aprendizaje automático a través de redes neuronales.
[Traducido de la versión inglesa por Google translator]
Metodología
La metodología se basa en clases magistrales que consisten en la presentación de la teoría, ejemplos y algunos estudios de caso para cada algoritmo del programa de estudios.
Los estudiantes deberán implementar de forma independiente los algoritmos estudiados en situaciones realistas como una parte crucial del proceso de aprendizaje.
[Traducido de la versión inglesa por Google translator]
Nota: se reservarán 15 minutos de una clase dentro del calendario establecido por el centro o por la titulación para que el alumnado rellene las encuestas de evaluación de la actuación del profesorado y de evaluación de la asignatura o módulo.
Actividades
| Título | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|
| Tipo: Dirigidas | |||
| Asistir a las clases y actividades relacionadas | 37,75 | 1,51 | 1, 2, 4, 3, 5, 6, 7, 9, 8, 10 |
| Evaluation of the teaching performance and evaluation of the subject or module | 0,25 | 0,01 | |
| Tipo: Autónomas | |||
| Tasques (implementació dels algorismes – activitat individual) | 42 | 1,68 | 1, 2, 4, 3, 6, 7 |
Evaluación
Hay 7 tareas prácticas realistas que consisten en un informe y un programa que funciona. Tres de ellas serán obligatorias y cuatro opcionales.
Las asignaciones opcionales se deben hacer individualmente y pueden incrementar la nota final hasta un 20%.
Actividades de evaluación
| Título | Peso | Horas | ECTS | Resultados de aprendizaje |
|---|---|---|---|---|
| Implementación de algoritmos en casos realistas en proyectos de equipo | 50% | 35 | 1,4 | 1, 2, 4, 3, 5, 6, 7, 9, 8, 10 |
| Implementación de algoritmos en casos realistas en proyectos individuales | 50% | 35 | 1,4 | 1, 2, 4, 3, 5, 6, 7, 9, 8, 10 |
Bibliografía
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/
Software
All programs used in the subject are "do it yourself"