Catálogo de publicaciones

Tesis (Magister en Análisis y Procesamiento de Imágenes)-- Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2015.

Los problemas de diseño topológico de redes de información caen dentro de la categoría de problemas de optimización combinatoria. En muchos casos, cuando el tamaño de la instancia del problema crece, los tiempos de resolución del mismo a través de técnicas exhaustivas pueden resultar inadmisibles. Por esta razón las heurísticas en general y la computación evolutiva en particular, son una alternativa válida para atacar este tipo de problemas. Este trabajo se centra en la resolución de problemas de diseño óptimo de redes confiables utilizando técnicas evolutivas. A continuación se muestra un esquema del desarrollo del mismo. En el capítulo 2 se realiza una revisión de las metodologías existentes aplicadas para resolver problemas de diseño de redes. La complejidad matemática asociada a la resolución de la obtención de la topología óptima se discute en el Capítulo 3. El abordaje del diseño de una red de comunicaciones cuando la función objetivo es el costo de implementación y la restricción recae sobre la confiabilidad del sistema, está plasmado en este capitulo, ubicando al problema dentro de una clase de problemas de optimización combinatoria. Este diseño se utiliza como problema test para analizar el comportamiento de un algoritmo estocástico. En el capítulo 4 se realiza una revisión de las técnicas proporcionadas por la computación evolutiva para resolver problemas de optimización. El mismo contiene los conceptos básicos relacionados con la aplicación de Algoritmos Evolutivos (AE), basados en AG, para resolver problemas de optimización. En el capítulo 5 se describe el diseño de un algoritmo evolutivo con conocimiento específico del problema para encontrar una topología de mínimo costo sujeto a restricciones de confiabilidad entre todas las terminales de la red. El Capítulo 6 contiene ejemplos de diseño de redes resueltos a través de las metodologías propuestas en esta tesis. Las conclusiones y futuras líneas de investigación se presentan en el Capítulo 7.

El mundo de los negocios actuales está sufriendo muchos cambios, ya no basta con generar reportes y realizar una correcta planificación. Se deben incluir herramientas de optimización para crear soluciones de negocios adaptativas como por ejemplo para límites de créditos, precios y descuentos, y scheduling. Esto redundará en beneficios para la empresa ya sea en la disponibilidad de tecnología de avanzada como también en la disminución de los costos asociados a la toma de decisiones óptimas, también incrementará la capacidad para aprender de experiencias previas y para adaptar a cambios en el mercado. En estos últimos años se han realizados muchos estudios de investigación respecto de la aplicación de las técnicas de computación evolutiva para la solución de problemas de scheduling. La principal ventaja de las técnicas evolutivas es su habilidad para proveer buenas soluciones a problemas extremadamente complejos usando tiempos razonables. En este trabajo se hace un revisión de las clases y características de algoritmos evolutivos así como también algunas mejoras introducidas a los mismos. Entre estas últimas se pueden incluir múltiple crossover, multiplicidad de padres y prevención de incesto. Asimismo se presentan algunas variantes de algoritmos evolutivos planteados para la resolución de un problema particular de scheduling como lo es el problema de job shop scheduling.

El presente trabajo realiza un análisis de los algoritmos genéticos que se diseñan para resolver problemas de optimización, que involucran no sólo funciones objetivo continuas y derivables sino aplicados a funciones con puntos de discontinuidad o de no derivabilidad. Asimismo se aplican a problemas de secuenciación en donde el espacio de soluciones está determinado por un conjunto de secuencias una de las cuales es la óptima, presente en muchos problemas de optimización en redes. En este tipo de problemas están presente las permutaciones y su representación intrínseca ha constituido un reto para los algoritmos genéticos. Se presenta un análisis de diferentes representaciones de los cromosomas que pueden ser utilizados en la resolución de los distintos problemas y del funcionamiento de los AG en los distintos casos, representaciones y parámetros que los gobiernan. Se seleccionan algunos ejemplos de aplicaciones de algoritmos genéticos en redes en los cuales se distinguen diferentes tipos de problemas y de aportes en los AG en cada ejemplo. Se hace hincapié en los operadores genéticos seleccionando para cada caso los más apropiados. Posteriormente se encara el diseño e implementación de un AG, utilizando el problema del viajante para un testeo preliminar de los AG y finalmente se aplica este diseño en uno de los ejemplos seleccionados. Conjuntamente se implementan algunas técnicas clásicas para contrastar los resultados. Finalmente se realiza una interpretación de los resultados justificando la exploración de estas técnicas como una alternativa válida en problemas de optimización de redes de datos, analizando las ventajas y desventajas de estos métodos frente a técnicas clásicas.

