Horarios Escolares

ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE CIENCIAS
DEPARTAMENTO DE MATE MÁTICAS

ALGOR IT M OS E VOLUT I VO S
A P L I C A D O S A L A G E N E R AC I Ó N
D E H O R A R I O S PA R A C O L E G I O

TESIS PREVIA A LA OBTENCIÓN DEL
TÍTULO DE INGENIERO
MATEMÁTICO
MENCIÓN INFORMÁTICA

POR
EDISON FERNANDO MERA MENÉNDEZ.

Q U I T O, 1 9 9 9

Certifico que la presente tesis ha sidoelaborada bajo mi dirección.

Dr. Polo Vaca Arellano.
Director de Tesis

2

Agradecimientos:
Al Dr. Polo Vaca Arellano.
Al Mat. Alfonso Salazar.
Al Ing. Oscar Parra.
Al Ing. Luis Torres.

Por la ayuda que me brindaron a lo largo del
desarrollo del presente trabajo.

3

Dedicatoria:
A mis padres: Walter y Filadelfia.
A mis hermanos: Walter, Fernando y Julio.

4

CONTENIDO
1INTRODUCCIÓN _________________________________________________ 7
1.1
1.2

2

METODOLOGÍA A USARSE EN LA ELABORACIÓN DE HORARIOS _____8
VARIABLES Y RESTRICCIONES QUE SE PRESENTAN EN LA
ELABORACIÓN DE LOS HORARIOS ________________________________ 10

ALGORITMOS EVOLUTIVOS______________________________________ 13
2.1
2.2

QUÉ ES UN ALGORITMO EVOLUTIVO ______________________________ 132.3

3

INTRODUCCION __________________________________________________ 13

VENTAJAS Y DESVENTAJAS DE LOS ALGORITMOS EVOLUTIVOS ___ 15

ELABORACIÓN DE HORARIOS POR MEDIO DE ALGORITMOS
EVOLUTIVOS ___________________________________________________ 17
3.1

INTRODUCCIÓN __________________________________________________ 17

3.2

DEFINICIONES BÁSICAS__________________________________________ 17

3.3

CONSTRUCCIÓN DE LA FUNCIÓN OBJETIVO Y LAS RESTRICCIONES 19

3.3.1
3.3.2
3.3.3
3.3.4
3.3.5
3.3.6
3.3.7
3.3.8
3.3.9

3.4
3.4.1
3.4.2
3.4.3
3.4.4

4

CRUCE DE PROFESORES ________________________________________________
CRUCE DE SESIONES EN UN MISMO CURSO ______________________________
AULAS DE UN TIPO DADO OCUPADAS ___________________________________DURACIÓN DE UNA SESIÓN DADA ______________________________________
CRUCE DE SESIONES ___________________________________________________
RESPETO DE LAS PROHIBICIONES DE MATERIAS. ________________________
RESPETO DE LAS PROHIBICIONES DE PROFESORES. ______________________
RESTRICCIONES ADICIONALES. _________________________________________
CONSTRUCCIÓN DEL MODELO MATEMÁTICO___________________________

19
19
20
21
21
21
22
22
25

PROGRAMA EVOLUTIVO UTILIZADO ______________________________ 26
OPERADOR DE CRUZAMIENTO__________________________________________
OPERADOR DE MUTACIÓN _____________________________________________
OPERADOR DE REPARACIÓN ___________________________________________
ALGORITMO EVOLUTIVO UTILIZADO ___________________________________

26
31
32
32DESARROLLO DEL SISTEMA DE GENERACIÓN DE HORARIOS ______ 35
4.1

INTRODUCCIÓN __________________________________________________ 35

4.2

ANÁLISIS ________________________________________________________ 36

4.2.1
4.2.2
4.2.3

4.3
4.3.1
4.3.2
4.3.3
4.3.4
4.3.5

4.4

INTRODUCCIÓN _______________________________________________________ 36
DESCRIPCIÓN DEL PROBLEMA__________________________________________ 36
IDENTIFICACIÓN Y CONCEPTUALIZACIÓN DE LOS OBJETOS Y PROCESOS _ 37

DISEÑO __________________________________________________________ 41
INTRODUCCIÓN _______________________________________________________
MODELO DE DATOS ____________________________________________________
DISEÑO DEL PROCESO _________________________________________________
DICCIONARIO DEDATOS _______________________________________________
SERVICIOS QUE OFRECE EL SISTEMA ___________________________________

41
41
61
77
79

IMPLEMENTACIÓN _______________________________________________ 96

5

4.4.1
4.4.2
4.4.3
4.4.4

INTRODUCCIÓN _______________________________________________________ 96
IMPLEMENTACIÓN DEL MODELO EN COMPUTADORA ____________________ 97
MODELO...