
Sistema Automático de Asignación de Aulas
1. Introducción
En este artículo presentamos el estudio, implementación y pruebas de un motor de procesamiento de para la asignación automática de aulas, basada en Algoritmos Genéticos (AG). Para su implementación se utilizó programación orientada a objetos en lenguaje C#, patrones de diseño y una interfaz de comunicación basada en archivos JSON.
Debemos prestar especial atención en la codificación de los genes y la función de fitness porque ellos son la clave del éxito o fracaso de todo el proyecto.
2. Descripción del problema
Se necesita organizar un grupo de comisiones en un conjunto de aulas disponibles. La asignación comisión-aula va a depender de las necesidades o requerimientos de la comisión y la disponibilidad y prestaciones del aula.
Las prestaciones son codificadas en la base de datos y a cada aula es configurada con las prestaciones que puede brindar. Como ejemplo de prestaciones podríamos citar: wifi, PCs, toma corrientes, pizarrón, proyector, mesas para trabajar en equipo, climatización, etc.
La capacidad es la cantidad estudiantes que soporta un aula. Análogamente también representa la cantidad de estudiantes que componen una comisión.
Las comisiones se definen también con un horario de cursada, este horario debe coincidir con la disponibilidad horaria de un aula, de modo que no podrán superponerse dos comisiones distintas en el mismo horario, en la misma aula.
En definitiva, al programa se le presentan un grupo de aulas configuradas con sus respectivas prestaciones y un conjunto de comisiones que deben ser asignadas a aquellas. El programa debe encontrar alguna de las combinaciones óptimas para satisfacer los requerimientos de la mayor cantidad de comisiones. Estas combinaciones, mejor llamadas soluciones, pueden ser varias y, de ser posible, se ofrecerán al usuario las tres mejores.

3. Definición del Algoritmo Genético
Los algoritmos genéticos tienen una estructura y funcionamiento general, pero existen muchas opciones distintas de implementación. Lo interesante es expresarlos de manera correcta para que se adapten al dominio del problema planteado y resulte eficaz su ejecución.
3.1 Codificación
La codificación del problema es uno de los puntos más importantes, en ella se basan las estructuras de datos a utilizar y de estas depende el consumo de memoria y tiempo de procesamiento, ya que debemos tener en cuenta que cada individuo está representado por esta estructura de datos. Usaremos una gran cantidad de individuos para garantizar
una búsqueda exhaustiva y si sus estructuras de datos no son óptimas, por ej. si representan más información de la necesaria, entonces tendremos una baja performance en la ejecución y un alto consumo de memoria.
En nuestro caso necesitamos representar la grilla horaria de todos los días de la semana, tal como expresa la Figura 1.
Cada casillero de esta grilla contendría una instancia de espacio y tiempo para ser ocupado por una comisión, en caso de coincidencia de requerimientos.
3.1.1 Cromosomas y genes
Proponemos invertir la grilla vista en la figura 1, de esta forma podremos visualizar que cada aula será representada por un gen y todas las aulas juntas representarán un cromosoma o individuo.

Aquí nos enfrentamos al problema de la codificación del cromosoma: su representación como vector unidimensional sería demasiado extensa al tener que cubrir la totalidad de las celdas de la matriz.
Por tanto, se propone una modificación experimental a la estructura clásica del gen en AG, convirtiendo a cada gen en un cromosoma más pequeño, es decir en un vector de valores enteros.
Esto también impacta en el funcionamiento de los operadores genéticos, fundamentalmente para el cruce (crossover), que deberán tener en cuenta esta nueva complejidad para intervenir en el interior de cada gen con el fin de aportar diversidad en la búsqueda de soluciones.

