Universidad de ciencias de la informatica




descargar 35.53 Kb.
títuloUniversidad de ciencias de la informatica
fecha de publicación25.01.2016
tamaño35.53 Kb.
tipoBibliografía
b.se-todo.com > Documentos > Bibliografía

UNIVERSIDAD DE CIENCIAS DE LA INFORMATICA


INGENIERIA DE EJECUCION EN INFORMATICA
SEMINARIO

Sistema de Apoyo a la Gestión de horarios

para el colegio Piamarta”

ROFESOR GUIA : José Miguel Santibáñez
ALUMNO : Claudia Cornejo.

Álvaro Aguilar

Juan Bello

Darío Díaz

Milton González

Eduardo Llanquileo
e-mail : calitacc@yahoo.es

aaguilare@gmail.com

juanenriquebellovergara@gmail.com

inddiaz@gmail.com

miltongo@gmail.com

eduardolb@gmail.com
FECHA : 02-12-06

Índice.


UNIVERSIDAD DE CIENCIAS DE LA INFORMATICA 1

Índice. 2

Introducción. 3

1.- Definición del problema. 3

1.1.- Restricciones Duras. 3

1.2.- Restricciones Suaves. 4

1.3.- Situación Actual. 4

2.- Marco Teórico. 5

2.1.- Problema de asignación de horarios o TimeTabling 5

2.1.1 NP-Completo 6

2.2.- Algoritmos Heurísticos. 8

2.2.1.- Introducción. 8

2.3.- Algoritmos Genéticos. 10

2.3.1.- Introducción. 10

2.3.2.- Resolución de un Algoritmo Genético. 11

Consta de 5 etapas: 11

Índice de Ilustraciones 12

Bibliografía 13

Conclusiones 14

Introducción.



En toda institución académica es importante la asignación de horarios, esto se debe realizar al comienzo de cada periodo, sea año o semestres, y lo más rápido posible. Esto no es posible debido a que se deben combinar diversos factores como las materias a dictar, tiempos a cubrir por materia, disponibilidad de tiempo de los profesores y materias que los profesores pueden dictar. El presente seminario esta orientado a la solución de este problema utilizando para ello algoritmos heurísticos.

1.- Definición del problema.


El desarrollo de la asignación de horarios contempla la implementación de diversas restricciones las cuales son necesarias para encontrar resultados óptimos en la utilización de los recursos, ramos y profesores. Estas restricciones de dividen en 2 grupos. El primero o restricciones duras, son aquellas que se deben cumplir para definir un resultado como valido. El segundo o restricciones suaves, son aquellas que al no ser satisfechas disminuyen el grado de satisfacción de ese resultado.

1.1.- Restricciones Duras.


  • Un profesor puede dictar una sola clase en un momento o modulo determinado.

  • Un ramo solo puede ser dictado por un solo profesor.

  • No se pueden asignar mayor cantidad de tiempo que lo disponible de un profesor.

  • No se pueden asignar mayor cantidad de tiempo que aquella definida para ser dictada en un ramo.



1.2.- Restricciones Suaves.


  • Un ramo se debe asignar en módulos consecutivos definidos.

  • El horario de un curso debe tener asignado toda su malla.


1.3.- Situación Actual.


La asignación de horarios implementa las restricciones definidas anteriormente y se realiza de la siguiente forma:


  • Una vez al año cada profesor define sus periodos de tiempo disponibles así como las materias y niveles a dictar.

  • El grupo encargado de la asignación de horarios utiliza la información de las mallas de cada nivel y la información de los profesores y comienza a hacer combinatorias.

  • De acuerdo al resultado del proceso manual se define la contratación de profesores para cubrir aquellos espacios que no pudieron ser asignados.


Esta tarea se realiza en un periodo de tiempo de 3 semanas.

2.- Marco Teórico.

2.1.- Problema de asignación de horarios o TimeTabling


Dentro del área de optimización combinatoria, el problema de asignación de horarios pertenece a la categoría del problema general de asignación, donde el tiempo es un factor importante. Este es un problema de gran complejidad computacional, razón por la cual se tiene un gran interés por obtener métodos eficientes para su solución. El problema de la asignación o planificación horaria pertenece a la clase de problemas NP-completos, para la cual no se conoce un algoritmo de tiempo polinomial determinístico. Desde el punto de vista de la complejidad teórica, el problema de asignación horaria es NP-completo como un problema de decisión, es decir, decidir si una solución existe, y NP-duro como un problema de solución, es decir, construir una solución. Además, no se conocen líneas generales para desarrollar soluciones válidas.

