Algoritmos metaheurísticos en el problema del particionado hardware/software de sistemas embebidos

El particionado hardware/software es una tarea fundamental en el co-diseño de sistemas embebidos. En ella se decide, teniendo en cuenta las métricas de diseño, qué componentes se ejecutarán en un procesador de propósito general (software) y cuáles en un hardware específico. En los últimos años se han propuesto diversas soluciones al problema del particionado dirigidas por algoritmos metaheurísticos. Sin embargo, debido a la diversidad de modelos y métricas utilizadas, la elección del algoritmo más apropiado sigue siendo un problema abierto. En este trabajo se presenta una comparación de seis algoritmos metaheurísticos: Búsqueda aleatoria (Random search), Búsqueda tabú (Tabu search), Recocido simulado (Simulated annealing), Escalador de colinas estocástico (Stochastic hill climbing), Algoritmo genético (Genetic algorithm) y Estrategia evolutiva (Evolution strategy). El modelo utilizado en la comparación está dirigido a minimizar el área ocupada y el tiempo de ejecución, las restricciones del modelo son consideradas como penalizaciones para incluir en el espacio de búsqueda otras soluciones. Los resultados muestran que los algoritmos Escalador de colinas estocástico y Estrategia evolutiva son los que mejores resultados obtienen en general, seguidos por el Algoritmo genético.

Optimización de áreas funcionales espaciales mediante algoritmos evolutivos multioperador. Aplicación a la delimitación de mercados locales de trabajo

El documento de esta tesis por compendio de publicaciones se divide en dos partes: la síntesis donde se resume la fundamentación, resultados y conclusiones de esta tesis, y las propias publicaciones en su formato original, que se incluyen como apéndices. Dado que existen acuerdo de confidencialidad (véase "Derechos" más adelante) que impiden su publicación en formato electrónico de forma pública y abierta (como es el repositorio de la UA), y acorde con lo que se dictamina en el punto 6 del artículo 14 del RD 99/2011, de 28 de enero, no se incluyen estos apéndices en el documento electrónico que se presenta en cedé, pero se incluyen las referencias completas y sí se incluyen integramente en el ejemplar encuadernado. Si el CEDIP y el RUA así lo decidiesen más adelante, podría modificarse este documento electrónico para incluir los enlaces a los artículos originales.

Aceleración de Algoritmos en Procesadores Multicore, GPGPU y FPGA

El avance en la potencia de cómputo en nuestros días viene dado por la paralelización del procesamiento, dadas las características que disponen las nuevas arquitecturas de hardware. Utilizar convenientemente este hardware impacta en la aceleración de los algoritmos en ejecución (programas). Sin embargo, convertir de forma adecuada el algoritmo en su forma paralela es complejo, y a su vez, esta forma, es específica para cada tipo de hardware paralelo. En la actualidad los procesadores de uso general más comunes son los multicore, procesadores paralelos, también denominados Symmetric Multi-Processors (SMP). Hoy en día es difícil hallar un procesador para computadoras de escritorio que no tengan algún tipo de paralelismo del caracterizado por los SMP, siendo la tendencia de desarrollo, que cada día nos encontremos con procesadores con mayor numero de cores disponibles. Por otro lado, los dispositivos de procesamiento de video (Graphics Processor Units - GPU), a su vez, han ido desarrollando su potencia de cómputo por medio de disponer de múltiples unidades de procesamiento dentro de su composición electrónica, a tal punto que en la actualidad no es difícil encontrar placas de GPU con capacidad de 200 a 400 hilos de procesamiento paralelo. Estos procesadores son muy veloces y específicos para la tarea que fueron desarrollados, principalmente el procesamiento de video. Sin embargo, como este tipo de procesadores tiene muchos puntos en común con el procesamiento científico, estos dispositivos han ido reorientándose con el nombre de General Processing Graphics Processor Unit (GPGPU). A diferencia de los procesadores SMP señalados anteriormente, las GPGPU no son de propósito general y tienen sus complicaciones para uso general debido al límite en la cantidad de memoria que cada placa puede disponer y al tipo de procesamiento paralelo que debe realizar para poder ser productiva su utilización. Los dispositivos de lógica programable, FPGA, son dispositivos capaces de realizar grandes cantidades de operaciones en paralelo, por lo que pueden ser usados para la implementación de algoritmos específicos, aprovechando el paralelismo que estas ofrecen. Su inconveniente viene derivado de la complejidad para la programación y el testing del algoritmo instanciado en el dispositivo. Ante esta diversidad de procesadores paralelos, el objetivo de nuestro trabajo está enfocado en analizar las características especificas que cada uno de estos tienen, y su impacto en la estructura de los algoritmos para que su utilización pueda obtener rendimientos de procesamiento acordes al número de recursos utilizados y combinarlos de forma tal que su complementación sea benéfica. Específicamente, partiendo desde las características del hardware, determinar las propiedades que el algoritmo paralelo debe tener para poder ser acelerado. Las características de los algoritmos paralelos determinará a su vez cuál de estos nuevos tipos de hardware son los mas adecuados para su instanciación. En particular serán tenidos en cuenta el nivel de dependencia de datos, la necesidad de realizar sincronizaciones durante el procesamiento paralelo, el tamaño de datos a procesar y la complejidad de la programación paralela en cada tipo de hardware.

