Pulmonary Artery-Vein Segmentation in Real and Synthetic CT Images = Segmentación Arteria-Vena Pulmonares en Imágenes de CT Reales y Sintéticas

La tomografía axial computerizada (TAC) es la modalidad de imagen médica preferente para el estudio de enfermedades pulmonares y el análisis de su vasculatura. La segmentación general de vasos en pulmón ha sido abordada en profundidad a lo largo de los últimos años por la comunidad científica que trabaja en el campo de procesamiento de imagen; sin embargo, la diferenciación entre irrigaciones arterial y venosa es aún un problema abierto. De hecho, la separación automática de arterias y venas está considerado como uno de los grandes retos futuros del procesamiento de imágenes biomédicas. La segmentación arteria-vena (AV) permitiría el estudio de ambas irrigaciones por separado, lo cual tendría importantes consecuencias en diferentes escenarios médicos y múltiples enfermedades pulmonares o estados patológicos. Características como la densidad, geometría, topología y tamaño de los vasos sanguíneos podrían ser analizados en enfermedades que conllevan remodelación de la vasculatura pulmonar, haciendo incluso posible el descubrimiento de nuevos biomarcadores específicos que aún hoy en dípermanecen ocultos. Esta diferenciación entre arterias y venas también podría ayudar a la mejora y el desarrollo de métodos de procesamiento de las distintas estructuras pulmonares. Sin embargo, el estudio del efecto de las enfermedades en los árboles arterial y venoso ha sido inviable hasta ahora a pesar de su indudable utilidad. La extrema complejidad de los árboles vasculares del pulmón hace inabordable una separación manual de ambas estructuras en un tiempo realista, fomentando aún más la necesidad de diseñar herramientas automáticas o semiautomáticas para tal objetivo. Pero la ausencia de casos correctamente segmentados y etiquetados conlleva múltiples limitaciones en el desarrollo de sistemas de separación AV, en los cuales son necesarias imágenes de referencia tanto para entrenar como para validar los algoritmos. Por ello, el diseño de imágenes sintéticas de TAC pulmonar podría superar estas dificultades ofreciendo la posibilidad de acceso a una base de datos de casos pseudoreales bajo un entorno restringido y controlado donde cada parte de la imagen (incluyendo arterias y venas) está unívocamente diferenciada. En esta Tesis Doctoral abordamos ambos problemas, los cuales están fuertemente interrelacionados. Primero se describe el diseño de una estrategia para generar, automáticamente, fantomas computacionales de TAC de pulmón en humanos. Partiendo de conocimientos a priori, tanto biológicos como de características de imagen de CT, acerca de la topología y relación entre las distintas estructuras pulmonares, el sistema desarrollado es capaz de generar vías aéreas, arterias y venas pulmonares sintéticas usando métodos de crecimiento iterativo, que posteriormente se unen para formar un pulmón simulado con características realistas. Estos casos sintéticos, junto a imágenes reales de TAC sin contraste, han sido usados en el desarrollo de un método completamente automático de segmentación/separación AV. La estrategia comprende una primera extracción genérica de vasos pulmonares usando partículas espacio-escala, y una posterior clasificación AV de tales partículas mediante el uso de Graph-Cuts (GC) basados en la similitud con arteria o vena (obtenida con algoritmos de aprendizaje automático) y la inclusión de información de conectividad entre partículas. La validación de los fantomas pulmonares se ha llevado a cabo mediante inspección visual y medidas cuantitativas relacionadas con las distribuciones de intensidad, dispersión de estructuras y relación entre arterias y vías aéreas, los cuales muestran una buena correspondencia entre los pulmones reales y los generados sintéticamente. La evaluación del algoritmo de segmentación AV está basada en distintas estrategias de comprobación de la exactitud en la clasificación de vasos, las cuales revelan una adecuada diferenciación entre arterias y venas tanto en los casos reales como en los sintéticos, abriendo así un amplio abanico de posibilidades en el estudio clínico de enfermedades cardiopulmonares y en el desarrollo de metodologías y nuevos algoritmos para el análisis de imágenes pulmonares. ABSTRACT Computed tomography (CT) is the reference image modality for the study of lung diseases and pulmonary vasculature. Lung vessel segmentation has been widely explored by the biomedical image processing community, however, differentiation of arterial from venous irrigations is still an open problem. Indeed, automatic separation of arterial and venous trees has been considered during last years as one of the main future challenges in the field. Artery-Vein (AV) segmentation would be useful in different medical scenarios and multiple pulmonary diseases or pathological states, allowing the study of arterial and venous irrigations separately. Features such as density, geometry, topology and size of vessels could be analyzed in diseases that imply vasculature remodeling, making even possible the discovery of new specific biomarkers that remain hidden nowadays. Differentiation between arteries and veins could also enhance or improve methods processing pulmonary structures. Nevertheless, AV segmentation has been unfeasible until now in clinical routine despite its objective usefulness. The huge complexity of pulmonary vascular trees makes a manual segmentation of both structures unfeasible in realistic time, encouraging the design of automatic or semiautomatic tools to perform the task. However, this lack of proper labeled cases seriously limits in the development of AV segmentation systems, where reference standards are necessary in both algorithm training and validation stages. For that reason, the design of synthetic CT images of the lung could overcome these difficulties by providing a database of pseudorealistic cases in a constrained and controlled scenario where each part of the image (including arteries and veins) is differentiated unequivocally. In this Ph.D. Thesis we address both interrelated problems. First, the design of a complete framework to automatically generate computational CT phantoms of the human lung is described. Starting from biological and imagebased knowledge about the topology and relationships between structures, the system is able to generate synthetic pulmonary arteries, veins, and airways using iterative growth methods that can be merged into a final simulated lung with realistic features. These synthetic cases, together with labeled real CT datasets, have been used as reference for the development of a fully automatic pulmonary AV segmentation/separation method. The approach comprises a vessel extraction stage using scale-space particles and their posterior artery-vein classification using Graph-Cuts (GC) based on arterial/venous similarity scores obtained with a Machine Learning (ML) pre-classification step and particle connectivity information. Validation of pulmonary phantoms from visual examination and quantitative measurements of intensity distributions, dispersion of structures and relationships between pulmonary air and blood flow systems, show good correspondence between real and synthetic lungs. The evaluation of the Artery-Vein (AV) segmentation algorithm, based on different strategies to assess the accuracy of vessel particles classification, reveal accurate differentiation between arteries and vein in both real and synthetic cases that open a huge range of possibilities in the clinical study of cardiopulmonary diseases and the development of methodological approaches for the analysis of pulmonary images.

Optimización de aperturas mediante técnicas de algoritmos evolutivos

Los sistemas de imagen por ultrasonidos son hoy una herramienta indispensable en aplicaciones de diagnóstico en medicina y son cada vez más utilizados en aplicaciones industriales en el área de ensayos no destructivos. El array es el elemento primario de estos sistemas y su diseño determina las características de los haces que se pueden construir (forma y tamaño del lóbulo principal, de los lóbulos secundarios y de rejilla, etc.), condicionando la calidad de las imágenes que pueden conseguirse. En arrays regulares la distancia máxima entre elementos se establece en media longitud de onda para evitar la formación de artefactos. Al mismo tiempo, la resolución en la imagen de los objetos presentes en la escena aumenta con el tamaño total de la apertura, por lo que una pequeña mejora en la calidad de la imagen se traduce en un aumento significativo del número de elementos del transductor. Esto tiene, entre otras, las siguientes consecuencias: Problemas de fabricación de los arrays por la gran densidad de conexiones (téngase en cuenta que en aplicaciones típicas de imagen médica, el valor de la longitud de onda es de décimas de milímetro) Baja relación señal/ruido y, en consecuencia, bajo rango dinámico de las señales por el reducido tamaño de los elementos. Complejidad de los equipos que deben manejar un elevado número de canales independientes. Por ejemplo, se necesitarían 10.000 elementos separados λ 2 para una apertura cuadrada de 50 λ. Una forma sencilla para resolver estos problemas existen alternativas que reducen el número de elementos activos de un array pleno, sacrificando hasta cierto punto la calidad de imagen, la energía emitida, el rango dinámico, el contraste, etc. Nosotros planteamos una estrategia diferente, y es desarrollar una metodología de optimización capaz de hallar de forma sistemática configuraciones de arrays de ultrasonido adaptados a aplicaciones específicas. Para realizar dicha labor proponemos el uso de los algoritmos evolutivos para buscar y seleccionar en el espacio de configuraciones de arrays aquellas que mejor se adaptan a los requisitos fijados por cada aplicación. En la memoria se trata el problema de la codificación de las configuraciones de arrays para que puedan ser utilizados como individuos de la población sobre la que van a actuar los algoritmos evolutivos. También se aborda la definición de funciones de idoneidad que permitan realizar comparaciones entre dichas configuraciones de acuerdo con los requisitos y restricciones de cada problema de diseño. Finalmente, se propone emplear el algoritmo multiobjetivo NSGA II como herramienta primaria de optimización y, a continuación, utilizar algoritmos mono-objetivo tipo Simulated Annealing para seleccionar y retinar las soluciones proporcionadas por el NSGA II. Muchas de las funciones de idoneidad que definen las características deseadas del array a diseñar se calculan partir de uno o más patrones de radiación generados por cada solución candidata. La obtención de estos patrones con los métodos habituales de simulación de campo acústico en banda ancha requiere tiempos de cálculo muy grandes que pueden hacer inviable el proceso de optimización con algoritmos evolutivos en la práctica. Como solución, se propone un método de cálculo en banda estrecha que reduce en, al menos, un orden de magnitud el tiempo de cálculo necesario Finalmente se presentan una serie de ejemplos, con arrays lineales y bidimensionales, para validar la metodología de diseño propuesta comparando experimentalmente las características reales de los diseños construidos con las predicciones del método de optimización. ABSTRACT Currently, the ultrasound imaging system is one of the powerful tools in medical diagnostic and non-destructive testing for industrial applications. Ultrasonic arrays design determines the beam characteristics (main and secondary lobes, beam pattern, etc...) which assist to enhance the image resolution. The maximum distance between the elements of the array should be the half of the wavelength to avoid the formation of grating lobes. At the same time, the image resolution of the target in the region of interest increases with the aperture size. Consequently, the larger number of elements in arrays assures the better image quality but this improvement contains the following drawbacks: Difficulties in the arrays manufacturing due to the large connection density. Low noise to signal ratio. Complexity of the ultrasonic system to handle large number of channels. The easiest way to resolve these issues is to reduce the number of active elements in full arrays, but on the other hand the image quality, dynamic range, contrast, etc, are compromised by this solutions In this thesis, an optimization methodology able to find ultrasound array configurations adapted for specific applications is presented. The evolutionary algorithms are used to obtain the ideal arrays among the existing configurations. This work addressed problems such as: the codification of ultrasound arrays to be interpreted as individuals in the evolutionary algorithm population and the fitness function and constraints, which will assess the behaviour of individuals. Therefore, it is proposed to use the multi-objective algorithm NSGA-II as a primary optimization tool, and then use the mono-objective Simulated Annealing algorithm to select and refine the solutions provided by the NSGA I I . The acoustic field is calculated many times for each individual and in every generation for every fitness functions. An acoustic narrow band field simulator, where the number of operations is reduced, this ensures a quick calculation of the acoustic field to reduce the expensive computing time required by these functions we have employed. Finally a set of examples are presented in order to validate our proposed design methodology, using linear and bidimensional arrays where the actual characteristics of the design are compared with the predictions of the optimization methodology.

