Universidad Pública de Navarra



Año Académico: 2023/2024 | Otros años:  2022/2023  |  2021/2022 
Graduado o Graduada en Ciencia de Datos/Graduado o Graduada en Administración y Dirección de Empresas por la Universidad Pública de Navarra
Código: 507311 Asignatura: OPTIMIZACIÓN II
Créditos: 6 Tipo: Obligatoria Curso: 3 Periodo: 2º S
Departamento: Estadística, Informática y Matemáticas
Profesorado:
MALLOR GIMENEZ, FERMÍN FRANCISCO (Resp)   [Tutorías ] CILDOZ ESQUIROZ, MARTA   [Tutorías ]

Partes de este texto:

 

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.

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

Metodología Horas presenciales Horas no presenciales
Clases expositivas/participativas 32  
Prácticas 24  
Realización de trabajos en grupo   13
Estudio y trabajo autónomo del estudiante   75
Tutorías   2
Total 60

90

 

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