Tesis Magíster

Permanent URI for this collection

https://repositorio.udec.cl/handle/11594/192

Browse

Now showing 1 - 20 of 591

A debiasing framework for deep learning applied to the morphological classification of galaxies.
(Universidad de Concepción., 2023) Medina Rosales, Esteban; Cabrera Vives, Guillermo, profesor guía
In order to train deep learning models, usually a large amount of correctly annotated data is needed. Depending on the data domain, the task of correctly annotating data can prove to be difficult, as in many cases the ground truth of the data is not obtainable. This is true for numerous problems within the astronomy domain, one of these being the morphological classification of galaxies. The aforementioned means that astronomers are forced to rely on an estimate of the ground truth, often generated by human annotators. The problem with this is that human generated labels have been shown to contain biases related to the quality of the data being labeled, such as image resolution. This type of bias is a consequence of the quality of the data, that is, it is independent of the annotators, meaning that even datasets annotated by experts can be affected by this type of bias. In this work, we show that deep learning models trained on biased data learn the bias contained in the data, transferring the bias to its predictions. We also propose a framework to train deep learning models, that allows us to obtain unbiased models even when training on biased data. We test our framework by training a classification model on images of morphologically classified galaxies from Galaxy Zoo 2 and show that we are able to diminish the bias in the data.
A model for local scour during flood waves = Un modelo para socavación local durante crecidas.
(Universidad de Concepción., 2016) Castillo Beroiza, Cristian Fernando; Link Lazo, Óscar Eduardo; supervisor de grado
The local scour during flood waves is the main cause of bridge collapses all over the world so its study and modeling is of great interest. However, the scour caused by flood waves has been scarcely investigated. The reason is attributed to the complexity in the accurate control of the discharge at laboratory flumes in order to reproduce hydrographs representative of river flows, and to the complexity in representing the scour processes with a model of the time-dependent scour during flood waves. With the aim to improve the estimation of the scour during flood waves the objective of this work is to study the impact of the shape, duration and peak discharge of flood hydrograph on the maximum scour depth and rate under clear-water condition. For the achievement of the main objective, the local scour during flood waves was modeled and analyzed through experiments that were conducted in a novel installation able to reproduce any hydrograph with high precision in the laboratory flume. Experimental results were used to test different time-dependent scour formulas including a new mathematical model (DFW) based on the hypothesis that there is a unique relationship between the dimensionless, effective flow work W* and the relative scour depth Z*. Model comparison confirms the reliability and better performance of the dimensionless, effective flow work based, DFW model under both, steady and unsteady hydraulic conditions, corroborating the hypothesis on which it relies. Analyses highlight the impact of different hydrographs on local scour demonstrating the strong control of the hydrograph shape on the temporal evolution of scour depth and scour rate, although final scour after a flood only depends on the total effective flow work exerted by the hydrograph on the sediment bed. Hysteresis between the flow discharge and the scour rate is reported and explained. Flow acceleration is shown to play a secondary role in scouring.
A simulation-optimization approach for the fire stations location and vehicle assignment problem: A case study in the Concepcion Province, Chile.
(Universidad de Concepción., 2020) Rodríguez Cartes, Sebastián A.; De la Fuente, Rodrigo; supervisor de grado
Bomberos son una parte importante los servicios de emergencia al ser responsables de atender varias emergencias urbanas. Para atender estas de mejor forma, ellos deben planificar una adecuada localización de sus compañías y asignación de vehículos. Para apoyar esta toma de decisiones, proponemos un método iterativo de simulación optimización que basado en parámetros de utilización previamente calculados actualiza la localización óptima de vehículos y compañías usando un modelo de programación lineal. Llamamos a este modelo el Facility Location and Equipment Emplacement Technique with Expected Coverage (FLEET-EXC), que considera múltiples tipos de emergencias y vehículos, y una política de despacho que depende del tipo de región. Luego, modelo de simulación es ejecutado con las localizaciones y asignaciones obtenidas para actualizar los parámetros de utilización. Adicionalmente, el modelo de simulación usa un método de muestreo espacio-temporal que acopla un Kernel Density Estimator para el componente espacial y un proceso de arribo non-Stationary non-Renewal basado en un modelo de Markov-Mixture of Erlangs of Common Order para generar los tiempos entre-arribos para el componente temporal. Ademas, un conjunto de incertidumbre para los parámetros de utilización es obtenido de la simulación; por lo tanto, proponemos un modelo de optimizan robusta para extender la formulación previa. Los principales resultados muestran que el método de muestreo propuesto logra una mejor representación del proceso de arribo de emergencias que aquellos generalmente usados en la literatura. Por otra parte, el procedimiento de simulación-optimización que usa el modelo de FLEET-EXC tiene un mejor desempeño que el modelo discrete FLEET, resultando en hasta 2% de mayor cobertura. Ademas, el modelo robusto también tuvo un mejor desempeño que el modelo discreto FLEET, pero tiene un desempeño variable al compararse con el FLEET-EXC. Sin embargo, el modelo robusto logra el menor tiempo de respuesta promedio cuando solo se consideran las emergencias bao el percentil 60.
Aceleración hardware para inferencia en redes neuronales convolucionales.
(Universidad de Concepción., 2021) Pérez Cerdeira, Ignacio Jesús; Figueroa Toro, Miguel Ernesto; supervisor de grado; Carvajal Barrera, Gonzalo Andrés; supervisor de grado
Gracias a su alta precisión para clasificar objetos en imágenes, las redes neuronales con volucionales (CNN) son una herramienta muy relevante en la visión computacional. Este tipo de red neuronal utiliza capas convolucionales para extraer características de las imágenes y las clasifica por medio de capas de clasificación. Típicamente, el proceso de reconocimiento, llamado inferencia, es aplicado en unidades centrales de procesamiento (CPU) o unidades de procesamiento gráfico (GPU), pero debido al alto paralelismo de estas últimas, las GPUs muestran un mejor desempeño. Aun así, su alto consumo de potencia dificulta la implementación de estas plataformas en dispositivos móviles. Por esto, una alternativa para solucionar este problema es diseñar arquitecturas hardware en sistemas dedicados, como arreglos de compuertas programables (FPGA), que permiten reducir el consumo de potencia y acelerar la inferencia. Debido a esto, en este trabajo diseñamos una arquitectura heterogénea para realizar la inferencia de la CNN MobileNet V2 sobre hardware dedicado. Esta arquitectura utiliza una CPU y memoria embebida para controlar y almacenar datos del proceso, y un acelerador hardware sintetizado en la lógica programable de un FPGA para disminuir los tiempos de inferencia. Para reducir la cantidad de operaciones y datos en la FPGA, utilizamos técnicas de loop tiling, pruning y cuantización. Implementamos la arquitectura sobre la plataforma Xilinx Zynq Ultrascale+, utilizando la CPU ARM Cortex-A53 como controlador, una memoria DDR4 de 2GB para almacenar datos y la FPGA XCZU7EV para sintetizar cuatro elementos de procesamiento que permiten la inferencia en paralelo. Nuestra implementación puede inferir una imagen de la base de datos ImageNet de 224×224 píxeles en 220ms, utilizando 532 bloques de RAM (BRAM), 24 RAMs de UltraScale (URAM) y 340 procesadores digitales de señales (DSP) del FPGA, y consumiendo 7.34W de potencia. Comparada con una implementación software sobre una GPU y CPU, nuestro diseño es 10.18 veces más lento que la GPU y tiene un frame-rate similar a la CPU, pero consume 29.23 y 12.93 veces menos potencia que estos dispositivos respectivamente
Acelerador hardware para búsqueda de motivos emergentes en streams de secuencias de ADN
(Universidad de Concepción., 2018) Saavedra Mondaca, Antonio Sebastián; Hernández Rivas, Cecilia; supervisora de grado
El descubrimiento de motivos en cadenas de ADN se define como la búsqueda de secuencias cortas de elementos compartidos en un conjunto largo de bases de nucleótidos que poseen una función biológica común. El descubrimiento de motivos entre los sitios de unión de los factores de transcripción, debido a la importancia de su función regulatoria en la expresión genética, resulta un problema de relevancia biológica. Este tipo de problemas presenta una alta complejidad computacional, especialmente debido a las dificultad de trabajar con bases de datos masivas. Las soluciones existentes en este tipo de problema se enfocan, por lo general, a plataformas en grandes clusters de alto costo, elevados tiempos de ejecución y consumo de potencia. En este trabajo se desarrolla un acelerador hardware reconfigurable para la búsqueda de motivos emergentes en secuencias de ADN. Los motivos emergentes se definen como aquellos que cumplen requisitos establecidos de frecuencia dentro de la secuencias analizadas. Su búsqueda representa un problema biológicamente relevante que presenta altos requisitos de memoria y costos computacionales. La plataforma se propone en base a algoritmos capaces de resolver el problema de la búsqueda de elementos más frecuentes dentro de un stream de datos. Estos algoritmos utilizan estructuras de datos conocidas como sketches para realizar una aproximación al proceso de conteo para determinar los elementos más frecuentes. A diferencia de un conteo tradicional, la utilización de sketches permite resolver, a través de procesos probabilísticos, en espacio sublineal, la estimación de la frecuencia de cada elemento del stream. Se implementaron en software los algoritmos CountSketch, Countmin, y Countmin-CU. Utilizando bases de datos biológicas públicas, se analizaron las dimensiones requeridas para operar con buena precisión y sensibilidad. El algoritmo Countmin-CU es capaz de encontrar los motivos emergentes de largos entre 10 y 20 utilizando arreglos de 65 mil contadores. El conteo tradicional requeriría sobre 100 mil millones. Se diseñó una arquitectura hardware dedicada que permite utilizar un FPGA como acelerador en un contexto de computación heterogénea. El algoritmo de streaming logra un balance adecuado entre el cómputo y los accesos requeridos a memoria permitiendo explotar el paralelismo fino de este tipo de plataforma. De esta manera, la lógica programable del FPGA con un diseño especializado nos permite reducir los costos de tiempo y el consumo de potencia de la solución. Este modelo de computación acelerada por hardware, con el FPGA nos permite trabajando con un reloj de 300MHz y consumiendo 3 Watts de potencia, nos permite alcanzar una aceleración de hasta 290 veces sobre la versión en software.
Acelerador hardware para búsqueda de motivos emergentes en streams de secuencias de ADN.
(Universidad de Concepción., 2018) Saavedra Moncada, Antonio Sebastián; Figueroa Toro, Miguel Ernesto; supervisor de grado
El descubrimiento de motivos en cadenas de ADN se define como la búsqueda de secuencias cortas de elementos compartidos en un conjunto largo de bases de nucleótidos que poseen una función biológica común. El descubrimiento de motivos entre los sitios de unión de los factores de transcripción, debido a la importancia de su función regulatoria en la expresión genética, resulta un problema de relevancia biológica. Este tipo de problemas presenta una alta complejidad computacional, especialmente debido a las dificultad de trabajar con bases de datos masivas. Las soluciones existentes en este tipo de problema se enfocan, por lo general, a plataformas en grandes clusters de alto costo, elevados tiempos de ejecución y consumo de potencia. En este trabajo se desarrolla un acelerador hardware reconfigurable para la búsqueda de motivos emergentes en secuencias de ADN. Los motivos emergentes se definen como aquellos que cumplen requisitos establecidos de frecuencia dentro de la secuencias analizadas. Su búsqueda representa un problema biológicamente relevante que presenta altos requisitos de memoria y costos computacionales. La plataforma se propone en base a algoritmos capaces de resolver el problema de la búsqueda de elementos más frecuentes dentro de un stream de datos. Estos algoritmos utilizan estructuras de datos conocidas como sketches para realizar una aproximación al proceso de conteo para determinar los elementos más frecuentes. A diferencia de un conteo tradicional, la utilización de sketches permite resolver, a través de procesos probabilísticos, en espacio sublineal, la estimación de la frecuencia de cada elemento del stream. Se implementaron en software los algoritmos CountSketch, Countmin, y Countmin-CU. Utilizando bases de datos biológicas públicas, se analizaron las dimensiones requeridas para operar con buena precisión y sensibilidad. El algoritmo Countmin-CU es capaz de encontrar los motivos emergentes de largos entre 10 y 20 utilizando arreglos de 65 mil contadores. El conteo tradicional requeriría sobre 100 mil millones. Se diseñó una arquitectura hardware dedicada que permite utilizar un FPGA como acelerador en un contexto de computación heterogénea. El algoritmo de streaming logra un balance adecuado entre el cómputo y los accesos requeridos a memoria permitiendo explotar el paralelismo fino de este tipo de plataforma. De esta manera, la lógica programable del FPGA con un diseño especializado nos permite reducir los costos de tiempo y el consumo de potencia de la solución. Este modelo de computación acelerada por hardware, con el FPGA nos permite trabajando con un reloj de 300MHz y consumiendo 3 Watts de potencia, nos permite alcanzar una aceleración de hasta 290 veces sobre la versión en software.
Acelerador hardware para la estimación de entropía empírica mediante sketches.
(Universidad de Concepción., 2021) Paulo Pedro, Ubisse; Figueroa, Miguel; supervisor de grado; Hernández, Cecilia; supervisora de grado
Los enfoques basados en entropía para la detección de anomalías son atractivos, ya que propor cionan información más detallada que el análisis de volumen de tráfico tradicional. Sin embargo, el cálculo de la entropía empírica exacta en un gran conjunto de datos puede ser costoso en uti lización de memoria, debido a que su cómputo requiere almacenar el número de ocurrencias de todos los elementos distintos observados en el flujo. Un alto uso de memoria reduce el desem peño de los aceleradores hardware, que son necesarios para estimar la entropía en redes de alta velocidad. Una solución práctica es, entonces, relajar la restricción de un cálculo exacto. En este trabajo, presentamos dos métodos probabilísticos basados en sketches para aproximar la entropía empírica de un gran conjunto de datos en procesamiento en tiempo real, con uso de espacio de memoria sublineal. Los sketches son estructuras de datos que utilizan espacio sublineal donde el uso de memoria crece de forma sublineal con los datos de entrada. Cuando el tamaño de la memoria utilizada es menor que la entrada, la pérdida de precisión es inevi table y conduce a resultados probabilísticos. Sin embargo, los algoritmos basados en sketches proporcionan aproximaciones con resultados de alta calidad. El primer enfoque consiste en es timar la entropía empírica de un flujo de datos, considerando los elementos top-K, o sea los K elementos más frecuentes. El segundo y principal enfoque de nuestro trabajo, consiste en aproximar la estimación de la entropía empírica no solo tomando la parte del flujo de datos que corresponde a los K elementos más frecuentes, sino también tomando la parte del flujo de datos que corresponde a los elementos menos frecuentes. Los dos enfoques han sido implementados en un sistema en chip (System on chip, SoC) Zynq UltraScale de Xilinx. Para el primer enfoque, los resultados experimentales del diseño de hardwa re en una FPGA Xilinx Zynq UltraScale+MPSoC ZCU102 (Field Programmable Gate Array), muestran que el sistema funciona a una frecuencia de reloj de 354 MHz y puede funcionar con una velocidad de red de 181 Gigabits por segundo (Gbps). Para el segundo y principal enfoque, los resultados experimentales en una arquitectura de propósito especial implementada en un FPGA ZCU104 de ultraescala Xilinx Zynq, muestran que el sistema alcanza un rendimiento de un paquete por ciclo a 400 MHz, lo que le permite operar a velocidades de red de hasta 204 Gbps.
Actualización de un controlador de modelo interno, basado en la identificación dinámica en lazo cerrado, para un intercambiador de calor
(Universidad de Concepción., 2016) Steel Heldt, Brian Andrew Brian Andrew; Melo Lagos, Diógenes; Canales Rebolledo, Edgardo
El control eficiente de los procesos químicos es fundamental para las industrias permitiendo operar los procesos de forma segura (cuidando el medio ambiente y la salud de los operadores) y maximizar utilidades (obteniendo un producto de calidad al mismo tiempo que se optimizan los consumos de suministros y reactivos). Para poder controlar un proceso de forma correcta se deben conocer las características estáticas (ganancia) y dinámicas (constantes de tiempo y retardo) del mismo. Este trabajo de tesis propone utilizar un método de identificación en lazo cerrado para obtener los parámetros que caracterizan las funciones de transferencia de, a diferencia de trabajos anteriores, procesos con controladores de modelo interno. Este modo de control reconoce la referencia, impidiendo identificar la ganancia de manera directa (la razón de amplitud a frecuencia angular cero es indeterminada). Por ello se ideó un algoritmo basado en numerosas simulaciones de sistemas de primer orden, el que se probó en procesos con parámetros y tiempos de muestreos aleatorios, demostrando ser exacto cuando la razón entre el tiempo de muestreo y la constante de tiempo del proceso estaba entre 2.5 y 8.5. Cada ensayo experimental consiste en realizar un cambio escalón en la referencia del controlador. Luego se registra la respuesta del sistema en lazo cerrado bajo la acción del controlador de modelo interno, la que se somete a un tratamiento matemático que involucra técnicas numéricas, permitiendo obtener la respuesta de frecuencia del sistema en lazo abierto. Un análisis de frecuencia de esta respuesta conduce a las características del sistema, ajustándole por ejemplo un modelo de primer orden con retardo. El modelo de la planta utilizado en el controlador es actualizado con los parámetros identificados. El funcionamiento del algoritmo del método de identificación se puso a prueba, primero, simulando el lazo de control de temperatura de un intercambiador de calor, para lo cual se empleó el software SIMULINK™. Para el sistema se usaron los parámetros identificados por Steel (2013). Para el modelo se tomaron como referencia los mismos parámetros, pero con cierto porcentaje de error. Posteriormente, se experimentó sobre lazos de control instalados en un intercambiador de calor que tiene cuatro pasadas por los tubos y una por la carcasa. Por los tubos circula agua fría y a través la carcasa vapor de agua. El método probó ser muy efectivo en los sistemas simulados. La calidad de los datos facilitó el trabajo. El mayor error en un parámetro fue del 2.61%. Los modelos iniciales que presentaban mayor error se mejoraron considerablemente. En los ensayos en el intercambiador de calor el ruido de los datos dificultó el trabajo del algoritmo, lo que no fue impedimento para que se ajustasen los modelos de primer orden con retardo, con los que se mejoró la sintonía de los lazos de control. Todas las mejoras en los modelos se reflejaron en las respuestas, disminuyendo sobrepasos, oscilaciones y el tiempo que demoraban en alcanzar el estado estacionario. Aunque un proceso real puede ser de orden superior, el ajuste demostró ser suficiente para el funcionamiento del controlador de modelo interno disponible en el software de control RSLogix 5000™ (éste solo ofrece un modelo de primer orden con retardo).
Adaptación de dominio profunda sobre imágenes astronómicas.
(Universidad de Concepción., 2022) Bolívar Severino, César Andrés; Cabrera Vives, Guillermo Felipe; supervisor de grado
Los modelos de Aprendizaje Profundo pueden verse afectados negativamente cuando ocurre un cambio de distribución entre el conjunto de datos de entrenamiento y el conjunto de datos de prueba. Esta baja en desempeño puede acrecentarse aún más cuando se tienen pocos datos etiquetados, pero puede mitigarse empleando técnicas de Apatación de Dominio. En este trabajo, se estudia la clasificación binaria de alertas astronómicas en “real” versus “bogus”, utilizando cuatro conjuntos de datos diferentes: Asteroid Terrestrial-impact Alert System (ATLAS), Dark Energy Survey (DES), High-cadence Transient Survey (HiTS) y Zwicky Transient Facility (ZTF). Se utiliza un modelo de clasificación profundo con un entrenamiento fine tuning y un modelo de adaptación de dominio llamado Minimax Entropy (MME), y se estudia el comportamiento de dichos modelos en diferentes escenarios donde el conjunto de entrenamiento difiere al de prueba, y donde se utiliza pocos elementos etiquetados por clase de los conjuntos de datos objetivo para el entrenamiento. Se muestra que el domain shift está presente en los conjuntos de datos, y que ambos modelos son capaces de mejorar la exactitud de un modelo base, incluso con apenas 1 elemento etiquetado por clase para algunos de los escenarios propuestos.
Adquisición de equipamiento médico basada en AHP caso de estudio de Servicio de Salud Maule (SSM)
(Universidad de Concepción., 2016) Muñoz Tiznado, Paulina de los Ángeles; Salazar Hornig, Eduardo Javier; profesor guía
En este trabajo se presenta la aplicación de una metodología de adquisición de equipos médicos basada en AHP (Proceso Analítico Jerárquico), donde en conjunto con el indicador financiero VAC (Valor Actual de Costos) es posible llegar a un resultado que busca la elección de un Equipo de Rx Digital Pórtatil acorde a las necesidades en conjunto con la optimización de los recursos. Esta metodología toma datos de una adquisición real del Servicio de Salud Maule (SSM), en la cual por medio de otra metodología se llega al ranking de equipos. Se catastran ambos resultados, se comparan y se concluye que la herramienta AHP sirve como apoyo para poder llegar a hacer una elección acorde a las necesidades específicas en las cuales se quiere adquirir el equipo médico, ya que es menos generalizada y el modelo se construye para cada caso y situación en particular, evidenciándose los beneficios cuando el equipo es puesto en marcha.
Adversarial variational domain adaptation for semi-supervised image classification.
(Universidad de Concepción., 2019) Pérez Carrasco, Manuel Ignacio; Cabrera Vives, Guillermo Felipe; supervisor de grado
For success fully training deep neural networks, we usually need a large amount of annotated data in order to avoid the overfitting and being able to generalize to new data. In most of real cases, getting labels is difficult and time consuming. In this work we address the problem of transferring knowledge obtained from a vast annotated source domain to a low labeled or unlabeled target domain, reducing the efforts to get labels on the target. We propose Adversarial Variational Domain Adaptation (AVDA), a semi-supervised domain adaptation method based on deep variational embedded representations. The idea of AVDA is to use a mixture of Gaussian distribution as a prior for the latent space, mapping samples that belong to the same class into the same Gaussian component, independently of the domain membership, using approximate inference. We use adversarial methods to align source and target distributions in latent space for each class independently. We tested our model using the digits dataset, which contains images of handwritten digits and images of number of houses. We empirically show that on a semi-supervised scenario, our approach improved the state of the art for digits dataset from 0.3 to 1.5% of accuracy using only 1 and 5 labels per class. Also, we tested out model using images of galaxies from the Cosmic Assembly Near-infrared Deep Extragalactic Legacy Survey (CANDELS, [23]) as source and the Cluster Lensing and Supernova Survey with Hubble (CLASH, [62]) as target. We empirically show that using few labels our model presents a significant speed-up in terms of the increase in accuracy, and the model keeps improving as more labels we add.
Ajuste de reglas de secuenciamiento de tareas en ambiente dinámico mediante optimización estocástica: Caso un recurso.
(Universidad de Concepción., 2004) Ahumada Ojeda, Jonhson Hernán; Cepeda Jünemann, Manuel; supervisor de grado
En esta investigación se aborda el problema de scheduling de una máquina considerando un ambiente dinámico, por lo tanto, el conjunto de tareas a ejecutar no es conocido a priori, sino que éstas llegan en paralelo con la evolución del tiempo, alterando la planificación actual y obligando a una reprogramación en tiempo real. Este problema será abordado mediante optimización estocástica, en particular la optimización del valor esperado de una medida de desempeño utilizando como herramienta la simulación, esto se conoce como optimización estocástica por simulación. El método de optimización estocástica aplicado al problema en estudio es el método del gradiente descendente utilizando perturbaciones finitas para estimar el gradiente. Se propone un índice de prioridad combinado que relaciona dos reglas de prioridad simple, de esta manera el problema original es transformado en uno de optimización paramétrica donde la función corresponde al valor esperado de la medida de desempeño. Los resultados obtenidos a través de los índices de prioridad combinado, son comparados con los resultados obtenidos al realizar el secuenciamiento de tareas por medio de las reglas de prioridad simple, obteniendo reducciones significativas en las medidas de desempeño. Para estimar el gradiente se implementaron dos criterios de término, el primero considera un número fijo de iteraciones y el segundo considera un criterio dinámico, sin embargo ambos criterios reportan idénticos resultados, pero el tiempo computacional empleado por el segundo criterio de término es significativamente menor.
Un algoritmo de descomposición de tareas para el reconocimiento de patrones de texto = A task decomposition algorithm for string matching.
(Universidad de Concepción., 2014) Elejalde Sierra, Erick; Ferres, Leo; supervisor de grado
Previous attempts to parallelize string matching algorithms have focused on data decomposition; that is, splitting the text on the number of available cores. In this work, we demonstrate that it is possible to use task decomposition efficiently, using a multiprocessor model. We introduce the Task Decomposition String Matching algorithm, a new algorithm based on bit parallelism and finite automata theory. We also present a producer/consumer strategy which may be applied to the traditional algorithms as an alternative way to parallelize them. We run experiments that compare both our approaches against traditional algorithms (such as Boyer-Moore, KMP and Bitap) by varying the length of the pattern and the properties of alphabets, two critical variables that affect performance in string matching. The Domain Decomposition strategy proved to be very efficient for this problem. Although task decomposition is asymptotically optimal, it is practically affected by cache contingencies.
Algoritmo de segmentación semiautomática de procesos neuronales en imágenes de microscopía de alta resolución.
(Universidad de Concepción., 2014) Rodríguez Gatica, Juan Eduardo; Guevara Álvez, Pamela Beatriz; supervisora de grado
El siguiente documento muestra las etapas realizadas para el diseño, desarrollo e implementación de un algoritmo a ser usado como herramienta de software que pretende resolver a lo menos en parte un problema fundamental de la neurociencia moderna, la clasificación de todas y cada una de las neuronas presentes en el tejido nervioso. Para esto se utilizaron imágenes de alta resolución obtenidas por medio de microscopia electrónica (EM: Electron Microscopy), en donde se presentan los procesos neuronales a segmentar. El marco teórico demuestra que aun cuando hay herramientas disponibles para el procesamiento de imágenes de microscopía electrónica, éstas dependen directamente de la interacción con el usuario, y por el momento ninguna de ellas permite el proceso completo de segmentación de procesos neuronales en forma automática. Por esta razón, actualmente la segmentación de este tipo de imágenes es una tarea tediosa, que consume mucho tiempo y es susceptible a errores. En este trabajo se desarrolló un algoritmo en MATLAB que permite la manipulación de las imágenes que son obtenidas por medio de EM, realizando el alineamiento de la secuencia de imágenes, así como todo el pre-procesamiento necesario antes de la segmentación, sin la necesidad de utilizar programas externos. El algoritmo permite seleccionar, en la primera imagen de la secuencia, los procesos neuronales de interés, para luego segmentar las neuronas seleccionadas por el usuario en forma automática. Finalmente el algoritmo etiqueta automáticamente los cuerpos segmentados, reconociendo todas las posibles ramificaciones como parte de un mismo cuerpo. Luego despliega los resultados de la segmentación en un mapa de conexiones 3D, además genera índices con el volumen y la cantidad de ramificaciones para cada uno de los cuerpos segmentados, los cuales son potencialmente útiles para el estudio de patologías, comparando muestras de tejidos. Se evaluó el buen funcionamiento del algoritmo mediante un set de validación, en donde los cuerpos neuronales han sido segmentados manualmente, el cual es el método más aceptado en la actualidad. La validación arrojó un error medio de un 3%. Se utilizaron 3 set de datos más, todos con diferentes características de resolución, cantidad de imágenes, pigmentación etc., con la finalidad de evaluar la robustez del algoritmo, frente a imágenes con características diferentes. Además, se evaluó una versión del algoritmo en Python, la cual mostró mejores tiempos de segmentación, resaltando la potencialidad del algoritmo. Para mostrar la versatilidad y potencialidad del algoritmo, 5 set de datos obtenidos con técnicas de fluorescencia fueron evaluados, al segmentar correctamente estos datos.
Algoritmo exacto para el problema de ruteo de vehículos con almacenamiento temporal.
(Universidad de Concepción., 2018) Concha Hulin, Iván Ignacio; Aguayo Bustos, Maichel Miguel; supervisor de grado
En este trabajo se estudia el problema de Ruteo de Vehículos con Almacenamiento Temporal, el cual es una extensión del problema de Ruteo de Vehículos que incorpora la característica de que los locales pueden almacenar productos de forma temporal para su posterior distribución. Se presentan dos modelos matemáticos para representar el problema, en el primero los locales son desdoblados, separando la parte del local que demanda productos de la que almacena temporalmente productos, mientras que en el segundo, los locales son representados por un único nodo en la red. Los modelos se validan empíricamente en instancias disponibles en la literatura, utilizando el solver CPLEX. Además, se presenta un algoritmo basado en un modelo relajado del problema, encontrándose soluciones con menor distancia recorrida respecto del problema de Ruteo de Vehículos.
Algoritmo GRASP para la programación de cirugías electivas en un hospital público chileno
(Universidad de Concepción., 2016) Cartes Rubilar, Ignacio Isaías; Medina Durán, Rosa; profesora guía
Los hospitales en Chile, reaccionando a la gran demanda actual y la necesidad de entregar servicios con recursos limitados (entre algunas cosas), han debido buscar métodos para la optimización de los recursos. En este estudio, además de presentar un estudio del estado del arte de la programación de cirugías electivas, se realiza una comparación en la resolución del problema de programación de cirugías electivas de un modelo IP presentado en un trabajo anterior con un algoritmo basado en la metaheurística Greedy Randomized Adaptive Search Procedures (GRASP) mediante instancias obtenidas con datos históricos de un hospital público chileno. El tiempo de ejecución del algoritmo GRASP es considerablemente menor al tiempo de ejecución del modelo lineal entero, siendo para la instancia de mayor tamaño 130800 segundos de ejecución versus 1.99 segundos del algoritmo GRASP, logrando una calidad de solución similar. Se resuelven además, instancias de mayor tamaño con el algoritmo GRASP considerando hasta 250 pacientes y 22 médicos.
Un algoritmo memético multipoblacional y un algoritmo memético celular para el problema del árbol de cobertura mínimo generalizado.
(Universidad de Concepción., 2013) Melgarejo Islas, Eliseo Adolfo; Pradenas Rojas, Lorena del Carmen; supervisora de grado
En esta Tesis, se diseñan dos propuestas de solución para el problema de conectividad conocido como el árbol de cobertura mínimo generalizado (GMSTP por sus siglas en inglés) mediante un algoritmo memético multipoblacional y un algoritmo memético celular. Se realiza una parametrización para cada algoritmo considerando aquellos factores considerados más importantes y que puedan afectar de mayor forma el desempeño del algoritmo a través de un análisis de los parámetros más relevantes. Para el cálculo de resultados se utilizan instancias disponibles y utilizadas en la literatura, las cuales muestran gran eficiencia del algoritmo en la calidad y tiempo comparables, principalmente en lo relativo a instancias medianas y grandes donde los autores previos presentan escasos resultados, lo que permite a ambos algoritmos propuesto convertirse en una alternativa viable para resolver éste tipo de problema.
Algoritmo metaheurístico basado en evolución horizontal de microorganismos = Metaheuristic Algorithm based on Horizontal Evolution of Microorganisms.
(Universidad de Concepción., 2014) Neira Jara, Rodrigo Eduardo; Contreras Arriagada, Ricardo; supervisor de grado
Este trabajo se orienta a la resolución de problemas de optimización combinatoria, mediante la utilización de un algoritmo bioinspirado, cuyo enfoque es metaheurístico. Actualmente, existen sistemas bioinspirados como los Algoritmos Genéticos o los Sistemas de Hormigas, los cuales se basan en cómo una población de individuos mejora su código genético mediante selección natural (competencia) y cómo las hormigas encuentran el mejor camino posible hacia una fuente de alimento, respectivamente. El algoritmo creado se inspira en cómo los microorganismos mejoran su código genético cooperativamente, lo cual tiene tras de sí un paradigma colaborativo. Los resultados de las pruebas realizadas - específicamente, a problemas TSP - al algoritmo son satisfactorios y muestran un comportamiento interesante, desde el punto de vista de la versatilidad de con figuraciones de parámetros que el algoritmo permite.
Algoritmo para determinar el origen de la vibración sincrónica en rotores rígidos verticales.
(Universidad de Concepción., 2022) Santa María González, Ignacio Sebastián; Rodríguez Godoy, Cristian; supervisor de grado
Dentro de las técnicas de mantenimiento empleadas en la actualidad se utiliza la medición y análisis de vibraciones para detectar distintas fallas. Esta técnica se basa, principalmente, en que los distintos modos de falla producen vibraciones a distintas frecuencias. Sin embargo, en la industria existen máquinas en las que el análisis mencionado tiene algunas complicaciones, ya que existen varios modos de falla que producen componentes vibratorias a una misma frecuencia, por lo que no es posible discriminar sobre su origen. Para identificar el origen, es necesario contar con mediciones a distintas condiciones de operación en las que la contribución relativa de los distintos modos de falla que originan la vibración sea diferente. El objetivo principal de este trabajo es desarrollar un algoritmo capaz de identificar la contribución de los distintos modos de falla que generan vibración a la velocidad de rotación de manera de establecer la importancia relativa de cada una de ellas. Se desarrolla el algoritmo aplicándolo al caso de turbinas hidráulicas de eje vertical, sin embargo, la metodología desarrollada es aplicable a cualquier rotor rígido. En primer lugar, se analizan los cuatro principales fenómenos que generan vibración sincrónica en turbinas hidráulicas de eje vertical: desbalanceamiento mecánico, desbalanceamiento magnético, desbalanceamiento hidráulico y runout; logrando obtener relaciones de proporcionalidad con las condiciones de operación para cada uno de estos fenómenos. Posteriormente, estas relaciones de proporcionalidad fueron utilizadas para conseguir la ponderación de las componentes en la vibración resultante bajo distintas condiciones de operación. En segunda instancia, se realiza el desarrollo matemático utilizando distintas condiciones de operación para plantear un sistema de ecuaciones y determinar los cuatro orígenes. Debido a que el sistema de ecuaciones tiene más incógnitas que ecuaciones, se utilizan las proporciones anteriormente descritas para plantear el sistema de ecuaciones en función de una ecuación definida, formando un sistema de ecuaciones de 𝑛 × 𝑛. Finalmente, resolviendo el sistema de ecuaciones, se obtienen las amplitudes de cada origen para un intervalo definido. Posteriormente se realiza una simulación, basada en mediciones reales, de cómo sería una vibración en presencia de los cuatro modos de falla, para luego estudiar su superposición. Además, con la simulación se realiza un estudio del error de la solución del sistema de ecuaciones en función de las diferencias de amplitud y fase. También se estudia el error en función de los intervalos seleccionados donde la principal conclusión obtenida es que, si se utilizan condiciones de operación similares, el número de condición de la matriz se hace muy alto, obteniéndose una solución con un error alto. Por otra parte, durante la programación del algoritmo se presentaron errores de cálculo no previstos por lo que se optó por plantear el sistema de ecuaciones de cinco formas distintas para luego entregar aquella solución que tenga el menor error estimado. El algoritmo se programó en lenguaje MATLAB, basado en las conclusiones obtenidas de la simulación. La programación se realizó de tal forma que al ejecutar el programa se abre una ventana que solicita una hoja de cálculo en archivo Excel que debe contener en sus columnas los vectores de tiempo, vibración, pulso, corriente y potencia. Luego, se buscan los intervalos donde sea factible plantear y resolver el sistema de ecuaciones. Posteriormente se realizan los cálculos y finalmente se entregan los resultados. La principal conclusión de la investigación es que el algoritmo queda validado mediante datos de simulación con errores relativos máximos de 2.12%, mientras que con mediciones reales hechas en una turbina hidráulica en junio de 2019 los errores relativos máximos fueron de 3.12% y con otras mediciones reales hechas en octubre de 2020 los errores relativos máximos fueron de 8.18%.
Algoritmo para la optimización de la generación solar en granjas con generación asimétrica.
(Universidad de Concepción., 2015) Silva Cortés, José Javier; Espinoza Castro, José Rubén; supervisor de grado
La energía solar es considerada la fuente de energía más abundante e inagotable disponible en el planeta. Particularmente en el norte de Chile se poseen los mayores índices de radiación solar a nivel mundial. Para aprovechar la energía solar en aplicaciones eléctricas es necesario la utilización de celdas fotovoltaicas que son capaces de captar los fotones emitidos por el sol y transformarlos en un flujo de electrones, las cuales poseen una característica de operación no lineal. Para aprovechar al máximo la conversión de energía solar a eléctrica es necesario que las celdas operen en un punto óptimo, llamado: punto de máxima potencia; lo cual, debido a su naturaleza no lineal, no es una tarea trivial. A pesar de que en la literatura se han reportado diversos algoritmos de búsqueda del máximo punto de potencia, aún se pueden mejorar los métodos ya existentes. En particular para el caso de grandes granjas solares que, debido a su distribución geográfica, poseen condiciones de radiación y/o temperatura que no necesariamente son homogéneos, el comportamiento de un gran conjunto de paneles fotovoltaicos puede presentar múltiples puntos máximos de operación, es ahí donde es necesario un algoritmo que sea capaz de encontrar el punto de máxima potencia global y no sólo un máximo local. En este trabajo se diseña y simula un nuevo algoritmo de búsqueda del punto óptimo de operación, tanto para granjas solares que operan bajo condiciones de radiación y temperatura homogéneas como para plantas solares que operan bajo condiciones no homogéneas. Para validar los algoritmos propuestos en este trabajo, se diseña y simula una planta fotovoltaica con capacidad de generación máxima de 100MW, basada en convertidores estáticos multinivel. Los resultados muestran que la planta opera siempre en el máximo de generación global a pesar de las condiciones asimétricas de radiación. Finalmente, para operar los convertidores estáticos, se propone una estrategia de control híbrida compuesta por un controlador lineal para el lazo de voltaje y un lazo de control predictivo para la corriente, que son validados tanto en simulación como implementación.

Browse

Browsing Tesis Magíster by Title

Results Per Page

Sort Options