Mining Abstractions in Scientific Workows

Los flujos de trabajo científicos han sido adoptados durante la última década para representar los métodos computacionales utilizados en experimentos in silico, así como para dar soporte a sus publicaciones asociadas. Dichos flujos de trabajo han demostrado ser útiles para compartir y reproducir experimentos científicos, permitiendo a investigadores visualizar, depurar y ahorrar tiempo a la hora de re-ejecutar un trabajo realizado con anterioridad. Sin embargo, los flujos de trabajo científicos pueden ser en ocasiones difíciles de entender y reutilizar. Esto es debido a impedimentos como el gran número de flujos de trabajo existentes en repositorios, su heterogeneidad o la falta generalizada de documentación y ejemplos de uso. Además, dado que normalmente es posible implementar un mismo método utilizando algoritmos o técnicas distintas, flujos de trabajo aparentemente distintos pueden estar relacionados a un determinado nivel de abstracción, basándose, por ejemplo, en su funcionalidad común. Esta tesis se centra en la reutilización de flujos de trabajo y su abstracción mediante la exploración de relaciones entre los flujos de trabajo de un repositorio y la extracción de abstracciones que podrían ayudar a la hora de reutilizar otros flujos de trabajo existentes. Para ello, se propone un modelo simple de representación de flujos de trabajo y sus ejecuciones, se analizan las abstracciones típicas que se pueden encontrar en los repositorios de flujos de trabajo, se exploran las prácticas habituales de los usuarios a la hora de reutilizar flujos de trabajo existentes y se describe un método para descubrir abstracciones útiles para usuarios, basadas en técnicas existentes de teoría de grafos. Los resultados obtenidos exponen las abstracciones y prácticas comunes de usuarios en términos de reutilización de flujos de trabajo, y muestran cómo las abstracciones que se extraen automáticamente tienen potencial para ser reutilizadas por usuarios que buscan diseñar nuevos flujos de trabajo. Abstract Scientific workflows have been adopted in the last decade to represent the computational methods used in in silico scientific experiments and their associated research products. Scientific workflows have demonstrated to be useful for sharing and reproducing scientific experiments, allowing scientists to visualize, debug and save time when re-executing previous work. However, scientific workflows may be difficult to understand and reuse. The large amount of available workflows in repositories, together with their heterogeneity and lack of documentation and usage examples may become an obstacle for a scientist aiming to reuse the work from other scientists. Furthermore, given that it is often possible to implement a method using different algorithms or techniques, seemingly disparate workflows may be related at a higher level of abstraction, based on their common functionality. In this thesis we address the issue of reusability and abstraction by exploring how workflows relate to one another in a workflow repository, mining abstractions that may be helpful for workflow reuse. In order to do so, we propose a simple model for representing and relating workflows and their executions, we analyze the typical common abstractions that can be found in workflow repositories, we explore the current practices of users regarding workflow reuse and we describe a method for discovering useful abstractions for workflows based on existing graph mining techniques. Our results expose the common abstractions and practices of users in terms of workflow reuse, and show how our proposed abstractions have potential to become useful for users designing new workflows.

Análisis de algoritmos para posicionamiento de aeronaves mediante respuestas SSR utilizando recepción omnidireccional

El transporte aéreo constituye un sector estratégico para el crecimiento económico de cualquier país. El sistema de gestión de tráfico aéreo ATM tiene como objetivo el movimiento seguro y eficiente de las aeronaves dentro del espacio aéreo y de los aeropuertos, siendo la seguridad, en la fase táctica, gestionada por el servicio de control de la circulación aérea. Mediante los procesos de control el tráfico aéreo es vigilado a través de sensores, regulado y guiado de forma organizada y segura. Es precisamente sobre la vigilancia donde se enfoca el contenido de la tesis, en el desarrollo de nuevos conceptos que proporcionen información de vigilancia de ‘bajo coste’ basados en las señales existentes proporcionadas por la infraestructura actual de radar secundario y por los sistemas de posicionamiento basados en satélite que utiliza la ADS-B. El conocimiento y acceso en tiempo real a las trayectorias de las aeronaves es un elemento de valor añadido no sólo para la provisión de los servicios de control de tránsito aéreo, sino para todos los actores del transporte aéreo o de la investigación, siendo uno de los elementos clave en el concepto operacional de los dos grandes proyectos tecnológicos, SESAR en Europa y NextGen en EE.UU.. En las últimas décadas el control de la circulación aérea en espacios aéreos de media y alta densidad de tráfico se ha basado en tecnologías complejas que requieren importantes infraestructuras como son el radar primario de vigilancia (PSR) y el radar secundario de vigilancia (SSR). La filosofía de los programas SESAR y NextGen siguiendo las directrices de la OACI es la de alejarse de las tecnologías basadas en tierra para evolucionar hacia nuevas tecnologías más dinámicas basadas en satélite como la ADS-B. Pero hasta que la implementación y operación de la ADS-B sea completa, existirá un período de transición que implica la coexistencia de aeronaves equipadas o no con ADS-B. El objetivo de la presente Tesis es determinar las metodologías y algoritmos más adecuados para poder hibridar las dos tecnologías descritas anteriormente, utilizando para ello un receptor de bajo coste con antena estática omnidireccional, que analice todas las señales presentes en el canal que comparten el SSR y ADS-B. Mediante esta hibridación se podrá obtener la posición de cualquier aeronave que transmita respuestas a interrogaciones SSR, en cualquiera de sus modos de trabajo, o directamente mensajes de posición ADS-B. Para desarrollar los algoritmos propuestos, además del hardware correspondiente, se han utilizado las aplicaciones LabVIEW para funciones de adquisición de datos reales, y el software MATLAB® para el desarrollo de algoritmos y análisis de datos. La validación de resultados se ha realizado mediante los propios mensajes de posición ADS-B y a través de las trazas radar proporcionadas por la entidad pública empresarial ENAIRE. La técnica desarrollada es autónoma, y no ha requerido de ninguna otra entrada que no sea la recepción omnidireccional de las señales. Sin embargo para la validación de resultados se ha utilizado información pública de las ubicaciones de la red de estaciones SSR desplegadas sobre territorio español y portugués y trazas radar. Los resultados obtenidos demuestran, que con técnicas basadas en superficies de situación definidas por los tiempos de llegada de las respuestas, es posible determinar con una precisión aceptable la posición de las estaciones SSR y la posición de cualquier aeronave que responda mediante el Modo A a éstas. ABSTRACT Air transport is a strategic sector for the economic growth of any country. The air traffic management system (ATM) aims at the safe and efficient movement of aircraft while operating within the airspace and airports, where safety, in the tactical phase, is managed by the air traffic control services. Through the air traffic control processes, aircraft are monitored by sensors, regulated and guided in an organized and safe manner. It is precisely on surveillance where this thesis is focused, developing new concepts that provide a 'low cost' surveillance information based on existing signals provided by currently secondary radar infrastructure and satellite-based positioning systems used by ADS-B. Having a deeper knowledge and a real-time access to the trajectories of the aircraft, is an element of added value not only for the provision of air traffic control services, but also for all air transport or research actors. This is one of the key elements in the operational concept proposed by the two large scale existing technological projects, SESAR in Europe and NextGen in the US. In recent decades, air traffic control in medium and high traffic density areas has been based on complex technologies requiring major infrastructures, such as the primary surveillance radar (PSR) and secondary surveillance radar (SSR). The philosophy of SESAR and NextGen programs, both following the guidelines of ICAO, is to move away from land-based technologies and evolving into some new and more dynamic satellite-based technologies such as ADS-B. Nevertheless, until the ADS-B implementation and operation is fully achieved, there will be a transitional period where aircraft with and without ADS-B equipment will have to coexist. The main objective of this thesis is to determine those methodologies and algorithms which are considered more appropriate to hybridize those two technologies, by using a low cost omnidirectional receiver, which analyzes all signals on the SSR and ADS-B shared channel. Through this hybridization, it is possible to obtain the position of any aircraft answering the SSR interrogations, in any of its modes of operation, or through the emission of ADS-B messages. To develop the proposed algorithms, LabVIEW application has been used for real-time data acquisition, as well as MATLAB software for algorithm development and data analysis, together with the corresponding hardware. The validation of results was performed using the ADS-B position messages and radar tracks provided by the Public Corporate Entity ENAIRE The developed technique is autonomous, and it does not require any other input other than the omnidirectional signal reception. However, for the validation of results, not only radar records have been used, but also public information regarding the position of SSR stations spread throughout the Spanish and Portuguese territory. The results show that using techniques based in the definition of positioning surfaces defined by the responses’ times of arrival, it is possible to determine with an acceptable level of accuracy both the position of the SSR stations as well as the position of any aircraft which transmits Mode A responses.

