Download RobertoPatino.pps - ingeniería informática - umss

DEFENSA DE TESIS
UNIVERSIDAD MAYOR DE SAN SIMÓN
FACULTAD DE CIENCIAS Y TECNOLOGÍA
Proyecto de grado
para optar el titulo de:
Ingeniero en Informática
“Combinación de métodos empíricos con
algoritmos de Inteligencia Artificial para la
Generación de horarios académicos en los
Colegios”
Autor: Roberto Patiño Cuenca
La creación de horarios Académicos
MATE
CIENCIAS
INGLES
F. HUMA
MATE
MATE
CIENCIAS
INGLES
INGLES
MATE
INGLES
F. HUMA
ARTE
INGLES
ARTE
INGLES
E. FISICA
COMPU
LENGUA
INGLES
LENGUA
MATE
LENGUA
LENGUA
INGLES
LENGUA
D. TECNI
MUSICA
D. TECNI
COMPU
MUSICA
D. TECNI
MATE
CIENCIAS
LENGUA
Los afectados
DOCENTES
ESTUDIANTES
DIRECTORES
Antecedentes
Este trabajo se lo realiza
manualmente
 Es altamente estresante, con
tiempo limitado para realizarlo
 Las soluciones presentadas en
la UMSS son para el entorno
universitario.

Combinatoria 2003.
 Algoritmos Genéticos 2005.

Interrogantes
¿Por qué este problema
es NP-Completo?
 ¿Cómo resuelve el
problema la inteligencia
artificial?

Objetivo General
 Experimentar
con la combinación de
soluciones empíricas y Algoritmos
de Inteligencia Artificial para la
generación de horarios académicos
en los colegios.
Objetivos Específicos
Estructurar las funciones fitness
para los recursos involucrados.
 Codificar la combinación de la
estrategia empírica con
estrategias de inteligencia
artificial.
 Experimentar la factibilidad de los
resultados obtenidos.

Metodología

Investigación empírica
prueba error.
 Análisis de resultados.
 Ensayo de soluciones.
 Extracción de las
experiencias probadas

Plataforma de desarrollo

SQL estándar
Potencia en el manejo de
datos.
 Lenguaje disponible en
varias plataformas de
programación.


Access
Depurador paso a paso
 Grabado Directo en disco.

Modelo conceptual
DOCENTE_TR
DOCENTE_LEC
docente
DIA
ID_DOCENTE
<pi> Serial
<M>
NOMBRE_DOC
Characters (100)
NOMBRE_ABREV
Characters (10)
PESO_DOC
Number
ID_DIA
<pi> Serial
<M>
NOMBRE_DIA
Characters (10)
ID_DIA <pi>
ID_DOCENTE <pi>
DIA_D
DOC_R
materia
ID_MATERIA
<pi> Serial
<M>
NOMBRE_MAT
Characters (100)
ABREV_MAT
Characters (10)
PESO_MAT
Number
MAT_R
DOC_O
DOCENTE_D
DIA
MAT_O
ID_MATERIA <pi>
DOCENTE
RESTRINGIR_TIEMPO
OCUPADO Boolean
MATERIA_LEC
HORA_SEMANA
HORA_O
ID_HORASEMANA <pi> Serial <M>
ID_HORASEMANA <pi>
MATERIA
HORA_SEM_D
LECCION
CURSO_O
ID_LECCION
<pi> Serial
SESIONES_SEMANA
Number
PERIODOS_CONTINUOS
Number Leccion
LECC_R
ID_LECCION <pi>
horario
DISPONIBLE
HORA
SESION Number
CURSO
CURSO_D
LECCION
LECCIONTRUNCADA
REINICIOS
SESION
POSICION
LLEGO
INICIA
Number
Number
Number
Number
SESIONES_SEMANA
PERIODOS_CONTINUOS
SESION
POSICION
...
CURSO
CURSO_LEC
ID_CURSO
<pi> Serial
<M>
NOMBRE_CUR
Characters (100)
CURSO
ID_CURSO <pi>
CURSO_R
HORA
Number
OCUPADO
Boolean
FEROMONA Number
Se construye con Restricciones Duras
Son las reglas que debe
cumplirse bajo cualquier
circunstancia.
 Ej.:
