Embed Size (px)
Citation preview
“Generación de horarios académicos en INACAP utilizando algoritmos genéticos”
Alumno: Jorge Ahumada A.Profesor Guía : Nelson Baloian T.30 de junio de 2014
Introducción
“La generación de un horario de una institución de educación, no es un proceso fácil”
“Generación de Horarios Académicos en INACAP”
Estado del Arte
Concepto de Timetabling.
Enfoques de solución.
Tipos de problemas.
Tipos de restricciones.
“Generación de Horarios Académicos en INACAP”
Justificación y contexto
INACAP 26 sedes. 115.000 alumnos. Crecimiento explosivo.
Generación de horarios en INACAP Cursos Salas Docentes
“Generación de Horarios Académicos en INACAP”
Justificación y contexto
Restricciones “duras” para asignación de horarios en INACAP
Un docente no puede asignarse a dos o más cursos en un mismo horario.
No se pueden planificar dos o más cursos de una misma carrera y un mismo nivel en un mismo horario.
No se pueden planificar dos o más cursos en una misma sala en un mismo horario.
A un docente no se le puede planificar más horas que el máximo de horas diarias y semanales.
Todo curso debe tener asignado una sala y un docente. Las secciones debe programarse en horario según su
jornada, diurna o vespertina.
“Generación de Horarios Académicos en INACAP”
Justificación y contexto
Restricciones “suaves” para asignación de horarios en INACAP
Se debe minimizar las “ventanas” para los docentes.
Se debe minimizar las “ventanas” en la planificación de cursos de un mismo nivel y carrera.
Se debe asignar en primer lugar a los profesores con mayor prioridad.
Se debe asignar en primer lugar las salas con mayor prioridad.
“Generación de Horarios Académicos en INACAP”
Estrategias de solución
Algoritmos genéticos
“los algoritmos genéticos son algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado, para constituir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas” [Goldberg, 1989]
“Generación de Horarios Académicos en INACAP”
Estrategias de solución
Algoritmos genéticos
La estructura general de un algoritmo genético puede representarse con los siguientes pasos:
1. Define población inicial.2. Evalúa población inicial.3. Selecciona padres.4. Cruza.5. Muta.6. Evalúa.7. Selecciona y descarta soluciones no aptas.8. Mientras no exista solución, vuelve a 3.
“Generación de Horarios Académicos en INACAP”
Cromosomas
Representación para el problema de asignación de horarios.
“Generación de Horarios Académicos en INACAP”
Función de cruza
Una función de cruza usa dos cromosomas padres y los combina, generando nuevos individuos que a su vez son evaluados y seleccionados como padres de nuevas generaciones.
“Generación de Horarios Académicos en INACAP”
Función de cruza
“Generación de Horarios Académicos en INACAP”
Función de cruza (dirigida)
“Generación de Horarios Académicos en INACAP”
Función de mutación
Una función de mutación se encarga de realizar una modificación en un cromosoma, sin combinarlo con otro. Esto ayuda a explorar nuevas posibles soluciones que no se alcanzarían mediante la cruza.
“Generación de Horarios Académicos en INACAP”
Función de mutación
“Generación de Horarios Académicos en INACAP”
Algoritmo genético
“Generación de Horarios Académicos en INACAP”
1. Define población inicial.
2. Evalúa población inicial.
3. Selecciona padres.4. Cruza.5. Muta.6. Evalúa.7. Selecciona y
descarta soluciones no aptas.
8. Mientras no exista solución, vuelve a 3.
Caso de estudio
“Generación de Horarios Académicos en INACAP”
40 Salas
84 Docentes
s100 secciones
s46 cursos
Algoritmo genético
Lunes Martes Miércoles Jueves Viernes
Caso de estudio – Resultados preliminares
“Generación de Horarios Académicos en INACAP”
Caso de estudio - Problemas
“Generación de Horarios Académicos en INACAP”
Mala calidad de la población inicial. No convergencia Alto tiempo de ejecución Alto uso de espacio de almacenamiento
Caso de estudio – resultados finales
“Generación de Horarios Académicos en INACAP”
Conclusiones
“Generación de Horarios Académicos en INACAP”
Técnica de algoritmos genéticos es apropiada para problemas de timetabling.
Soluciones rápidas y eficientes. Técnica de algoritmos genéticos entrega
flexibilidad. Entrega una solución óptima y varias “casi”
óptimas. Dificultad para modelar restricciones “suaves”.
Objetivos cumplidos : menor tiempo en generar un horario y fácil integración con sistemas existentes
“Generación de horarios académicos en INACAP utilizando algoritmos genéticos”
Alumno: Jorge Ahumada A.Profesor Guía : Nelson Baloian T.30 de junio de 2014