Parametric and structural self-adaptation of embedded systems using evolvable hardware

Los sistemas empotrados han sido concebidos tradicionalmente como sistemas de procesamiento específicos que realizan una tarea fija durante toda su vida útil. Para cumplir con requisitos estrictos de coste, tamaño y peso, el equipo de diseño debe optimizar su funcionamiento para condiciones muy específicas. Sin embargo, la demanda de mayor versatilidad, un funcionamiento más inteligente y, en definitiva, una mayor capacidad de procesamiento comenzaron a chocar con estas limitaciones, agravado por la incertidumbre asociada a entornos de operación cada vez más dinámicos donde comenzaban a ser desplegados progresivamente. Esto trajo como resultado una necesidad creciente de que los sistemas pudieran responder por si solos a eventos inesperados en tiempo diseño tales como: cambios en las características de los datos de entrada y el entorno del sistema en general; cambios en la propia plataforma de cómputo, por ejemplo debido a fallos o defectos de fabricación; y cambios en las propias especificaciones funcionales causados por unos objetivos del sistema dinámicos y cambiantes. Como consecuencia, la complejidad del sistema aumenta, pero a cambio se habilita progresivamente una capacidad de adaptación autónoma sin intervención humana a lo largo de la vida útil, permitiendo que tomen sus propias decisiones en tiempo de ejecución. Éstos sistemas se conocen, en general, como sistemas auto-adaptativos y tienen, entre otras características, las de auto-configuración, auto-optimización y auto-reparación. Típicamente, la parte soft de un sistema es mayoritariamente la única utilizada para proporcionar algunas capacidades de adaptación a un sistema. Sin embargo, la proporción rendimiento/potencia en dispositivos software como microprocesadores en muchas ocasiones no es adecuada para sistemas empotrados. En este escenario, el aumento resultante en la complejidad de las aplicaciones está siendo abordado parcialmente mediante un aumento en la complejidad de los dispositivos en forma de multi/many-cores; pero desafortunadamente, esto hace que el consumo de potencia también aumente. Además, la mejora en metodologías de diseño no ha sido acorde como para poder utilizar toda la capacidad de cómputo disponible proporcionada por los núcleos. Por todo ello, no se están satisfaciendo adecuadamente las demandas de cómputo que imponen las nuevas aplicaciones. La solución tradicional para mejorar la proporción rendimiento/potencia ha sido el cambio a unas especificaciones hardware, principalmente usando ASICs. Sin embargo, los costes de un ASIC son altamente prohibitivos excepto en algunos casos de producción en masa y además la naturaleza estática de su estructura complica la solución a las necesidades de adaptación. Los avances en tecnologías de fabricación han hecho que la FPGA, una vez lenta y pequeña, usada como glue logic en sistemas mayores, haya crecido hasta convertirse en un dispositivo de cómputo reconfigurable de gran potencia, con una cantidad enorme de recursos lógicos computacionales y cores hardware empotrados de procesamiento de señal y de propósito general. Sus capacidades de reconfiguración han permitido combinar la flexibilidad propia del software con el rendimiento del procesamiento en hardware, lo que tiene la potencialidad de provocar un cambio de paradigma en arquitectura de computadores, pues el hardware no puede ya ser considerado más como estático. El motivo es que como en el caso de las FPGAs basadas en tecnología SRAM, la reconfiguración parcial dinámica (DPR, Dynamic Partial Reconfiguration) es posible. Esto significa que se puede modificar (reconfigurar) un subconjunto de los recursos computacionales en tiempo de ejecución mientras el resto permanecen activos. Además, este proceso de reconfiguración puede ser ejecutado internamente por el propio dispositivo. El avance tecnológico en dispositivos hardware reconfigurables se encuentra recogido bajo el campo conocido como Computación Reconfigurable (RC, Reconfigurable Computing). Uno de los campos de aplicación más exóticos y menos convencionales que ha posibilitado la computación reconfigurable es el conocido como Hardware Evolutivo (EHW, Evolvable Hardware), en el cual se encuentra enmarcada esta tesis. La idea principal del concepto consiste en convertir hardware que es adaptable a través de reconfiguración en una entidad evolutiva sujeta a las fuerzas de un proceso evolutivo inspirado en el de las especies biológicas naturales, que guía la dirección del cambio. Es una aplicación más del campo de la Computación Evolutiva (EC, Evolutionary Computation), que comprende una serie de algoritmos de optimización global conocidos como Algoritmos Evolutivos (EA, Evolutionary Algorithms), y que son considerados como algoritmos universales de resolución de problemas. En analogía al proceso biológico de la evolución, en el hardware evolutivo el sujeto de la evolución es una población de circuitos que intenta adaptarse a su entorno mediante una adecuación progresiva generación tras generación. Los individuos pasan a ser configuraciones de circuitos en forma de bitstreams caracterizados por descripciones de circuitos reconfigurables. Seleccionando aquellos que se comportan mejor, es decir, que tienen una mejor adecuación (o fitness) después de ser evaluados, y usándolos como padres de la siguiente generación, el algoritmo evolutivo crea una nueva población hija usando operadores genéticos como la mutación y la recombinación. Según se van sucediendo generaciones, se espera que la población en conjunto se aproxime a la solución óptima al problema de encontrar una configuración del circuito adecuada que satisfaga las especificaciones. El estado de la tecnología de reconfiguración después de que la familia de FPGAs XC6200 de Xilinx fuera retirada y reemplazada por las familias Virtex a finales de los 90, supuso un gran obstáculo para el avance en hardware evolutivo; formatos de bitstream cerrados (no conocidos públicamente); dependencia de herramientas del fabricante con soporte limitado de DPR; una velocidad de reconfiguración lenta; y el hecho de que modificaciones aleatorias del bitstream pudieran resultar peligrosas para la integridad del dispositivo, son algunas de estas razones. Sin embargo, una propuesta a principios de los años 2000 permitió mantener la investigación en el campo mientras la tecnología de DPR continuaba madurando, el Circuito Virtual Reconfigurable (VRC, Virtual Reconfigurable Circuit). En esencia, un VRC en una FPGA es una capa virtual que actúa como un circuito reconfigurable de aplicación específica sobre la estructura nativa de la FPGA que reduce la complejidad del proceso reconfiguración y aumenta su velocidad (comparada con la reconfiguración nativa). Es un array de nodos computacionales especificados usando descripciones HDL estándar que define recursos reconfigurables ad-hoc: multiplexores de rutado y un conjunto de elementos de procesamiento configurables, cada uno de los cuales tiene implementadas todas las funciones requeridas, que pueden seleccionarse a través de multiplexores tal y como ocurre en una ALU de un microprocesador. Un registro grande actúa como memoria de configuración, por lo que la reconfiguración del VRC es muy rápida ya que tan sólo implica la escritura de este registro, el cual controla las señales de selección del conjunto de multiplexores. Sin embargo, esta capa virtual provoca: un incremento de área debido a la implementación simultánea de cada función en cada nodo del array más los multiplexores y un aumento del retardo debido a los multiplexores, reduciendo la frecuencia de funcionamiento máxima. La naturaleza del hardware evolutivo, capaz de optimizar su propio comportamiento computacional, le convierten en un buen candidato para avanzar en la investigación sobre sistemas auto-adaptativos. Combinar un sustrato de cómputo auto-reconfigurable capaz de ser modificado dinámicamente en tiempo de ejecución con un algoritmo empotrado que proporcione una dirección de cambio, puede ayudar a satisfacer los requisitos de adaptación autónoma de sistemas empotrados basados en FPGA. La propuesta principal de esta tesis está por tanto dirigida a contribuir a la auto-adaptación del hardware de procesamiento de sistemas empotrados basados en FPGA mediante hardware evolutivo. Esto se ha abordado considerando que el comportamiento computacional de un sistema puede ser modificado cambiando cualquiera de sus dos partes constitutivas: una estructura hard subyacente y un conjunto de parámetros soft. De esta distinción, se derivan dos lineas de trabajo. Por un lado, auto-adaptación paramétrica, y por otro auto-adaptación estructural. El objetivo perseguido en el caso de la auto-adaptación paramétrica es la implementación de técnicas de optimización evolutiva complejas en sistemas empotrados con recursos limitados para la adaptación paramétrica online de circuitos de procesamiento de señal. La aplicación seleccionada como prueba de concepto es la optimización para tipos muy específicos de imágenes de los coeficientes de los filtros de transformadas wavelet discretas (DWT, DiscreteWavelet Transform), orientada a la compresión de imágenes. Por tanto, el objetivo requerido de la evolución es una compresión adaptativa y más eficiente comparada con los procedimientos estándar. El principal reto radica en reducir la necesidad de recursos de supercomputación para el proceso de optimización propuesto en trabajos previos, de modo que se adecúe para la ejecución en sistemas empotrados. En cuanto a la auto-adaptación estructural, el objetivo de la tesis es la implementación de circuitos auto-adaptativos en sistemas evolutivos basados en FPGA mediante un uso eficiente de sus capacidades de reconfiguración nativas. En este caso, la prueba de concepto es la evolución de tareas de procesamiento de imagen tales como el filtrado de tipos desconocidos y cambiantes de ruido y la detección de bordes en la imagen. En general, el objetivo es la evolución en tiempo de ejecución de tareas de procesamiento de imagen desconocidas en tiempo de diseño (dentro de un cierto grado de complejidad). En este caso, el objetivo de la propuesta es la incorporación de DPR en EHW para evolucionar la arquitectura de un array sistólico adaptable mediante reconfiguración cuya capacidad de evolución no había sido estudiada previamente. Para conseguir los dos objetivos mencionados, esta tesis propone originalmente una plataforma evolutiva que integra un motor de adaptación (AE, Adaptation Engine), un motor de reconfiguración (RE, Reconfiguration Engine) y un motor computacional (CE, Computing Engine) adaptable. El el caso de adaptación paramétrica, la plataforma propuesta está caracterizada por: • un CE caracterizado por un núcleo de procesamiento hardware de DWT adaptable mediante registros reconfigurables que contienen los coeficientes de los filtros wavelet • un algoritmo evolutivo como AE que busca filtros wavelet candidatos a través de un proceso de optimización paramétrica desarrollado específicamente para sistemas caracterizados por recursos de procesamiento limitados • un nuevo operador de mutación simplificado para el algoritmo evolutivo utilizado, que junto con un mecanismo de evaluación rápida de filtros wavelet candidatos derivado de la literatura actual, asegura la viabilidad de la búsqueda evolutiva asociada a la adaptación de wavelets. En el caso de adaptación estructural, la plataforma propuesta toma la forma de: • un CE basado en una plantilla de array sistólico reconfigurable de 2 dimensiones compuesto de nodos de procesamiento reconfigurables • un algoritmo evolutivo como AE que busca configuraciones candidatas del array usando un conjunto de funcionalidades de procesamiento para los nodos disponible en una biblioteca accesible en tiempo de ejecución • un RE hardware que explota la capacidad de reconfiguración nativa de las FPGAs haciendo un uso eficiente de los recursos reconfigurables del dispositivo para cambiar el comportamiento del CE en tiempo de ejecución • una biblioteca de elementos de procesamiento reconfigurables caracterizada por bitstreams parciales independientes de la posición, usados como el conjunto de configuraciones disponibles para los nodos de procesamiento del array Las contribuciones principales de esta tesis se pueden resumir en la siguiente lista: • Una plataforma evolutiva basada en FPGA para la auto-adaptación paramétrica y estructural de sistemas empotrados compuesta por un motor computacional (CE), un motor de adaptación (AE) evolutivo y un motor de reconfiguración (RE). Esta plataforma se ha desarrollado y particularizado para los casos de auto-adaptación paramétrica y estructural. • En cuanto a la auto-adaptación paramétrica, las contribuciones principales son: – Un motor computacional adaptable mediante registros que permite la adaptación paramétrica de los coeficientes de una implementación hardware adaptativa de un núcleo de DWT. – Un motor de adaptación basado en un algoritmo evolutivo desarrollado específicamente para optimización numérica, aplicada a los coeficientes de filtros wavelet en sistemas empotrados con recursos limitados. – Un núcleo IP de DWT auto-adaptativo en tiempo de ejecución para sistemas empotrados que permite la optimización online del rendimiento de la transformada para compresión de imágenes en entornos específicos de despliegue, caracterizados por tipos diferentes de señal de entrada. – Un modelo software y una implementación hardware de una herramienta para la construcción evolutiva automática de transformadas wavelet específicas. • Por último, en cuanto a la auto-adaptación estructural, las contribuciones principales son: – Un motor computacional adaptable mediante reconfiguración nativa de FPGAs caracterizado por una plantilla de array sistólico en dos dimensiones de nodos de procesamiento reconfigurables. Es posible mapear diferentes tareas de cómputo en el array usando una biblioteca de elementos sencillos de procesamiento reconfigurables. – Definición de una biblioteca de elementos de procesamiento apropiada para la síntesis autónoma en tiempo de ejecución de diferentes tareas de procesamiento de imagen. – Incorporación eficiente de la reconfiguración parcial dinámica (DPR) en sistemas de hardware evolutivo, superando los principales inconvenientes de propuestas previas como los circuitos reconfigurables virtuales (VRCs). En este trabajo también se comparan originalmente los detalles de implementación de ambas propuestas. – Una plataforma tolerante a fallos, auto-curativa, que permite la recuperación funcional online en entornos peligrosos. La plataforma ha sido caracterizada desde una perspectiva de tolerancia a fallos: se proponen modelos de fallo a nivel de CLB y de elemento de procesamiento, y usando el motor de reconfiguración, se hace un análisis sistemático de fallos para un fallo en cada elemento de procesamiento y para dos fallos acumulados. – Una plataforma con calidad de filtrado dinámica que permite la adaptación online a tipos de ruido diferentes y diferentes comportamientos computacionales teniendo en cuenta los recursos de procesamiento disponibles. Por un lado, se evolucionan filtros con comportamientos no destructivos, que permiten esquemas de filtrado en cascada escalables; y por otro, también se evolucionan filtros escalables teniendo en cuenta requisitos computacionales de filtrado cambiantes dinámicamente. Este documento está organizado en cuatro partes y nueve capítulos. La primera parte contiene el capítulo 1, una introducción y motivación sobre este trabajo de tesis. A continuación, el marco de referencia en el que se enmarca esta tesis se analiza en la segunda parte: el capítulo 2 contiene una introducción a los conceptos de auto-adaptación y computación autonómica (autonomic computing) como un campo de investigación más general que el muy específico de este trabajo; el capítulo 3 introduce la computación evolutiva como la técnica para dirigir la adaptación; el capítulo 4 analiza las plataformas de computación reconfigurables como la tecnología para albergar hardware auto-adaptativo; y finalmente, el capítulo 5 define, clasifica y hace un sondeo del campo del hardware evolutivo. Seguidamente, la tercera parte de este trabajo contiene la propuesta, desarrollo y resultados obtenidos: mientras que el capítulo 6 contiene una declaración de los objetivos de la tesis y la descripción de la propuesta en su conjunto, los capítulos 7 y 8 abordan la auto-adaptación paramétrica y estructural, respectivamente. Finalmente, el capítulo 9 de la parte 4 concluye el trabajo y describe caminos de investigación futuros. ABSTRACT Embedded systems have traditionally been conceived to be specific-purpose computers with one, fixed computational task for their whole lifetime. Stringent requirements in terms of cost, size and weight forced designers to highly optimise their operation for very specific conditions. However, demands for versatility, more intelligent behaviour and, in summary, an increased computing capability began to clash with these limitations, intensified by the uncertainty associated to the more dynamic operating environments where they were progressively being deployed. This brought as a result an increasing need for systems to respond by themselves to unexpected events at design time, such as: changes in input data characteristics and system environment in general; changes in the computing platform itself, e.g., due to faults and fabrication defects; and changes in functional specifications caused by dynamically changing system objectives. As a consequence, systems complexity is increasing, but in turn, autonomous lifetime adaptation without human intervention is being progressively enabled, allowing them to take their own decisions at run-time. This type of systems is known, in general, as selfadaptive, and are able, among others, of self-configuration, self-optimisation and self-repair. Traditionally, the soft part of a system has mostly been so far the only place to provide systems with some degree of adaptation capabilities. However, the performance to power ratios of software driven devices like microprocessors are not adequate for embedded systems in many situations. In this scenario, the resulting rise in applications complexity is being partly addressed by rising devices complexity in the form of multi and many core devices; but sadly, this keeps on increasing power consumption. Besides, design methodologies have not been improved accordingly to completely leverage the available computational power from all these cores. Altogether, these factors make that the computing demands new applications pose are not being wholly satisfied. The traditional solution to improve performance to power ratios has been the switch to hardware driven specifications, mainly using ASICs. However, their costs are highly prohibitive except for some mass production cases and besidesthe static nature of its structure complicates the solution to the adaptation needs. The advancements in fabrication technologies have made that the once slow, small FPGA used as glue logic in bigger systems, had grown to be a very powerful, reconfigurable computing device with a vast amount of computational logic resources and embedded, hardened signal and general purpose processing cores. Its reconfiguration capabilities have enabled software-like flexibility to be combined with hardware-like computing performance, which has the potential to cause a paradigm shift in computer architecture since hardware cannot be considered as static anymore. This is so, since, as is the case with SRAMbased FPGAs, Dynamic Partial Reconfiguration (DPR) is possible. This means that subsets of the FPGA computational resources can now be changed (reconfigured) at run-time while the rest remains active. Besides, this reconfiguration process can be triggered internally by the device itself. This technological boost in reconfigurable hardware devices is actually covered under the field known as Reconfigurable Computing. One of the most exotic fields of application that Reconfigurable Computing has enabled is the known as Evolvable Hardware (EHW), in which this dissertation is framed. The main idea behind the concept is turning hardware that is adaptable through reconfiguration into an evolvable entity subject to the forces of an evolutionary process, inspired by that of natural, biological species, that guides the direction of change. It is yet another application of the field of Evolutionary Computation (EC), which comprises a set of global optimisation algorithms known as Evolutionary Algorithms (EAs), considered as universal problem solvers. In analogy to the biological process of evolution, in EHW the subject of evolution is a population of circuits that tries to get adapted to its surrounding environment by progressively getting better fitted to it generation after generation. Individuals become circuit configurations representing bitstreams that feature reconfigurable circuit descriptions. By selecting those that behave better, i.e., with a higher fitness value after being evaluated, and using them as parents of the following generation, the EA creates a new offspring population by using so called genetic operators like mutation and recombination. As generations succeed one another, the whole population is expected to approach to the optimum solution to the problem of finding an adequate circuit configuration that fulfils system objectives. The state of reconfiguration technology after Xilinx XC6200 FPGA family was discontinued and replaced by Virtex families in the late 90s, was a major obstacle for advancements in EHW; closed (non publicly known) bitstream formats; dependence on manufacturer tools with highly limiting support of DPR; slow speed of reconfiguration; and random bitstream modifications being potentially hazardous for device integrity, are some of these reasons. However, a proposal in the first 2000s allowed to keep investigating in this field while DPR technology kept maturing, the Virtual Reconfigurable Circuit (VRC). In essence, a VRC in an FPGA is a virtual layer acting as an application specific reconfigurable circuit on top of an FPGA fabric that reduces the complexity of the reconfiguration process and increases its speed (compared to native reconfiguration). It is an array of computational nodes specified using standard HDL descriptions that define ad-hoc reconfigurable resources; routing multiplexers and a set of configurable processing elements, each one containing all the required functions, which are selectable through functionality multiplexers as in microprocessor ALUs. A large register acts as configuration memory, so VRC reconfiguration is very fast given it only involves writing this register, which drives the selection signals of the set of multiplexers. However, large overheads are introduced by this virtual layer; an area overhead due to the simultaneous implementation of every function in every node of the array plus the multiplexers, and a delay overhead due to the multiplexers, which also reduces maximum frequency of operation. The very nature of Evolvable Hardware, able to optimise its own computational behaviour, makes it a good candidate to advance research in self-adaptive systems. Combining a selfreconfigurable computing substrate able to be dynamically changed at run-time with an embedded algorithm that provides a direction for change, can help fulfilling requirements for autonomous lifetime adaptation of FPGA-based embedded systems. The main proposal of this thesis is hence directed to contribute to autonomous self-adaptation of the underlying computational hardware of FPGA-based embedded systems by means of Evolvable Hardware. This is tackled by considering that the computational behaviour of a system can be modified by changing any of its two constituent parts: an underlying hard structure and a set of soft parameters. Two main lines of work derive from this distinction. On one side, parametric self-adaptation and, on the other side, structural self-adaptation. The goal pursued in the case of parametric self-adaptation is the implementation of complex evolutionary optimisation techniques in resource constrained embedded systems for online parameter adaptation of signal processing circuits. The application selected as proof of concept is the optimisation of Discrete Wavelet Transforms (DWT) filters coefficients for very specific types of images, oriented to image compression. Hence, adaptive and improved compression efficiency, as compared to standard techniques, is the required goal of evolution. The main quest lies in reducing the supercomputing resources reported in previous works for the optimisation process in order to make it suitable for embedded systems. Regarding structural self-adaptation, the thesis goal is the implementation of self-adaptive circuits in FPGA-based evolvable systems through an efficient use of native reconfiguration capabilities. In this case, evolution of image processing tasks such as filtering of unknown and changing types of noise and edge detection are the selected proofs of concept. In general, evolving unknown image processing behaviours (within a certain complexity range) at design time is the required goal. In this case, the mission of the proposal is the incorporation of DPR in EHW to evolve a systolic array architecture adaptable through reconfiguration whose evolvability had not been previously checked. In order to achieve the two stated goals, this thesis originally proposes an evolvable platform that integrates an Adaptation Engine (AE), a Reconfiguration Engine (RE) and an adaptable Computing Engine (CE). In the case of parametric adaptation, the proposed platform is characterised by: • a CE featuring a DWT hardware processing core adaptable through reconfigurable registers that holds wavelet filters coefficients • an evolutionary algorithm as AE that searches for candidate wavelet filters through a parametric optimisation process specifically developed for systems featured by scarce computing resources • a new, simplified mutation operator for the selected EA, that together with a fast evaluation mechanism of candidate wavelet filters derived from existing literature, assures the feasibility of the evolutionary search involved in wavelets adaptation In the case of structural adaptation, the platform proposal takes the form of: • a CE based on a reconfigurable 2D systolic array template composed of reconfigurable processing nodes • an evolutionary algorithm as AE that searches for candidate configurations of the array using a set of computational functionalities for the nodes available in a run time accessible library • a hardware RE that exploits native DPR capabilities of FPGAs and makes an efficient use of the available reconfigurable resources of the device to change the behaviour of the CE at run time • a library of reconfigurable processing elements featured by position-independent partial bitstreams used as the set of available configurations for the processing nodes of the array Main contributions of this thesis can be summarised in the following list. • An FPGA-based evolvable platform for parametric and structural self-adaptation of embedded systems composed of a Computing Engine, an evolutionary Adaptation Engine and a Reconfiguration Engine. This platform is further developed and tailored for both parametric and structural self-adaptation. • Regarding parametric self-adaptation, main contributions are: – A CE adaptable through reconfigurable registers that enables parametric adaptation of the coefficients of an adaptive hardware implementation of a DWT core. – An AE based on an Evolutionary Algorithm specifically developed for numerical optimisation applied to wavelet filter coefficients in resource constrained embedded systems. – A run-time self-adaptive DWT IP core for embedded systems that allows for online optimisation of transform performance for image compression for specific deployment environments characterised by different types of input signals. – A software model and hardware implementation of a tool for the automatic, evolutionary construction of custom wavelet transforms. • Lastly, regarding structural self-adaptation, main contributions are: – A CE adaptable through native FPGA fabric reconfiguration featured by a two dimensional systolic array template of reconfigurable processing nodes. Different processing behaviours can be automatically mapped in the array by using a library of simple reconfigurable processing elements. – Definition of a library of such processing elements suited for autonomous runtime synthesis of different image processing tasks. – Efficient incorporation of DPR in EHW systems, overcoming main drawbacks from the previous approach of virtual reconfigurable circuits. Implementation details for both approaches are also originally compared in this work. – A fault tolerant, self-healing platform that enables online functional recovery in hazardous environments. The platform has been characterised from a fault tolerance perspective: fault models at FPGA CLB level and processing elements level are proposed, and using the RE, a systematic fault analysis for one fault in every processing element and for two accumulated faults is done. – A dynamic filtering quality platform that permits on-line adaptation to different types of noise and different computing behaviours considering the available computing resources. On one side, non-destructive filters are evolved, enabling scalable cascaded filtering schemes; and on the other, size-scalable filters are also evolved considering dynamically changing computational filtering requirements. This dissertation is organized in four parts and nine chapters. First part contains chapter 1, the introduction to and motivation of this PhD work. Following, the reference framework in which this dissertation is framed is analysed in the second part: chapter 2 features an introduction to the notions of self-adaptation and autonomic computing as a more general research field to the very specific one of this work; chapter 3 introduces evolutionary computation as the technique to drive adaptation; chapter 4 analyses platforms for reconfigurable computing as the technology to hold self-adaptive hardware; and finally chapter 5 defines, classifies and surveys the field of Evolvable Hardware. Third part of the work follows, which contains the proposal, development and results obtained: while chapter 6 contains an statement of the thesis goals and the description of the proposal as a whole, chapters 7 and 8 address parametric and structural self-adaptation, respectively. Finally, chapter 9 in part 4 concludes the work and describes future research paths.