En la Figura 3 se puede observar la codificación de un individuo o solución. Cada grupo de valores encerrados entre paréntesis representaría la asignación de comisiones para un aula. En este ejemplo lo acotamos a 8 horas, pero en la implementación real deberíamos agregar el total de las horas semanales, es decir todos los días de la semana desagregados por horas.
3.2 Operadores genéticos
Los operadores genéticos son los que posibilitan la combinación de genes de individuos padres para generar una nueva población más eficiente en términos de la resolución del problema.
En nuestra implementación diseñaremos los distintos operadores genéticos utilizando patrones de diseño, Strategy por ejemplo, para poder experimentar con distintas versiones de cada operador genético. De esta forma podremos encontrar la mejor configuración del algoritmo genético para nuestro problema y a la vez generaremos un código fuente legible, ordenado y extensible.
A continuación, describiremos algunos tipos de operadores genéticos que, a priori, consideramos ideales para nuestra implementación. No obstante, es probable que implementemos otras variantes de operadores genéticos.
3.2.1 Selección por torneo
Existen distintos métodos de selección para la reproducción de los individuos: selección por ruleta, selección por torneo, etc.
En nuestro caso utilizaremos la selección por torneo. Este método selecciona azar dos individuos de la generación actual para competir por la posibilidad de reproducirse. El más apto de los dos es seleccionado y el perdedor es descartado.
Consideramos que este es un buen método para mantener la diversidad genética. Si sólo se seleccionaran los individuos más aptos de cada generación, el algoritmo convergería tempranamente en una solución óptima local, perdiendo la posibilidad de explorar el resto del campo de búsqueda. Al hacer un torneo entre dos individuos al azar podría ser que se seleccionen dos buenos individuos: sólo uno se reproduciría y se perdería el otro. Asumimos este riesgo en pos de mantener la diversidad genética, pues también los menos aptos de una generación tendrán oportunidad de tener descendencia y su información genética, que en una generación temprana no representa una buena solución, quizás en una generación posterior pueda ser de utilidad para hallar la solución óptima.
3.2.2 Crossover (Cruce)
Una vez seleccionados los individuos para la reproducción se procederá a formar parejas para la reproducción. La forma de reproducción general es tomar trozos de información genética de ambos padres y generar con ella dos nuevos individuos. Hay varias formas de realizar esto, las más clásicas son el cruce de 1 punto, el cruce de 2 puntos y el cruce uniforme.
3.2.2.1 Crossover recursivo
Este es nuestro aporte al método crossover. Debido a la naturaleza multidimensional de nuestra codificación deberemos tener en cuenta esta estructura de datos compleja. Si utilizáramos un cruce clásico estaríamos atados hasta el final a la diversidad de combinaciones creadas al azar en la generación 0. Y sólo moveríamos esas combinaciones entre aulas, pero no variaría la distribución de comisiones en las horas.
Una estructura como la primera del ejemplo de la Figura 3 (1,1,1,1,0,8,8,0) permanecería intacta hasta el final y sólo presenciaríamos un intercambio de lugares entre estructuras fijas.
Para remediar este problema y aportar más diversidad en la búsqueda debemos intervenir también en el interior de estas estructuras.
Usaremos el crossover de un punto a nivel del cromosoma, y otro crossover de un punto al nivel de cada gen.
También la operación de crossover podría ser implementada una sola vez y llamarla de forma recursiva, tanto para el cromosoma como para el gen.
3.2.3 Elitismo
Este método se aplica para cuidar la genética de los mejores individuos. Aplicaremos el elitismo dejando pasar a la siguiente generación un porcentaje bajo de las mejores soluciones, probablemente un solo individuo. El elitismo garantiza contar siempre con la mejor solución encontrada durante todo el proceso de evolución.
3.2.4 Mutación
Imitando a la naturaleza, se aplicará un porcentaje mínimo (no más del 2%) de mutación en algún gen de los individuos seleccionados para tal fin.
En la naturaleza aparece la mutación como un error en la copia de información genética.
Si bien en la mayoría de los casos es perjudicial para el individuo que la sufre, en otros casos la mutación es algo positivo que fortalece la especie.
Con la mutación reforzamos un poco más la diversidad en la exploración del campo de búsqueda.
3.3 Método de evaluación: La función Fitness
Es la función clave en la implementación de nuestro algoritmo genético, debe representar la lógica de nuestro dominio.
Cada individuo tendrá asignado un valor Fitness que representará el nivel de error de la solución y necesitamos que ese valor tienda a 0. Ni bien un individuo tenga fitness 0, querrá decir que obtuvimos una solución óptima. Por lo tanto, el nuestro es un problema de minimización de errores.
De este modo, debemos enumerar una serie de reglas para evaluar a los individuos:
• Las asignaciones de comisión y aula deberán ser coincidentes respecto a sus requerimientos y prestaciones.
– Sería conveniente asignar un puntaje o peso a cada prestación, cuantificando los niveles de importancia. Por ej.: Acondicionador de aire es una característica preferible pero no indispensable, peso=1. Por otro lado, la capacidad suficiente del aula es una prestación indispensable,
peso=10.
• No deberá existir superposición de horario y aulas entre comisiones.
• No deberá existir superposición de asignaciones para una misma comisión en varias aulas, al mismo tiempo.
• Es preferible el agrupamiento horario.
3.4 Pseudocódigo del algoritmo principal
Una vez definidas todas las partes anteriores es momento de definir de forma general el funcionamiento del algoritmo principal. Este es sencillo, consta de unas cuantas instrucciones y un ciclo de repetición que se ejecutará hasta que se cumpla alguna de las condiciones de terminación. En nuestro caso, las condiciones de terminación son:
• Cuando se alcanza el límite de iteraciones (generaciones).
• Cuando la diversidad genética de la población actual no supera el 0,005%.
• Y fundamentalmente, cuando se encuentra un individuo de Fitness=0.
A continuación, mostramos el pseudocódigo:
Comienzo:
Inicializar población.
Evaluar población inicial, calcular Fitness.
Generación = 0.
Hacer Mientras [Fitness>0 Y Generación0.005]
Ejecutar Selección.
Ejecutar Elitismo.
Ejecutar Crossover (nuevos individuos).
Ejecutar Mutación.
Calcular Fitness.
Medir Diversidad genética.
Eliminar los individuos menos aptos.
Incrementar Generación.
Fin Mientras.
Devolver la mejor solución (el individuo más apto).
Fin.
4. Implementación y pruebas
Se implementó el algoritmo como una librería escrita en C#, .NET Core 3.5. Se utilizó programación orientada a objetos y se lo diseñó siguiendo patrones de diseño clásicos, con la idea de obtener un modelo de objetos claro y reutilizable Los datos de entrada (Comisiones, Aulas, cantidad de horas semanales, Prestaciones) son proporcionados en un archivo de formato JSON, que es deserializado y convertido a colecciones de objetos contenidos en un Dataset visible por todos los componentes del sistema.
El sistema encuentra efectivamente soluciones óptimas o cercanas en un tiempo promedio de 2 minutos.
Debido al importante consumo de tiempo de procesamiento, el algoritmo emite eventos con información acerca del progreso de la evolución.
La información provista en cada evento es:
• Generación (ciclo de iteración)
• Mejor solución de la iteración actual
• Peor solución en la iteración actual
• Mejor solución encontrada en todas las iteraciones
• Porcentaje de diversidad genética de la población actual (diversidad = distintos/población)
• Porcentaje de completitud
• Tiempo transcurrido
• Tiempo restante
4.1 Pruebas
La mejor configuración probada fue con poblaciones de 15000 individuos y 100 iteraciones (generaciones) en una notebook con 8GB de memoria RAM y un procesador Intel Core i5-6200U CPU @ 2.30GHz 2.40GHz, tomando unos 2 minutos promedio en alcanzar la solución óptima.
Para garantizar la diversidad genética y evitar una rápida convergencia del algoritmo, se le aplicó un porcentaje de mutación del 1%.
4.2 Mínimos locales: El problema del estancamiento
En una primera versión, durante el proceso de evolución, creímos conveniente dejar pasar a la siguiente generación a los padres seleccionados para la reproducción, además de sus hijos.
Esta decisión de diseño del algoritmo se tomó en un marco de pruebas, cuando se sufrían los efectos de un error de programación relativo a la copia de referencias de objetos. Esto se solucionó implementando un método de clonación de objetos.
Con la supervivencia de los padres entre una generación y otra, se observó con cierta frecuencia que la búsqueda caía en un mínimo local y quedaba estancada allí hasta el final de las iteraciones. Es decir, si se encontraba una buena solución (de fitness=3, por ejemplo) el algoritmo seguía generando soluciones muy parecidas e incluso idénticas, sin tener la posibilidad de explorar otras combinaciones.
Para medir la diversidad genética de la población se implementó un método llamado ADN() en el objeto individuo. Este método genera una cadena de texto que da identidad a la solución, a modo de ADN. Con esto, se pudieron comparar en cada iteración, todos los individuos de la población y así calcular su diversidad genética.
Conociendo la diversidad genética de la población en cada generación se pudo comprobar efectivamente una caída abrupta de dicha diversidad en iteraciones tempranas.

