evolutivos

Capitulo Nº 6: Resolución Del Problema
6.1 Resumen
La asignación de horarios, es un problema general de combinatoria que afecta a todas las instituciones, educacionales.
Existen muchas alternativas para encontrar algoritmos convenientes para la resolución del problema de asignación. Este capitulo muestra un acercamiento para abordar este problema usando un algoritmo genético. Tambiénpresenta un bosquejo de un programa evolutivo de este algoritmo genético, junto con los resultados y las conclusiones.
6.2 Introducción
El problema de asignación de horarios es un problema general de combinación, muy adecuado para ser solucionado con algoritmos computacionales. Esto Implica programar en forma optima un horario evitando conflictos al utilizar ciertos recursos satisfaciendo ciertosrequerimientos. El horario resultante debe ser válido y respetar, si puede, un grupo de restricciones adicionales dependientes del ámbito. El colegio cuenta con un grupo de profesores, un grupo de asignaturas y un grupo de requerimientos por nivel de los cursos o Malla de nivel.
Los horarios son la programación de clases a dictar en un curso determinado. Un curso pertenece a un nivel. Así elprimero A, es del nivel 1 y el cuarto B del nivel 4. Un horario esta compuesto por una serie módulos. Cada uno de ellos representa la intersección entre un día de la semana y un momento en el día. En la Ilustración 1 se muestra la intersección del un miércoles con el momento 4, esto define el módulo numero 4 de un miércoles.
 
Lunes
Martes
Miércoles
Jueves
Viernes
Sábado
Domingo
1
 
 
  
 
 
 
2
 
 
 
 
 
 
 
3
 
 
 
 
 
 
 
4
 
 
 módulo
 
 
 
 
5
 
 
 
 
 
 
 
6
 
 
 
 
 
 
 
7
 
 
 
 
 
 
 
8
 
 
 
 
 
 
 
9
 
 
 
 
 
 
 
10
 
 
 
 
 
 
 
Ilustración 1: Representación de un módulo
Un módulo tendrá asignado una asignatura y un profesor que la dicta. La asignación de esta información deben cumplir conuna serie de restricciones, tales como:
Un profesor no debe dictar mas de una asignatura en un mismo módulo.
Un módulo no debe tener definido mas de una sola asignatura
Una asignatura no debe ser dictada en un curso por más de un profesor.
No se debe asignar más módulos de una asignatura que aquellas definidas en la malla.
Estas se llaman restricciones duras. Así mismo existen otros tipos derestricciones, las cuales no son críticas y que al no ser cumplidas no quiebran la consistencia del horario, pero al ser cumplidas entregan un horario mucho mas optimizado que aquellas combinaciones que no las cumplen. Ellas se llaman restricciones suaves. Y algunas de ellas son:
Evitar módulos sin asignación de asignatura y profesor.
Asignar una asignatura en módulos consecutivos para un mismodía. Esto evita que exista otra asignatura entre dos módulos iguales.
Por otro lado los recursos con los cuales se cuentan son las disponibilidades de cada uno de los profesores, además de una serie de asignaturas que ellos pueden dictar.
La malla de cada nivel, es un grupo de asignaturas que deben ser asignadas en cada uno de los horarios, de los cursos que estén en ese nivel. Cadaasignatura, dentro de la malla, tiene un requerimiento de horas. Así, por ejemplo, Matemáticas para primero básico, debe cumplir con ocho módulos a la semana. La asignación de estos ocho módulos estará sujeta a los recursos disponibles, esto quiere decir que dependerá de que módulos dispondrá un profesor para dictar dicha asignatura.
6.3 Aproximación al algoritmo genético en el problema de asignación
Elproblema de asignación de horarios es, por su naturaleza, un problema computacional muy complejo. Un algoritmo que encuentre siempre una solución perfecta utilizando una búsqueda exhaustiva es impracticable debido al crecimiento exponencial en el tiempo de ejecución. Otros enfoques para resolver el problema de asignación de horarios es simular el pensamiento resolviendo el...