Metodología para la optimización y análisis de la respuesta de medios e infraestructuras en el sistema aeroportuario en operaciones invernales mediante modelos basados en algorítmos genéticos

En este estudio, englobado dentro del campo de la investigación operacional en aeropuertos, se considera el problema de la optimización de la secuencia de descontaminación de nieve de los tramos que componen el área de maniobras de un aeropuerto, denominado RM-AM. Este problema se enfrenta a la optimización de recursos limitados para retirar la nieve de las calles de rodadura y pistas, dejándolas en un estado aceptable para la operación de aeronaves. El campo de vuelos se divide en subconjuntos de tramos significativos para la operación y se establecen tiempos objetivo de apertura al tráfico de aeronaves. Se desarrollan varios algoritmos matemáticos en los que se proponen distintas funciones objetivo, como son la hora de finalización del proceso, la suma de las horas de finalización de cada tramo, o el retraso entre la hora estimada y la hora de finalización. Durante este proceso, se van introduciendo restricciones operativas relativas al cumplimiento de objetivos operativos parciales aplicados a las zonas de especial interés, o relativas a la operación de los equipos de descontaminación. El problema se resuelve mediante optimización basada en programación lineal. Los resultados de las pruebas computacionales se hacen sobre cinco modelos de área de maniobras en los que va creciendo la complejidad y el tamaño. Se comparan las prestaciones de los distintos algoritmos. Una vez definido el modelo matemático para la optiamización, se propone una metodología estructurada para abordar dicho problema para cualquier área de manobras. Se define una estrategia en la operación. Se acomete el área de maniobras por zonas, con la condición de que los subconjuntos de tramos significativos queden englobados dentro de una sola de estas zonas. El problema se resuelve mediante un proceso iterativo de optimización aplicado sucesivamente a las zonas que componen el área de maniobras durante cada iteración. Se analiza la repercusión de los resultados en los procesos DMAN, AMAN y TP, para la integración de los resultados en el cálculo de TSAT y EBIT. El método se particulariza para el caso del área de maniobras del Aeropuerto Adolfo Suárez Madrid Barajas. ABSTRACT This study, which lies within the field of operations research in airports, considers the optimisation of the sequence for clearing snow from stretches of the manoeuvring area of an airport, known as RM-AM. This issue involves the optimisation of limited resources to remove snow from taxiways and runways thereby leaving them in an acceptable condition for operating aircraft. The airfield is divided into subsets of significant stretches for the purpose of operations and target times are established during which these are open to aircraft traffic. The study contains several mathematical models each with different functions, such as the end time of the process, the sum of the end times of each stretch, and gap between the estimated and the real end times. During this process, we introduce different operating restrictions on partial fulfilment of the operational targets as applied to zones of special interest, or relating to the operation of the snow-clearing machines. The problem is solved by optimisation based on linear programming. Computational tests are carried out on five distinct models of the manoeuvring area, which cover increasingly complex situations and larger areas. The different algorithms are then compared to one other. Having defined the mathematical model for the optimisation, we then set out a structured methodology to deal with any type of manoeuvring area. In other words, we define an operational strategy. The airfield is divided into subsets of significant stretches for the purpose of operations and target times are set at which these are to be open to aircraft traffic. The manoeuvring area is also divided into zones, with the condition that the subsets of significant stretches lie within just one of these zones. The problem is solved by an iterative optimisation process based on linear programming applied successively to the zones that make up the manoeuvring area during each iteration. The impact of the results on DMAN, AMAN and TP processes is analysed for their integration into the calculation of TSAT and EBIT. The method is particularized for the case of the manoeuvring area of Adolfo Suarez Madrid - Barajas Airport.