La Figura 4 ilustra una ejecución donde la diversidad genética decae definitivamente en la generación 43. El problema queda sin ser explorado de forma exhaustiva y el algoritmo nos arroja una solución mediocre.
Cabe aclarar que este tipo de casos no se dieron con mucha frecuencia, y a pesar de este problema de estancamiento, el algoritmo arrojó soluciones óptimas en la mayoría de los casos.
4.2 ¿Cómo evitar el decaimiento de la diversidad genética?: Hay que matar a los padres
Después de permitirnos esta pequeña broma, explicaremos la solución para mantener la diversidad genética.
Frente a un problema como este se podría pensar en la solución más tentadora: aumentar considerablemente el porcentaje de mutación. Es cierto que la mutación aporta diversidad a las poblaciones, diversidad muy valiosa en situaciones de estancamiento del algoritmo. Pero el abuso en la mutación resta inteligencia a nuestro algoritmo y lo acerca a una simple búsqueda aleatoria.
Encontramos otra solución bastante aceptable eliminando a los individuos seleccionados para la reproducción, luego de cada iteración, y generando en su lugar cuatro descendientes, producto de dos operaciones de Crossover.
Con este cambio obtuvimos una estabilidad considerable en el porcentaje de diversidad genética, incluso hasta el final de las iteraciones.
En la siguiente figura observamos los resultados de la ejecución del algoritmo, con la misma configuración que el ejemplo anterior, pero incorporando el nuevo cambio.

