manual

TIMETABLING ACADÉMICO USANDO ALGORITMOS
GENÉTICOS Y PROGRAMACIÓN CELULAR
Francisco J. Martínez Ruiz*, Eduardo García Sánchez,
Jaime Muñoz Arteaga y Carlos H. Castañeda Ramírez.
Universidad Autónoma de Zacatecas. Departamento de Ingeniería en Computación,
Avenida Ramón López Velarde No. 801, Zacatecas, Zacatecas, México. C. P. 98060,
TEL. (492) 9239407 Ext. 1512, email:jmartinez@cantera.reduaz.mx.
RESUMEN.
En el ámbito educativo, se requiere la creación y planeación de horarios de la forma más
eficiente posible. Cada periodo académico, se deben organizar los horarios de alumnos
y profesores, de acuerdo a una serie de restricciones que para un programa educativo
mediano, implican un gran esfuerzo. Las soluciones construidas de manera manual,
además de tomar días o semanas, nogarantizan la remoción de bloqueos, es decir, que
un alumno no pueda tomar ciertos cursos debido a que les fue asignado el mismo
horario. La programación de horarios académicos es una caracterización del problema
general de timetabling (TTP). En este trabajo, se presentan los avances de una propuesta
de solución basada en algoritmos genéticos y programación celular.
INTRODUCCIÓN.
Elproblema de timetabling (generación
de horarios, ver fig. 1) es, un problema
clásico del área de optimización
combinatoria y es, así mismo, un
problema
de
gran
complejidad
computacional [1]. Ya que, pertenece a
una familia de problemas conocidos
como NP-Completos, para los cuales no
se conoce un algoritmo, que permita su
resolución en tiempo polinomial [2].
Este problema se ha estudiadoampliamente, ya que se tiene mucho
interés en obtener métodos eficientes
para su resolución [3].

Figura 1. Ejemplo de una tabla típica de
horarios escolares.

__________________________
*Autor a quien se debe enviar la correspondencia

Se han propuesto varios métodos para
su resolución entre ellos: coloreo de
grafos [4], recocido simulado [5],
colonia de hormigas [1] y algoritmosgenéticos [6].
El objetivo de esta investigación es
proponer una nueva estrategia de
resolución al problema de generación de
horarios basada en algoritmos genéticos
y programación celular. Por lo cual, a
continuación daremos una breve
introducción a estos dos conceptos para
proseguir con la descripción del modelo
propuesto.
Cabe destacar que, esta es una versión
minimalista. Donde,muchas de las
decisiones de diseño, buscan una
reducción del número de parámetros a
controlar para simplificar el problema
estudiado.

ALGORITMOS GENÉTICOS.
Los algoritmos genéticos (AGs) son
algoritmos
de
optimización.
Se
desarrollaron tomando como base el
proceso de evolución de los seres vivos
[7]. La idea de los AGs fue planteada
por John Holland [8] y una de las
primerasaplicaciones no triviales de los
AGs, la propuso David Goldberg en [9].
Los AGs son parte de un grupo de
algoritmos conocidos como algoritmos
evolutivos [10] y su fortaleza radica en
que llevan a cabo una búsqueda paralela
en el espacio de soluciones [11].

Inicialmente, esta población es generada
de manera aleatoria (la denotaremos
como X = {X1…Xn}). Cada solución
candidata se codificará enun
cromosoma [9]. Del como representar
las soluciones como cromosomas,
hablaremos más adelante. La idea
central de los AGs, es que las
soluciones compiten por ver quien es la
mejor MAX (Xi,…,Xn). De las mejores,
se produce una nueva generación, a
través, de la implementación de la
reproducción. La cual consiste en la
combinación de los cromosomas de dos
soluciones de la generaciónanterior que
resultaron bien evaluadas [12].

Para incrementar las posibilidades de
producir soluciones novedosas, se
introduce el operador de mutación que
imita al proceso natural de errores en el
copiado de algunas posiciones del
cromosoma de los padres en los hijos
[12].

Figura 2. Elementos de un algoritmo genético

ESTRUCTURA GENERAL DE UN
ALGORITMO GENÉTICO.
La estructura que...