Estratégias de busca reativa utilizando aprendizagem por reforço e algoritmos de busca local

Técnicas de otimização conhecidas como as metaheurísticas tem conseguido resolversatisfatoriamente problemas conhecidos, mas desenvolvimento das metaheurísticas écaracterizado por escolha de parâmetros para sua execução, na qual a opção apropriadadestes parâmetros (valores). Onde o ajuste de parâmetro é essencial testa-se os parâmetrosaté que resultados viáveis sejam obtidos, normalmente feita pelo desenvolvedor que estaimplementando a metaheuristica. A qualidade dos resultados de uma instância1 de testenão será transferida para outras instâncias a serem testadas e seu feedback pode requererum processo lento de “tentativa e erro” onde o algoritmo têm que ser ajustado para umaaplicação especifica. Diante deste contexto das metaheurísticas surgiu a Busca Reativaque defende a integração entre o aprendizado de máquina dentro de buscas heurísticaspara solucionar problemas de otimização complexos. A partir da integração que a BuscaReativa propõe entre o aprendizado de máquina e as metaheurísticas, surgiu a ideia dese colocar a Aprendizagem por Reforço mais especificamente o algoritmo Q-learning deforma reativa, para selecionar qual busca local é a mais indicada em determinado instanteda busca, para suceder uma outra busca local que não pode mais melhorar a soluçãocorrente na metaheurística VNS. Assim, neste trabalho propomos uma implementação reativa,utilizando aprendizado por reforço para o auto-tuning do algoritmo implementado,aplicado ao problema do caixeiro viajante simétrico e ao problema escalonamento sondaspara manutenção de poços.

Estudo da participação das espécies fortemente oxidantes produzidas durante a oxidação eletroquímica de corantes usando eletrodo de diamante dopado com boro: função das propriedades eletroquímicas do eletrodo e condições experimentais

The textile industry is one of the most polluting in the world (AHMEDCHEKKAT et al. 2011), generating wastewater with high organic loading. Among the pollutants present in these effluents are dyes, substances with complex structures, toxic and carcinogenic characteristics, besides having a strong staining. Improper disposal of these substances to the environment, without performing a pre-treatment can cause major environmental impacts. The objective this thesis to use a technique of electrochemical oxidation of boron doped diamond anode, BDD, for the treatment of a synthetic dye and a textile real effluent. In addition to studying the behavior of different electrolytes (HClO4, H3PO4, NaCl and Na2SO4) and current densities (15, 60, 90 and 120 mA.cm-2 ), and compare the methods with Rhodamine B (RhB) photolysis, electrolysis and photoelectrocatalytic using H3PO4 and Na2SO4. Electrochemical oxidation studies were performed in different ratio sp3 /sp2 of BDD with solution of RhB. To achieve these objectives, analysis of pH, conductivity, UV-visible, TOC, HPLC and GC-MS were developed. Based on the results with the Rhodamine B, it was observed that in all cases occurred at mineralization, independent of electrolyte and current density, but these parameters affect the speed and efficiency of mineralization. The radiation of light was favorable during the electrolysis of RhB with phosphate and sulfate. Regarding the oxidation in BDD anode with different ratio sp3 /sp2 (165, 176, 206, 220, 262 e 329), with lower carbon-sp3 had a longer favoring the electrochemical conversion of RhB, instead of combustion. The greater the carbon content on the anodes BDD took the biggest favor of direct electrochemical oxidation

Formulações e algoritmos para o problema das p-medianas heterogêneo livre de penalidade

