Módulo/Materia
- Materia Nivel 1: Optimización
- Materia Nivel 2: Optimización
Subir
Descripción/Contenidos
Optimización metaheurística. Fundamentos de búsqueda estocástica. Generación artificial de aleatoriedad. Scatter search. Tabú search. Simulated annealing. Greedy randomized adaptive search procedures. Variable neighborhood search. Aplicación en problemas reales de organización, planificación y logística. 5
Subir
Competencias genéricas
- CG5 - Identificar las soluciones más adecuadas y efectivas para los problemas que se planteen el marco de la Ciencia de Datos, teniendo en cuenta tanto las características propias del problema como el entorno del mismo.
- CG6 - Crear modelos y tomar decisiones basadas en los datos disponibles combinando los conocimientos adquiridos y siendo capaz de aplicar otros nuevos para la resolución de problemas.
- CB5 - Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía.
- CT5 - Capacidad para trabajar por proyectos.
Subir
Competencias específicas
- CE11- Ser capaces de utilizar las técnicas de análisis de datos adecuadas para extraer modelos matemáticos que enriquezcan formulaciones matemáticas de problemas de optimización.
- CE12- Dominar las técnicas de optimización metaheurísticas, incluyendo las basadas en poblaciones y en sociedades, así como el uso de combinaciones de las mismas en metaheurísticas híbridas.
- CE20- Resolver problemas de optimización complejos y dinámicos aplicando las técnicas más adecuadas a cada situación.
Subir
Resultados aprendizaje
- RA5. Conocer el concepto de metaheurística como base para la resolución de problemas de optimización complejos.
- RA6. Aplicar métodos de búsqueda estocástica para la resolución de problemas de optimización complejos.
- RA7. Identificar los algoritmos metaheurísticos más apropiados para la resolución de un problema.
- RA8. Diseñar e implementar algoritmos metaheurísticos adaptados a cada problema específico.
- RA9. Combinar diferentes estrategias de optimización para resolver problemas complejos.
- RA10. Evaluar las ventajas y desventajas de los diferentes algoritmos de optimización.
Subir
Metodología
|
|
|
Clases expositivas/ participativas
|
|
|
|
|
|
Realización de trabajos/proyectos en
|
|
|
Estudio y trabajo autónomo del estudiante
|
|
|
|
|
|
|
|
|
Total
|
|
|
Subir
Idiomas
Castellano.
Subir
Evaluación
Resultados de aprendizaje |
Actividad de evaluación |
Peso (%) |
Carácter recuperable |
Nota mínima requerida |
RA5, RA6, RA7, RA8, RA9 |
Pruebas escritas |
50 |
Sí |
5 |
RA6, RA7, RA8, RA9, RA10 |
Trabajos e informes |
50 |
No |
|
Si en alguna de las actividades no se cumpliera el mínimo para ponderar, la nota de la asignatura será como máximo 4,9 sobre 10 (suspenso).
Subir
Temario
- Tema 1: Introducción a la generación artificial de la aleatoriedad
- Generadores de números pseudoaleatorios.
- Generación de variables aleatorias.
- Tema 2: Problemas de optimización sobre grafos
- Conceptos básicos. Problemas de accesibilidad.
- Conectividad. Árbol de mínima expansión.
- Optimización de recorridos. Problema de ruta mínima, del cartero chino y viajante.
- Tema 3: Problemas de optimización sobre redes
- Conceptos básicos. Problemas de flujo máximo. Extensiones.
- Problemas de minimización de costes sobre redes.
- Tema 4: Introducción a los métodos metaheurísticos de optimización
- Conceptos y notación.
- Necesidad y naturaleza de los algoritmos metaheurísticos.
- Espacios de búsqueda. Intensificación y diversificación.
- Procedimiento de búsqueda local. Ejemplos.
- Tema 5: Tabu Search
- Conceptos básicos del método Tabu Search. Esquema del algoritmo.
- Conceptos avanzados de Tabu Search.
- Ejercicios, aplicaciones y práctica con ordenador.
- Tema 6: Simulated Annealing
- Fundamentos del método Simulated Annealing. Esquema del algoritmo.
- Fundamentos teóricos de Simulated Annealing.
- Ejercicios, aplicaciones y práctica con ordenador.
- Tema 7: Greedy Randomized Adaptative Search Procedures (GRASP)
- Estructura general del metaheurístico.
- Construcción de la Lista Restringida de Candidatos.
- Extensiones. GRASP Reactivo. Path relinking.
- Ejercicios, aplicaciones y práctica con ordenador.
- Tema 8: Variable Neighborhood Search (VNS)
- Esquema básico del metaheurístico.
- Extensiones.
- Ejercicios, aplicaciones y práctica con ordenador.
- Tema 9: Otras metaheurísticas
- Scatter Search.
- Large Neighborhood Search.
- Matheuristics.
- Ejercicios, aplicaciones y práctica con ordenador.
- Tema 10: Comparación computacional de algoritmos heurísticos
- Bancos de problemas.
- Comparación de la calidad de soluciones.
- Comparación de tiempos de ejecución.
Subir
Bibliografía
Acceda a la bibliografía que el profesorado de la asignatura ha solicitado a la Biblioteca.
La bibliografía de la asignatura es la que sigue:
- GENDREAU, M.; POTVIN, J-Y. (Editors) (2019). Handbook of Metaheuristics. Springer, 3ª Ed.
- BURKE, E. K; KENDALL, G. (Editors) (2014). Search Methodologies. Springer. 2ª Ed
- MARTÍ, R., PARDALOS, P. M., RESENDE, M. G. C. (Editors) (2018) Handbook of Heuristics. Springer.
- TALBI, E.-G. (2009). Metaheuristics: from design to implementation. Wiley.
Se recomienda igualmente consular las siguientes revistas:
- European Journal of Operational Research
- Computers and Operations Research
- Applied Soft Computing
- Heuristics
- Annals of Operations Research
Subir
Lugar de impartición
Universidad Pública de Navarra, Campus Arrosadía.
Subir