Ir a Contenido Principal

AURORA - Sistema de Información Académico

 

AYUDA | SALIR

Información detallada de curso

 

Primer semestre 2019
Mar 28, 2024
Imagen transparente
1. IDENTIFICACION DEL CURSO

Código y Nombre de la Asignatura: IST 4450 - OPTIMIZACIÓN COMBINATORIA
División Académica: División de Ingenierías
Departamento Académico: Dpto. Ingeniería de Sistemas
IST 7111 Calificación mínima de 3.0
Número de créditos:
Intensidad horaria (semanal para nivel pregrado y total para nivel postgrado):
3.000 Horas de Teoría
0.000 Horas de Laboratorio
0.000 Otras Horas
Niveles: Educación Superior Pregrado
Tipos de Horario: Teoría

Optimización combinatoria abarca métodos combinatorios y/o estadísticos para obtener soluciones a problemas de naturaleza discreta cuya solución exacta requiere alto poder de cómputo y tiempos exponenciales. Problemas típicos en esta área son el agente viajero, el ruteo de vehículos y selección optima de funciones bases en problemas tradicionales de optimización numérica. Inicialmente, estructuras discretas tales como vectores, matrices y listas son utilizadas para representar el esquema general de soluciones a problemas de optimización. Una vez la estructura de la solución es definida, meta-heurísticas tales como: Búsqueda Tabú, Recocido Simulado, Algoritmos Evolutivos, Colonia de Hormigas, entre otros, son utilizados para llevar a cabo el proceso de optimización. Como en cualquier contexto de optimización, este proceso puede basarse en una única función objetivo (problemas combinatorios mono-objetivo) o en más de una función objetivo (problemas combinatorios multi-objetivo) En este último escenario, técnicas clásicas de optimización numérica son utilizados para encontrar frentes de pareto con soluciones óptimas teniendo en cuenta el criterio multi-objetivo. Esto es con el fin de explotar las meta-heurísticas previamente diseñadas para la solución de problemas mono-objetivos en esquemas de optimización multi-objetivo.


3. JUSTIFICACIÓN

Los problemas de naturaleza combinatoria son encontrados en diferentes ramas de la ciencia. Un área de común interés en el cual algoritmos de naturaleza combinatoria afloran es investigación de operaciones. Esta área ha sido el detonante para que miles de investigadores centren sus esfuerzos en el diseño e implementación de meta-heuristicas para la solución de problemas combinatorios con alto impacto en el sector productivo, por ejemplo, el problema del agente viajero y el ruteo de vehículos. Aun cuando el diseño e implementación de estas estrategias data de los años 80, ninguna metodología es cien por ciento eficaz ante diversos tipos de problemas y/o factores encontrados en diferentes ramas de la ciencia. Aún más, el reciente diseño de sistema de soporte para la toma de decisiones en sectores productivos, hace que nuevos métodos sean requeridos para la correcta operación y producción en plantas industriales siendo esto un ente crítico, sobre todo, cuando la lógica de negocio se basa en recursos no renovables. Se hace necesario entonces, el correcto diseño, implementación y validación de estrategias meta-heurísticas para la solución de problemas combinatorios con alto impacto industrial.



4. OBJETIVO GENERAL DEL CURSO

Diseño e implementación de meta-heuristicas para la optimización mono/multi-objetivo de problemas de naturaleza combinatoría.

Este curso se orientará a:
- Estudiantes de pregrado de ingeniería.

COMPETENCIA A DESARROLLAR

Competencia Profesional: Diseño e implementación de meta-heurísticas para la solución de problemas combinatorios en el sector productivo.
Programa: Ingeniería de Sistemas y Computación


5. RESULTADOS DE APRENDIZAJE

Al finalizar el curso, los estudiantes deben estar en capacidad de:

Dimensión de la competencia Resultado de aprendizaje

Conocimientos (Saber Conocer):
- Solución a problemas de naturaleza combinatoria.
- Representación de soluciones en problemas de naturaleza combinatoria.
- Esquemas de optimización mono-objetivo sobre estructuras discretas.

Habilidades (Saber Hacer):
- Generación de espacio de soluciones factibles a problemas de naturaleza combinatoria.
- Diseño de sistemas de soporte para la toma de decisiones.

Actitudes (Saber Ser):
- Toma de decisiones.


6. PROGRAMACIÓN DEL CURSO

Temas, Subtemas, No. de Horas a cargo del profesor, Trabajo independiente (describir las actividades)
Fundamentos de Optimización, Campo de Optimización en Ingeniería.