This work presents a new model for the Heterogeneous p-median Problem (HPM), proposed to recover the hidden category structures present in the data provided by a sorting task procedure, a popular approach to understand heterogeneous individual’s perception of products and brands. This new model is named as the Penalty-free Heterogeneous p-median Problem (PFHPM), a single-objective version of the original problem, the HPM. The main parameter in the HPM is also eliminated, the penalty factor. It is responsible for the weighting of the objective function terms. The adjusting of this parameter controls the way that the model recovers the hidden category structures present in data, and depends on a broad knowledge of the problem. Additionally, two complementary formulations for the PFHPM are shown, both mixed integer linear programming problems. From these additional formulations lower-bounds were obtained for the PFHPM. These values were used to validate a specialized Variable Neighborhood Search (VNS) algorithm, proposed to solve the PFHPM. This algorithm provided good quality solutions for the PFHPM, solving artificial generated instances from a Monte Carlo Simulation and real data instances, even with limited computational resources. Statistical analyses presented in this work suggest that the new algorithm and model, the PFHPM, can recover more accurately the original category structures related to heterogeneous individual’s perceptions than the original model and algorithm, the HPM. Finally, an illustrative application of the PFHPM is presented, as well as some insights about some new possibilities for it, extending the new model to fuzzy environments

Sobre a integração indefinida de funções racionais complexas: teoria e implementação de algoritmos racionais

We present indefinite integration algorithms for rational functions over subfields of the complex numbers, through an algebraic approach. We study the local algorithm of Bernoulli and rational algorithms for the class of functions in concern, namely, the algorithms of Hermite; Horowitz-Ostrogradsky; Rothstein-Trager and Lazard-Rioboo-Trager. We also study the algorithm of Rioboo for conversion of logarithms involving complex extensions into real arctangent functions, when these logarithms arise from the integration of rational functions with real coefficients. We conclude presenting pseudocodes and codes for implementation in the software Maxima concerning the algorithms studied in this work, as well as to algorithms for polynomial gcd computation; partial fraction decomposition; squarefree factorization; subresultant computation, among other side algorithms for the work. We also present the algorithm of Zeilberger-Almkvist for integration of hyperexpontential functions, as well as its pseudocode and code for Maxima. As an alternative for the algorithms of Rothstein-Trager and Lazard-Rioboo-Trager, we yet present a code for Benoulli’s algorithm for square-free denominators; and another for Czichowski’s algorithm, although this one is not studied in detail in the present work, due to the theoretical basis necessary to understand it, which is beyond this work’s scope. Several examples are provided in order to illustrate the working of the integration algorithms in this text

Avaliação anti-inflamatória e antipeçonhenta das espécies Hancornia speciosa e Mimosa tenuiflora em modelos experimentais de inflamação e envenenamento induzidos por Bothrops jararaca e Tityus serrulatus

Accidents caused by venomous animals represents a significant and serious public health problem in certain regions of Brazil, as well as in other parts of the world by the frequency with which they occur and the mortality they cause. The use of plant extracts as an antidote for poisoning cases is an ancient practice used in many communities that have no access to antivenom. Medicinal plants represent an important source of obtaining bioactive compounds able to assist directly in the treatment of poisoning or indirectly supplementing serum therapy currently used. The aim of this study was to evaluate the effect of extracts, fractions and isolated compounds from M. tenuiflora and H. speciosa in the inflammatory process induced by carrageenan and the venom of B. jararaca and T. serrulatus. The results showed that both M. tenuiflora and H. speciosa were capable of inhibiting cell migration and cytokines levels in peritonitis induced by carrageenin and venom of T. serrulatus. In poisoning by B. jararaca model, mice treated with the plants in studies decreased the leukocyte influx into the peritoneal cavity. Finally the M. tenuiflora and H. speciosa had antiphlogistic activity, reducing edema formation and exerted inhibitory action of leukocyte migration in local inflammation induced by the venom of B. jararaca. Through of Thin Layer Chromatography (TLC) analysis was possible identified the presence of flavonoids ,saponins and/or terpenes in aqueous extract of M. tenuiflora. By High Performance Liquid Chromatography analysis, it was possible to identify the presence of rutin and chlorogenic acid in aqueous extract of H. speciosa. We conclude that the administration of extracts, fractions and isolated compounds of H. speciosa and M. tenuiflora resulted in inhibition of the inflammatory process in different experimental models. This study demonstrates for the first time the effect of M. tenuiflora and H. speciosa in inhibition of the inflammation caused by B. jararaca and T. serrulatus venom.

Distribuição de derivados de petróleo por redes de polidutos: uma abordagem através de algoritmos evolucionários híbridos para um problema triobjetivo

