Generación De Horarios

“GENERACIÓN DE HORARIOS ACADÉMICOS UNIVERSITARIOS EMPLEANDO ALGORITMOS GENÉTICOS”

Autores:

Gabriel Rodríguez, Marianela nelagabriel@latinmail.com

Cruz Ortiz, Julio César jucecruz@terra.com

Miguel Vásquez, Fredy Ricardo fredymv@hotmail.com

Romero Ruiz, Hugo José Luis genesyss@hotmail.com

Institución:

Universidad Privada del Norte

Facultad de Ingeniería de Sistemas

Av. Ejercito Nº 920, Trujillo, Perú

Teléfono: (051) 044 – 220062

Portal Web: www.upnorte.edu.pe

Palabras Clave.- Búsqueda, generación de horarios, algoritmos genéticos, inteligencia artificial

El presente trabajo de investigación detalla la construcción de una aplicación informática que implementa rutinas de búsquedas para la generación de horarios académicos basados en la teoría de John Holland quien propuso una manera de seleccionar individuos y de cruzarlos y Goldberg quien lo popularizó como el algoritmo genético simple, con la salvedad de que nuestra investigación no reduce los códigos genéticos a binario, sino que los trabaja en su formato original, gracias a la tecnología de punta computacional actual. La aplicación ha sido desarrollada en Microsoft Visual Studio .NET

El funcionamiento del algoritmo genético sigue el siguiente proceso:

1. El sistema genera varios centenares de individuos o soluciones posibles.

2. Los que mejor se ajustan a los requerimientos, obtienen más posibilidades de reproducirse.

3. Se procede al cruzamiento de individuos aleatoriamente

4. De acuerdo a una heurística se decide, si los individuos, además deben mutarse o no y así se obtiene una nueva generación de individuo o soluciones.

5. Nuevamente se evalúa a los que mejor se ajustan a los requerimientos y obtienen más posibilidades de reproducirse. Las peores son descartadas.

6. Continuación: los pasos 3 y 4 se reiteran docenas de miles de veces. Tras miles de generaciones, el mejor individuo-solución resuelve el problema de manera satisfactoria. No se puede aspirar al óptimo absoluto.

Todo este proceso se basa en el tipo de reproducción en el que la dotación genética del nuevo ser tiene dos o más orígenes. La gran ventaja del ordenador es que puede simular decenas de miles de generaciones en minutos.

Este trabajo está basado en un algoritmo genético adecuadamente configurado. La función para nuestra evaluación esta definida independientemente por el usuario final, para reflejar sus deseos particulares (es decir, incluir en esta, todas las restricciones que deberán ser consideradas en el AG, así mismo las bonificaciones y penalizaciones a que se hace acreedor el/los individuo(s) en evaluación) con respecto a la calidad de la solución a obtener. También implica, que pueden utilizarse varias heurísticas o probabilidades ya desarrolladas, en la generación de nuevos individuos, lo que a menudo conduce a una mejora del rendimiento de éstos.

Modelo de Aplicación del Algoritmo Genético

El caso de estudio que se presenta en esta sección corresponde a las necesidades académicas para el semestre 2003-1 de la Universidad Privada del Norte - UPN.

Partiremos entonces para este modelo, de un conjunto de clases (ofertas de un curso previstas por la universidad para un semestre académico), cada una de las cuales tiene asociada una duración y un tamaño, que es la cantidad de horas asignadas a la clase (divididas en horas de teoría, horas de practica y horas de laboratorio) y el número de estudiantes real o estimado que se espera que asistan a él. Además existe un conjunto de aulas de diversas características y capacidades, y un conjunto de períodos de tiempo, en los cuales se llevarán a cabo los eventos.

Definimos entonces qué: un horario es una colección de N asignaciones, una para cada evento. Esta definición está sometida a múltiples restricciones, y con diferentes pesos. Algunas son inviolables, es decir, ningún horario será aceptado si

...