Este trabajo de Tesis tiene por objetivo general dar soluciones a diferentes problemas relacionados con la detección automática de señales sísmicas. Dichos problemas incluyen el picado de los tiempos de los primeros arribos en exploración sísmica, la detección y determinación de los tiempos de llegada de fases de terremotos en registros de estaciones sismológicas, y la declaración y picado de los arribos de eventos en registros de microsismicidad. Para ello, se estudian diversos atributos sísmicos convencionales y no convencionales diseñados para realzar la llegada de las señales de interés por sobre el ruido de fondo de los datos. A partir de estos atributos se proponen nuevos algoritmos, estrategias y métodos para detectar las señales buscadas de forma eficiente, automática y precisa. En particular, se analiza la dimensión fractal de la traza sísmica, se aclaran algunas suposiciones teóricas e hipótesis que deben realizarse al considerar una traza sísmica como una curva fractal, y se evalúan distintas estrategias para estimar su dimensión. A partir de ejemplos con datos sintéticos y reales, se prueba que la dimensión fractal obtenida a través del método del variograma es un atributo que evidencia claramente la transición entre el ruido y la señal con ruido. Se desarrollan también tres nuevos métodos para detectar los tiempos de los primeros arribos en registros sísmicos complejos de forma automática. Los atributos en los que se basan estos nuevos algoritmos están dados por un cociente de energías, por la entropía de la traza sísmica, y por su dimensión fractal, aprovechando en este último caso los resultados del análisis previo. Los cambios detectados en los atributos son realzados mediante la aplicación de un filtro de suavizado que preserva los saltos bruscos. Estos algoritmos determinan los primeros arribos analizando las trazas sísmicas individualmente. Se introduce luego un novedoso proceso de corrección de picados erróneos que considera simultáneamente todo el conjunto de las trazas pertenecientes a un mismo registro de disparo común teniendo en cuenta la alineación aproximada de los primeros arribos dada por el modelo de refracción. Este procedimiento permite además descartar las trazas malas de forma automática. Los métodos propuestos son luego mejorados y aplicados a un gran volumen de datos reales provistos por la industria que presentan distintos desafíos y dificultades. Para estudiar la detección de señales en sismología, se realiza un análisis comparativo entre ocho métodos V de detección automática de fases de terremotos. El conjunto de ocho métodos analizado está formado por la adaptación de los tres algoritmos desarrollados para picar primeros arribos, por tres métodos tradicionales, y por dos métodos obtenidos a partir de modificaciones a dos de los métodos tradicionales. El estudio es llevado a cabo utilizando registros obtenidos en la Estación Sismológica de La Plata (LPA). Como resultado, se realiza una valoración relativa de los ocho métodos de detección en la que algunos de ellos se destacan por sobre otros, y se obtienen así herramientas computacionales para realizar la detección automática de fases de terremotos en estaciones sismológicas. Por último, se seleccionan tres de estos ocho métodos y a partir de ellos se genera una nueva metodología para detectar microsismos de forma automática que consta de dos pasos. En el primer paso se detectan y determinan todos los tiempos de aquellos eventos que representan un potencial arribo de un microsismo, traza por traza en todo el registro. En el segundo paso, se utiliza un criterio que analiza todo el registro en su conjunto para declarar la presencia de microsismos. Como resultado se obtienen el número de microsismos declarados, un indicador de confianza asociado a cada uno de ellos, y los tiempos de llegada para aquellas trazas en las que el evento es detectado.

