Título
Fusión de algoritmos meméticos con técnicas de satisfacción de restricciones y búsqueda local para calendarización de cursos
Autor
Dulce Jacqueline Magaña Lozano
Nivel de Acceso
Acceso Abierto
Materias
Resumen o descripción
El problema de Calendarización de Cursos (CTT - Course Timetabling), también conocido como Calendarización de Universidad (UTT - University Timetabling), se refiere a la programación de un conjunto de cursos dentro de un número finito de salones y en periodos de tiempo predeterminados. Este problema se considera interesante porque en cada ciclo escolar las instituciones educativas de nivel superior dedican días a la construcción de sus horarios, los cuáles a veces no resultan ser los que mejor se adaptan a las necesidades de sus estudiantes. Técnicas de investigación de operaciones, interacción humano-computadora, e inteligencia artificial se han utilizado para resolver el problema de CTT.
En este trabajo se propone el uso de un algoritmo híbrido que utiliza las técnicas de satisfacción de restricciones (CSPs), búsqueda local y algoritmos meméticos para calendarizar un conjunto de cursos en un tiempo razonable, respetando todas las restricciones de asignación y tratando de cumplir con un conjunto de preferencias. Las restricciones de asignación de cursos que se deben de satisfacer forzosamente en los problemas de CTT se conocen como restricciones duras, mientras que las preferencias se manejan como restricciones suaves, y son aquellas que son deseables más no obligatorias. Este algoritmo híbrido se compone de tres fases, la primera fase tiene que ver con la generación de una población de individuos, los cuales representan posibles soluciones al problema. Una parte de estos individuos serán creados con ayuda de un algoritmo de satisfacción de restricciones y la otra parte de manera aleatoria. La segunda fase consiste en evolucionar la población inicial de individuos mediante un algoritmo memético, con el fin de reducir las inconsistencias existentes en la población con respecto al conjunto de restricciones duras y blandas del problema, de forma rápida. La última fase de este algoritmo consiste en ejecutar una búsqueda local sobre el mejor individuo encontrado por el algoritmo memético, con el fin de eliminar cualquier posible conflicto persistente con restricciones duras. El objetivo de combinar estas tres técnicas es generar soluciones factibles y al mismo tiempo con un menor número de restricciones suaves violadas que cuando se aplican los algoritmos de forma independiente.
Los resultados obtenidos con el algoritmo híbrido se comparan con los resultados producidos independientemente mediante algoritmos genéticos, CSPs y el buscador local utilizado, y se demuestra que la combinación de algoritmos propuesta produce resultados competitivos en instancias del problema de CTT clasificadas como difíciles, ya que siempre obtiene soluciones factibles y con pocas restricciones suaves violadas, y mejores conforme se complica el problema a resolver.
Editor
Instituto Tecnológico y de Estudios Superiores de Monterrey
Fecha de publicación
1 de diciembre de 2008
Tipo de publicación
Tesis de maestría
Recurso de información
Formato
application/pdf
Idioma
Español
Repositorio Orígen
Repositorio Institucional del Tecnológico de Monterrey
Descargas
0