Ciencias Exactas y Ciencias de la Salud
Permanent URI for this collectionhttps://hdl.handle.net/11285/551039
Pertenecen a esta colección Tesis y Trabajos de grado de las Maestrías correspondientes a las Escuelas de Ingeniería y Ciencias así como a Medicina y Ciencias de la Salud.
Browse
Search Results
- Hipocorísticas mediante un enfoque neuro-evolutivo para el ordenamiento dinámico de variables en problemas de satisfacción de restricciones(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2008-12-01) Fuentes Rosado, Jorge Iván; FUENTES ROSADO, JORGE IVAN; 218157; Terashima Marín, Hugo; Acevedo Mascarúa, Joaquín; Valenzuela Rendón, Manuel; Conant Pablos, Santiago E.; Tecnológico de Monterrey, Campus Monterrey; División de Graduados en Mecatrónica y Tecnologías de Información; Campus MonterreyMuchos de los problemas de las Ciencias de la Computación y de la Inteligencia Artificial (IA) pueden ser caracterizados como problemas de Satisfacción de Restricciones. Un CSP, por sus siglas en inglés, está compuesto por un conjunto de variables, un conjunto dominio de posibles valores y una serie de restricciones entre variables a ser satisfechas. Encontrar una solución para un problema de satisfacción de restricciones consiste en encontrar una asignación consistente para todo el conjunto de variables de tal manera que satisfaga todas las restricciones. Los algoritmos de solución más conocidos son Backtracking, Foward Checking y otros híbridos los cuales están basados en la teoría de algoritmos de búsqueda en árboles. La solución de estos problemas cuando son considerados difíciles por métodos tradicionales se vuelve muy lento y tedioso puesto que el espacio de búsqueda es muy grande, es por ello que se han realizado muchas investigaciones para la optimización de la forma de solucionar estos problemas. Además, existen instancias de CSPs que son particularmente difíciles de resolver, ya que requieren una elevada cantidad de verificaciones de consistencia para encontrar una solución o demostrar que no existe alguna. El ordenamiento de las variables juega un papel de suma importancia en la búsqueda de la solución. Un buen ordenamiento de variables al momento de buscar una solución representa una menor complejidad en la búsqueda. Existen dos enfoques para el ordenamiento de variables. El primer enfoque es conocido como en ordenamiento estático el cual consiste en definir el orden en la cual las variables estarían instanciadas antes de empezar a solucionar el problema. El otro enfoque es conocido como ordenamiento dinámico el cual consiste en determinar la variable a instanciar en tiempo de solución. Para esto surgieron algunas heurísticas que ayudan en este proceso, de las cuales podemos nombrar Fail First, Rho, Kappa, entre otras, pero ninguna de ellas ha demostrado ser eficiente para todas las instancias. En este enfoque la heurística elegida es aplicada en todos los niveles del árbol sin importar las modificaciones del problema. Recientemente se ha empezado a trabajar con un enfoque basado en hiperheurísticas, el cual, dada las características del estado del problema determina que heurística debe ser aplicada para elegir la variable a ser asignada, en este modelo en cada nivel del árbol la heurística aplicada puede variar respecto a la anterior. Este modelo se compone de una etapa de entrenamiento y una de prueba. La fase de entrenamiento consiste en utilizar un algoritmo genético para evolucionar una población de redes neuronales. Las redes neuronales son entrenadas por medio del algoritmo de retroprogramación del error y después evaluadas con diferentes instancias de CSPs. La red neuronal tiene como entrada el estado del problema y como salida la heurística sencilla a aplicar. La intención de utilizar diferentes instancias de CSPs durante la etapa de entrenamiento es desarrollar procesos de solución generales que puedan ser aplicados para resolver un gran número de instancias, mías que encontrar buenas soluciones para instancias específicas. La idea general es la siguiente, dado el estado del CSP P es utilizado para alimentar la red neuronal de la cual se obtendrá como salida la heurística sencilla a aplicar. Una vez aplicada la heurística el CSP P cambia a un CSP P', el cual es una versión actualizada del anterior. El procedimiento se repite hasta resolver el problema completamente. Al terminar el entrenamiento de la población se toma el mejor individuo y es utilizado para solucionar tanto los problemas utilizados para su entrenamiento como problemas nuevos. Lo anterior para hacer comparaciones con los resultados de la aplicación individual de las heurísticas simples. Los resultados demuestran que es factible la creación de una hiperheurística bajo este modelo de solución puesto que las hiperheurísticas generadas se comportaron como la mejor heurística sencilla aplicada y con esto mejor que el promedio que ellas. La mejor heurística simple puede ser diferente en cada instancia del problema.
- Hiperheurísticas mediante un enfoque evolutivo para el ordenamiento dinámico de variables en problemas de satisfacción de restricciones(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2008-05-01) Ortiz Bayliss, José Carlos; Ortiz Bayliss, José Carlos; 212577; Terashima Marín, Hugo; Acevedo Mascarúa, Joaquín; Uresti Charre, Eduardo; Valenzuela Rendón, Manuel; ITESM-Campus Monterrey; División de Graduados en Mecatrónica y Tecnologías de InformaciónLos problemas de satisfacción de restricciones (CSPs por sus siglas en inglés) representan un tema de gran interés en el área de sistemas inteligentes y sus aplicaciones incluyen planeación, visión, distribución de recursos, etc. Un CSP está compuesto por un conjunto de variables, un dominio de valores para cada variable y un conjunto de restricciones definidas sobre los valores que pueden tomar las variables simultáneamente. Asociado a los CSPs se encuentra el problema del ordenamiento de variables y de valores. Un buen ordenamiento de variables al momento de buscar una solución representa una menor complejidad en la búsqueda. Existen una gran cantidad de heurísticas que se han diseñado para seleccionar dinámicamente la siguiente variable a instanciar, pero ninguna de ellas ha demostrado ser eficiente para todas las instancias. Además, existen instancias de CSPs que son particularmente difíciles de resolver, ya que requieren una elevada cantidad de verificaciones de consistencia para encontrar una solución o demostrar que no existe alguna. Este trabajo considera el problema del ordenamiento dinámico de variables en CSPs utilizando hiperheurísticas producidas mediante un modelo evolutivo. Este modelo se compone de una etapa de entrenamiento y una de prueba. La etapa de entrenamiento se realiza con ayuda de un algoritmo genético con cromosomas de longitud variable. Durante la etapa de entrenamiento, el AG se encarga de evolucionar una población de individuos que representan las hiperheurísticas mediante la solución de un conjunto de entrenamiento formado por diferentes instancias de CSPs difíciles. La intención de utilizar diferentes instancias de CSPs durante la etapa de entrenamiento es desarrollar procesos de solución generales que puedan ser aplicados para resolver un gran número de instancias, más que encontrar buenas soluciones para instancias específicas. Estos individuos de la población representan grupos de reglas del tipo condición-acción, en donde la condición simboliza un estado específico del problema y la acción es una heurística de ordenamiento de variables. En términos generales, el procedimiento que se lleva a cabo es el siguiente: dado un estado P del problema, encontrar la regla más cercana i y aplicar la heurística asociada a dicha regla. Al llevar a cabo esta acción, el problema se transforma en P1 . El procedimiento se repite hasta resolver el problema completamente. La función primordial del AG durante la etapa de entrenamiento es seleccionar diferentes estados del problema y asociar cada uno de ellos con alguna de las heurísticas de bajo nivel para el ordenamiento dinámico de variables. Una misma heurística puede asociarse a varios estados o a ninguno. Al finalizar la etapa de entrenamiento, el mejor individuo de la población es utilizado para resolver el conjunto de problemas de prueba, el cual está formados por diferentes instancias de CSPs de las que fueron utilizadas durante el proceso de entrenamiento. Las hiperheurísticas generadas mediante el modelo presentado en este trabajo se comparan con los resultados obtenidos mediante la aplicación por separado de las heurísticas de bajo nivel para los problemas de entrenamiento y prueba. La investigación demuestra que es posible generar hiperheurísticas con eficiencia competitiva para una gran cantidad de instancias de CSPs mediante el modelo evolutivo presentado. Los resultados también dejan en claro que no existe una heurística capaz por sí sola de resolver eficientemente todas las instancias de CSPs. Sin embargo, el modelo evolutivo fue capaz de generar una hiperheurística general competitiva, la cual logró resultados muy parecidos a los producidos por el mejor resultado de las heurísticas simples y una reducción significativa al compararse contra el número de verificaciones de consistencia requerido por el resultado promedio de las heurísticas simples.
- Optimización de Corte de Material en Dos Dimensiones Mediante Hiperheurísticas Construidas con un Algoritmo Genético(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2004-01-12) Morán Saavedra, Armando; Dr. Hugo Terashima Marín; Dr. Horacio Martínez Alfaro; Dr. Manuel Valenzuela Rendón; ITESMEn la presente tesis se plantea explorar y aprovechar un enfoque reciente de bÚsqueda llamado Hiperheurística para resolver Problemas de Optimización de Corte de Material en Dos Dimensiones. Las hiperheurísticas son una combinación de heurísticas que en conjunto son capaces de encontrar mejores resultados que cada heurística simple. Actualmente varios de los enfoques para atacar este tipo de problemas de Optimización utilizan Algoritmos Genéticos los cuales se conforman de una codificación directa del problema en el cromosoma, sin embargo, a pesar de que los resultados obtenidos mediante estas técnicas no son ineficientes, no han gozado del suficiente éxito ya que requieren un alto grado de conocimiento específico del dominio y dicha representación genera que el espacio de bÚsqueda y el tiempo requerido para ejecutarlos crezca considerablemente conforme la entrada de los problemas crece. Una posible respuesta a estos inconvenientes es la codificación indirecta del problema, es decir, que los individuos no representen una solución al problema sino un proceso de solución. El presente trabajo propone utilizar una hiperheurística para tal fin de modo que se utilice un algoritmo genético para la construcción de una hiperheurística que solucione el problema. Existen métodos similares que ya han tenido éxito resolviendo otros problemas de Optimización como la Asignación de Horarios para Exámenes, Problemas de Acomodo de Cajas en Depósitos, entre otros. Tales resultados son un aliciente para la implantación de este nuevo enfoque que intenta eludir los inconvenientes que presenta la codificación directa y con esto poder evaluar su eficiencia para resolver una clase de problemas de tipo NP-completos que cuenta con mÚltiples aplicaciones industriales.