Ingeniería de Sistemas y de Control (conjunto con UNED)

Máster. Curso 2018/2019.

OPTIMIZACIÓN HEURÍSTICA Y APLICACIONES - 604443

Curso Académico 2018-19

Datos Generales

SINOPSIS

COMPETENCIAS

ACTIVIDADES DOCENTES

Breve descriptor:

Algunos tipos de problemas de optimización son relativamente fáciles de resolver, ya que sus características intrínsecas permiten el uso de técnicas deterministas capaces de encontrar su solución optima. Este es el caso, por ejemplo, de los problemas lineales, que pueden ser resueltos con el método Simplex. Sin embargo, la gran mayoría de problemas reales no pueden ser resueltos con algoritmos determinista, bien porque sus características no han permitido el desarrollo de ninguna técnica "exacta" que asegure la localización de la solución óptima, o porque aun pudiendo ser las técnicas exactas utilizadas, el tiempo necesario para obtener la solución del problema resulte prohibitivo. La alternativa para estos casos, la constituyen los métodos heurísticos, que mediante diferentes mecanismos buscan una solución "buena" - aunque no necesariamente óptima- en un tiempo razonable. En esta asignatura se introduce al alumno en el uso de los métodos iterativos heurísticos, clasificándolos en dos grupos: (a) métodos basados en búsquedas locales; y (b) métodos basados en poblaciones. En los primeros, se realiza una búsqueda de la solución del problema en el entorno de la solución anteriormente localizada. En los segundos, se realiza una búsqueda global del óptimo, combinando la información del conjunto de posibles soluciones que constituyen la población. Muchos de los algoritmos de ambos grupos son algoritmos de optimización estocásticos, ya que sus procesos de búsqueda utilizan mecanismos aleatorios. El problema de optimización en si mismo también puede tener una componente estocástica que haga necesaria de un método de simulación de Monte Carlo en el proceso de evaluación de las posibles soluciones. Por lo tanto, en esta asignatura también se introducen algunas técnicas de simulación de Monte Carlo, y se discute su uso en la solución de problemas tanto deterministas como estocásticos. Por último, además del estudio de los diferentes métodos, se propondrán prácticas que muestren la aplicación de los mismos a problemas concretos. La asignatura se engloba dentro de la materia de OPTIMIZACIÓN.

Requisitos

CONTEXTUALIZACIÓN:
La asignatura se engloba dentro de la materia de OPTIMIZACIÓN, que a su vez está ubicada dentro del MÓDULO I (Matemáticas y Computación) del que también forman parte las asignaturas:
- Minería de Datos
- Sistemas Inteligentes
- Introducción a la Programación Matemática

Los métodos heurísticos son procedimientos para resolver problemas de optimización bien definidos mediante una aproximación intuitiva, en la que la estructura del problema se utiliza de forma inteligente para obtener una buena solución en un tiempo aceptable. Por lo tanto su forma de operar constituye una alternativa general a los métodos deterministas, aplicables a problemas con unas características Determinadas, estudiados en la asignatura Introducción a la Programación Matemática.

CONOCIMIENTOS PREVIOS RECOMENDABLES:
Los conocimientos necesarios para poder abordar la asignatura son:
Fundamentos de Programación

Además, debido a las características de los ejemplos utilizados para ilustrar los diferentes métodos que se estudiarán a lo largo de la asignatura, es conveniente que los alumnos también tengan conocimientos de:
- Modelado de Sistemas
- Fundamentos Control de Sistemas

Objetivos

RESULTADOS DEL APRENDIZAJE:
Una vez cursada la asignatura, los alumnos serán capaces de:
- Identificar el tipo de problemas de optimización que pueden ser resueltos mediante métodos heurísticos.
- Valorar los pros y contras de cada uno de los métodos estudiados en función del tipo de aplicación.
- Implementar en un lenguaje de programación los diferentes métodos de optimización heurística estudiados en la asignatura.

METODOLOGÍA:
La metodología que utilizaremos es la general de la UNED, basada en una educación a distancia apoyada por el uso de tecnologías de la información y el conocimiento. El alumno contará con el apoyo de una guía de estudio que explica en detalle el plan de trabajo propuesto para la asignatura y proporciona orientaciones sobre el estudio y las actividades que debe realizar. En esa guía encontrará información sobre cómo está organizada la asignatura, cómo utilizar los materiales y medios, qué actividades y prácticas se pondrán en marcha, y qué calendario deben seguir para concluir y enviar documentos y trabajos.
Las actividades formativas que contemplamos pueden agruparse en tres grandes grupos:
- Trabajo con contenidos teóricos.
- Realización de actividades prácticas.
- Trabajo autónomo.
La distribución temporal del total de créditos ECTS de la asignatura entre los grupos anteriores será la siguiente. Trabajo con contenidos teóricos 20%. Realización de actividades prácticas 20%. Trabajo autónomo 60%

Contenido

1. Introducción
2. Optimización heurística basada en Búsquedas Locales
1. Búqueda Local
2. Búsqueda Tabú
3. Simulated Annealing
 
