Asignación de horarios utilizando algoritmos evolutivos Juan Pablo Pascual, Ignacio Chiazzo Facultad de Ingenieria,Algoritmos Evolutivos Email :
[email protected],
[email protected]
Abstract— Un aspecto importante en la gestión académica de las universidades es la generación de horarios y la asignación de salones de clase para los distintos cursos que se dictan. En este artículo se presenta la aplicación de un algoritmo evolutivo para la resolución de un problema de asignación de horarios, para las asignaturas de la facultad de Ingenieria, dictadas en el Edificio Polifuncional José Luis Massera (también llamado aulario) cumpliendo eficientemente con ciertos requerimentos y condiciones. Se tratará de organizar, generar y distribuir horarios de las materias de Facultadad de Ingenieria que se dictan en el Aulario.
I. INTRODUCCIÓN El Edificio Polifuncional José Luis Massera, es un edificio ubicado entre la Facultad de Ingeniería y el estadio Luis Franzini, el cual es compartido por la Facultad de Ingeniería, Facultad de Arquitectura y la Facultad de Ciencias Economicas para los dictados de distintos cursos de dichas facultades.[1] Actualmente se le asigna a cada una de las facultades una cantidad fija de cantidad horas donde pueden utilizar los salones del aulario. Los horarios del aulario son asignados de la siguiente manera : La Facultad de Arquitectura en coordinación con la Facultad de Economía asignan horarios y salones a sus distintas materias que serán dictadas en el edificio Polifuncional, una vez realizado esto, se plantea a la Facultad de Ingeniería los correspondientes horarios asignados por las otras dos facultades, y ésta es quien asigna sus horarios teniendo en cuenta los horarios ya fijados. En este artículo se presenta la resolución de asignación de horarios de las asignaturas de facultad de Ingenieria dictadas en el aulario, tomando en cuenta las asignaturas ya prefijadas por la facultad de Arquitectura y de Ciencias Económicas. Se toma como base la asignación de horarios prefijados por la Facultad de Arquitectura y de Ciencias Económicas para el primer semestre del año presente. La información de la asignación de horarios del aulario fue relevada de la Facultad de Ingeniería, y de los funcionarios administrativos del Edificio Polifuncional. A su vez se tiene en cuenta la asistencia a clase de cada materia, estos datos son estimados de acuerdo a las inscripciones de cada materia y un estimativo que se deriva de experiencia de asistencia del año en curso y años anteriores. La asignación de horarios de clases es un problema complejo, que cuenta con una buena cantidad de restricciones. El problema Scheduling Problem (SP), se
describe como el proceso de seleccionar y asignar recursos y tiempo al conjunto de actividades de una planificación, y teniendo en cuenta que la asignación debe cumplir con un conjunto de restricciones que reflejan la relación temporal entre las actividades y la capacidad limitada de los recursos compartidos [2]. Una forma particular del SP es el Problema de Programación de Horarios (Timetabling Problem) [2]. Este tipo de problemas, generalmente son problemas de optimización difíciles de resolver en forma exacta, en donde la complejidad de los métodos exactos aumenta de manera exponencial según el tamaño del problema y hace que la aplicación de los mismos sea inviable dado la gran cantidad de recursos que son necesarios para solucionarlos, principalmente en tiempo de proceso. En la búsqueda de soluciones a una gran cantidad de problemas en el área de la computación, se notó que hay algunos más difíciles de resolver que otros, teniendo en cuenta principalmente el tiempo de procesamiento y la cantidad de espacio en memoria que se requiere para resolver el problema. Dicho esto la complejidad del problema se puede clasificar en 2 clases principales: P y NP. En la clase P se encuentran aquellos problemas que pueden ser resueltos en un tiempo polinomial en una computadora deterministica, como por ejemplo problemas de ordenamiento, busqueda binaria, etc. En la segunda clase se encuentran aquellos problemas que puede ser resuelto en un tiempo polinomial pero usando una computadora no deterministica, se considera que estos son faciles de verificar la solución pero dificir de hallarla.[3] [4] El problema de asignación de horarios es considerado NP-Hard, por tanto es necesario utilizar heurísticas o metaheurísticas que permitan calular soluciones de calidad aceptable en un tiempo razonable.[5] [6]
II.
P ROBLEMA DE ASIGNACIÓN DE HORARIOS DEL E DIFICIO P OLIFUNCIONAL J.L M ASSERA
Esta sección presenta la descripción del problema de asignación de hoarios del Edificio Polifuncional J.L Massera y su formulación matemática como problema de optimización.
II-A. Descripción y modelo del problema El problema de asignación dispone de ciertas restricciones, de las cuales se clasifican en dos tipos : fuertes y débiles. Las restricciones fuertes son aquellas que deben ser cumplidas obligatoriamente mientras que las restricciones débiles, si bien no son obligatorias, representan condiciones deseables al problema, de las cuales son las que nos determinan la calidad de la solución. Éstas últimas restricciones están incluidas en la función objetivo, donde se trata de maximizar la cantidad de veces que estas son satisfechas, cada vez que estas restricciones no se cumplan se penalizará. A su vez se tiene en cuenta la preferencia de estas restricciones, es decir no todas las restricciones tienen la misma relevancia, se tomará en cuenta la importancia de las restricciones dando una mayor penalización a aquellas soluciones que no cumplan con las reestricciones de mayor importancia. A continuación se detalla las restricciones fuertes y débiles. Restricciones fuertes : Superposición: En un salón, en un mismo período de tiempo, se puede dictar una sola clase. Capacidad del Salón: La capacidad del salón es suficiente para la clase asignada Dispersión de materias : Si la materia se dicta en mas de un dia, no puede haber dos teóricos en un mismo día. La duración de una clase es fija y debe ser en periodos de media hora contiguos en el mismo salón. Los horarios prefijados por la facultad de Ciencias Económicas y la facultad de Arquitectura no se pueden modificar. Se debe respetar el bloque a las que pertenecen las materias del primer semestre. Restricciones débiles : Desperdicio de Salón: No se utilizan salones de gran capacidad para clases con pocos alumnos. La distancia en periodos entre las materias de un mismo semestre dictadas en un mismo día tiene que ser mínima. En un mismo día se trata de que no haya una sola materia de un mismo semestre. Se busca que los estudiantes no tengan que concurrir a clase por una sola materia. Notas : Distintos teóricos/prácticos de una materia son consideradas distintas materias, por ejemplo dos teóricos distintos de una misma materia como por ejemplo cálculo 1 son considerados materias distintas y son dictadas por distintos profesores. No se tiene en cuenta la disponibilidad de los profesores ya que en la práctica los profesores no son quienes eligen la preferencia de horarios. II-B. Formulación Matemática A continuación se presenta la formulación matemática para el problema de asignación de horarios para el Aulario.
Disponemos de las siguientes variables del problema : C = Cantidad de salones. Ki = Capacidad del salón. Cantidad máxima de alumnos que entran en un salón i. A = Cantidad de asignaturas. Ei = Cantidad de alumnos inscriptos en la asignatura i. Di = Duración de la materia i en cantidad de periodos. Si = Semestre de la materia i P = Cantidad de periodos para un dia. Ti = Día i, donde 0 < i < 6 y 1 corresponde al día lunes, 2 corresponde al día martes y así sucesivamente. Variable de decisión :
Xijkd
1, Si la materia i es asignada al salón j y en el = periodo k del dia d. 0, si no.
Restricciones : No superposición.
PA
i=0
Xijkd ≤ 1
Capacidad del salon. (Kj − Ei ) ∗ Xijkd ≤ 0 Disperción de las ( materias. P5 Di Si la materia i es dictada el dia d d=1 Xijkd = 0, si no ∀i. Duración fija de una clase. P Sea ini el primer periodo ini+D para la materia i en el día. k=ini i Xijkd = Di ∀i y un mismo salon (j).
III.
A LGORITMOS EVOLUTIVOS
La computación evolutiva es una rama de la computación emergente que engloba técnicas que simulan la evolución natural, y constituye un enfoque alternativo para abordar problemas complejos de búsqueda y aprendizaje a través de modelos computacionales de procesos evolutivos. Parte de un hecho observado en la naturaleza: los organismos vivos poseen una destreza consumada en la resolución de los problemas que se les presentan, y obtienen sus habilidades, casi sin proponérselo, a través del mecanismo de la evolución natural. La evolución se produce, en casi todos los organismos, como consecuencia de dos procesos primarios: la selección natural y la reproducción (cruce). La evolución natural es un proceso de cambio sobre una población reproductiva que contiene variedades de individuos con algunas características heredables y en donde algunas variedades difieren en su aptitud (éxito reproductivo).
El termino Algoritmo Evolutivo (AE) es empleado para describir sistemas de resolución de problemas de optimización o búsqueda basados en el ordenador empleando modelos computacionales de algún mecanismo de evolución conocido como elemento clave en su diseño e implementación. Los algoritmos evolutivos trabajan con una población de individuos, que representan soluciones candidatas a un problema. Esta población se somete a ciertas transformaciones y después a un proceso de selección, que favorece a los mejores. Cada ciclo de transformación y selección constituye una generación, de forma que después de cierto número de generaciones se espera que el mejor individuo de la población esté cerca de la solución buscada. Los algoritmos evolutivos combinan la búsqueda aleatoria, dada por las transformaciones de la población, con una búsqueda dirigida dada por la selección. [7] A continuacion se describe un pseudo-codigo de un algorimto evolutivo general [8]: Algorithm 1 Pseudo-Codigo Algoritmo Evolutivo 1: Inicializar (P(0)) 2: t ← 0{contadordegeneracion} 3: while 6= T erminado do 4: Evaluar(P(t)) 5: padres ← seleccion(P (t)) 6: hijos ← operadoresdevariacion(padres) 7: newpop ← reemplazo(hijos, P (t)) 8: t++ 9: P (t) ← newpop 10: end while 11: return mejor individuo hallado
IV.
D ISEÑO E IMPLEMENTACIÓN DEL ALGORITMO EVOLUTIVO PROPUESTO
Decidimos implementar el algoritmo evolutivo en Java con el framework WatchMaker.[9] IV-A.
WatchMaker
WatchMaker es una biblioteca código abierto de computación evolutiva implementada en Java. Fue desarrollada por Daniel Dyer como un proyecto independiente. Soporta únicamente AE, lo que permite que sea una biblioteca simple desde el punto de vista de programación. Algunas de las características principales son: [9] Soporta multi-threading por defecto No invasiva: cualquier clase puede ser objeto de evolución, sin implementar funciones abstractas. Varias estrategias de selección implementadas (Roulette Wheel Selection, Tournament Selection, etc). Estrategias de de evolucion implementados ([µ, λ], µ + λ). Soporte para islas. Operaciones de cruzamiento y mutación implementados para tipos de datos simples (string de bits, string de caracteres, arrays y listas).
Biblioteca opcional de componentes Swing para interacción y/o configuración del algoritmo. IV-B.
Representación de la solución
Los cursos son dictados de lunes a viernes cada semana (un total de 5 días por semana), de los cuales cada día tiene disponible el aulario de 08:00 hs a 23:00 hs (30 períodos de tiempo, cada período de tiempo es media hora). A su vez se cuenta con un total de 15 salones que cuentan con distintas capacidades. Las soluciones del problema son representadas como tuplas de largo 2050. Donde 2050 es calculado de la siguiente manera : Días de la semana * cantidad de períodos * Cantidad de salones, un total de 5 ∗ 30 ∗ 15 = 2250 slots. Cada slot del vector representa el código de la materia asignada a un día, a un horario, a un salón. Cada día = 450 slots, siendo los primeros 450 slots posee 2050 5 correspondientes al día lunes, los segundos 450 slots al día martes y así sucesivamente hasta el viernes. Dentro de los 450 slots de cada día, los primeros 450 15 = 30 slots corresponden al primer salon, los segundos 30 slots al segundo salon y asi sucesivamente. A modo de ejemplo se muestra a continuacion, en forma general, el arreglo con p Periodos, s Salones, y los cinco dias de la semana : dia0 dia0 dia0 dia0 dia0 dia0 dia0 dia0 dia0 dia0 dia4
salon0 salon0 salon0 salon0 salon0 ... salon0 salon1 salon1 salon1 .... salon1 ... salonS
periodo0 periodo1 periodo2 periodo3 periodo4 periodoP periodo0 periodo1 periodo2 periodoP periodoP
Dicho orden fue elegido por simplicidad en la iteración de los periodos, ya que de esta forma las materias asignadas a un horario en un mismo salón quedan en bloques continuos. En otras palabras, podemos ver que los cromosomas son representados como una matriz tridimensional, cuyos ejes coordenados representan los 5 días de la semana (eje x), los 30 períodos de cada día (eje z), y los 15 salones del aulario (eje y). Esto se puede apreciar en la siguiente figura :
Rf : Cantidad de restriciones fuertes del problema. Rd : Cantidad de restriciones débiles del problema. wf : Peso ponderado a las restricciones fuertes. wdi : Peso ponderado a la restriccion debil i. fi : Cumplicmiento de la restriccion fuerte i. ( Donde fi toma los siguientes valores: 1 Si se cumple la restriccion fuerte i fi 0 si no
Figura1. Representación del cromosoma
IV-C.
Inicialización de la población
Primero asignamos los horarios prefijados por las dos facultades (FARQ y CECEA) a nuestro vector mediante una marca especial que nos indique que ese horario no se puede modificar. Luego asignamos los horarios de las materias del primer semestre a sus bloques correspondiente, respetando sus horarios. Luego de forma random asignamos las restantes materias, y aplicamos el algoritmo de correción para corregir soluciones no factibles. Las asignaciones de las distintas materias se realizan en periodos contiguos dependiendo de la duración de la materia, es decir si una materia dura 1 :30 hs (3 periodos) se va a asignar 3 periodos contiguos (siempre y cuando estos tres periodos contiguos pertenezcan al mismo dia y salon). IV-D.
Algoritmo de correción
Observamos que de la forma que inicializamos la poblacion nos genera soluciones que no cumplen con alguna de las restricciones fuertes, especificamente las restricciones de Capacidad del salón y Dispersión de materias, por lo tanto procedemos por corregirlas. Para corregir la capacidad del salón se verifica la restricción, si no se cumple se busca otro salón que cumpla con la capacidad y que este libre, de no encontrase se busca un nuevo salón que cumpla capacidad y este ocupada por una materia cuya cantidad de alumnos sea menor, por ultimo si estos criterios no funcionan se procede por quitar varias materias y colocarlas nuevamente. Para corregir la dispersión se verifica la condición, si no se cumple se opta por asignar a otro día las materias en conflicto, buscando un horario acorde al bloque si corresponde. IV-E.
di : es un valor ponderado entre 0 y 1 que evalua la restriccion debil i. El calculo del valor di depende de la restriccion debil. A modo de ejemplo para la restriccion debil de dispersion de salon di se calcula aterias como TTotal−Alumnos−M otal−Alumnos−Salones , donde Total-Alumnos se calcula como la suma de la cantidad de alumnos que estan utilizando los salones, y Total-Salones es la suma de las capacidades de los salones utilizados, para los distintos periodos en que estos se utilizan. Además se cumple que : wf +
i=R Xd
wdi = 1
(1)
i=0
Se considera solución factible aquella solución que cumple todas las restricciones fuertes lo tanto es Pi=Rpor d razonable considerar que wf >> i=0 wdi ya que un incumplimiento de una restricción fuerte se debe tomar una mayor penalización que el incumplimiento de una restricción débil. De acuerdo a los datos relevados por bedelias, y en coordinación con personal administrativo encargado de asignar horarios, se obtuvo un orden de preferencias de las restricciones débiles, y se determinó el peso de cada una de ellas. Se asignaron los siguientes valores : wf = 0.8 wd1 = 0.08 Desperdicio de salon. wd2 = 0.11 Dispercion de materias. wd3 = 0.01 En un mismo dia no puede dictarse solo una materia de un mismo semestre. Observemos que las restricciones fuertes tienen un peso mayor que la suma de las déiles, además dicha asignación cumple con la ecuación(1).
Función de fitness
En la función de fitness se tiene en cuenta el cumplimiento de las restricciones fuertes y débiles, con una mayor peso a las restricciones fuertes. Se asocia un peso menor a las débiles, teniendo en cuenta la relevancia de la restricción, es decir estas restricciones no son homogeneas, para eso se asocia un peso ponderado a las distintas restricciones. F = wf
QRf
i=1
fi +
Pi=Rd i=0
wdi di
A continuación se describen las variables utilizadas en el fitness:
Otra observación a destacar es, dado que wf > Pi=Rd i=0 wdi y (1) vemos que si un individuo cumple f itness < wf entonces podemos afirmar que ese individuo tiene una solucion no factible, ya que no cumple alguna(s) de la(s) restriccion(es) fuerte(s). Màs aun, podemos decir que el fitness va a tomar un valor de [0, 0.20] o [0.80, 1], donde el primer conjunto se encuentra el fitness para aquellas soluciones no factibles (en ese caso algun fi vale 0 lo que hace el fitness quede determinado por las debiles cuyo maximo es 0.20), mientras que en el segundo conjunto se encuentran los fitness a las soluciones factibles ya que
QRf Pi=R wf i=1 fi = 0.80 y lo que varìa es i=0 d wdi di que a lo sumo es 0.20;
IV-F.
Operadores
IV-F.1. Selección: La elección del operador de selección no plantea dificultades específicas relacionadas con el problema de la asignación de horarios. Se utilizará un operador de selección por torneo de tamaño dos. IV-F.2. Mutación: Dado un gen a mutar se cumplen los siguientes pasos : 1) Se obtiene la materia correspondiente al gen.
V.
Esta sección reporta el analisis experimental del algoritmo evolutivo propuesto sobre un conjunto de instancias realistas del problema. V-A.
3) Se sortea una posición del individuo una cierta cantidad de veces hasta encontrar un salón en el que tenga disponible para dictar esa materia. 4)Si se encontró un salon disponible se le asigna dicho salon a la materia y salta a 5), si no se encontró, se utiliza un algoritmo de sustitucion por otra materia que funciona de la siguiente manera : -Se busca una materia m que tenga menor cantidad de alumnos que la materia en conflicto. Una vez encontrada la materia m se vacia el salon asociado a esa materia y se asigna ese salon a la materia en conflicto. Por ultimo se repite (2) siendo m la materia a asginar. 5) Se ejecuta el algoritmo de corrección de capacidad, y se retorna el individuo. IV-F.3. Cruzamiento: Dado el padre1 y el padre2 se crean dos nuevos hijos, donde el primer hijo se crea de la siguiente manera : Se asigna al nuevo gen las materias correspondientes a la Facultad de Arquitectura y CeCea. Se sortea la cantidad de materias del padre 1 y las materias a asignar. Se asignan dichas materias al nuevo gen. Por ultimo se asignan las materias restantes de forma random. Se procede analogamente para el segundo hijo, con la diferencia que para este hijo las materias sorteadas son del segundo padre. IV-F.4. Condición de parada: La condicion de parada sera de acuerdo a la cantidad de generaciones, dado que no se conoce el optimo global. Para determinar el numero de la condicion de parada se hizo un estudio informal, preliminar a la etapa de calibracion de los parametros, observando que con 10000 generaciones se obtenia resultados aceptables y si utilizamos 15000 o 20000 el tiempo demandado por el algoritmo aumentaba linealmente mientras que el fitness no tenia un cambio significante. Por lo tanto se utilizaron 10000 generaciones.
Plataforma de desarrollo y ejecución
El AE se desarrollo en Java, utilizando la biblioteca WatchMaker y el compilador de la IDE NetBeans version 8.0.2. Tanto la calibracion como la evaluacion se llevaron a cabo en un equipo con procesador Intel Core i3-4150 a 3.50Ghz, con 4GB de RAM y sistema operativo Linux Fedora, Version 21. V-B.
2) Se asigna el salón asociado a la materia como no asignado a ninguna materia.
R ESULTADO EXPERIMENTAL
Instancias del problema
Para la correcta evaluacion del problema, optamos por utizilar ocho intancias, cuatro de ellas utilizadas para la calibración, y las cuatro restantes utilizadas para evaluar el algoritmo y compararlo contra una algoritmo ávido. Las instancias de calibración, son de un tamaño menor ya que son untilizadas para calibrar los parametros del problema. Entre las instancias de evaluación, se encuentra la instancia real, la cual es la que representa la asignación de salones para el primer semestre del corriente año, las restantes tres instancias de evaluación cuentan con dimenciones similares a la instancia real. Dichas instancias fueron utilizadas para la correcta evaluacion del algoritmo y para su posterior comparación con el algoritmo ávido. Todas las instancias fueron generadas variando la cantidad de periodos, la cantidad de salones y las materias que se deben de asignar, tratando de representar varios escenarios diferentes para el problema. V-C.
Ajuste paramétrico
Debido a la cualidad estocástica de los algoritmos evolutivos, es necesario calibrar los parametros previamente al análisis experimental. Para los experimentos de configuración pramétrica se utilizaron 4 instancias del problema con diferentes características. Se optó por calibrar los parámetros de probabilidad de recombinación pC y probabilidad de mutación pM , cuyos valores candidatos fueron {0.55, 0.75, 0.90} y {0.001, 0.01, 0.1} respectivamente. Se estudiaron todas las combinaciones de estos valores sobre las 4 instancias de calibración, realizando 30 ejecuciones independientes del AE en cada caso, con 10000 generaciones en cada ejecucion. Debido al tiempo computacional que el algoritmo demanda se hizo, en una etapa preliminar al ajuste de los parametros, un estudio del tamaño de poblacion, en el cual se observo que con una poblacion pequeña como de 50 individuos, y una población de 100 individuos,
en los resultados obtenidos con una poblacion de 100 el fitness no varia significativamente y se duplica el tiempo computacional, por lo que se optó por tomar un tamaño de poblacion promedio entre estos valores (T p = 75). A continuación se presentan los resultados de la etapa de calibración, donde las siguientes cuatro tablas representan los fitness promedios de las 4 instancias, para las distintas combinaciones entre las dos probabilidades estudiadas. Figura1. Instancia1 pc /pm 0, 55 0,75 0,9
0, 1 0.8713499804 0.8713804196 0.8714343775
0, 01 0.8713878957 0.8713696898 0.871621062
0, 001 0.8710932806 0.8710814844 0.8711806769
Tabla I. Instancia1.
pc /pm 0, 55 0,75 0,9
0, 1 0.8585818622 0.8589236998 0.8586698495
0, 01 0.8586968503 0.8582234252 0.8581196113
0, 001 0.8578006826 0.8577319289 0.8577679398
Figura2. Instancia2
Tabla II. Instancia2.
pc /pm 0, 55 0,75 0,9
0, 1 0.8636434695 0.8637964313 0.8637674246
0, 01 0.8645879709 0.8643047329 0.8640294327
0, 001 0.8477448594 0.8641761669 0.8641095428
Tabla III. Instancia3.
pc /pm 0, 55 0,75 0,9
0, 1 0.8476533581 0.8476639442 0.8475339393
0, 01 0.8475764563 0.8480923098 0.8479435926
Figura3. Instancia3
0, 001 0.8477373204 0.8847569851 0.8474993569
Tabla IV. Instancia4.
Dado que no hubo ninguna combinación de parametros que reportaba el mejor fitness promedio para mas de una instancia, se decidió tomar la probabilidad de cruzamiento y mutación que estuviera asociadas mas veces a la mejor combinación de cada instancia. Para dos de las instancias se observa que el mejor fitness promedio se obtiene cuando la probabilidad de mutación es 0.01, y también para otras dos instancias se observó que la probabilidad de cruzamiento que obtiene el mejor fitness promedio vale 0.75, por lo tanto se decidió tomar como probabilidad de cruzamiento 0.75 y como probabilad de mutación 0.01 . Las Figuras 1, 2 ,3 y 4 reportan el fitness promedio obtenido para los distintos algoritmos estudiados, empleados en las cuatro instancias.
Figura4. Instancia4 V-D.
Evaluación experimental
La evaluación experimental trata de evaluar el desempeño del algoritmo evolutivo y su calidad en las soluciones obtenidas. Para evitar el sesgo en la parametrización se utilizaron cuatro instancias del problema diferentes a las utilizadas en la etapa de calibración de parametros, donde una de ellas corresponde con la entrada real, correspondiente
a los salones, periodos y materias del primer semestre del año en curso. Los escenarios correspondientes a estas instancias se hicieron variando el numero de materias, la cantidad de salones y la cantidad de periodos en el dia, siendo cada uno de estos parametros razonables con una instancia real. V-D.1. Resultados Numéricos: La Tabla V reporta los resultados del AE para las cuatro instancias del problema estudiadas. Las ejecuciones fueron realizadas con la configuración paramétrica determinada en los experimentos de calibracion. Se realizaron 30 ejecuciones independientes del algoritmo evolutivo para cada una de las instancias mencionadas anteriormente. Para analizar las soluciones se procedió por aplicar el test de Shapiro-Wilk [10] para determinar si los valores de los mejores fitnes obtenidos seguían o no una distribución normal. La Tabla V reporta los siguientes valores: max(In) denota el fitness mas alto para el fitness inicial, IN promedio de los mejores valores de fitness inicial, max(f ) el mejor valor de fitness alcanzado, f el promedio de los mejores fitness alcanzados,σ 2 (f itness) varianza de los mejores fitness alcanzados, min(T ) el mejor tiempo reportado, T el promedio de los mejores tiempos reportados, ;σ 2 (T ) varianza de los mejores tiempos alcanzados, min(gen) la minima de las generaciones que alcanzó la mejor solución, gen generación promedio que alcanzó la mejor solución, p-valor del test de ShapiroWilk sobre los valores de costo (p-valor S-W). Los campos que toman como variable el tiempo se están en segundos. En la tabla V se puede observar que para un nivel de significacion de α = 0.05 en el test de Shapiro-Wilk para la normalidad de los valores de los mejores fitness obtenidos, todas las ejecuciones cumplen que p − valor > α, donde podemos concluir que no es posible descartar la hipotesis nula del test de Saphiro-Wilk, que propone que los valores siguen una distribución normal, por lo tanto podemos confiar en que los datos de los mejores fitness alcanzados siguen una distribucion normal [10]. Otros resultados, así como las tablas completas son reportadas en la carpeta de entrega dentro de datos. V-D.2. Comparación con algoritmo ávido: Un algoritmo ávido (greedy) es un método de construcción de soluciones que toma la decisión localmente óptima en cada paso, con la esperanza de llegar a un óptimo global del problema. Es relevante comparar el desempeño del AE frente a un algoritmo ávido en terminos de la calidad de las soluciones alcanzadas y de la eficiencia computacional. Con este propósito, se implemento un algoritmo ávido sencillo para resolver el problema. Para implementar el algoritmo greedy se tuvo en cuenta
que dado una solución al problema, si queremos mejorar esa solución mejorando alguna de las restricciones debiles se puede entrar en conflicto con otras restricciones, por ejemplo, dada una solución factible del problema, si queremos mejorar en cuanto a capacidad de salon cambiando la asignacion de una materia a otro salon, es probable que esta nueva asignación tenga repercusiones negativas con otra restriccion (por ejemplo que dicha asignación tenga un impacto negativo en la restriccion de distancia entre periodos de materias de un mismo semestre),es por ello que se optó por utilizar un algoritmo de greedy donde en cada paso se busca el optimo local una de las restricciones debiles, especifícamente se decidió buscar el óptimo local en cuanto a dispersión de alumnos en el salón . A continuación se muestra un pseudo-código del greedy mencionado: 1) Se asignan los horarios de Farq y CCEA 2) Se asignan los horarios del primer semestre 3) Se asignan las restantes materias de la siguiente manera: Dada una materia se busca colocarla en el salon cuya diferencia entre la capacidad del salon y la cantidad de alumnos sea mínima, y además el salon este libre. En la tabla VI se presenta una comparación entre el algoritmo evolutivo y el greedy implementado para las 4 instancias mencionadas anteriormente. En dicha tabla, se reportan valores porcentuales de Gap, especificamente se reportan dos, uno de ellos es la diferencia porcentual entre el fitness promedio y 0.80 (GAP (f − 0.80)), y otra es la diferencia porcentual enre 1.0 y el fitness promedio (GAP (1 − f )), para ambos el valor porcentual está expresado en % y se calcula de la siguiente manera %GAP = [f (V T )−f (AE)]/f (AE)), donde V T representa el valor teórico (0.80; 1.0) y AE el algoritmo evolutivo. Tales valores 1.0 y 0.8 fueron estudiados ya que de acuerdo a nuestro problema y la manera que definimos el fitness, como se explicó en (IV-E), el fitness de aquellas soluciones que son factibles estan acotadas, precisamente se ubican en el intervalo [0.80; 1.0]. Tambien se reporta la mejora porcentual con respecto al promedio y maximo del fitness alcanzado entre el algoritmo evolutivo y el algoritmo greedy, ambas se reportan en % y se calcula analogamente a los porcentajes explicados anteriormente. Podemos observar que en las 4 instancias el algoritmo evolutivo supera al algoritmo de greedy tanto en el fitness promedio como en el mejor fitness, siendo la instancia 3 la que reporta el mejor valor porcentual de mejora.
Instancia Instancia 1 Instancia 2 Instancia 3 Instancia 4
max(In) 0.85449978 0.85028139 0.84933135 0.8432139
IN 0.853222172 0.849172055 0.846325696 0.842556228
max(f ) 0.8587711 0.854282039 0.855098781 0.848463573
f 0.857939722 0.08533398048 0.8535622206 0.847319877
σ 2 (f itness) 1.19658 ∗ 107 2.58686 ∗ 107 1.0311986 ∗ 106 3.46834 ∗ 107
min(T) 163.57 200.7 165.8 918.8
T 176.1 204.7 173.2 959.9
σ 2 (T ) 143.0 10.3 29.5 503.95
min(gen) 5964 2086 1189 1887
Tabla V. Instancia Instancia 1 Instancia 1 Instancia 2 Instancia 2 Instancia 3 Instancia 3 Instancia 4 Instancia 4
Algoritmo greedy AE greedy AE greedy AE greedy AE
f 0.8337898716 0.8579397226 0.839984449 0.8533398048 0.813995945 0.8535622206 0.8296703842 0.8473198772
max(f ) 0.8337898716 0.8587711004 0.839984449 0.854280395 0.813995945 0.8550987813 0.813995945 0.8484635731
Tiempo 0.0 176.1 0.0 204.7 0.0 173.2 0.0 959.9
p-valor (W-M) 1.86e-09 1.86e-09 1.86e-09 1.86e-09
GAP (f − 0.80) 4.1 6.7 4.7 6.3 1.7 6.3 3.6 5.6
GAP (1 − f ) 19.9 16.6 19.0 17.2 22.8 17.2 20.5 18.0
Tabla VI
En la figura 5 podemos observar una gráfica que representa los dos gaps porcentuales explicados anteriormente. Cuanto más bajo sea el gap sobre 1.0 mas cercano a 1 será el fitness alcanzado, analogamente cuanto mas bajo sea el gap sobre 0.80 mas cercano a 0.80 será el fitness alcanzado. Por lo tanto podemos ver que la mejor solución se da cuando el gap sobre 1.0 es bajo y el gap sobre 0.80 es alto, y se da en la instancia 3 al aplicar el algoritmo evolutivo.
Figura6. Estudio porcentual de la mejora sobre greedy
Figura5. Estudio porcentual de los Gaps La figura 6 representa una gráfica de la mejora porcentual de los mejores fitness y de los fitness promedios reportados del algoritmo evolutivo con respecto al greedy. En la figura podemos observar que en las 4 instancias ejecutadas el ae supera al greedy teniendo el mejor resultado para la instancia 3. En la tabla VI, tambien se reporta el p-valor obtenido sobre los valores de los mejores fitness reportados para las distintas instancias, al aplicar el test U de Man-Whitney para comparar el algoritmo evolutivo con el algoritmo ávido. El test mencionado nos reporta que existe una diferencia que es significativa entre las soluciones obtenidas por el algoritmo evolutivo y las soluciones reportadas por el greedy.
gen 9088 7590 6053 8563
p-valor 0.34 0.84 0.19 0.96
VI.
C ONCLUSIONES
Este trabajo ha presentado el diseno e implementacion de un algoritmo evolutivo para la resolucion del problema de asignacion de horarios del edificio J.L.Massera. Este tipo de problemas (TimeTabling) tienen la complejidad de que al agregar una nueva restriccion la complejidad aumenta exponencialmente, ya que no solo hay que estudiar su cumplimiento sino que tambien esta nueva restricción entra en conflicto con las demás restricciones del problema teniendo que evaluar el comportamiento con las demás. El algoritmo evolutivo propuesto conforma una precisa y eficiente solucion para el problema abordado. El análisis experimental realizado usando un conjunto de instancias del problema, mostró una notoria mejoría al comparar los resultados del algoritmo evolutivo, frente a un algoritmo ávido(Greedy). R EFERENCES [1] https://www.fing.edu.uy/node/4435, Consultado el 20 de Mayo de 2015. [2] A. Wren. Scheduling, Timetabling and Rostering – A Special Relationship? In E. Burke and P. Roos,The Practice and Theory of Automated Timetabling: Selected Papers from the 1st International Conference, pages 46–75. [3] Elvira Mayordomo. NP-completos. Universidad de Zaragoza. Zaragoza – España [4] Raúl Esteban Naupari Quiroz, GisselaKatheryn Rosales Gerónimo. Aplicación de algoritmos genéticos para el diseño de un sistema de apoyo a la generación de horarios de clases para la Facultad de Ingeniería de Sistemas e Informática de la UNMSM. Universidad Nacional Mayor de San Marcos.2010 Lima – Perú. [5] MULTISKILLED WORKFORCE SCHEDULING FOR BUSINESS WITH VARIABLE DEMAND USING THE GRASP ALGORITHM,Ing. David Álvarez Martínez, MSc. Eliana Mirledy Toro Ocampo. Febrero 2010. [6] Even, Sl, Atai, A., and Shamir, A. “On the commplexity of timetable and multicommodity flow problems”. SIAM Journal on Computing 5(1976) pp. 691-703. [7] http://www.it.uc3m.es/ jvillena/irc/practicas/estudios/aeag, Consultado el 21 de Agosto de 2015 [8] http://www.sc.ehu.es/ccwbayes/docencia/mmcc/docs/temageneticos.pdf. Consultado el 22 de Agosto de 2015. [9] http://watchmaker.uncommons.org/, Consultado el 21 de Agosto de 2015. [10] http://www.ub.edu/aplica_infor/spss/cap5-6.htm, Consultado el 23 de Agosto de 2015.
