Asignación de horarios utilizando ag

REPRINTED FROM: UNIVERSIDAD DE LOS LLANOS

1

Asignac i´n de Horarios de Clase utilizando o Algoritmos Gen´ticos e
Edica Xiomara L´pez C´rdenas o a (Invited Paper)
Abstract—El presente art´ ıculo se muestra la implementaci´n de una t´cnica de la computaci´n evolutiva como o e o es los algoritmos gen´ticos para la soluci´n de problemas e o de asignaci´n de horarios de clase, problemacomplejo deo bido a la cantidad de restricciones que se deben tener en cuenta y al criterio con el que se aplican. Finalmente se muestra las conclusiones y ventajas de implementar un algoritmo gen´tico a la hora de encontrar la asignaci´n de e o cargas acad´micas a docentes y alumnos, de tal manera que e optimice los recursos f´ ısicos y humanos Index Terms—Computaci´n o Evolutiva, Algoritmos Gen´ticos,Scheduling, Horarios, Problemas de Asignaci´n. e o

´ III. ALGORITMOS GENETICOS Una de las caracter´ ısticas m´s notables de la Natua raleza es la existencia de organismos adaptados para la supervivencia en pr´cticamente cualquier ecosistema. Esta a t´cnica se basa en los mecanismos de selecci´n que utiliza e o la naturaleza, de acuerdo a los cuales los individuos m´s a aptos de una poblaci´nson los que sobreviven al adapo tarse m´s f´cilmente a los cambios que se producen en su a a entorno. Estos cambios se efect´an en los genes de un inu dividuo, y sus atributos m´s deseables, es decir los que le a permiten adaptarse mejor a su entorno, se transmiten a sus descendientes cuando ´ste se reproduce sexualmente. e [1] Los AGs son programas de computadora que desarrollan diferentes patronesde la selecci´n natural para poder o resolver problemas muy complejos, consiste en encontrar la soluci´n ´ptima, y por tanto, los AGs son en realidad un o o m´todo de b´squeda. Pero un m´todo de b´squeda muy e u e u especial, en el que las soluciones al problema son capaces de reproducirse entre s´ combinando sus caracter´ ı, ısticas y generando nuevas soluciones. Su funcionamiento est´ a regidopor dos procesos b´sicos: la selecci´n natural y la a o reproducci´n sexual. El primero es la conexi´n entre los o o cromosomas y la capacidad de sobrevivencia de sus estructuras decodificadas. Esto contribuye a que los cromosomas que codifican estructuras aptas se reproduzcan con m´s frea cuencia que los que codifican estructuras poco aptas, as´ se ı determina que miembros de la poblaci´n sobrevivenpara o poder reproducirse, y el segundo, asegura la recombinaci´n o de genes de los progenitores. [2] .El siguiente diagrama muestra el proceso de un Algoritmo Gen´tico. e

´ I. INTRODUCCION

E

L problema de asignaci´n de horario de clase es un o problema que se presenta en cada uno de los periodos acad´micos en todas las instituciones educativas y cuya e soluci´n puede tornase dif´ demodelar por la cantidad o ıcil de variables y de restricciones que se deben tener en cuenta o simplemente puede tomar mucho tiempo. ´ II. DESCRIPCION DEL PROBLEMA

Para realizar una adecuada asignaci´n acad´mica en una o e instituci´n educativa se debe realizar un descripci´n geno o eral donde se establecen los factores que influyen como tambi´n las relaciones que existen entre cada uno de ellos, ees decir se debe determinar el n´mero de materias vistas u en cada periodo en cada uno de los semestres por cada carrera, la cantidad de salones disponible, n´meros de horas u por materias, la cantidad y disponibilidad de los docentes y algunas otras pol´ ıticas particulares de asignaci´n de clases o que var´ en las instituciones. Los principales factores que ıan influyen en la asignaci´n dehorarios en una instituci´n de o o Educaci´n Superior son: o • Pensum: Programa de estudios que comprende todas las materias que un estudiante debe cursar a lo largo de toda la carrera. • Disponibilidad Horaria del personal • Docente: Horas disponibles y preferencias de un profesor para dictar las clases de una o m´s materias. a • N´ mero de Secciones a abrir para un per´ u ıodo lectivo. • N´ mero y...