Algoritmos de decisión para priorizar las acciones de restauración en el mantenimiento de redes

En la actualidad, cualquier compañía de telecomunicaciones que posea su propia red debe afrontar el problema del mantenimiento de la misma. Ofrecer un mínimo de calidad de servicio a sus clientes debe ser uno de sus objetivos principales. Esta calidad debe mantenerse aunque ocurran incidencias en la red. El presente trabajo pretende resolver el problema de priorizar el orden en que se restauran los cables, caminos y circuitos, dañados por una incidencia, dentro de una red troncal de transporte perteneciente a una operadora de telecomunicaciones. Tras un planteamiento detallado del problema y de todos los factores que influirán en la toma de decisión, en primer lugar se acomete una solución basada en Métodos Multicriterio Discretos, concretamente con el uso de ELECTRE I y AHP. A continuación se realiza una propuesta de solución basada en Redes Neuronales (con dos aproximaciones diferentes al problema). Por último se utiliza un método basado en la Optimización por Enjambre de Partículas (PSO), adaptado a un problema de permutación de enteros (ordenación), y con una forma particular de evaluar la mejor posición global del enjambre. Complementariamente se realiza una exposición de lo que es una empresa Operadora de telecomunicaciones, de sus departamentos y procesos internos, de los servicios que ofrece, de las redes sobre las que se soportan, y de los puntos clave a tener en cuenta en la implementación de sus sistemas informáticos de gestión integral. ABSTRACT: Nowadays, any telecommunications company that owns its own network must face the problem of maintaining it (service assurance). Provide a minimum quality of service to its customers must be one of its main objectives. This quality should be maintained although any incidents happen to occur in the network. This thesis aims to solve the problem of prioritizing the order in which the damaged cables, trails, path and circuits, within a backbone transport network, should be restored. This work begins with a detailed explanation about network maintenance issues and all the factors that influence decision-making problem. First of all, one solution based on Discrete Multicriteria methods is tried (ELECTRE I and AHP algorithms are used). Also, a solution based on neural networks (with two different approaches to the problem) is analyzed. Finally, this thesis proposes an algorithm based on Particle Swarm Optimization (PSO), adapted to a problem of integers permutation, and a particular way of evaluating the best overall position of the swarm method. In addition, there is included an exhibition about telecommunications companies, its departments, internal processes, services offered to clients, physical networks, and key points to consider when implementing its integrated management systems.

