Algoritmos Geneticos

os Geneticos Algoritmos Genéticos para la Optimización de Asignación de Espacios Áulicos
Marcelo J. Karanik José S. Pérez
{marcelo;jsantiago}@frre.utn.edu.ar

Grupo de Investigación Sobre Inteligencia Artificial (GISIA) U. T. N., Facultad Regional Resistencia – French 414 – Resistencia (3500) Chaco – Argentina
Resumen. Es sabido que la asignación de recursos finitos a necesidades que cambiandinámicamente es un problema difícil de tratar. Si a esto se le suma la necesidad de optimizar varios objetivos a la vez, las alternativas que puedan ser implementadas son escasas. Este trabajo describe un modelo genético para la optimización de la asignación de espacios áulicos en la Facultad Regional Resistencia de la Universidad Tecnológica Nacional. En la primera parte se describe el problemaque se trata de resolver. En la segunda se muestra el modelo utilizado y en la tercera los resultados obtenidos. Palabras clave: algoritmos genéticos, estructura del cromosoma, función de aptitud, optimización multi objetivos.

el mínimo movimiento de alumnos en los cambios de módulo y reasignando las aulas en caso de inasistencias de docentes o alguna circunstancia no prevista. La cantidad decombinaciones posibles de cursos a asignar está dada por:
1 · ⎣ ⎦ i! n : Cantidad total de cursos

∑ ⎢ (n − i)! ⎥ ⎢ ⎥
i =1

n

⎡

n! ⎤

2

(1) i : Cantidad de cursos a asignar.

1. INTRODUCCIÓN La asignación de recursos en cualquier organización deja de ser un problema trivial cuando los recursos son limitados y las necesidades van cambiando. Por lo general, la solución de estetipo de problemas trae aparejada una serie de condiciones de eficiencia, tiempo y oportunidad que deben ser tenidas en cuenta, más allá de que la asignación esté correcta. En este trabajo se propone una solución a la asignación dinámica de las aulas de la Facultad Regional Resistencia de la U.T.N. utilizando algoritmos genéticos. Para realizar la asignación, se tienen en cuenta los distintos cursosque se dictan, la cantidad de alumnos por cursos, la capacidad de las aulas y algunas necesidades específicas para el dictado de clases. Este problema puede ser abstraído de la siguiente manera: se supone que existen n recursos que son necesarios asignar a [1,.., i,.., n] demandantes del recurso y que las características de los recursos son parecidas en sustancia pero no en característicascuantificables. A medida que n aumenta, la explosión combinatoria se vuelve inmanejable si se quiere revisar todos los casos. Bajo estas condiciones, se puede pensar en esas combinaciones como un espacio de estados donde cada estado es una configuración posible de asignación. De esta manera, y como revisar un espacio de combinaciones muy grande es dificultoso, conviene dirigir o conducir la búsqueda de lasolución que permita resolver el problema de forma eficiente[4]. 2. DESCRIPCIÓN DEL PROBLEMA Dominio de aplicación La asignación de aulas a distintos cursos de las carreras dictadas en la Facultad Regional Resistencia, de la U.T.N. es un problema que genera inconvenientes tanto a alumnos como a docentes y personal administrativo. Algunas de las características de este problema son:
• • • • • • •• Las aulas tienen distintas capacidades. Las aulas están acondicionadas de forma distinta. En ciertos intervalos de tiempo durante la jornada no se utilizan todas las aulas, y en otros que no hay aulas libres. Los cursos no tienen la misma cantidad de alumnos. A medida que transcurre el año el número de alumnos por curso tiende a disminuir. La inasistencia de los docentes genera liberación deaulas durante ciertos módulos. Eventos especiales pueden requerir el uso de aulas. Es preferible mínimo movimiento de alumnos en los cambios de hora.

Como máximo se pueden asignar 19 cursos en forma simultánea, lo que equivale a 1,21 · 1017 combinaciones aproximadamente si se cubrieran todas las aulas. Dicha cantidad aumenta si se producen cambios en la asignación y se desocupan aulas. El...