Ciencias de la Computación (plan 2013) 2018-1

Optativas, Seminario de Ciencias de la Computación B

Heuríticas de Optimización Combinatoria

EL HORARIO PROBABLEMENTE PODAMOS CAMBIARLO.

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 (recomendada)
• Complejidad Computacional (recomendada)

Temario

1. Introducción
   • Complejidad computacional
   • Problemas NP-Completos y NP-Duros
   • Optimización combinatoria
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. Algoritmos Genéticos
   • Teoría de la Evolución
   • Poblaciones y cromosomas
   • Función de reproducción
   • Heurística de algoritmo genético
   • Aplicaciones

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. Además expondrán un problema junto con la heurística y diseño correspondiente para resulverlo. Por último expondrán sus resultados.

Evaluación práctica

Habrá dos proyectos; ambos a realizar de forma individual. El primero consistirá en escribir una implementación de recocido simulado. El segundo consistirá en escribir una implementación de la heurística de optimización combinatoria que el estudiante exponga al grupo.

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.

Renuncias, NPs y extraordinarios largos

Para alumnos inscritos, la única forma en que se les pondrá NP en actas es si solicitan renunciar al curso mediante un correo electrónico dirigido al profesor, a más tardar en la octava semana de clases. Si no mandan un correo electrónico a más tardar en la octava semana, un alumno escrito tendrá en actas la calificación que obtenga en el curso, no importa cuál sea ésta, y no importa si deja o no de asistir a clases o de entregar proyectos.

No se guardan calificaciones para próximos semestres ni para exámenes extraordinarios. Mucho menos se “pasan” o “reciben” calificaciones a o de otros profesores.