Desarrollo de un Procedimiento Basado en Algoritmos de Optimización para el Dimensionado de Absorbedores Puntuales Aplicados a la Conversión de Energía Undimotriz

La energía transportada por el oleaje a través de los océanos (energía undimotriz) se enmarca dentro de las denominadas energías oceánicas. Su aprovechamiento para generar energía eléctrica (o ser aprovechada de alguna otra forma) es una idea reflejada ya hace más de dos siglos en una patente (1799). Desde entonces, y con especial intensidad desde los años 70, ha venido despertando el interés de instituciones ligadas al I+D+i y empresas del sector energético y tecnológico, debido principalmente a la magnitud del recurso disponible. Actualmente se puede considerar al sector en un estado precomercial, con un amplio rango de dispositivos y tecnologías en diferente grado de desarrollo en los que ninguno destaca sobre los otros (ni ha demostrado su viabilidad económica), y sin que se aprecie una tendencia a converger un único dispositivo (o un número reducido de ellos). El recurso energético que se está tratando de aprovechar, pese a compartir la característica de no-controlabilidad con otras fuentes de energía renovable como la eólica o la solar, presenta una variabilidad adicional. De esta manera, diferentes localizaciones, pese a poder presentar recursos de contenido energético similar, presentan oleajes de características muy diferentes en términos de alturas y periodos de oleaje, y en la dispersión estadística de estos valores. Esta variabilidad en el oleaje hace que cobre especial relevancia la adecuación de los dispositivos de aprovechamiento de energía undimotriz (WEC: Wave Energy Converter) a su localización, de cara a mejorar su viabilidad económica. Parece razonable suponer que, en un futuro, el proceso de diseño de un parque de generación undimotriz implique un rediseño (en base a una tecnología conocida) para cada proyecto de implantación en una nueva localización. El objetivo de esta tesis es plantear un procedimiento de dimensionado de una tecnología de aprovechamiento de la energía undimotriz concreta: los absorbedores puntuales. Dicha metodología de diseño se plantea como un problema de optimización matemático, el cual se resuelve utilizando un algoritmo de optimización bioinspirado: evolución diferencial. Este planteamiento permite automatizar la fase previa de dimensionado implementando la metodología en un código de programación. El proceso de diseño de un WEC es un problema de ingería complejo, por lo que no considera factible el planteamiento de un diseño completo mediante un único procedimiento de optimización matemático. En vez de eso, se platea el proceso de diseño en diferentes etapas, de manera que la metodología desarrollada en esta tesis se utilice para obtener las dimensiones básicas de una solución de referencia de WEC, la cual será utilizada como punto de partida para continuar con las etapas posteriores del proceso de diseño. La metodología de dimensionado previo presentada en esta tesis parte de unas condiciones de contorno de diseño definidas previamente, tales como: localización, características del sistema de generación de energía eléctrica (PTO: Power Take-Off), estrategia de extracción de energía eléctrica y concepto concreto de WEC). Utilizando un algoritmo de evolución diferencial multi-objetivo se obtiene un conjunto de soluciones factibles (de acuerdo con una ciertas restricciones técnicas y dimensionales) y óptimas (de acuerdo con una serie de funciones objetivo de pseudo-coste y pseudo-beneficio). Dicho conjunto de soluciones o dimensiones de WEC es utilizado como caso de referencia en las posteriores etapas de diseño. En el documento de la tesis se presentan dos versiones de dicha metodología con dos modelos diferentes de evaluación de las soluciones candidatas. Por un lado, se presenta un modelo en el dominio de la frecuencia que presenta importantes simplificaciones en cuanto al tratamiento del recurso del oleaje. Este procedimiento presenta una menor carga computacional pero una mayor incertidumbre en los resultados, la cual puede traducirse en trabajo adicional en las etapas posteriores del proceso de diseño. Sin embargo, el uso de esta metodología resulta conveniente para realizar análisis paramétricos previos de las condiciones de contorno, tales como la localización seleccionada. Por otro lado, la segunda metodología propuesta utiliza modelos en el domino estocástico, lo que aumenta la carga computacional, pero permite obtener resultados con menos incertidumbre e información estadística muy útil para el proceso de diseño. Por este motivo, esta metodología es más adecuada para su uso en un proceso de dimensionado completo de un WEC. La metodología desarrollada durante la tesis ha sido utilizada en un proyecto industrial de evaluación energética preliminar de una planta de energía undimotriz. En dicho proceso de evaluación, el método de dimensionado previo fue utilizado en una primera etapa, de cara a obtener un conjunto de soluciones factibles de acuerdo con una serie de restricciones técnicas básicas. La selección y refinamiento de la geometría de la solución geométrica de WEC propuesta fue realizada a posteriori (por otros participantes del proyecto) utilizando un modelo detallado en el dominio del tiempo y un modelo de evaluación económica del dispositivo. El uso de esta metodología puede ayudar a reducir las iteraciones manuales y a mejorar los resultados obtenidos en estas últimas etapas del proyecto. ABSTRACT The energy transported by ocean waves (wave energy) is framed within the so-called oceanic energies. Its use to generate electric energy (or desalinate ocean water, etc.) is an idea expressed first time in a patent two centuries ago (1799). Ever since, but specially since the 1970’s, this energy has become interesting for R&D institutions and companies related with the technological and energetic sectors mainly because of the magnitude of available energy. Nowadays the development of this technology can be considered to be in a pre-commercial stage, with a wide range of devices and technologies developed to different degrees but with none standing out nor economically viable. Nor do these technologies seem ready to converge to a single device (or a reduce number of devices). The energy resource to be exploited shares its non-controllability with other renewable energy sources such as wind and solar. However, wave energy presents an additional short-term variability due to its oscillatory nature. Thus, different locations may show waves with similar energy content but different characteristics such as wave height or wave period. This variability in ocean waves makes it very important that the devices for harnessing wave energy (WEC: Wave Energy Converter) fit closely to the characteristics of their location in order to improve their economic viability. It seems reasonable to assume that, in the future, the process of designing a wave power plant will involve a re-design (based on a well-known technology) for each implementation project in any new location. The objective of this PhD thesis is to propose a dimensioning method for a specific wave-energy-harnessing technology: point absorbers. This design methodology is presented as a mathematical optimization problem solved by using an optimization bio-inspired algorithm: differential evolution. This approach allows automating the preliminary dimensioning stage by implementing the methodology in programmed code. The design process of a WEC is a complex engineering problem, so the complete design is not feasible using a single mathematical optimization procedure. Instead, the design process is proposed in different stages, so the methodology developed in this thesis is used for the basic dimensions of a reference solution of the WEC, which would be used as a starting point for the later stages of the design process. The preliminary dimensioning methodology presented in this thesis starts from some previously defined boundary conditions such as: location, power take-off (PTO) characteristic, strategy of energy extraction and specific WEC technology. Using a differential multi-objective evolutionary algorithm produces a set of feasible solutions (according to certain technical and dimensional constraints) and optimal solutions (according to a set of pseudo-cost and pseudo-benefit objective functions). This set of solutions or WEC dimensions are used as a reference case in subsequent stages of design. In the document of this thesis, two versions of this methodology with two different models of evaluation of candidate solutions are presented. On the one hand, a model in the frequency domain that has significant simplifications in the treatment of the wave resource is presented. This method implies a lower computational load but increased uncertainty in the results, which may lead to additional work in the later stages of the design process. However, use of this methodology is useful in order to perform previous parametric analysis of boundary conditions such as the selected location. On the other hand, the second method uses stochastic models, increasing the computational load, but providing results with smaller uncertainty and very useful statistical information for the design process. Therefore, this method is more suitable to be used in a detail design process for full dimensioning of the WEC. The methodology developed throughout the thesis has been used in an industrial project for preliminary energetic assessment of a wave energy power plant. In this assessment process, the method of previous dimensioning was used in the first stage, in order to obtain a set of feasible solutions according to a set of basic technical constraints. The geometry of the WEC was refined and selected subsequently (by other project participants) using a detailed model in the time domain and a model of economic evaluation of the device. Using this methodology can help to reduce the number of design iterations and to improve the results obtained in the last stages of the project.