3. Optimización heurística basada en Poblaciones
1. Algoritmos evolutivos (genéticos)
2. Algoritmos sociales (nubes de partículas)
 
4. Metodos de optimización de Monte-Carlo
1. Técnicas de simulación de Monte-Carlo
2. Algoritmos estocásticos
3. Problemas estocásticos

 

Evaluación

EVALUACIÓN DE LOS APRENDIZAJES:
La evaluación tendrá en cuenta los ejercicios prácticos realizados a lo largo del curso (40%).
Se realizará una práctica final en la que se pongan de manifiesto los conocimientos y destrezas adquiridas durante el desarrollo de la asignatura (60%). Dicho trabajo constara de la realización de una memoria explicativa, y de una presentación para el profesor y el resto de los alumnos.
Los objetivos de cada practica final serán propuestos de forma conjunta por los profesores y el alumno. Los alumnos propondrán a los profesores los problemas que desean resolver y los algoritmos que quieren utilizar. Los profesores analizarán la dificultad de la propuesta, aceptarán aquellas cuyos contenidos se ajusten a las habilidades desarrolladas a lo largo de la asignatura, y solicitarán cambios de objetivos (tanto para elevar la complejidad como para reducirla) en las restantes.
Para superar la asignatura será necesario aprobar la práctica final acordada entre los profesores y el alumno, y haber superado los ejercicios prácticos mandados a lo largo del curso.

TUTORIZACIÓN Y SEGUIMIENTO:
Se hará un seguimiento continuado del alumno evaluando los conocimientos y destrezas adquiridos en cada uno de los temas mediante la realización de ejercicios prácticos.
Para ello, a medida que se vayan abordando los diferentes temas, se solicitará que el alumno implemente diferentes operadores y/o algoritmos.
Adicionalmente, se realizará un proyecto final consistente en la aplicación de algunos de los algoritmos estudiados a un ejemplo concreto.

Bibliografía

ISBN(13): 9780387332543
Título: EVOLUTIONARY ALGORITHMS FOR SOLVING MULTIOBJECTIVE
PROBLEMS (2)
Autor/es: Lamont, Gary B. ; Coello Coello, Carlos A. ; Van
Veldhuizen, David A. ;
Editorial: : SPRINGER

ISBN(13): 9780470180945
Título: BAYESIAN SIGNAL PROCESSING: CLASSICAL, MODERN AND
PARTICLE FILTERING APPROACHES (1)
Autor/es: Candy, James V. ;
Editorial: : JOHN WILEY & SONS

ISBN(13): 9780792381877
Título: TABU SEARCH (1)
Autor/es: Glover, Fred W. ; Laguna, Manuel ;
Editorial: : KLUWER ACADEMIC PUBLISHERS

ISBN(13): 9781905209040
Título: PARTICLE SWARM OPTIMIZATION (1)
Autor/es: Clerc, Maurice ;
Editorial: Wiley-ISTE

Tabu Search. F.W. Glover, M. Laguna. Kluwer Academic Publishers. 1997.
Este libro está dedicado a los algoritmos de búsqueda tabú, que es una de las técnicas heurísticas de búsqueda local que serán estudiadas en esta asignatura

Evolutionary Algorithms for Solving Multi-Objective Problems. C.A. Coello-Coello, G.B. Lamont, D.A. van Veldhuizen. Springer. 2007
El contenido de este libro se centra en las técnicas heurísticas que optimizan conjuntos de soluciones con operadores inspirados en la evolución de las especies.

Particle Swarm Optimization. M. Clerc, Wiley-ISTE. 1995
Otro libro de técnicas heurísticas que manipulan conjuntos de soluciones utilizando para este fin operadores inspirados en la inteligencia colectiva y el comportamiento social de diferentes especies animales

Bayesian Signal Processing: classical, modern and Particle Filtering Approaches. J.M. Candy, John Wiley & Son. 2008.
En este libro se presentan diferentes técnicas de simulación de Monte Carlo útiles para la optimización de funciones no deterministas y/o para el desarrollo de nuevos algoritmos de optimización estocástica.

Otra información relevante

A lo largo del curso se facilitará material complementario de cada uno de los temas, relacionado con las aplicaciones que los alumnos consideren especialmente interesantes.

También se proporcionarán direcciones de Internet donde el alumno podrá ampliar conocimientos, ver modos alternativos de presentación de la materia, y relaciones entre los diferentes temas.

Como apoyo en el estudio de la asignatura, el estudiante dispone de los recursos siguientes:
1. Guía docente.
2. Curso virtual.
3. Tutorías con el equipo docente.
4. Biblioteca.
5. Internet.
6. Software específico.

Estructura

MódulosMaterias
No existen datos de módulos o materias para esta asignatura.

Grupos

Clases teóricas y/o prácticas
GrupoPeriodosHorariosAulaProfesor
Grupo A - - -ANTONIO OSCAR GARNICA ALCAZAR
EVA BESADA PORTAS
PABLO MANUEL RABANAL BASALO


Exámenes finales
GrupoPeriodosHorariosAulaProfesor
Grupo único de examen final - - -