- Lectura de artículos científicos básicos en el área de optimización.
- Consultar artículos bibliográficos con taxonomía de meta-heurísticas.
- Optimización combinatoria
- Historia
- Problemas de naturaleza combinatoria
- Representación de soluciones
- Estructuras discretas
- Lectura de artículos científicos asociados a representación de soluciones factibles en problemas de optimización combinatoria.
- Generando el espacio de soluciones factibles
- Función transición
- Validación de soluciones factibles.
- Meta-heurísticas.
- Estrategias de búsqueda local.
- Lectura del artiuclo "Pirlot, M. (1996). General local search methods. European journal of operational research, 92(3), 493-511."
- Lectura del artículo "Glover, F. (1989). Tabu search-part I. ORSA Journal on computing, 1(3), 190-206."
- Lectura del articulo "Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR), 35(3), 268-308."
- Implementación de meta-heuristicas hacienda uso de MATLAB
- Búsqueda Tabú.
- Recocido Simulado.
- Evitando óptimos locales.
- Algoritmos evolutivos.
- Algoritmos basados en Colonia de Hormigas.
- Optimización Multi-objetivo.
- Frentes de pareto.
- Adaptación de meta-heuristicas para la optimización mono-objetivo de problemas de naturaleza combinatoria a problemas combinatorios multi-objetivo.
- Implementación en MATLAB de metaheuristicas de optimización multi-objetivo.
- Suma con pesos.
- Métricas de optimización multi-objetivo.


7. OPCIONES METODOLÓGICAS - ACTIVIDADES DE APRENDIZAJE

Opción metodológica* (Para escoger tenga en cuenta el listado propuesto en el comentario).
Descripción


8. EVALUACIÓN

- Evidencia de aprendizaje (Para escoger tenga en cuenta el listado propuesto en el comentario).
- Formas o instrumentos para valorar la competencia.
- Periodo de la evaluación.
- Ponderación de la evaluación
- Comprender la dificultad en la solución de problemas combinatorios.
- Examen escrito 4 semana, 25%
- Diseñar el espacio de soluciones factibles para un problema combinatorio dado.
- Examen escrito 6 semana, 25%
- Implementación computacional de algoritmos para la solución de problemas combinatorios.
- Programa computacional 10 semana, 25%
- Propuesta de algoritmos para la solución de problemas combinatorios en esquemas mono-objetivo.
- Artículo científico 16 semana, 25%


9. BIBLIOGRAFÍA

Tanto para Bibliografía Básica cómo Bibliografía Complementaria se requiere de:

Tipo de bibliografía (Básica o Complementaria)
Tipo de referencia (Si es libro impreso, revista impresa, artículo de revista, VER LISTADO).
Idioma, Norma Técnica (ICONTEC, APA, otras)
Existe en Biblioteca o No LISTADO (Norma técnica estándar APA)

1. Libro Completo
Glover, F. W., & Kochenberger, G. A. (Eds.). (2006). Handbook of metaheuristics (Vol. 57). Springer Science & Business Media.
Glover, F., & Sörensen, K. (2015). Metaheuristics. Scholarpedia, 10(4), 6532.

2. Artículo en Revista
Glover, F. (1989). Tabu search-part I. ORSA Journal on computing, 1(3), 190-206.
Hoos, H. H., & Stützle, T. (2015). Stochastic Local Search Algorithms: An Overview. In Springer Handbook of Computational Intelligence (pp. 1085-1105). Springer Berlin Heidelberg.
Misevičius, A., Blažauskas, T., Blonskis, J., & Smolinskas, J. (2015). An Overview of Some Heuristic Algorithms for Combinatorial Optimization Problems. Information Technology and Control, 30(1).
Juan, A. A., Faulin, J., Grasman, S. E., Rabe, M., & Figueira, G. (2015). A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems. Operations Research Perspectives, 2, 62-72.
Pirlot, M. (1996). General local search methods. European journal of operational research, 92(3), 493-511.
Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR), 35(3), 268-308.
Guzman, L. G., Ruiz, E. N., Ardila, C. J., Jabba, D., & Nieto, W. (2016, May). A novel framework for the parallel solution of combinatorial problems implementing tabu search and simulated annealing algorithms. In 2016 6th International Conference on Computers Communications and Control (ICCCC) (pp. 259-263). IEEE.

Regresar a Anterior Nueva búsqueda
Imagen transparente
Versión: 8.7.2 [BSC: 8.10]