Ciencias de la Computación (plan 2013) 2023-2

Optativas, Seminario de Ciencias de la Computación B

Heuríticas de Optimización Combinatoria

Es necesario que hayan aprobado las siguientes materias para llevar el seminario:

• Modelado y Programación
• Análisis de Algoritmos
• Inteligencia Artificial
• Ingeniería de Software
• Complejidad Computacional (recomendada)

Temario

Exceptuando por recocido simulado y el Problema del Agente Viajero, todas las heurísticas y problemas en el temario son posibles ejemplos de lo que se verá en el seminario: se espera que los alumnos elijan problemas NP-duros y heurísticas para resoverlos y que vayan exponiendo ambos a lo largo del semestre.

1. Introducción
   1. Complejidad computacional
   2. Breve repaso de problemas NP-Completos y NP-Duros
   3. Optimización combinatoria
   4. La gráfica del espacio de búsqueda
2. Recocido Simulado
   1. Recocido simulado en metalurgia
   2. Función objetivo
   3. Heurística de recocido simulado
   4. Aceptación por umbrales
   5. Aplicaciones
3. Colonia de Abejas Artificiales
   1. Colonias de abejas
   2. Abejas empleadas, supervisoras y exploradoras
   3. Fuentes de alimento
   4. Heurística de colonia de abejas artificiales
   5. Aplicaciones
4. Optimización de Colonia de Hormigas
   1. Colonias de hormigas
   2. Evaporación de feromonas
   3. Sistemas elitistas
   4. Sistemas máx-min
   5. Heurística de optimización de colonia de hormigas
   6. Aplicaciones
5. Búsqueda con Cardumen de Peces
   1. Cardúmenes de peces
   2. Peso de peces
   3. Movimiento local
   4. Conciencia social
   5. Heurística de búsqueda con cardumen de peces
   6. Aplicaciones
6. Algoritmo de Optimización con Leones
   1. Cooperación de manada
   2. Defensa territorial
   3. Invasión territorial
   4. Apareamiento
   5. Heurística algoritmo de optimización con leones
   6. Aplicaciones
7. Optimización de Enjambre de Partículas
   1. Inteligencia de enjambre
   2. Posición y velocidad de partículas
   3. Selección de parámetros
   4. Comunicación entre partículas
   5. Heurística de optimización de enjambre de partículas
   6. Aplicaciones
8. Optimización de Ondas de Agua
   1. Teoría de onda en aguas poco profundas
   2. Propagación, refracción y rompimiento
   3. Fondo del océano como espacio de búsqueda
   4. Heurística de optimización de ondas de agua
   5. Aplicaciones

Modo presencial

El curso será en modalidad presencial.

Evaluación

El curso se evaluará de la siguiente manera:

Evaluación teórica

Los estudiantes expondrán su implementación de recocido simulado para el Problema del Agente Viajero, con actualizaciones pertinentes antes de entregarlo; lo mismo con el segundo proyecto. Además expondrán un problema junto con la heurística y diseño correspondiente para resolverlo. Por último expondrán sus resultados.

El curso es en modalidad seminario, por lo que se espera que los alumnos participen a lo largo del semestre en la discusión grupal de los problemas NP-duros, las distintas heurísticas y los contratiempos que se encuentren en la etapa de implementación. Una falta de participación ameritará una calificación no aprobatoria.

Además de las exposiciones y participación durante el curso, para el segundo y tercer proyectos deberán entregar un reporte; básicamente un documento (escrito en LaTeX) de alrededor de 10 cuartillas, donde expliquen el problema, la heurística utilizada para resolverlo y el diseño e implementación del sistema que lo resuelve, incluyendo figuras y tablas explicando el desempeño del mismo.

Evaluación práctica

Habrá tres proyectos; todos a realizar de forma individual. El primero consistirá en escribir una implementación de recocido simulado del problema del agente viajero. En el segundo un problema NP-duro se le presentará a los estudiantes y ellos podrán elegir la heurística para resolverlo. En el tercer proyecto los estudiantes eligirán tanto el problema NP-duro a resolver, como la heurística para resolverlo. Los proyectos 2 y 3 serán concurrentes al menos en parte.

Habrá distintos problemas que se expondrán para que los alumnos puedan resolver usando una heurística de optimización combinatoria. Dos distintos estudiantes pueden resolver el mismo problema con dos distintas heurísticas, o dos problemas distintos con la misma heurística: pero dos estudiantes distintos no pueden resolver el mismo problema con la misma heurística.

La fecha límite de entrega de los proyectos es inamovible.