El caso mostrado en la Figura 5 fue ejecutado sin hacer uso del operador genético de Elitismo. Recordemos que este operador copia la mejor solución encontrada, de una generación a la siguiente.
En estas pruebas evitamos el elitismo para observar gráficamente la evolución de los mejores individuos de cada generación. Se inicia la iteración con soluciones aleatorias aceptables para rápidamente diversificar su población y elevar los niveles de error. Esto es algo necesario para garantizar una mayor exploración del campo de búsqueda.
Finalmente el algoritmo converge en soluciones con Fitness=0.
5. Paralelismo
Uno de los principales inconvenientes de las implementaciones de AG es el gran consumo de tiempo de computación. Con la intención de reducir el tiempo de respuesta global del sistema, y teniendo en cuenta las altas prestaciones de los sistemas de hardware actual, podemos permitirnos experimentar con la paralelización del algoritmo.
Existen varios enfoques para abordar este asunto. Una buena idea sería construir un algoritmo genético distribuido. Distintos procesos concurrentes, trabajando en distintos espacios de memoria (diferentes equipos) que colaboren entre sí mediante el intercambio de mensajes. Este enfoque trata a cada proceso como una isla donde su población evoluciona independientemente del resto de las islas, a lo sumo recibiendo “visitantes extranjeros” que aporten su información genética, eventualmente.
Descartamos el desarrollo de un algoritmo genético distribuido por la complejidad y el tiempo de desarrollo que requiere, pero dejamos en esta idea un pedacito de corazón anhelando retomarlo en el futuro en forma de tesis (específicamente en el campo de la programación genética distribuida).
La opción adoptada en el presente trabajo fue la realización de ciertas modificaciones necesarias para lograr la ejecución del algoritmo en paralelo, mediante el uso de programación multithreading.
En el primer intento de diseño, los hilos de ejecución intercambiaban sus mejores individuos en cada generación. La idea era acelerar la obtención de una solución óptima con la ayuda de «visitantes extranjeros” que aportarían una renovación genética a la población.
Según las pruebas realizadas esto no funcionó como se esperaba, produciendo el efecto contrario: todos los hilos paralelos convergían prematuramente en mínimos locales, producto de la uniformidad genética (falta de diversidad).
Los mejores resultados se obtuvieron tratando a cada hilo de ejecución como una isla absolutamente desconectada del resto y evolucionando independientemente. Es una
idea básica pero efectiva.
Planteamos el mismo problema de búsqueda para las versiones simple y multihilo de nuestro algoritmo. Ambas versiones trabajaron con el mismo set de datos y lo más interesante: las dos versiones deberían consumir aproximadamente la misma cantidad de memoria.
En concreto:
- Versión simple:
o 1 hilo de ejecución.
o Población de 15000 individuos.
o 100 generaciones. - Versión multihilo:
o 5 hilos de ejecución.
o Población de 3000 individuos (cada hilo).
o 100 generaciones.
La Figura 6 muestra la evolución del algoritmo con un solo hilo de ejecución. Esta es la forma de ejecución simple con la cual vinimos trabajando hasta el momento.