2.1.1 NP-Completo


Un problema de decisión C es NP-completo si

  1. Es un problema NP y

  2. Todo problema de NP se puede transformar polinomialmente en él.

Una transformación polinomial de L en C es un algoritmo determinista que transforma instancias de l ∈ L en instancias de c ∈ C, tales que la respuesta a c es positiva si y solo si la respuesta a l lo es.

Como consecuencia de esta definición, de tenerse un algoritmo en P para C, se tendría una solución en P para todos los problemas de NP.

Esta definición fue propuesta por Stephen Cook en 1971. Al principio parecía sorprendente que existieran problemas NP-completos, pero Cook demostró (teorema de Cook) que el problema de satisfacibilidad booleana es NP-completo. Desde entonces se ha demostrado que miles de otros problemas pertenecen a esta clase, casi siempre por reducción a partir de otros problemas para los que ya se había demostrado su pertenencia a NP-completo; muchos de esos problemas aparecen en el libro de Garey and Johnson's de 1979 Computers and Intractability: A Guide to NP-completeness.

Un problema que satisface la segunda condición pero no la primera pertenece a la clase NP-duros.

Actualmente, todos los algoritmos conocidos para problemas NP-completos utilizan tiempo exponencial con respecto al tamaño de la entrada. Se desconoce si hay mejores algoritmos, por la cual, para resolver un problema NP-completo de tamaño arbitrario se utiliza uno de los siguientes enfoques:

  • Aproximación: Un algoritmo que rápidamente encuentra una solución no necesariamente óptima, pero dentro de un cierto rango de error. En algunos casos, encontrar una buena aproximación es suficiente para resolver el problema, pero no todos los problemas NP-completos tienen buenos algoritmos de aproximación.

  • Probabilístico: Un algoritmo probabilístico obtiene en promedio una buena solución al problema planteado, para una distribución de los datos de entrada dada.

  • Casos particulares: Cuando se reconocen casos particulares del problema para los cuales existen soluciones rápidas.

  • Métodos Heurísticos (Algoritmos Genéticos): Algoritmos que mejoran las posibles soluciones hasta encontrar una que posiblemente esté cerca del óptimo. Tampoco existe forma de garantizar la calidad de la respuesta.

2.2.- Algoritmos Heurísticos.

2.2.1.- Introducción.


La palabra "heurística" se deriva del verbo griego “heuriskein”, que significa "encontrar" o "descubrir" "reglas prácticas" utilizadas por los expertos para generar buenas soluciones sin tener que embarcarse en exhaustivas búsquedas. De acuerdo con ANSI/IEEE Std 100-1984, la heurística trata de aquellos métodos o algoritmos exploratorios para la resolución de problemas en los que las soluciones se descubren por la evaluación del progreso logrado en la búsqueda de un resultado final. En estos métodos el progreso se logra evaluando los resultados. Los algoritmos heurísticos ganan eficiencia en la utilización de tiempo de cómputo en desmedro de la precisión. No se aseguran soluciones óptimas sino solamente soluciones válidas, aproximadas.

Algunos problemas de optimización no pueden ser abordados por métodos exactos, ya sea, por su alto grado combinatorio o por la dificultad de generar un modelo basado en programación matemática que represente exactamente una situación real. Para situaciones de ésta naturaleza se han venido generando desde la década de los sesenta métodos conocidos como heurísticos1, capaces de encontrar soluciones de buena calidad pero en muchos casos aproximada a la solución óptima.