Un docente no puede dictar
clases en dos sitios diferentes
al mismo tiempo
También Restricciones Suaves
Son las que pueden ser
ignoradas con el objetivo
de lograr la construcción
del horario.
 Ej.:
evitar los puentes en
una jornada laboral para el
docente
Bases teóricas
Colonia de Hormigas
Algoritmo Genético
Búsqueda Tabú
Método Empírico
Colonia de Hormigas
Algoritmo Genético
La técnica de construir la
función fitness
Búsqueda tabú

Tocar lo intocable (Taboo)

Cambiar los horarios ya establecidos
Método Empírico

Experiencia humana para resolver
este problema

Base de estructural del algoritmo
Seudo código AHE (Algoritmo Horarios Efectivos)
Calificar Complejidad Docente
Repetir mientras Exista lecciones
Extraer horas disponibles para el curso y docente
Calificar feromona a horas disponibles
Si hay hora disponible entonces
Asignar a la mejor hora disponible
Sino
Retroceder lecciones asignadas
Si no es posible asignación Entonces
Reportar como lección truncada
Fin si
Fin si
Fin mientras
Calificar la complejidad docente

Peso Docente
V0 = ∑HS*PM+∑HR
 V1 = ∑HS+∑PM+∑HR
 V2 = ∑HS+∑PM*01+∑HR
 V3 = ∑HS+∑PM*0.1+∑HR*1.05
 V4 = ∑HS+∑PM*0.1+∑HR*1.3
 V5 = ∑PM +∑HS+∑HR*1.3

HS : Horas Semana PM: Peso Materia HR: Horas Restringidas
Resultado de aplicar la Función Fitness
Peso Docente
ID_DOCENTE
NOMBRE_DOC
PESO_DOC
7
Prof. Ingles A
47.5
6
Prof. Ingles B
47.5
3
Prof. Matemáticas
1
Prof. Ciencias Naturales
41.6
10
Prof. Dibujo Técnico
41.2
4
Prof. Lenguaje
39.6
9
Prof. Edu. Física
38.1
5
Prof. Sociales
11
Prof. Arte
35.9
12
Prof. Música/Comp
35.4
8
Prof. Form. Humana
26.8
2
Prof. Ciencias Naturales B
12.8
44
36
Seudo código Algoritmo AHE
Calificar Complejidad Docente
Repetir mientras Exista lecciones
Extraer horas disponibles para el curso y docente
Calificar feromona a horas disponibles
Si hay hora disponible entonces
Asignar a la mejor hora disponible
Sino
Retroceder lecciones asignadas
Si no es posible asignación Entonces
Reportar como lección truncada
Fin si
Fin si
Fin mientras
Flujograma Ciclo creación de horarios
Flujograma Ciclo creación de horarios
Flujograma Ciclo creación de horarios
Prueba N°1 Sin Restricciones docentes
565
iteraciones
67
Reinicios
Iteraciones = Intentos de construcción
 Reinicializa = Complejidad Presentada.

