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
- Algoritmos de balanceo de clases en problemas de clasificación binaria de conjuntos altamente desproporcionados(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2008-12-01) López Pineda, Arturo; Terashima Marín, Hugo; Valenzuela Rendón, Manuel; Conant Pablos, Santiago E.; División de Mecatrónica y Tecnologías de Información; Campus MonterreyEl aprendizaje automático es un tema de gran interés en la inteligencia artificial y sus aplicaciones, puesto que se trata de la generalización de comportamientos a partir de ejemplos conocidos. Este tema tiene una gran cantidad de aplicaciones como diagnósticos médicos, detección de fraudes, análisis de mercados, clasificación de secuencias, entre otros. El proceso de inducción seguido en estos problemas tiene que ver con el entrenamiento de un modelo lógico que represente un conjunto de datos conocidos. Los ejemplos históricos tienen distintos tamaños, proporciones y calidad en su integridad, dependiendo del tipo de información que se esté manejando. En particular, la rama de aprendizaje automático supervisado con el problema de clasificación de datos representa una muy frecuente línea de investigación por la gran utilidad que genera. En este contexto es que surge el problema del desbalance de clases, que implica que la información no se encuentre distribuida equitativamente entre todas las clases que la componen, por lo que se generan efectos no deseados en el proceso de clasificación. Esto significa que alguna de las clases del conjunto de datos tiene una cantidad mucho mayor al resto. Este trabajo considera el caso de conjuntos de datos que solamente tiene dos clases y una de ellas cuenta con una mayor cantidad de ejemplos que la otra, específicamente cuando están altamente desproporcionados. El interés principal es la aplicación de técnicas de balanceo de clases como método de preprocesamiento de datos en el proceso de entrenamiento, para mejorar, en la medida de lo posible, los resultados de clasificación. En este trabajo se aplica la técnica de muestreo de datos mediante la aplicación de dos enfoques: sobremuestreo y submuestreo. Para lograr este objetivo se establecen el límite máximo al cual se puede incrementar la clase minoritaria y el límite mínimo al cual se puede disminuir la clase mayoritaria. Con dichos límites se utilizan ambas técnicas de muestreo para mejorar la proporción de las clases. Para llevar a cabo el proceso de balanceo se utiliza la idea de generación de elementos artificiales basado en elementos más cercanos. La investigación demuestra que es factible aplicar algoritmos de balanceo de clases en el preprocesamiento de datos en la etapa de entrenamiento de los problemas de clasificación, generando mejores resultados sin alterar las características del proceso del método de aprendizaje utilizado, especialmente cuando se trata de algoritmos de balanceo de clases que implementan elementos sintéticos a partir de elementos cercanos, como SMOTE y NSU, para cada una de las clases, pero también se mejora significativamente al implementar métodos híbridos como HSR, que funcionan a través de todas las clases. También se deja claro que cada uno de los métodos de balanceo tiene diferentes grados de efectividad y su implementación se limita al tiempo de ejecución, complejidad de programación y características particulares de la información con la cual se trabaja. Finalmente, también se establece la efectividad de estos algoritmos a través de diversos clasificadores con diferentes enfoques y que son los principales métodos de clasificación implementados: árboles de decisión, clasificadores bayesiano y redes neuronales.
- 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.
- Hiperheur�?sticas para resolver el problema de empacado irregular de material en dos dimensiones(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2007-05-01) López Camacho,Eunice; LOPEZ CAMACHO, EUNICE; 271511; Terashima Marín, Hugo; Valenzuela Rendón, Manuel; Uresti Charre, Eduardo; ITESM-Campus Monterrey; Dieck Assad, GracianoEl problema de corte y empacado de materiales en dos dimensiones tiene gran relevancia práctica; por ejemplo, en la industria textil, de lámina metálica, madera, piel, plástico y papel [1]. Es por esto que ha sido ampliamente estudiado en los últimos a ̃nos, sobretodo en lo que se refiere al corte de piezas rectangulares. El corte de figuras irregulares es más complejo por lo que es posible abordarlo desde muy distintos enfoques. La presente investigación aplica al caso de los polígonos irregulares, un método para generar hiperheurísticas basado en un algoritmo genético (AG) que ha probado ser eficaz para el problema de corte de figuras rectangulares. Este método es llamado GHH-2D y fue descrito por Terashima-Mar ́ın [28] y Farías [14].Al generalizar el modelo GHH-2D a polígonos irregulares se incrementa la complejidad geométrica; por ejemplo: el cálculo de áreas, intersecciones, desplazamientos y rotaciones. El AG usa una representación de longitud variable que evoluciona combi-naciones de reglas del tipo condición-acción. Las condiciones de cada regla representan posibles estados de un problema mediante un vector de 8 números reales. Esta representación toma en cuenta el porcentaje de piezas que faltan por acomodar, la altura, el área y la rectangularidad de las piezas que faltan por acomodar. Gomes y Oliveira[19] definen rectangularidad con base en la diferencia entre el área de la pieza y el área del rectángulo que la contiene. Las acciones de cada regla indican heurísticas simples que encuentran una solución al problema de corte y empacado de material en dos dimensiones. La función primordial del AG es la de seleccionar diferentes estados del problema y asociar cada uno de ellos con alguna de las cuarenta acciones disponibles. Se realizaron experimentos donde el AG se evolución o durante 500 ciclos o generaciones. El mejor individuo del último ciclo constituye la hiperheurística generada la cual relaciona distintos estados del problema con heurísticas simples convenientes, de tal modo que al resolver una instancia utilizando las reglas de la hiperheurística se obtienen, en promedio, mejores resultados que empleando cualquiera de las heurísticas simples de manera exclusiva. El modelo desarrollado considera instancias con polígonos convexos de tres a ocho lados que deberán acomodarse en el menor número de objetos rectangulares idénticos. Para probar el modelo propuesto se generaron aleatoriamente 540 instancias, además de una instancia documentada en la literatura que incluye sólo figuras convexas. Se realizaron cuatro experimentos donde las instancias se dividen enconjuntos de entrenamiento y prueba. En cada experimento, se desarrollo una hiperheurística a partir de los problemas de entrenamiento y posteriormente se utilizó la hiperheurística generada para resolver las instancias de prueba. Se obtuvieron muy aceptables resultados, pues la hiperheurística desarrollada resolvió las instancias de prueba utilizando en promedio 1.38 objetos menos que el promedio de las 40 eucarísticas simples consideradas.
- Hiper-Heurística a través de sistemas de clasificadores para solucionar problemas de corte de material en dos dimensiones(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2004-01-12) Flores Álvarez, Edgardo Javier; Terashima Marín, Hugo; Martínez Alfaro, Horacio; Valenzuela Rendón, Manuel; ITESMEl tema de corte de material ha sido estudiado ampliamente en los últimos años debido a la gran cantidad de aplicaciones que puede tener, algunas de ellas son: empaque de materiales, carga de vehículos y contenedores limitados por la capacidad de carga, partición de problemas, calendarización de tareas en espacios limitados de tiempo, organización de localidades de memoria, organización de horarios, y corte de materiales en donde la materia prima puede tener una, dos o tres dimensiones, por ejemplo cable, madera, piel o papel. El problema de corte de materiales también ha sido de suma importancia en cuanto a la teoría, pues ha servido de base para muchas investigaciones en el análisis del comportamiento de los algoritmos de aproximación. Esto involucra, el determinar el radio de desempeño del peor caso, identificar el límite inferior en el mejor desempeño posible y el analizar el comportamiento del caso promedio de distintos algoritmos de optimización [19].
- Mecanismos adaptables sobre castigos en problemas de calendarización de actividades utilizando algoritmos genéticos(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2003-12-01) Huerta Amante, Daniel Ángel; Terashima Marín, Hugo; Martínez Alfaro, Horacio; Valenzuela Rendón, Manuel; Programa de Graduados en Electrónica. Computación, Información y Comunicaciones; División de Electrónica, Computación, Información y Comunicaciones; Campus MonterreyCuando un algoritmo genético es utilizado para resolver un problema que cuenta con restricciones, es necesario asignar un castigo a cada restricción y así, cuando un individuo viole una restricción, se le penaliza de acuerdo con el valor de castigo correspondiente. La aptitud de un individuo depende de dos factores: (1) El desempeño de la solución que representa el individuo ante el problema, el cual es dado por la función objetivo, y (2) la sumatoria de los castigos dado las restricciones que violó, calculado por la función de penalización. El algoritmo genético busca una solución que cumpla con la mayor cantidad de restricciones y que tenga mejor desempeño ante el problema. Tradicionalmente, los castigos permanecen estáticos a lo largo de las generaciones del algoritmo genético; en este trabajo se utilizan técnicas para variar estos castigos, cada cierto número de generaciones, utilizando una retroalimentación de generaciones anteriores; a estas técnicas se les conoce como técnicas de adaptación de castigos. Últimamente ha crecido el interés por la adaptación de castigos basándose en la premisa de que un algoritmo genético utiliza procesos dinámicos, por lo tanto, es natural que todos sus parámetros sean dinámicos. Se utilizó un problema de calendarización de actividades para realizar los experimentos; la principal característica de este problema es que existen diferentes formas de delimitar el dominio de una variable i.e. tipos de restricciones, por lo tanto, el grado de violación se mide de diferente manera. Otra característica de este tipo de problemas es que la función de penalización es, en sí, la función objetivo, i.e. una solución que no viole ninguna restricción es la óptima, aunque por las características y la naturaleza de este problema en especial, es poco común satisfacer todas las restricciones ya que algunas restricciones se empalman creando problemas imposibles; en estos casos la solución óptima varía dependiendo de la instancia del problema. Los resultados obtenidos a lo largo de esta investigación se inclinan por la adaptación de castigos. Se propone también una serie de pasos a seguir para introducir adaptabilidad al problema de calendarización, los cuales pueden ser utilizados sobre otros problemas que cuenten con restricciones
- Optimización del problema de empacado de material en 3-D mediante algoritmos genéticos(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2002-05-01) Uc Cetina, Víctor Emanuel de Atocha; UC CETINA, VICTOR EMANUEL DE ATOCHA; 292393; Terashima Marín, Hugo; Valenzuela Rendón, Manuel; González Velarde, José Luis; Programa de Graduados en Electrónica, Computación, Información y Comunicaciones; División de Graduados e Investigación; Campus MonterreyEste documento presenta la tesis para obtener el grado de Maestro en Ciencias en Sistemas Inteligentes. La tesis trata sobre la optimización de la carga de contenedores, lo cual se considera como un problema de empacado en tres dimensiones. El siguiente trabajo propone el uso de una técnica de la Inteligencia Artificial para encontrar soluciones eficientes al problema mencionado, mediante el uso de Algoritmos Genéticos (AGs), los cuales son algoritmos de búsqueda basados en la mecánica de la selección natural y en la genética natural, un método que ha sido aplicado exitosamente en diversos problemas de optimización. El problema de la carga de contenedores presenta dos grupos de datos básicos, por una parte, existe una lista de objetos grandes consistente de uno o más contenedores, y por otra parte, una lista de objetos más pequeños que deben ser empacados dentro de los contenedores. Aparte de ciertos objetivos específicos y restricciones dadas, el principal aspecto de la carga de contenedores concierne a la combinación geométrica de objetos pequeños formando patrones de empacado que pueden ser asignados a los contenedores de la lista, dependiendo de sus formas y dimensiones. Como resultado de esta investigación, se diseñó y se implemento un AG para optimización en este dominio. El AG fue denominado Algoritmo Genético para Empacado (AGE) y fue probado con problemas de un contenedor, usando tres funciones objetivo distintas y dos operadores de cruce diferentes. Además, se realizaron experimentos con problemas de empacado de más de un contenedor. Finalmente, se utilizó el AGE para resolver dos problemas reales de carga de contenedores de una compañía de transportación, obteniendo resultados satisfactorios.
- Generación Automática de Programas Mediante Programación Genética(Instituto Tecnológico y de Estudios Superiores de Monterrey, 01/06/2000) Lucas González, Sócrates A.; Terashima Marín, Hugo; Cantú Ortiz, Francisco Javier; Valenzuela Rendón, Manuel; ITESMLa programación automática es un área de interés tanto para la ingeniería de software como para la Inteligencia Artificial (IA). La programación genética es una técnica de la IA desarrollada por John R. Koza, inspirada en algoritmos genéticos, que provee la forma de evolucionar programas mediante operaciones genéticas similares a las naturales, como el cruce y la mutación, con la finalidad de obtener programas que resuelvan un problema. Una variante de programación genética implementada por Helmut H�rner utiliza gramáticas del tipo Backus-Naur-Form (BNF) como material genético. Los métodos usuales que siguen algunos trabajos sobre programación automática son métodos formales que involucran conceptos de lógica; en esta tesis se muestra un método diferente al utilizar la programación genética con gramática BNF como una opción para la programación automática. Esto se consiguió mediante la integración de un sistema generador de programas, basado en la variante de programación genética de H�rner, que utiliza un conjunto de subrutinas definidas en una gramática BNF, así como de un procedimiento de ejecución de programas y de procedimientos para su evaluación. La integración del sistema generador tiene el objetivo de elaborar programas que tratan de satisfacer a una especificación inicial, en la cual se indica lo que se espera que realice un programa. Los ejemplos tratados por el sistema generador pertenecen al Algebra Lineal. Los primeros dos ejemplos fueron encontrar un programa para la multiplicación de un vector por un escalar y encontrar otro programa para la bÚsqueda de un nÚmero dentro de un arreglo, en ambos ejemplos los resultados fueron favorables para el sistema generador. Los ejemplos siguientes fueron encontrar programas para el producto punto de dos vectores y para la adición de matrices, ambos representaron mayor dificultad para el sistema generador; sin embargo, se obtuvieron resultados favorables al encontrar los programas para cada ejemplo; por Último, los ejemplos para los cuales el generador no encontró programas tan favorables fueron la obtención de programas para la corrección de códigos y la obtención de programas que efectuasen la inversa de una matriz, tales resultados se debieron a especificaciones rígidas que poco ayudaron a la conducción hacia programas efectivos, produciendo una inadecuada evolución de los programas.