En el primer tiempo se generaron métodos orientados específicamente a la resolución de cada problema, gran parte de estos métodos fueron generados inspirándose en la resolución de problemas de fácil representación pero de muy difícil solución como lo son: el Problema del Vendedor Viajero, el problema de la mochila; el problema de los conjuntos de cobertura; etc. A partir de los años 80` se han generado una familia de métodos conocidos como meta-heurísticos que ahora tienen la capacidad de ser aplicables a problemas de diversa naturaleza. Es decir, una misma plantilla algorítmica puede ser utilizada para resolver problemas que provienen de diversos sectores.


Los métodos meta-heurísticos más conocidos son:

  • Búsqueda Tabú.

  • Simalated Anneling.

  • Redes Neuronales.

  • Métodos basados en la Trayectoria de Hormiga.

  • Métodos basados en la Inteligencia Artificial.

  • Algoritmos Genéticos.

El formato general del problema de optimización abordable mediante métodos heurísticos es el siguiente:

Minimizar f(x)

s.a. X 

La función f(x), es una función matemática que se desea minimizar y las soluciones posibles deben pertenecer a un espacio W, Los métodos de búsqueda heurística recorren el espacio W tratando de identificar la solución que genera el mejor valor para f(x), el menor en la caso de minimización o el mayor en el caso de maximización.

2.3.- Algoritmos Genéticos.

2.3.1.- Introducción.


Los Algoritmos Genéticos son métodos de búsqueda que recorren el espacio de posibilidades de W en forma paralela y aleatoria, obedecen a una analogía con la evolución de las especies Darwiniana. En cada etapa, se tiene una población de soluciones posibles para el problema a partir de ésta se genera una nueva población de soluciones mediante operadores que emulan la selección entre las especies del cruzamiento y la mutación. El método trabaja, generación tras generación, mejorando la calidad de la mejor solución de cada población hasta que algún criterio de detección se cumpla, por ejemplo que el esfuerzo computacional que se ha invertido en la solución del problema ha superado el límite predefinido.

El problema de asignación de horarios pude ser abordado por este tipo de algoritmo, pues este va mejorando, evolucionando los resultados obtenidos, acercando a la una solución mas optima en cada ciclo.

2.3.2.- Resolución de un Algoritmo Genético.

Consta de 5 etapas:


  1. Inicializar aleatoriamente una población de soluciones a un problema, representadas por una estructura de datos adecuada.

  2. Evaluar cada una de las soluciones, y asignarle una puntuación o fitness según lo bien que lo hayan hecho.

  3. Escoger de la población la parte que tenga una puntuación mayor.

  4. Mutar (cambiar) y entrecruzar (combinar) las diferentes soluciones de esa parte escogida, para reconstruir la población.



Figura 1: Cruce de soluciones



Figura 2: Mutación de soluciones

  1. Repetir un número determinado de veces, o hasta que se haya encontrado la solución deseada.

Índice de Ilustraciones


Figura 1: Cruce de soluciones…………………………. 9

Figura 2: Mutación de soluciones……………….......... 9

Bibliografía


Wikipedia

NP-completo

http://es.wikipedia.org/wiki/NP-completo
Wikipedia

Algoritmo Genético

http://es.wikipedia.org/wiki/Algoritmo_gen%C3%A9tico
Wikipedia

Heurística

http://es.wikipedia.org/wiki/Heur%C3%ADstico

Conclusiones


En la búsqueda de soluciones que satisfagan el problema de asignación de horarios, existen diversos tipos o enfoques, los cuales no garantizan que para un problema en particular se encuentre la más óptima. Dentro de estos se puede utilizar el Heurístico, este permite mediante la evaluación del progreso de la búsqueda encontrar aquellas más cercanas a la óptima. Uno de los algoritmos Heurísticos es el genético, que por medio de evolución de soluciones va mejorando el promedio de la población. Este es el más recomendable para la abordar el problema de la asignación de horarios.

1 Método popularizado matemático George Pólya

similar:

Universidad de ciencias de la informatica iconUniversidad ciencias de la informática

Universidad de ciencias de la informatica iconDirección Postal: E. T. S. Ingenieria Informatica, Campus de Teatinos,...

Universidad de ciencias de la informatica iconUniversidad de ciencias médicas (ucimed) escuela autonoma de ciencias...

Universidad de ciencias de la informatica iconUniversidad Peruana de ciencias aplicadas

Universidad de ciencias de la informatica iconFacultad de Ciencias, Universidad de Chile

Universidad de ciencias de la informatica iconUniversidad de ciencias empresariales y sociales

Universidad de ciencias de la informatica iconUniversidad metropolitana departamento de Ciencias Básicas Generales

Universidad de ciencias de la informatica iconUniversidad nacional de rosario facultad de Ciencias Bioquímicas y farmacéuticas

Universidad de ciencias de la informatica icon2014 Facultad de Ciencias Médicas Universidad Nacional de Rosario

Universidad de ciencias de la informatica iconUniversidad nacional de rosario facultad de Ciencias Bioquímicas y farmacéuticas




Todos los derechos reservados. Copyright © 2015
contactos
b.se-todo.com