Las ecuaciones que gobiernan los fenómenos en electrofisiología son ecuaciones de reacción-difusión anisótropas con un término reactivo altamente no lineal definido por un conjunto de ecuaciones diferenciales ordinarias rígidas. Estas características del sistema implica la necesidad de mallas espacio-temporales muy finas de manera de capturar el frente de propagación evitando la aparición de oscilaciones espúreas en el frente de onda. En esta tesis doctoral se han desarrollado algoritmos eficientes para la resolución de este tipo de problema en el entorno de programación paralela,con aplicaciones al cálculo de grandes prestaciones. Entre los algoritmos desarrollados se encuentran un esquema de diferencias finitas compacto de alto orden que tiene en cuenta la anisotropía del tejido e incorpora un esquema de paso temporal adaptativo. Este permite una solución precisa del potencial y el flujo, trabajar con mallas más gruesas que aquellas requeridas por los métodos de diferencias finitas de segundo orden o elementos finitos lineales. Esta característica permite reducir el tiempo de cálculo y los requerimientos de memoria para modelos celulares complejos. También se ha desarrollado un esquema de elementos finitos inmersos que permite definir mallas jerárquicas estáticamente reducibles lográndolas mantener el coste computacional de invertir el sistema de ecuaciones en un mínimo, permitiendo incrementar la resolución espacial con la que se resuelve el problema. Al igual que en el caso anterior se ha acoplados un algoritmo de integración temporal con paso adaptativo que permiten una mejora adicional en el rendimiento del código. Con este método se ha obtenido una escalabilidad superior que para elementos lineales, con una aceleración efectiva de hasta cuatro veces con respecto a estos elementos para resolver un problema con igual n´umero de grados de libertad. Como aplicaciones del código desarrollado se llevó a cabo un estudio de la influencia de la isquemia aguda regional sobre preparaciones tridimensionales de miocardio de cobaya. Aquí se investigó la influencia del tamaño y localización de la zona isquémica en los patrones de reentradas y la vulnerabilidad del tejido. Además se estudio la heterogeneidad transmural en un corazón normal. En una geometría realista de corazón se introdujeron células epicardiales, tipo M y endocardiales, considerando estos tipos de células se propusieron tres distribuciones de las mismas a través del miocardio y se vio como estas influyen en las derivaciones precordiales del ECG. El estudio de isquemia aguda regional se extendió a un corazón humano con heterogeneidad transmural para lo cual se caracterizaron los modelos de corriente iónica humana a condiciones de isquemia, adaptando el mismo a este tipo de patología. Con el modelo adaptado se estudiaron los patrones de reentradas y la influencia de una isquemia aguda regional en las derivaciones precordiales de un ECG

El problema de Localización y Ruteo de Vehículos con Capacidades (CLRP) es la combinación de dos problemas muy estudiados del área de la Investigación Operativa: el problema de localización de depósitos con capacidades (CFLP) y el problema de ruteo de vehículos con múltiples depósitos (MDVRP). Dado un conjunto de posibles localizaciones se busca determinar cuáles utilizar para satisfacer las demandas de un conjunto de clientes y programar las rutas que los visitan. Se busca minimizar los costos de apertura de depósitos, de utilización de vehículos y de ruteo satisfaciendo restricciones de capacidad tanto en los vehículos como en los depósitos. En este trabajo se presenta una nueva versión del problema denominada Localización y Ruteo de Vehículos con Capacidades y Premios (PC-CLRP) que busca generalizar el problema CLRP permitiendo la posibilidad de que los clientes sean o no visitados. Los clientes atendidos otorgan un beneficio y la maximización de la suma de los beneficios forma parte del objetivo del nuevo problema. Se proponen en este trabajo algoritmos para el problema PC-CLRP. En primer lugar se introduce un algoritmo metaheurístico para resolverlo basado en el método de optimización por Colonia de Hormigas. Se implementa una metaheurística de 3 colonias de hormigas que colaboran construyendo las distintas etapas de una solución PC-CLRP: localización, clusterizado y ruteo. Posteriormente, se presentan modelos de programación lineal entera basadas en modelos de flujo de 2 índices y 3 índices. Se analizan distintas familias de desigualdades válidas utilizadas para CLRP y se proponen nuevas versiones de las mismas para el problema PC-CLRP. Además, se definen nuevas desigualdades válidas y cortes de optimalidad junto a sus correspondientes algoritmos de separación. Por último, se implementa un algoritmo Branch&Cut utilizando uno de los modelos de programación lineal entera propuestos. Se reportan los resultados obtenidos por ambos algoritmos para el problema PC-CLRP sobre un conjunto de instancias especialmente dise~nadas para el nuevo problema. Se compara además los resultados frente a los reportados en otros trabajos sobre el problema CLRP obteniendo resultados competitivos. Palabras claves: problema de localización y ruteo de vehículos, programación lineal entera, branch and cut, colonia de hormigas, optimización combinatoria, recolección de premios.

El método más comunmente usado para estimar los coeficientes de una regresión lineal es el de mínimos cuadrados. Este método que es óptimo en el caso de errores distribuídos normalmente, es muy sensible a la presencia de outliers. Para remediar ese problema se han desarrollado otros métodos de estimación llamados métodos robustos, los cuales se ven poco afectados por la presencia de datos atípicos. Una medida de la robustez de un estimador es su punto de ruptura. Entre los estimadores de regresión robustos se encuentran los LTS, LMS y los S estimadores. Estos estimadores son equivariantes por transformaciones afines, de regresión, y de escala y además tiene un alto punto de ruptura. El inconveniente que presenta su calculo es que requiere muchas horas de computadora. Rouseeuw y Van Driessen desarrollaron un algoritmo, llamado Fast -LTS, que mejora la velocidad de cálculo del estimador de mínimos cuadrados podados. El objetivo de este trabajo es desarrollar un nuevo algoritmo, análogo al Fast-LTS, para computar S estimadores. Del mismo modo que el algoritmo desarrollado por Rouseeuw, este nuevo algoritmo está basado en el mejoramiento local de los nuevos estimadores iniciales. Esto permite una significativa reducción del número de candidatos requeridos para obtener una buena aproximación de la solución óptima. Se ha realizado un estudio de simulación que ha mostrado que los S estimadores calculados con el algoritmo Fast-S, son comparativamente mejores a los estimadores LTS calculados con el algoritmo Fast-LTS. Algunas de las ventajas del nuevo algoritmo son: 1) Menor porcentaje de muestras afectadas por los datos atípicos. 2) Menor error cuadrático medio. 3) Menor tiempo de cómputo.