Análisis y Diseño de Algoritmos de Control Discreto de Sistemas MIMO Lineales y No Lineales Aplicando Técnicas de Control de Estructura Variable

Dentro de las técnicas de control de procesos no lineales, los controladores de estructura variable con modos deslizantes (VSC-SM en sus siglas en inglés) han demostrado ser una solución robusta, por lo cual han sido ampliamente estudiados en las cuatro últimas décadas. Desde los años ochenta se han presentado varios trabajos enfocados a especificar controladores VSC aplicados a sistemas de tiempo discreto (DVSC), siendo uno de los mayores intereses de análisis obtener las mismas prestaciones de robustez e invarianza de los controladores VSC-SM. El objetivo principal del trabajo de Tesis Doctoral consiste en estudiar, analizar y proponer unos esquemas de diseño de controladores DVSC en procesos multivariable tanto lineales como no lineales. De dicho estudio se propone una nueva filosofía de diseño de superficies deslizantes estables donde se han considerado aspectos hasta ahora no estudiados en el uso de DVSC-SM como son las limitaciones físicas de los actuadores y la dinámica deslizante no ideal. Lo más novedoso es 1) la propuesta de una nueva metodología de diseño de superficies deslizantes aplicadas a sistemas MIMO lineales y la extensión del mismo al caso de sistemas multivariables no lineales y 2) la definición de una nueva ley de alcance y de una ley de control robusta aplicada a sistemas MIMO, tanto lineales como no lineales, incluyendo un esquema de reducción de chattering. Finalmente, con el fin de ilustrar la eficiencia de los esquemas presentados, se incluyen ejemplos numéricos relacionados con el tema tratado en cada uno de los capítulos de la memoria. ABSTRACT Over the last four decades, variable structure controllers with sliding mode (VSC-SM) have been extensively studied, demonstrating to be a robust solution among robust nonlinear processes control techniques. Since the late 80s, several research works have been focused on the application of VSC controllers applied to discrete time or sampled data systems, which are known as DVSC-SM, where the most extensive source of analysis has been devoted to the robustness and invariance properties of VSC-SM controllers when applied to discrete systems. The main aim of this doctoral thesis work is to study, analyze and propose a design scheme of DVSC-SM controllers for lineal and nonlinear multivariable discrete time processes. For this purpose, a new design philosophy is proposed, where various design features have been considered that have not been analyzed in DVSC design approaches. Among them, the physical limitations and the nonideal dynamic sliding mode dynamics. The most innovative aspect is the inclusion of a new design methodology applied to lineal sliding surfaces MIMO systems and the extension to nonlinear multivariable systems, in addition to a new robust control law applied to lineal and nonlinear MIMO systems, including a chattering reduction scheme. Finally, to illustrate the efficiency of the proposed schemes, several numerical examples applied to lineal and nonlinear systems are included.

Sistemas radiolarios: geometrías y arquitecturas derivadas

Uno de los temas más importantes dentro del debate contemporáneo, es el que se refiere a la sostenibilidad a largo plazo de la sociedad tal y como la entendemos hoy. El ser humano está recuperando la sensibilidad perdida que le concebía como una pieza más dentro del ciclo natural de la vida. Por fin hemos entendido que no podemos ser auto suficientes e independientes del entorno natural que nos rodea. Más allá del respeto y del cuidado, está abierta la puerta del conocimiento infinito que nos brinda la naturaleza a todos los niveles y a todas las escalas. Dentro de la disciplina arquitectónica han existido ejemplos como Antoni Gaudí o Frei Otto que han referenciado su obra en el mundo Natural, encontrando en él las estrategias y bases para el diseño arquitectónico. Sin embargo han sido una minoría dentro del enorme elenco de arquitectos defensores del ángulo recto. En las últimas décadas, la tendencia está cambiando. No nos referimos tanto a la sensibilidad creciente por conseguir una mayor eficiencia energética que ha llevado a una puesta en valor de la arquitectura vernácula, trasladando su sabiduría a las estrategias bioclimáticas. Nos referimos a un caso específico dentro del amplio abanico de formas arquitectónicas que han aparecido gracias a la incorporación de las herramientas computacionales en el diseño y la producción. Las arquitecturas que nos interesan son las que aprovechan estas técnicas para analizar e interpretar las estrategias complejas y altamente eficientes que encontramos en la naturaleza, y trasladarlas a la disciplina arquitectónica. Esta tendencia que se enmarca dentro de la Biomímesis o Biomimética es conocida con el nombre de Bioarquitectura. La presente tesis trata de morfología y sobre todo de morfogénesis. El término morfología se refiere al estudio de una forma concreta que nos permite entender un caso específico, nuestro foco de atención se centra sin embargo en la morfogénesis, es decir, en el estudio de los procesos de generación de esas formas, para poder reproducir patrones y generar abanicos de casos adaptables y reconfigurables. El hecho de estudiar la forma no quiere decir que ésta sea una tesis “formalista” con la connotación peyorativa y gestual que se le suele atribuir a este término. La investigación concibe el concepto de forma como lo hace el mundo natural: forma como síntesis de eficiencia. No hay ninguna forma natural gratuita, que no cumpla una función determinada y que no se desarrolle con el mínimo material y gaste la mínima energía posible. Este afán por encontrar la “forma eficaz” es lo que nos hace traspasar la frontera de la arquitectura formalista. El camino de investigación morfológica se traza, como el título de la tesis indica, siguiendo el hilo conductor concreto de los radiolarios. Estos microorganismos unicelulares poseen unos esqueletos tan complejos que para poder entender su morfología es necesario establecer un amplio recorrido que abarca más de 4.000 años de conocimiento humano. Desde el descubrimiento de los sólidos platónicos, poliedros que configuran muchas de las formas globales de estos esqueletos; hasta la aplicación de los algoritmos generativos, que permiten entender y reproducir los patrones de comportamiento que existen detrás de los sistemas de compactación y teselación irregular de los esqueletos radiolarios. La tesis no pretende plantear el problema desde un punto de vista biológico, ni paleontológico, aunque inevitablemente en el primer capítulo se realiza un análisis referenciado del estado del conocimiento científico actual. Sí se analizan en mayor profundidad cuestiones morfológicas y se tratan los diferentes posicionamientos desde los cuales estos microorganismos han servido de referencia en la disciplina arquitectónica. Además encontramos necesario analizar otros patrones naturales que comparten estrategias generativas con los esqueletos radiolarios. Como ya hemos apuntado, en el segundo capítulo se aborda un recorrido desde las geometrías más básicas a las más complejas, que tienen relación con las estrategias de generación de las formas detectadas en los microorganismos. A su vez, el análisis de estas geometrías se intercala con ejemplos de aplicaciones dentro de la arquitectura, el diseño y el arte. Finalizando con un cronograma que sintetiza y relaciona las tres vías de investigación abordadas: natural, geométrica y arquitectónica. Tras los dos capítulos centrales, el capítulo final recapitula las estrategias analizadas y aplica el conocimiento adquirido en la tesis, mediante la realización de diferentes prototipos que abarcan desde el dibujo analítico tradicional, a la fabricación digital y el diseño paramétrico, pasando por modelos analógicos de escayola, barras metálicas, resina, silicona, látex, etc. ABSTRACT One of the most important issues in the contemporary debate, is the one concerning the long-term sustainability of society as we understand it today. The human being is recovering the lost sensitivity that conceived us as part of the natural cycle of life. We have finally understood that we cannot be self-sufficient and independent of the natural environment which surrounds us. Beyond respect and care, we’ll find that the gateway to the infinite knowledge that nature provides us at all levels and at all scales is open. Within the architectural discipline, there have been remarkable examples such as Antoni Gaudí or Frei Otto who have inspired their work in the natural world. Both, found in nature the strategies and basis of their architectural designs. However, they have been a minority within the huge cast of architects defenders of the right angle. In recent decades, the trend is changing. We are not referring to the growing sensitivity in trying to achieve energy efficiency that has led to an enhancement of vernacular architecture, transferring its wisdom to bioclimatic strategies. We refer to a specific case within the wide range of architectural forms that have appeared thanks to the integration of computer tools in both design and production processes. We are interested in architectures that exploit these techniques to analyse and interpret the complex and highly efficient strategies found in nature, and shift them to the discipline of architecture. This trend, which is being implemented in the framework of the Biomimicry or biomimetics, is called Bioarchitecture. This thesis deals with morphology and more specifically with morphogenesis. Morphology is the study of a concrete form that allows us to understand a specific case. However, our focus is centered in morphogenesis or, in other words, the study of the processes of generation of these forms, in order to replicate patterns and generate a range of adaptable and reconfigurable cases. The fact of studying shapes does not mean that this is a “formalistic” thesis with the pejorative connotation that is often attributed to this term. This study conceives the concept of shape as Nature does: as a synthesis of efficiency. There is no meaningless form in nature. Furthermore, forms and shapes in nature play a particular role and are developed with minimum energetic consumption. This quest to find the efficient shape is what makes us go beyond formalistic architecture. The road of morphological investigation is traced, as the title of the thesis suggests, following the thread of radiolaria. These single-cell microorganisms possess very complex skeletons, so to be able to understand their morphology we must establish a wide spectrum which spans throughout more than 4.000 years of human knowledge. From the discovery of the platonic solids, polyhedrons which configure a huge range of global shapes of these skeletons, through the application of generative algorithms which allow us to understand and recreate the behavioral patterns behind the systems of compression and irregular tessellation of the radiolarian skeletons. The thesis does not pretend to lay out the problem from a biological, paleontological standpoint, although inevitably the first chapter is developed through an analysis in reference to the current state of the science. A deeper analysis of morphological aspects and different positionings is taken into account where these microorganisms have served as reference in the architectonic discipline. In addition we find necessary to analyse other natural patterns which share generative strategies with radiolarian skeletons. Aforementioned, in the second chapter an itinerary of the most basic geometries to the more complex ones is addressed. These are related, in this chapter, to the generative strategies of the shapes found in microorganisms. At the same time, the analysis of these geometries is placed among examples of applications inside the fields of architecture, design and the arts. To come to an end, a time chart synthesizes and relates the three investigation paths addressed: natural, geometrical and architectonic. After the two central chapters, the final chapter summarises the strategies analysed and applies the knowledge acquired throughout the thesis. This final chapter is shaped by the realization of different prototypes which range from traditional analytical drawings, to digital fabrication and parametric design, going through plaster analogical models, metal bars, resin, silicone, latex, etc.