An important problem faced by the oil industry is to distribute multiple oil products through pipelines. Distribution is done in a network composed of refineries (source nodes), storage parks (intermediate nodes), and terminals (demand nodes) interconnected by a set of pipelines transporting oil and derivatives between adjacent areas. Constraints related to storage limits, delivery time, sources availability, sending and receiving limits, among others, must be satisfied. Some researchers deal with this problem under a discrete viewpoint in which the flow in the network is seen as batches sending. Usually, there is no separation device between batches of different products and the losses due to interfaces may be significant. Minimizing delivery time is a typical objective adopted by engineers when scheduling products sending in pipeline networks. However, costs incurred due to losses in interfaces cannot be disregarded. The cost also depends on pumping expenses, which are mostly due to the electricity cost. Since industrial electricity tariff varies over the day, pumping at different time periods have different cost. This work presents an experimental investigation of computational methods designed to deal with the problem of distributing oil derivatives in networks considering three minimization objectives simultaneously: delivery time, losses due to interfaces and electricity cost. The problem is NP-hard and is addressed with hybrid evolutionary algorithms. Hybridizations are mainly focused on Transgenetic Algorithms and classical multi-objective evolutionary algorithm architectures such as MOEA/D, NSGA2 and SPEA2. Three architectures named MOTA/D, NSTA and SPETA are applied to the problem. An experimental study compares the algorithms on thirty test cases. To analyse the results obtained with the algorithms Pareto-compliant quality indicators are used and the significance of the results evaluated with non-parametric statistical tests.

Metodologia de estimação de estados para tratamento de medições errôneas e registros não sincronizados em algoritmos de localização de faltas em linhas de transmissão

The performance of algorithms for fault location i n transmission lines is directly related to the accuracy of its input data. Thus, fa ctors such as errors in the line parameters, failures in synchronization of oscillographic recor ds and errors in measurements of voltage and current can significantly influence the accurac y of algorithms that use bad data to indicate the fault location. This work presents a new method ology for fault location in transmission lines based on the theory of state estimation in or der to determine the location of faults more accurately by considering realistic systematic erro rs that may be present in measurements of voltage and current. The methodology was implemente d in two stages: pre-fault and post- fault. In the first step, assuming non-synchronized data, the synchronization angle and positive sequence line parameters are estimated, an d in the second, the fault distance is estimated. Besides calculating the most likely faul t distance obtained from measurement errors, the variance associated with the distance f ound is also determined, using the errors theory. This is one of the main contributions of th is work, since, with the proposed algorithm, it is possible to determine a most likely zone of f ault incidence, with approximately 95,45% of confidence. Tests for evaluation and validation of the proposed algorithm were realized from actual records of faults and from simulations of fictitious transmission systems using ATP software. The obtained results are relevant to show that the proposed estimation approach works even adopting realistic variances, c ompatible with real equipments errors.

Análise de desempenho de algoritmos de compressão de dados com perda para aplicações industriais

The great amount of data generated as the result of the automation and process supervision in industry implies in two problems: a big demand of storage in discs and the difficulty in streaming this data through a telecommunications link. The lossy data compression algorithms were born in the 90’s with the goal of solving these problems and, by consequence, industries started to use those algorithms in industrial supervision systems to compress data in real time. These algorithms were projected to eliminate redundant and undesired information in a efficient and simple way. However, those algorithms parameters must be set for each process variable, becoming impracticable to configure this parameters for each variable in case of systems that monitor thousands of them. In that context, this paper propose the algorithm Adaptive Swinging Door Trending that consists in a adaptation of the Swinging Door Trending, as this main parameters are adjusted dynamically by the analysis of the signal tendencies in real time. It’s also proposed a comparative analysis of performance in lossy data compression algorithms applied on time series process variables and dynamometer cards. The algorithms used to compare were the piecewise linear and the transforms.

Algoritmo modificado de PSO matricial aplicado a identificação de sistemas com análise de convergência

