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

Metodología de trabajo en línea

Si el grupo es suficientemente pequeño (menos de 10 personas), trataremos por todos los medios posibles de usar videoconferencia con Google Meet: inicialmente el profesor expondría los primeros temas, y más adelante los estudiantes mostrarían cada semana sus avances.

Independientemente del tamaño del grupo, el lunes 1º de marzo tendremos una videoconferencia usando Google Meet para abrir el grupo; si el correo electrónico que tienen registrado en la Facultad no es el institucional (@ciencias.unam.mx), por favor escríbanle al profesor para proporcionárselo y que se les invite.

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 (ya sea en videoconferencia o vía correo electrónico) ameritará una calificación no aprobatoria.

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.

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.