En este ejemplo la búsqueda es exitosa y se encuentra una solución de Fitness=0 en 145
segundos (2’ 25”).
Ahora veamos como le fue a la versión multihilo. A continuación mostramos una serie
de cinco figuras, cada una corresponde a un hilo de ejecución. Vale aclarar que todos los
hilos se ejecutaron al mismo tiempo, en paralelo.


Figura 7.2 – Hilo 2. Finaliza con Fitness=3.



En los gráficos anteriores se puede observar lo siguiente:
- La primera solución Fitness=0 se encuentra a los 33 segundos de ejecución, en el hilo 5.
- La segunda solución Fitness=0 se encuentra a los 56 segundos de ejecución, en el hilo 4.
- El resto de los hilos arrojaron resultados no tan óptimos pero útiles: Fitness=1, Fitness=3 y Fitness=8.
5.1 El estigma de la Población inicial
Con estas pruebas verificamos una de las características de los Algoritmos Genéticos: la configuración de la población inicial tiene una notable incidencia en el hallazgo de la solución global. Como venimos diciendo, el campo de búsqueda es muy extenso y los algoritmos genéticos tienen la virtud de explorarlo inteligentemente, evitando un recorrido completo y exhaustivo por la totalidad de posibilidades. A causa de eso, sucede a veces que el algoritmo puede explorar un campo cercano a la solución óptima sin llegar a encontrarla.
Podemos decir entonces, que existe un estigma que acompañara al algoritmo hasta el final de la ejecución. Este estigma es la forma en que se define la población inicial.
Recordemos que la población inicial se genera de manera aleatoria. También hay quienes sugieren “dirigir” esa aleatoriedad para establecer a la población inicial a un terreno cercano a una posible solución global.
En nuestro caso, intervenimos en el establecimiento de la población inicial con la norma
de asignar secuencialmente las horas de una comisión en un aula, una a continuación de la otra. Esta pequeña mano inicial que le damos al algoritmo es para que este tienda a obtener soluciones donde abunden los bloques horarios, tratando de evitar la alta fragmentación horaria (por ejemplo: si en un día hay una clase de 4 horas, es preferible que sean asignadas secuencialmente en un solo bloque y no fraccionadas en varios segmentos más pequeños).
Con la observación de los resultados del ejemplo anterior podemos detectar la injerencia de la población inicial, pues ejecutando el mismo algoritmo en cinco instancias paralelas hubieron dos de ellas que encontraron soluciones óptimas (y distintas) y las demás se acercaron pero no lograron alcanzar el Fitness=0.
Esto solo se explica poniendo atención en la configuración de la población inicial, como también en el componente azaroso que tienen los procesos de Selección, Corssover y, en menor medida, la Mutación.
Como conclusión, me atreveré a sintetizar la idea en una máxima, al estilo de los grandes hombres. Sólo pido que alguien la escriba en mi lápida:
“Podrá creer un algoritmo que es libre de explorar su propio camino, pero en realidad sigue un
sendero trazado antes de comenzar a andar.”
5.2 Los aportes del modelo paralelo
En comparación con su antecesor, este modelo de AG paralelo es definitivamente más efectivo. Encuentra la solución óptima aproximadamente dos veces más rápido que el algoritmo simple. Además, la ejecución del total de iteraciones es más rápida por no tener que manipular tantos individuos en cada iteración. Como última ventaja podemos mencionar que este modelo aporta varias soluciones óptimas y distintas, al provenir ellas de procesos de evolución independientes.
A la luz de estas evidencias decidimos utilizar el modelo paralelo en la implementación real del sistema SADA.
5. Conclusiones
Luego de realizar este trabajo hemos verificado una vez más, y de manera empírica, que los algoritmos genéticos son una herramienta muy útil para la búsqueda y optimización de soluciones.
Como ejemplo, podemos proponer un caso realista. Supongamos que tenemos que configurar las asignaciones de horarios para:
- 7 Aulas
- 10 Comisiones
- 12 horas semanales16
- 3 Prestaciones
Si utilizáramos el método de búsqueda secuencial (fuerza bruta) para encontrar una solución óptima, en el peor de los casos, deberíamos revisar una cantidad ingente de combinaciones:
7^10^12^3 = 1.71907333981×10304 individuos a evaluar
Con nuestro algoritmo genético versión simple de un solo hilo de ejecución, con 100 generaciones (iteraciones) y una población de 15000 individuos:
15000 * 100 = 1500000 individuos a evaluar
Tomando el peor de los casos, nuestro algoritmo tardaría alrededor de 4 minutos.
Prorrateando ese tiempo entre todos los individuos generados, la creación y evaluación de cada uno tomaría unos 0.16 milisegundos.
Y si trasladamos este valor a la búsqueda secuencial podemos inferir el tiempo que llevaría recorrer todo el campo de búsqueda:
1.71907333981×10304 x 0.16ms = 2.7505173437x10303ms
2.7505173437x10303ms/1000/3600/24/365 = 8.72183328164×10292 Años!!!!
Cabe aclarar que habrá más de una solución en todo el campo de búsqueda, y que con el método de búsqueda secuencial no necesariamente se debería iterar hasta el final.
Pero vale el cálculo como panorama de la magnitud del problema.
Otra ventaja con la que cuenta el método del algoritmo genético es la posibilidad de medir las distancias hipotéticas que hay entre las distintas soluciones, algo que la búsqueda secuencial no nos podría dar en este caso.
Como último comentario debemos mencionar la búsqueda aleatoria. Por tratarse de la probabilidad de 1 sobre el total del campo de búsqueda, P(x) = 1/1.71907333981×10304, por cada intento, podemos inferir que esta búsqueda se tornaría infinita.
Tanto la búsqueda secuencial como la aleatoria son métodos inviables y computacionalmente imposibles de llevar a cabo.
Por ello, los métodos evolutivos siguen siendo de gran aporte para la solución de este tipo de problemas.