Vista horario de Docente Matemáticas
Prueba N°1
HORA
LUNES
MARTES
MIERCOLES
JUEVES
VIERNES
1
_8 8vo Plomo
_15 8vo Plomo
_22 8vo Plomo
_29 8vo Guindo
_36 8vo Guindo
2
_9 8vo Plomo
_16 8vo Plomo
_23 8vo Plomo
_30 8vo Guindo
_37 8vo Guindo
3
_10 8vo Guindo
_17 7mo Guindo
_24 7mo Guindo
_31 7mo Guindo
_38 7mo Plomo
4
_11 8vo Guindo
_18 7mo Guindo
_25 7mo Guindo
_32 7mo Guindo
_39 7mo Plomo
5
_12 7mo Plomo
_19 6to Plomo
_26 6to Plomo
_33 6to Guindo
_
6
_13 7mo Plomo
_20 6to Plomo
_27 6to Plomo
_34 6to Guindo
_41 6to Guindo
7
_14 6to Plomo
_21 7mo Plomo
_28 6to Guindo
_35 7mo Plomo
_42 6to Guindo
Vista horario curso 7°guindo
Prueba N°1
HORA
LUNES
MARTES
MIERCOLES
JUEVES
VIERNES
1
_8 Ciencias Naturales
_15 Sociales
_22 Sociales
_29 Ingles
_36 Ingles
2
_9 Ciencias Naturales
_16 Sociales
_23 Sociales
_30 Ingles
_37 Ingles
3
_10 Ingles
_17 Matemáticas
_24 Matemáticas
_31 Matemáticas
_38 Lenguaje
4
_11 Ingles
_18 Matemáticas
_25 Matemáticas
_32 Matemáticas
_39 Lenguaje
5
_12 Formación Humana
_19 Ingles
_26 Dibujo Técnico
_33 Sociales
_40 Educación Física
6
_13 Lenguaje
_20 Ingles
_27 Dibujo Técnico
_34 Música/Comp.
_41 Arte
7
_14 Lenguaje
_21 Ciencias Naturales
_28 Música/Comp.
_35 Lenguaje
_42 Ciencias Naturales
Selección horario incomodo
Docente Formación Humana Prueba N°1
HORA
LUNES
MARTES
MIERCOLES
JUEVES
VIERNES
1
_
_
_
_
_
2
_
_
_
_
_
3
_10 7mo Plomo
_
_
_31 8vo Plomo
_
4
_11 6to Guindo
_
_
_
_
5
_12 7mo Guindo
_
_26 8vo Guindo
_33 6to Plomo
_
6
_
_
_
_
_
7
_
_
_
_
_
Prueba N°2
Restricciones para Formación Humana
Prueba N°2
605
iteraciones
75
Reinicios
Prueba N°2
Vista Resultado obtenido
HORA
LUNES
MARTES
MIERCOLES
JUEVES
VIERNES
1
_
_15 RESERVADO
_22 RESERVADO
_
_36 RESERVADO
2
_
_16 RESERVADO
_23 RESERVADO
_
_37 RESERVADO
3
_10 7mo Plomo
_17 RESERVADO
_24 RESERVADO
_
_38 RESERVADO
4
_
_18 RESERVADO
_25 RESERVADO
_32 6to Guindo
_39 RESERVADO
5
_
_19 RESERVADO
_26 RESERVADO
_
_40 RESERVADO
6
_13 6to Plomo
_20 RESERVADO
_27 RESERVADO
_34 7mo Guindo
_41 RESERVADO
7
_14 8vo Guindo
_21 RESERVADO
_28 RESERVADO
_35 8vo Plomo
_42 RESERVADO
14489
iteraciones
685
Reinicios
Prueba N°3
Datos completos reales
Prueba N°4 Horario inviable
54848
iteraciones
2104
Reinicios
Resumen de complicaciones al Crear Horario
Nombre_Doc
Elegido
PESO_DOC
TOTAL REINICIOS
1
2
3
4
5
6
Prof. Música/Comp
35.4
278
24
75
110
28
25
16
Prof. Arte
35.9
128
18
27
59
10
9
5
Prof. Form. Humana
35.9
113
32
48
19
14
36
451
77
97
143
49
42
Prof. Edu. Física
38.1
74
18
Prof. Lenguaje
39.6
317
44
59
96
39
38
Prof. Dibujo Técnico
41.2
82
14
24
29
14
1
Prof. Ciencias Naturales
41.6
262
71
66
62
63
44
247
28
17
55
28
Prof. Ingles A
47.5
68
Prof. Ingles B
47.5
84
Prof. Sociales
Prof. Matemáticas
43
43
17
13
54
21
53
1=Sexto Guindo; 2=Sexto Plomo;3= Séptimo Guindo; 4=Séptimo Plomo;
5= Octavo Guindo; 6 Octavo Guindo
43
41
65
4
14
Resultado de la elección
6621
iteraciones
531
Reinicios
Aporte informático
Se ha creado un nuevo algoritmo especializado.
 Se ha combinado técnicas de Inteligencia
Artificial.
 Se ha creado una plataforma de exploración,
para futuras investigaciones en horarios.

Conclusión
Se respeta las restricciones particulares de
cada institución
 Aporta información para realizar cambios o
negociaciones con los afectados
 Se agiliza el tiempo de construcción de los
horarios.

Recomendaciones

Hay nuevos desafíos
Integrar el costo económico del proceso.
 Integrar el costo social del proceso.
 Incrementar la funcionalidad que sugiera el
mejor camino, cuando no es posible construir
el horario
 Programar procesamiento en paralelo.

Tesis completa a [email protected]
Demostración del Software AHE
Ruta C:\HorariosAHE