Los problemas de dominación forman un área de investigación en crecimiento, debido a la cantidad de aplicaciones que pueden modelar, entre las cuales podemos nombrar redes sociales, sistemas distribuidos, redes biológicas, problemas de localización de instalaciones, etc. En esta tesis estudiamos los siguientes problemas de dominación (i) el conjunto dominante mínimo, (ii) dominación romana, (iii) dominación eficiente por vértices, (iv) dominación eficiente por aristas (también conocida como matching inducido dominante), (v) dominación perfecta por vértices (vi) dominación perfecta por aristas, y (vii) subgrafo cordal máximo inducido sin vertices propiamente dominados (también conocido como eliminación de vértices para formar clusters). Para el problema (i) determinamos su complejidad para clases de grafos donde se prohiben subgrafos inducidos con a lo sumo cuatro vértices. Estudiamos los problemas (i) y (ii) para varias subclases de grafos P5-free, dando algoritmos eficientes, robustos y simples en ambos casos. Algoritmos de complejidad lineal para grafos arco-circulares fueron presentados para los problemas (iv), (v), (vi) usando algoritmos existentes para el problema (iii). Damos tres algoritmos de tiempo exponencial para resolver el problema (iv) en grafos generales. Además, para el problema (iv), presentamos algoritmos de complejidad O(n) restringidos a grafos cordales, dualmente-cordales, biconvexos, y claw-free. Estudiamos cuatro variantes del problema (vii) y presentamos algoritmos eficientes para todos ellos cuando nos restringimos a grafos de intervalos propios, grafos de intervalos, grafos arco-circulares, grafos de permutación, y grafos trapezoide. Por otro lado, probamos que las cuatro variantes son NP-Dificil para grafos bipartitos. Finalmente, mostramos que dos variantes son NP-Dificil para grafos split, mientras que las otras dos variantes se pueden resolver en tiempo polinomial.

El posicionamiento de un objeto sobre la corteza terrestre durante años ha sido una tarea de innumerables investigaciones y adelantos tecnológicos. Desde los mercantes que usaban los cuerpos celestiales para ubicarse en su navegación por los océanos, hasta los sistemas autónomos que, portando un micro-dispositivo embebido, resuelven en cuestión de segundos la posición actual sobre la faz de la tierra para poder realizar su navegación. Muchas son las aplicaciones que se favorecen de esta tecnología y en general la mayoría de ellas se pueden llevar a cabo sin inconvenientes en cuanto a la precisión requerida. Algunas áreas específicas como la agricultura de precisión, la aeronavegación, la navegación marítima, los desarrollos aeroespaciales, necesitan una mayor precisión para realizar sus tareas. Existen muchas investigaciones y desarrollos de empresas, gobiernos e instituciones que afrontan a diario este desafío. Muchos de ellos con resultados exitosos y comprobables. Por otro lado, también es razonable pensar que estos desarrollos no alcanzan a la totalidad de los usuarios que los necesitan. En algunos casos las razones son económicas y en otros la región de residencia no se ve beneficiada por el servicio. Adquirir la infraestructura para montar un sistema de posicionamiento preciso, como el DGPS por ejemplo, puede requerir la inversión de millones de dólares. En otros casos puede implicar el abono de un servicio mensual. Aún así, y más allá de contar con la capacidad económica, en ciertas regiones no es posible acceder a las señales de corrección por características del terreno o por estar fuera del área de cobertura. Por ello, la necesidad de desarrollar soluciones tecnológicas para estas regiones es un desafío recurrente. Este proyecto trata de reducir la brecha existente entre estos desarrollos y los usuarios finales que necesitan realizar tareas con mayor precisión posicional que la entregada originalmente por un sistema global de navegación satelital (GNSS) como es el NAVSTAR-GPS. La propuesta está basada en el desarrollo de un sistema de posicionamiento relativo de precisión dotado de receptores de bajo costo. La contribución está dada por el desarrollo de una metodología y técnicas para el tratamiento de información que proviene de los receptores.