Algoritmos geneticos

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS
FACULTAD DE INGENIERÍA DE SISTEMAS E INFORMÁTICA
E.A.P. DE INGENIERÍA DE SISTEMAS

Aplicación de algoritmos genéticos para el diseño de un sistema
de apoyo a la generación de horarios de clases para la Facultad de
Ingeniería de Sistemas e Informática de la UNMSM.

TESINA
Para optar el Título Profesional de Ingeniero de Sistemas.

AUTOR
Bach.Raúl Esteban Naupari Quiroz
Bach. Gissela Katheryn Rosales Gerónimo

LIMA – PERÚ
2010

Título:
APLICACIÓN DE ALGORITMOS GENÉTICOS PARA EL DISEÑO DE
UN SISTEMA DE APOYO A LA GENERACIÓN DE HORARIOS DE
CLASES PARA LA FACULTAD DE INGENIERÍA DE SISTEMAS E
INFORMÁTICA DE LA UNMSM.

Bachilleres:
NAUPARI QUIROZ, Raúl Esteban
ROSALES GERÓNIMO, Gissela Katheryn

Tesina presentada aconsideración del cuerpo docente de la Facultad de Ingeniería de
Sistemas e Informática de la UNMSM como parte de los requisitos para obtener el
Título Profesional de Ingeniero de Sistemas.
Aprobado por:

Nombre:
Presidente

Nombre:

Nombre:

Miembro del Jurado

Miembro Asesor

Lima – Perú
Febrero 2010

ii

Resumen
Título:

Aplicación de algoritmos genéticos para el diseño de unsistema de
apoyo a la generación de horarios de clases para la Facultad de
Ingeniería de Sistemas e Informática de la UNMSM.

Bachilleres:

NAUPARI QUIROZ, Raúl Esteban
ROSALES GERÓNIMO, Gissela Katheryn

Asesor u Orientador de la Tesina:

CORTEZ VASQUEZ, Augusto

Título o Grado académico a obtener:

Ingeniero de Sistemas

El presente trabajo tiene como objetivo encontrar una soluciónal problema de
elaboración de horarios de clases que existe en la Facultad de Ingeniería de Sistemas
e Informática de la UNMSM. Este problema consiste en la asignación de un conjunto
de recursos dentro de un número limitado de periodos de tiempo; además de satisfacer
un conjunto de restricciones que se presentan en el ámbito académico. La importancia
de resolver el problema radica enminimizar el tiempo y la cantidad de personal que
interviene en el proceso de elaboración de horarios, además de brindar un apoyo en
dicho proceso al personal responsable. Durante la investigación se realizó una
comparativa entre algunas técnicas de búsqueda y optimización conocidas, tales como:
la Búsqueda Tabú, los Algoritmos Meméticos, el Recocido Simulado y los Algoritmos
Genéticos, paraidentificar cual de ellas posee las mejores características que permita
resolver nuestra problemática. Una vez realizado esto, se determinó utilizar los
Algoritmos Genéticos, los cuales pertenecen al grupo de técnicas metaheurísticas.
Estas técnicas son métodos que consisten en desarrollar algoritmos eficientes que
sean capaces de dar “buenas soluciones” a problemas, en donde encontrar el óptimoresulta costoso. En base a lo descrito, se propone un modelo matemático en el cual se
definen las restricciones del problema, para luego establecer el diseño de la solución y
la adaptación del algoritmo a ésta. Para la implementación del algoritmo se utilizó el
lenguaje de programación Java; obteniéndose como resultado diferentes horarios de
clases, los cuales son validados con los horarioselaborados manualmente; dicha
comparación permitirá determinar el alcance y las limitaciones del algoritmo creado en
este trabajo. Finalmente se llegó a la conclusión que el modelo desarrollado encontró
buenas soluciones al problema dentro del margen de error definido.
Palabras claves: Algoritmos Genéticos, Timetabling, Optimización, Asignación de
carga académica, Meta Heurísticas.

iiiAbstract
Title:

Application of genetic algorithms to design a support system to generate
class schedules for the Faculty of Engineering and Computer Systems of
San Marcos University.

Bachees:

NAUPARI QUIROZ, Raúl Esteban
ROSALES GERÓNIMO, Gissela Katheryn

Advisor or Supervisor of Dissertation:

CORTEZ VASQUEZ, Augusto

Qualification or degree to obtain:

Systems Engineer...