Estudio de algoritmos de detección de anomalías y su aplicación a entornos de ciberseguridad

Uno de los principales objetivos de los sistemas informáticos es ser capaces de detectar y controlar aquellos accesos no autorizados, o incluso prevenirlos antes de que se produzca una pérdida de valor en el sistema. Se busca encontrar un modelo general que englobe todos los posibles casos de entradas no deseadas al sistema y que sea capaz de aprender para detectar intrusiones futuras. En primer lugar se estudiará la relevancia de las técnicas utilizadas para el almacenamiento de la información. Big Data ilustra los elementos esenciales necesarios para el almacenamiento de los datos con un formato único identificable y unos atributos característicos que los definan, para su posterior análisis. El método de almacenamiento elegido influirá en las técnicas de análisis y captura de valor utilizadas, dado que existe una dependencia directa entre el formato en el que se almacena la información y el valor específico que se pretende obtener de ella. En segundo lugar se examinarán las distintas técnicas de análisis y captura de datos actuales, y los diferentes resultados que se pueden obtener. En este punto aparece el concepto de machine learning y su posible aplicación para detección de anomalías. La finalidad es lograr generalizar diferentes comportamientos a partir de una información no estructurada y generar un modelo aplicable a nuevas entradas al sistema que no son conocidas con anterioridad. En último lugar, se analizarán diferentes entornos de ciberseguridad y se propondrá un conjunto de recomendaciones de diseño o ajustes respecto a las técnicas mencionadas anteriormente, realizando una breve clasificación según las variables de entrada que se tienen y el resultado que se desea obtener. El propósito de este Trabajo de Fin de Grado es, por tanto, la comparación general de las diferentes técnicas actuales de detección de comportamientos anómalos en un sistema informático, tales como el aprendizaje de máquinas o minería de datos, así como de un planteamiento de cuáles son las mejores opciones según el tipo de valor que se desea extraer de la información almacenada.

Imputação de dados em experimentos multiambientais: novos algoritmos utilizando a decomposição por valores singulares

As análises biplot que utilizam os modelos de efeitos principais aditivos com inter- ação multiplicativa (AMMI) requerem matrizes de dados completas, mas, frequentemente os ensaios multiambientais apresentam dados faltantes. Nesta tese são propostas novas metodologias de imputação simples e múltipla que podem ser usadas para analisar da- dos desbalanceados em experimentos com interação genótipo por ambiente (G×E). A primeira, é uma nova extensão do método de validação cruzada por autovetor (Bro et al, 2008). A segunda, corresponde a um novo algoritmo não-paramétrico obtido por meio de modificações no método de imputação simples desenvolvido por Yan (2013). Também é incluído um estudo que considera sistemas de imputação recentemente relatados na literatura e os compara com o procedimento clássico recomendado para imputação em ensaios (G×E), ou seja, a combinação do algoritmo de Esperança-Maximização com os modelos AMMI ou EM-AMMI. Por último, são fornecidas generalizações da imputação simples descrita por Arciniegas-Alarcón et al. (2010) que mistura regressão com aproximação de posto inferior de uma matriz. Todas as metodologias têm como base a decomposição por valores singulares (DVS), portanto, são livres de pressuposições distribucionais ou estruturais. Para determinar o desempenho dos novos esquemas de imputação foram realizadas simulações baseadas em conjuntos de dados reais de diferentes espécies, com valores re- tirados aleatoriamente em diferentes porcentagens e a qualidade das imputações avaliada com distintas estatísticas. Concluiu-se que a DVS constitui uma ferramenta útil e flexível na construção de técnicas eficientes que contornem o problema de perda de informação em matrizes experimentais.

Algoritmos recursivos e não-recursivos aplicados à estimação fasorial em sistemas elétricos de potência

Este trabalho apresenta uma análise de algoritmos computacionais aplicados à estimação de fasores elétricos em SEPs. A medição dos fasores é realizada por meio da alocação de Unidades de Medição Fasorial nestes sistemas e encontra diversas aplicações nas áreas de operação, controle, proteção e planejamento. Para que os fasores possam ser aplicados, são definidos padrões de medição, sincronização e comunicação, por meio da norma IEEE C37.118.1. A norma apresenta os padrões de mensagens, timetag, fasores, sistema de sincronização, e define testes para avaliar a estimação. Apesar de abranger todos esses critérios, a diretriz não define um algoritmo de estimação padrão, abrindo espaço para uso de diversos métodos, desde que a precisão seja atendida. Nesse contexto, o presente trabalho analisa alguns algoritmos de estimação de fasores definidos na literatura, avaliando o comportamento deles em determinados casos. Foram considerados, dessa forma, os métodos: Transformada Discreta de Fourier, Método dos Mínimos Quadrados e Transformada Wavelet Discreta, nas versões recursivas e não-recursivas. Esses métodos foram submetidos a sinais sintéticos, a fim de verificar o comportamento diante dos testes propostos pela norma, avaliando o Total Vector Error, tempo de resposta e atraso e overshoot. Os algoritmos também foram embarcados em um hardware, denominado PC104, e avaliados de acordo com os sinais medidos pelo equipamento na saída analógica de um simulador em tempo real (Real Time Digital Simulator).

Aceleración de algoritmos para imágenes hiperespectrales con OpenCL

En el presente trabajo se propone dar solución a uno de los problemas principales surgido en el campo del análisis de imágenes hiperespectrales. En las últimas décadas este campo está siendo muy activo, por lo que es de vital importancia tratar su problema principal: mezcla espectral. Muchos algoritmos han tratado de solucionar este problema, pero que a través de este trabajo se propone una cadena nueva de desmezclado en paralelo, para ser acelerados bajo el paradigma de programación paralela de OpenCl. Este paradigma nos aporta el modelo de programación unificada para acelerar algoritmos en sistemas heterogéneos. Podemos dividir el proceso de desmezclado espectral en tres etapas. La primera tiene la tarea de encontrar el número de píxeles puros, llamaremos endmembers a los píxeles formados por una única firma espectral, utilizaremos el algoritmo conocido como Geometry-based Estimation of number of endmembers, GENE. La segunda etapa se encarga de identificar los píxel endmembers y extraerlos junto con todas sus bandas espectrales, para esta etapa se utilizará el algoritmo conocido por Simplex Growing Algorithm, SGA. En la última etapa se crean los mapas de abundancia para cada uno de los endmembers encontrados, de esta etapa será encargado el algoritmo conocido por, Sum-to-one Constrained Linear Spectral Unmixing, SCLSU. Las plataformas utilizadas en este proyecto han sido tres: CPU, Intel Xeon E5-2695 v3, GPU, NVidia GeForce GTX 980, Acelerador, Intel Xeon Phi 31S1P. La idea de este proyecto se basa en realizar un análisis exhaustivo de los resultados obtenidos en las diferentes plataformas, con el fin de evaluar cuál se ajusta mejor a nuestras necesidades.

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.