- Adquirir capacidad para formalizar problemas de optimización combinatoria, proponiendo representaciones de soluciones eficientes, y estudiando el espacio de búsqueda.



- Diseñar e implementar algoritmos constructivos, algoritmos single-solution y algoritmos poblacionales tales como algoritmos genéticos o algoritmos de colonias de hormigas.



- Aprender a reconocer problemas de optimización multiobjetivo, optimización dinámica, y optimización con restricciones, y ser capaces de seleccionar alternativas existentes en la literatura para resolverlos



- Aprender a diseñar un marco experimental para realizar comparaciones de algoritmos estocásticos. Utilizar técnicas de visualización de resultados, aplicar métodos de análisis estadísticos, y extraer conclusiones sólidas.

* Tema 1 - Introducción a los heurísticos de búsqueda

1.1. Problemas de optimización combinatoria.

1.2. Codificación de soluciones y espacios de búsqueda.

1.2. Complejidad computacional.

1.3. Revisión de algoritmos clásicos.

1.4. Algoritmos constructivos.



* Tema 2 - Algoritmos heurísticos de búsqueda local

2.1. Función de vecindario

2.2. Búsqueda local

2.3. Criterios de selección

2.4. Máximos y mínimos locales y su estimación

2.5. Bases de atracción



* Tema 3 - Búsqueda local avanzada

3.1. Métodos Multi-start (MLS, GRASP, ILS,...)

3.2. Métodos de vecindario variable (VNS, VND...)

3.3. Métodos de selección de peores soluciones (SA, TS,...)



* 4. Gaia - Algoritmos poblacionales

4.1. Introducción

4.2. Algoritmos genéticos

4.3. Estimation of Distribution Algorithms

4.4. Swarm Intelligence (ACO, PSO)



* Tema 5. Variantes de problemas de optimización

5.1. Optimización multiobjetivo

5.2. Optimización dinámica

5.3. Optimización con restricciones



* Tema 6. Otros paradigmas de optimización

6.1. Bayesian Optimization

6.2. Reinforcement Learning to learn heuristics

6.3. Evolving with NNs



* Tema 7. Diseño experimental y comparación de algoritmos

7.1. Diseño de una experimentación

7.2. Ejecución de algoritmos

7.3. Visualización de resultados

7.4. Análisis estadístico de los resultados (incertidumbre)

Esta asignatura consta de cuatro tipos de actividades:



Clases Magistrales - En ellas se presentará la teoría de la asignatura que se ilustrará con ejemplos sencillos. Se fomentará la participación del alumnado mediante pequeños retos/ejercicios sobre problemas de combinatoria que se resolverán en la pizarra.



Prácticas Individuales de Laboratorio - Los/as alumnos/as, de manera individual, desarrollarán una serie de ejercicios prácticos que implicarán programar (en Python) y permitirán ilustrar los contenidos teóricos impartidos.



Proyecto en grupo - Las/os alumnas/os, en grupos de dos, o individualmente, desarrollarán un proyecto (en tres fases) en el que dado un problema de optimización combinatoria, deberán formalizar y para cuya resolución deberán plantear dos algoritmos metaheurísticos. Además, se llevará a cabo un estudio experimental que permita evaluar el rendimiento de los algoritmos. Todo ello se recogerá en un artículo de carácter científico de 4 páginas que se entregará cuando finalice el curso.



Seminarios - Se organizarán 3 seminarios sobre una temática complementaria al temario ya presentado y de manera relajada, debatiremos dichos contenidos en clase donde los alumnos primeramente trabajarán los contenidos y a continuación realizaremos una puesta en común.

Habrá dos formas de evaluación disponibles: CONTINUA y FINAL. En ambos casos habrá que obtener una nota mínima de 5 sobre 10 para aprobar la asignatura.



En EVALUACIÓN CONTINUA habrá seis tareas a cumplir: 2 pruebas (una teórica 30% y otra práctica 30%), 2 entregas de proyecto (20%), y 2 entregas de laboratorio (20%). La suma de las notas obtenidas en cada una de las pruebas resultará en la nota final. Por defecto, todo el alumnado comenzará por evaluación continua. En esta modalidad de evaluación, la nota final se calculará mediante los siguientes hitos:



Proyecto - %20 (en dos fases, cada entrega 10%)

1. Prueba teórica - %30

2. Prueba práctica - %30

Entregas de laboratorio - 20% (cada entrega 10%)



En cada prueba práctica habrá que obtener una calificación de 3.5 sobre 10 para continuar en evaluación continua. Si no se obtiene ese mínimo, el/la alumno/a pasará automáticamente a evaluación final. El alumno podrá cambiar voluntariamente de modalidad siempre y cuando lo haga antes de la segunda prueba práctica.



La EVALUACIÓN FINAL consistirá en una prueba mixta teórico-práctica del 80% y la entrega del proyecto del 20% que tendrá lugar en la convocatoria ordinaria de exámenes. La suma de las notas conseguidas en cada una de las pruebas será la nota final. En caso de no aprobar la prueba mixta (por debajo de 4 sobre 8), el alumno tendrá opción de ser evaluado nuevamente en la convocatoria extraordinaria de exámenes solo de esa parte.





En el caso de que el/la alumno/a por evaluación continua no apruebe, deberá realizar un único examen práctico en la convocatoria extraordinaria de exámenes.



A la vista de los contenidos expuestos, y dado el carácter práctico de la asignatura, se anima a seguir por evaluación continua.

Apuntes de la asignatura que se proporcionarán en eGela, así como numerosos artículos científicos que el profesor recomendará al alumnado. Por último, los ejercicios prácticos se programarán en Python e utilizando Jupyter Notebooks o Google Colab.

Bibliografía básica

* 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

Bibliografía de profundización

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

Revistas

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