sistema de apoyo a la gestión de horarios para el colegio piamarta
DESCRIPTION
Sistema de Apoyo a la Gestión de horarios para el colegio PiamartaTRANSCRIPT
Introduccin
UNIVERSIDAD DE CIENCIAS DE LA INFORMATICA
INGENIERIA DE EJECUCION EN INFORMATICA
SEMINARIO
Sistema de Apoyo a la Gestin de horarios
para el colegio Piamarta
ROFESOR GUIA: Jos Miguel SantibezALUMNO : Claudia Cornejo.lvaro Aguilar
Juan Bello
Daro Daz
Milton Gonzlez
Eduardo Llanquileo
[email protected]@[email protected]@[email protected]
: 02-12-06
ndice.
1UNIVERSIDAD DE CIENCIAS DE LA INFORMATICA
2ndice.
3Introduccin.
31.- Definicin del problema.
31.1.- Restricciones Duras.
41.2.- Restricciones Suaves.
41.3.- Situacin Actual.
52.- Marco Terico.
52.1.- Problema de asignacin de horarios o TimeTabling
62.1.1 NP-Completo
82.2.- Algoritmos Heursticos.
82.2.1.- Introduccin.
102.3.- Algoritmos Genticos.
102.3.1.- Introduccin.
112.3.2.- Resolucin de un Algoritmo Gentico.
11Consta de 5 etapas:
12ndice de Ilustraciones
13Bibliografa
14Conclusiones
Introduccin.En toda institucin acadmica es importante la asignacin de horarios, esto se debe realizar al comienzo de cada periodo, sea ao o semestres, y lo ms rpido 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 solucin de este problema utilizando para ello algoritmos heursticos.
1.- Definicin del problema.
El desarrollo de la asignacin de horarios contempla la implementacin de diversas restricciones las cuales son necesarias para encontrar resultados ptimos en la utilizacin 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 satisfaccin 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 mdulos consecutivos definidos.
El horario de un curso debe tener asignado toda su malla.1.3.- Situacin Actual.La asignacin de horarios implementa las restricciones definidas anteriormente y se realiza de la siguiente forma: Una vez al ao cada profesor define sus periodos de tiempo disponibles as como las materias y niveles a dictar.
El grupo encargado de la asignacin de horarios utiliza la informacin de las mallas de cada nivel y la informacin de los profesores y comienza a hacer combinatorias.
De acuerdo al resultado del proceso manual se define la contratacin 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 Terico.2.1.- Problema de asignacin de horarios o TimeTabling
Dentro del rea de optimizacin combinatoria, el problema de asignacin de horarios pertenece a la categora del problema general de asignacin, donde el tiempo es un factor importante. Este es un problema de gran complejidad computacional, razn por la cual se tiene un gran inters por obtener mtodos eficientes para su solucin. El problema de la asignacin o planificacin horaria pertenece a la clase de problemas NP-completos, para la cual no se conoce un algoritmo de tiempo polinomial determinstico. Desde el punto de vista de la complejidad terica, el problema de asignacin horaria es NP-completo como un problema de decisin, es decir, decidir si una solucin existe, y NP-duro como un problema de solucin, es decir, construir una solucin. Adems, no se conocen lneas generales para desarrollar soluciones vlidas. 2.1.1 NP-Completo
Un problema de decisin C es NP-completo si
1. Es un problema NP y
2. Todo problema de NP se puede transformar polinomialmente en l.
Una transformacin 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 definicin, de tenerse un algoritmo en P para C, se tendra una solucin en P para todos los problemas de NP.
Esta definicin fue propuesta por Stephen Cook en 1971. Al principio pareca 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 reduccin a partir de otros problemas para los que ya se haba 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 condicin 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 tamao de la entrada. Se desconoce si hay mejores algoritmos, por la cual, para resolver un problema NP-completo de tamao arbitrario se utiliza uno de los siguientes enfoques:
Aproximacin: Un algoritmo que rpidamente encuentra una solucin no necesariamente ptima, pero dentro de un cierto rango de error. En algunos casos, encontrar una buena aproximacin es suficiente para resolver el problema, pero no todos los problemas NP-completos tienen buenos algoritmos de aproximacin.
Probabilstico: Un algoritmo probabilstico obtiene en promedio una buena solucin al problema planteado, para una distribucin de los datos de entrada dada.
Casos particulares: Cuando se reconocen casos particulares del problema para los cuales existen soluciones rpidas.
Mtodos Heursticos (Algoritmos Genticos): 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 Heursticos.2.2.1.- Introduccin.
La palabra "heurstica" se deriva del verbo griego heuriskein, que significa "encontrar" o "descubrir" "reglas prcticas" utilizadas por los expertos para generar buenas soluciones sin tener que embarcarse en exhaustivas bsquedas. De acuerdo con ANSI/IEEE Std 100-1984, la heurstica trata de aquellos mtodos o algoritmos exploratorios para la resolucin de problemas en los que las soluciones se descubren por la evaluacin del progreso logrado en la bsqueda de un resultado final. En estos mtodos el progreso se logra evaluando los resultados. Los algoritmos heursticos ganan eficiencia en la utilizacin de tiempo de cmputo en desmedro de la precisin. No se aseguran soluciones ptimas sino solamente soluciones vlidas, aproximadas.Algunos problemas de optimizacin no pueden ser abordados por mtodos exactos, ya sea, por su alto grado combinatorio o por la dificultad de generar un modelo basado en programacin matemtica que represente exactamente una situacin real. Para situaciones de sta naturaleza se han venido generando desde la dcada de los sesenta mtodos conocidos como heursticos, capaces de encontrar soluciones de buena calidad pero en muchos casos aproximada a la solucin ptima. En el primer tiempo se generaron mtodos orientados especficamente a la resolucin de cada problema, gran parte de estos mtodos fueron generados inspirndose en la resolucin de problemas de fcil representacin pero de muy difcil solucin 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 aos 80` se han generado una familia de mtodos conocidos como meta-heursticos que ahora tienen la capacidad de ser aplicables a problemas de diversa naturaleza. Es decir, una misma plantilla algortmica puede ser utilizada para resolver problemas que provienen de diversos sectores.
Los mtodos meta-heursticos ms conocidos son:
Bsqueda Tab.
Simalated Anneling.
Redes Neuronales.
Mtodos basados en la Trayectoria de Hormiga.
Mtodos basados en la Inteligencia Artificial.
Algoritmos Genticos.
El formato general del problema de optimizacin abordable mediante mtodos heursticos es el siguiente:
Minimizar f(x)
s.a. X ((La funcin f(x), es una funcin matemtica que se desea minimizar y las soluciones posibles deben pertenecer a un espacio W, Los mtodos de bsqueda heurstica recorren el espacio W tratando de identificar la solucin que genera el mejor valor para f(x), el menor en la caso de minimizacin o el mayor en el caso de maximizacin.2.3.- Algoritmos Genticos.
2.3.1.- Introduccin.Los Algoritmos Genticos son mtodos de bsqueda que recorren el espacio de posibilidades de W en forma paralela y aleatoria, obedecen a una analoga con la evolucin de las especies Darwiniana. En cada etapa, se tiene una poblacin de soluciones posibles para el problema a partir de sta se genera una nueva poblacin de soluciones mediante operadores que emulan la seleccin entre las especies del cruzamiento y la mutacin. El mtodo trabaja, generacin tras generacin, mejorando la calidad de la mejor solucin de cada poblacin hasta que algn criterio de deteccin se cumpla, por ejemplo que el esfuerzo computacional que se ha invertido en la solucin del problema ha superado el lmite predefinido.
El problema de asignacin de horarios pude ser abordado por este tipo de algoritmo, pues este va mejorando, evolucionando los resultados obtenidos, acercando a la una solucin mas optima en cada ciclo.
2.3.2.- Resolucin de un Algoritmo Gentico.
Consta de 5 etapas:
1. Inicializar aleatoriamente una poblacin de soluciones a un problema, representadas por una estructura de datos adecuada.
2. Evaluar cada una de las soluciones, y asignarle una puntuacin o fitness segn lo bien que lo hayan hecho.
3. Escoger de la poblacin la parte que tenga una puntuacin mayor.
4. Mutar (cambiar) y entrecruzar (combinar) las diferentes soluciones de esa parte escogida, para reconstruir la poblacin.
Figura 1: Cruce de soluciones
Figura 2: Mutacin de soluciones5. Repetir un nmero determinado de veces, o hasta que se haya encontrado la solucin deseada.
ndice de IlustracionesFigura 1: Cruce de soluciones.9Figura 2: Mutacin de soluciones..........9
Bibliografa
Wikipedia
NP-completo
http://es.wikipedia.org/wiki/NP-completoWikipedia
Algoritmo Gentico
http://es.wikipedia.org/wiki/Algoritmo_gen%C3%A9ticoWikipedia
Heurstica
http://es.wikipedia.org/wiki/Heur%C3%ADsticoConclusiones
En la bsqueda de soluciones que satisfagan el problema de asignacin de horarios, existen diversos tipos o enfoques, los cuales no garantizan que para un problema en particular se encuentre la ms ptima. Dentro de estos se puede utilizar el Heurstico, este permite mediante la evaluacin del progreso de la bsqueda encontrar aquellas ms cercanas a la ptima. Uno de los algoritmos Heursticos es el gentico, que por medio de evolucin de soluciones va mejorando el promedio de la poblacin. Este es el ms recomendable para la abordar el problema de la asignacin de horarios. Mtodo popularizado matemtico George Plya
PAGE
_1220882174.xlsHoja1
346392252362Padres
346362252392Hijos
_1224857574.xlsHoja1
Seleccin aleatoria
Opciones0123456789
Antes346362
Seleccin aleatoria
Despues349362