Recentemente diversas técnicas de computação evolucionárias têm sido utilizadas em áreas como estimação de parâmetros de processos dinâmicos lineares e não lineares ou até sujeitos a incertezas. Isso motiva a utilização de algoritmos como o otimizador por nuvem de partículas (PSO) nas referidas áreas do conhecimento. Porém, pouco se sabe sobre a convergência desse algoritmo e, principalmente, as análises e estudos realizados têm se concentrado em resultados experimentais. Por isso, é objetivo deste trabalho propor uma nova estrutura para o PSO que permita analisar melhor a convergência do algoritmo de forma analítica. Para isso, o PSO é reestruturado para assumir uma forma matricial e reformulado como um sistema linear por partes. As partes serão analisadas de forma separada e será proposta a inserção de um fator de esquecimento que garante que a parte mais significativa deste sistema possua autovalores dentro do círculo de raio unitário. Também será realizada a análise da convergência do algoritmo como um todo, utilizando um critério de convergência quase certa, aplicável a sistemas chaveados. Na sequência, serão realizados testes experimentais de maneira a verificar o comportamento dos autovalores após a inserção do fator de esquecimento. Posteriormente, os algoritmos de identificação de parâmetros tradicionais serão combinados com o PSO matricial, de maneira a tornar os resultados da identificação tão bons ou melhores que a identificação apenas com o PSO ou, apenas com os algoritmos tradicionais. Os resultados mostram a convergência das partículas em uma região delimitada e que as funções obtidas após a combinação do algoritmo PSO matricial com os algoritmos convencionais, apresentam maior generalização para o sistema apresentado. As conclusões a que se chega é que a hibridização, apesar de limitar a busca por uma partícula mais apta do PSO, permite um desempenho mínimo para o algoritmo e ainda possibilita melhorar o resultado obtido com os algoritmos tradicionais, permitindo a representação do sistema aproximado em quantidades maiores de frequências.

Evoluções nas modelagens de substratos artificiais (metamateriais) com práticas experimentais em antenas de microfita

Esse trabalho tem como objetivo apresentar configurações de substratos dielétricos inovadores projetados e fabricados a partir de estruturas metamateriais. Para isso, são avaliados diversos fatores que podem influenciar no seu desempenho. A princípio, foi feito um levantamento bibliográfico a respeito dos temas, que estão relacionados com as pesquisas sobre: materiais dielétricos, metamateriais e interferometria óptica. São estudados, pesquisados e desenvolvidos dois projetos experimentais propostos, que comprovam a eficiência de métodos, para se alcançar a permeabilidade magnética negativa na formação de metamateriais. O primeiro projeto é a produção de uma nova estrutura, com u anel ressoador triangular equilateral (Split Equilateral Triangle Resonator - SETR). O segundo projeto: aplica os princípios da interferometria óptica, especialmente, com o interferômetro de Fabry-Perot. Técnicas para obtenção dos dispositivos que complementam a placa metamaterial como substrato foram pesquisadas na literatura e exemplificadas principalmente por meio de simulações e medições. Foram feitas comparações, simulações e medições de estruturas convencionais e especiais. As experiências se concentram nas evoluções e modelagens de substratos metamateriais com aplicações em antenas de microfita. As melhorias de alguns parâmetros de desempenho de antenas também são relatadas. As simulações das antenas foram feitas nos programas computacionais comerciais. Os resultados medidos foram obtidos com um analisador vetorial de redes da Rhode and Schwarz modelo ZVB 14.

Evoluções nas modelagens de substratos artificiais (metamateriais) com práticas experimentais em antenas de microfita

Esse trabalho tem como objetivo apresentar configurações de substratos dielétricos inovadores projetados e fabricados a partir de estruturas metamateriais. Para isso, são avaliados diversos fatores que podem influenciar no seu desempenho. A princípio, foi feito um levantamento bibliográfico a respeito dos temas, que estão relacionados com as pesquisas sobre: materiais dielétricos, metamateriais e interferometria óptica. São estudados, pesquisados e desenvolvidos dois projetos experimentais propostos, que comprovam a eficiência de métodos, para se alcançar a permeabilidade magnética negativa na formação de metamateriais. O primeiro projeto é a produção de uma nova estrutura, com u anel ressoador triangular equilateral (Split Equilateral Triangle Resonator - SETR). O segundo projeto: aplica os princípios da interferometria óptica, especialmente, com o interferômetro de Fabry-Perot. Técnicas para obtenção dos dispositivos que complementam a placa metamaterial como substrato foram pesquisadas na literatura e exemplificadas principalmente por meio de simulações e medições. Foram feitas comparações, simulações e medições de estruturas convencionais e especiais. As experiências se concentram nas evoluções e modelagens de substratos metamateriais com aplicações em antenas de microfita. As melhorias de alguns parâmetros de desempenho de antenas também são relatadas. As simulações das antenas foram feitas nos programas computacionais comerciais. Os resultados medidos foram obtidos com um analisador vetorial de redes da Rhode and Schwarz modelo ZVB 14.

Planejamento de trajetórias e navegação de robôs móveis

Oil exploration at great depths requires the use of mobile robots to perform various operations such as maintenance, assembly etc. In this context, the trajectory planning and navigation study of these robots is relevant, as the great challenge is to navigate in an environment that is not fully known. The main objective is to develop a navigation algorithm to plan the path of a mobile robot that is in a given position (