Tópicos selectos de optimización

Implementación, aplicación y análisis de métodos heurísticos

Esta es la página de la unidad de aprendizaje Tópicos selectos de optimización, impartida en el verano del 2012 por Elisa Schaeffer para estudiantes de ITS de la FIME, UANL. Las clases comienzan el 25 de junio y terminan el 13 de julio; es una sesión por día a horario M1-3 (07:00-09:30) en el salón 4208.

La versión impartida en esta ocasión se enfoca en los métodos heurísticos: su implementación (diseño y programación), aplicación (en problemas prácticas, modelados a través de la matemática) y análisis (evaluación de desempeño en términos de la calidad de la solución obtenida y en términos del tiempo de ejecución y la memoria requerida por el algoritmo).

Los prerequisitos para éxitosamente cursar la unidad son las siguientes unidades en su versión ITS o conocimientos equivalentes adquiridos por otros mecanismos.

Además se puede beneficiar de haber cursado éxitosamente las siguientes unidades:

Si una persona no puede inscribirse por motivos de lo que el departamento escolar decide manejar como dependencias formales entre unidades, estáa bienvenido a participar. Si aprueba la materia, la profesora le otorga una constancia escrita de esto para propósitos de futura revalidación (que no se puede garantizar).

Objetivo

Enseñar al estudiante los fundamentos y las metodologías para resolver problemas de optimización difíciles de forma eficiente y con soluciones comprobablemente de buena calidad.

Temario

Son 15 sesiones de 150 minutos cada uno. En una sesión típicamente primero trabajamos en el pizarrón 50 minutos, seguido por 50 minutos de demostraciones en vivo en la computadora de la profesora, terminando con 50 minutos para que los participantes comienzan a aplicar la técnica revisada.

  1. Repaso de conceptos centrales de análisis de algoritmos y optimización exacta
  2. Formación de equipos, selección de problemas y la revisión de su NP-dureza
  3. Obtención y generación de instancias reales y artificiales
    Ejemplo para el problema de la mochila en Python
  4. Cálculo de cotas inferiores y superiores
    Ejemplo para el problema de la mochila en Python
  5. Construcción de soluciones iniciales
    Ejemplo para el problema de la mochila en Python
  6. Metaheurística de búsqueda local voraz iterativa
    Ejemplo para el problema de la mochila en Python (ocupa gnuplot)
  7. Metaheurística de búsqueda tabú
    Ejemplo para el problema de la mochila en Python (ocupa gnuplot)
  8. Metaheurística de recocido simulado
    Ejemplo para el problema de la mochila en Python (ocupa gnuplot)
  9. Metaheurística genética básica
    Ejemplo para el problema de la mochila en Python (ocupa gnuplot)
  10. Metaheurística básica de colonia de hormigas
    Ejemplo para el problema de la mochila en Python (ocupa gnuplot)
  11. Híperheuristicos
    Ejemplo parcial para el problema de la mochila en Python (ocupa gnuplot)
  12. Análisis estadístico de desempeño
    Ejemplo parcial para el problema de la mochila en Python (ocupa gnuplot)
    Un script de bash para ejecutar el experimento
    Los archivos de configuración
  13. Visualización de evaluación de heurísticos
    Archivo de datos ejemplo
    Un script de Gnuplot ejemplo (para minimización)
    Un ejemplo de cálculo de promedio y desviación estándar en gnuplot
    Un ejemplo de un script de awk para calcular promedios y desviaciones estándar para las instancias del problema de la mochila generados con el script de bash
    Un ejemplo de un script de bash para recompilar las estadísticas agrupados por el tamaño de la instancia
    Un ejemplo de un script de gnuplot para graficas resultados por instancia de cuatro tamaños de instancias del problema de la mochila
    La gráfica generado por un experimento en PDF
  14. Análisis de complejidad asintótica de heurísticos
  15. Examen

En las sesiones 2-14, cada equipo (de dos o tres personas; no se puede ni solo ni en equipos de cuatro si no son oyentes por lo menos la mitad) produce una entrada en el blog del equipo, documentado el resultado de ese día. Lo que no se concluye en la sesión de clase (por falta de fluidez de programación de los integrantes), debe completarse fuera del salón para la sesión siguiente. Son 13 reportes, de los cuales hay que entregar por lo menos 9 para tener derecho a segundas; cada reporte vale un máximo de 10 puntos; se califica por equipo. El examen vale un máximo de 20 puntos y se califica de forma individual, aunque se realiza de forma grupal.

El examen oral se realiza en forma de presentaciones finales, cuyos preguntas aseguran que cada integrante de cada equipo comprendió de forma adecuada los pasos realizados. La sesión del examen será grabada en video para fines de comprobación. Si un participante, con derecho a segunda oportunidad, no aprueba en este examen, inmediatamente al concluirlo, presentará un examen escrito de segunda oportunidad de forma individual.

Temas y equipos

  1. Problema de k-centro métrico (Vic, Vane, Pedrito)
  2. Asignación de objetivos para armas (Omar, Saúl, Sosa, ¿Pollo?)
  3. Mínima suma de cuadrados (Dago, Ever)
  4. Calendarización (Mario, Max, Champy)
  5. Camarilla máxima (Rafa, Valdo, Blanka)
  6. Cubierta de vértices (Karen, Richard, Kevin)
EquipoReportes Total
123456 789101112 13
1 / Vic+ 97865 899-9 9-382
2 / Omar+ 87849 99745 ---70
3 / Dago+ 989910 101091010 999100+21
4 / Mario+ 1079910 101010-- 8--83
5 / Rafa+ 88944 87--5 97372
6 / Karen+ 75758 666-5 74369

Material

El material de apoyo sobre el diseño y análisis de algoritmos está disponible en PDF.

Libros

El mundo está lleno de libros relacionados. Los siguientes libros de texto, que son favoritos personales de la profesora, sirven como material de estudio, aunque asistencia en las clases o estudio de las diapositivas cubrirá los temas esenciales también.

Notas y tutoriales

Enlaces útiles

Actualizada el 12 de julio del 2012.
URL: http://elisa.dyndns-web.com/~elisa/teaching/opt/heur/