Algoritmo Genético aplicado al problema de programación en procesos tecnológicos de maquinado con ambiente Flow Shop

Debido a las limitaciones de las técnicas de optimización convencionales, en el siguiente trabajo se presenta una metaheurística basada en un algoritmo genético (AG), para resolver problemas de programación de tipo flow shop, con el objetivo de minimizar el tiempo de finalización de todos los trabajos, más conocido como makespan. Este problema, considerado de difícil solución, es típico de la optimización combinatoria y se presenta en talleres con tecnología de maquinado, donde existen máquinas-herramientas convencionales y se fabrican diferentes tipos de piezas que tienen en común una misma ruta tecnológica (orden del proceso). La solución propuesta se probó con problemas clásicos publicados por otros autores, obteniéndose resultados satisfactorios en cuanto a la calidad de las soluciones encontradas y el tiempo de cómputo empleado.

Algoritmo genético aplicado a la programación en talleres de maquinado

En este trabajo se utiliza la metaheurística nombrada algoritmo genético, para dos variantes típicas de problemas de planificación presentes en un taller de maquinado de piezas: las variantes flujo general y flujo regular, y se ha seleccionado la minimización del tiempo de finalización de todos los trabajos o camino máximo, como objetivo a optimizar en un plan de trabajo. Este problema es considerado de difícil solución y es típico de la optimización combinatoria. Los resultados demuestran la calidad de las soluciones encontradas en correspondencia con el tiempo de cómputo empleado, al ser comparados con problemas clásicos reportados por otros autores. La representación propuesta de cada cromosoma genera el universo completo de soluciones factibles, donde es posible encontrar valores óptimos globales de solución y cumple con las restricciones del problema.

Un "organismo" evolutivo. El pabellón de Barcelona visto por Sota, Cabrero, (Aburto) y Navarro Baldeweg

El texto plantea la visión del pabellón de Barcelona como un organismo evolutivo a partir de las opiniones y obras de los arquitectos seleccionados.

Algoritmo de control anticipatorio assisted-as-needed para neurorrehabilitación funcional de extremidad superior

Los dispositivos robóticos se están convirtiendo en una alternativa muy extendida a las terapias de neurorrehabilitación funcional tradicionales al ofrecer una práctica más intensiva sin incrementar el tiempo empleado en la supervisión por parte de los terapeutas especialistas. Por ello, este trabajo de investigación propone un algoritmo de control anticipatorio que, bajo el paradigma 'assisted-as-needed', proporcione a una ortesis robótica las capacidades de actuación necesarias para comportarse tal y como lo haría un terapeuta que proporciona una sesión de terapia manual. Dicho algoritmo de control ha sido validado mediante un simulador robótico obteniéndose resultados que demuestran su eficacia.

Nuevo algoritmo de generalización lineal y ortogonalización de construcciones en un entorno urbano.

Resumen: La generalización cartográfica es el proceso que permite la obtención de cartografía derivada a partir de la generada mediante el registro de información geográfica. Normalmente, la generalización implica una reducción de escala, aunque podría ser una reducción de la cantidad de información sin reducir la escala, debido a un cambio de objetivo de la cartografía. La dificultad de la generalización aumenta cuanto menor es la escala destino y mayor la diferencia entre ésta y la escala origen. Estas dificultades se concentran en aquellas entidades que representan objetos modificados por el hombre, es decir, principalmente en los núcleos urbanos, ya que deben preservar ciertas propiedades en su geometría una vez generalizados. En este artículo, se propone un algoritmo para la generalización lineal de núcleos urbanos, basándose en las características constructivas y relacionales de las edificaciones que los conforman. Abstract: Mapping generalization is the process which derived maps are obtained from others generated by recording geographic information. Usually, generalization involves a reduction of scale, although it could be a reduction in the amount of information without reducing the scale, due to a change in target mapping. The smaller target scale, the more difficult is the generalization. Also, the more difference between origin scale and target scale, the more difficult is the generalization. The difficulties are concentrated in entities that represent objects modified by man, mainly in urban areas, as they must preserve certain geometry properties once generalized. In this paper, an algorithm is proposed for linear generalization of urban areas, based on constructive and relational characteristics of the buildings that shape them.

Algoritmo para la clasificación de nubes de puntos LiDAR en entornos urbanos: discriminación entre vegetación y edificaciones.

Los sistemas de registro aerotransportados que utilizan láser (LiDAR) se están convirtiendo en el principal instrumental para la recogida de la información cartográfica debido, principalmente, a la gran densidad de puntos, precisión alcanzada y rapidez en la obtención de modelos digitales. Sin embargo, sería importante disponer de algoritmos que permitan filtrar la información, seleccionando aquellos puntos medidos en zonas deseadas. Cuando se miden zonas urbanas, los elementos más importantes son las edificaciones. Por ello, se propone un nuevo algoritmo que permite clasificar y diferenciar aquellos puntos medidos sobre edificios, extrayendo, como resultado, el límite exterior que definen, de tal forma que se podría calcular la zona edificada. Abstarct: Registration systems using airborne laser (LIDAR) are becoming the main device for the collection of cartographic information, mainly due to the high density of points, accuracy and rate achieved in obtaining digital models. However, it would be important to have algorithms that filter the information by selecting those points measured in targeted areas. When measuring urban areas, buildings are the most important objects. Therefore, a new algorithm is proposed to classify those measured points on buildings and to compute their outer boundaries, so the built up area can be computed.

Portado del algoritmo de Viterbi a una arquitectura multiprocesador

Cada vez es más frecuente que los sistemas de comunicaciones realicen buena parte de sus funciones (modulación y demodulación, codificación y decodificación...) mediante software en lugar de utilizar hardware dedicado. Esta técnica se denomina “Radio software”. El objetivo de este PFC es estudiar un algoritmo implementado en C empleado en sistemas de comunicaciones modernos, en concreto la decodificación de Viterbi, el cual se encarga de corregir los posibles errores producidos a lo largo de la comunicación, para poder trasladarlo a sistemas empotrados multiprocesador. Partiendo de un código en C para el decodificador que realiza todas sus operaciones en serie, en este Proyecto fin de carrera se ha paralelizado dicho código, es decir, que el trabajo que realizaba un solo hilo para el caso del código serie, es procesado por un número de hilos configurables por el usuario, persiguiendo que el tiempo de ejecución se reduzca, es decir, que el programa paralelizado se ejecute de una manera más rápida. El trabajo se ha realizado en un PC con sistema operativo Linux, pero la versión paralelizada del código puede ser empleada en un sistema empotrado multiprocesador en el cual cada procesador ejecuta el código correspondiente a uno de los hilos de la versión de PC. ABSTRACT It is increasingly common for communications systems to perform most of its functions (modulation and demodulation, coding and decoding) by software instead of than using dedicated hardware. This technique is called: “Software Radio”. The aim of the PFC is to study an implemented algorithm in C language used in modern communications systems, particularly Viterbi decoding, which amends any possible error produced during the communication, in order to be able to move multiprocessor embedded systems. Starting from a C code of the decoder that performs every single operation in serial, in this final project, this code has been parallelized, which means that the work used to be done by just a single thread in the case of serial code, is processed by a number of threads configured by the user, in order to decrease the execution time, meaning that the parallelized program is executed faster. The work has been carried out on a PC using Linux operating system, but the parallelized version of the code could also be used in an embedded multiprocessor system in which each processor executes the corresponding code to every single one of the threads of the PC version.

Algoritmos de agrupación para flujos de datos en entornos centralizados y distribuidos

Los avances en el hardware permiten disponer de grandes volúmenes de datos, surgiendo aplicaciones que deben suministrar información en tiempo cuasi-real, la monitorización de pacientes, ej., el seguimiento sanitario de las conducciones de agua, etc. Las necesidades de estas aplicaciones hacen emerger el modelo de flujo de datos (data streaming) frente al modelo almacenar-para-despuésprocesar (store-then-process). Mientras que en el modelo store-then-process, los datos son almacenados para ser posteriormente consultados; en los sistemas de streaming, los datos son procesados a su llegada al sistema, produciendo respuestas continuas sin llegar a almacenarse. Esta nueva visión impone desafíos para el procesamiento de datos al vuelo: 1) las respuestas deben producirse de manera continua cada vez que nuevos datos llegan al sistema; 2) los datos son accedidos solo una vez y, generalmente, no son almacenados en su totalidad; y 3) el tiempo de procesamiento por dato para producir una respuesta debe ser bajo. Aunque existen dos modelos para el cómputo de respuestas continuas, el modelo evolutivo y el de ventana deslizante; éste segundo se ajusta mejor en ciertas aplicaciones al considerar únicamente los datos recibidos más recientemente, en lugar de todo el histórico de datos. En los últimos años, la minería de datos en streaming se ha centrado en el modelo evolutivo. Mientras que, en el modelo de ventana deslizante, el trabajo presentado es más reducido ya que estos algoritmos no sólo deben de ser incrementales si no que deben borrar la información que caduca por el deslizamiento de la ventana manteniendo los anteriores tres desafíos. Una de las tareas fundamentales en minería de datos es la búsqueda de agrupaciones donde, dado un conjunto de datos, el objetivo es encontrar grupos representativos, de manera que se tenga una descripción sintética del conjunto. Estas agrupaciones son fundamentales en aplicaciones como la detección de intrusos en la red o la segmentación de clientes en el marketing y la publicidad. Debido a las cantidades masivas de datos que deben procesarse en este tipo de aplicaciones (millones de eventos por segundo), las soluciones centralizadas puede ser incapaz de hacer frente a las restricciones de tiempo de procesamiento, por lo que deben recurrir a descartar datos durante los picos de carga. Para evitar esta perdida de datos, se impone el procesamiento distribuido de streams, en concreto, los algoritmos de agrupamiento deben ser adaptados para este tipo de entornos, en los que los datos están distribuidos. En streaming, la investigación no solo se centra en el diseño para tareas generales, como la agrupación, sino también en la búsqueda de nuevos enfoques que se adapten mejor a escenarios particulares. Como ejemplo, un mecanismo de agrupación ad-hoc resulta ser más adecuado para la defensa contra la denegación de servicio distribuida (Distributed Denial of Services, DDoS) que el problema tradicional de k-medias. En esta tesis se pretende contribuir en el problema agrupamiento en streaming tanto en entornos centralizados y distribuidos. Hemos diseñado un algoritmo centralizado de clustering mostrando las capacidades para descubrir agrupaciones de alta calidad en bajo tiempo frente a otras soluciones del estado del arte, en una amplia evaluación. Además, se ha trabajado sobre una estructura que reduce notablemente el espacio de memoria necesario, controlando, en todo momento, el error de los cómputos. Nuestro trabajo también proporciona dos protocolos de distribución del cómputo de agrupaciones. Se han analizado dos características fundamentales: el impacto sobre la calidad del clustering al realizar el cómputo distribuido y las condiciones necesarias para la reducción del tiempo de procesamiento frente a la solución centralizada. Finalmente, hemos desarrollado un entorno para la detección de ataques DDoS basado en agrupaciones. En este último caso, se ha caracterizado el tipo de ataques detectados y se ha desarrollado una evaluación sobre la eficiencia y eficacia de la mitigación del impacto del ataque. ABSTRACT Advances in hardware allow to collect huge volumes of data emerging applications that must provide information in near-real time, e.g., patient monitoring, health monitoring of water pipes, etc. The data streaming model emerges to comply with these applications overcoming the traditional store-then-process model. With the store-then-process model, data is stored before being consulted; while, in streaming, data are processed on the fly producing continuous responses. The challenges of streaming for processing data on the fly are the following: 1) responses must be produced continuously whenever new data arrives in the system; 2) data is accessed only once and is generally not maintained in its entirety, and 3) data processing time to produce a response should be low. Two models exist to compute continuous responses: the evolving model and the sliding window model; the latter fits best with applications must be computed over the most recently data rather than all the previous data. In recent years, research in the context of data stream mining has focused mainly on the evolving model. In the sliding window model, the work presented is smaller since these algorithms must be incremental and they must delete the information which expires when the window slides. Clustering is one of the fundamental techniques of data mining and is used to analyze data sets in order to find representative groups that provide a concise description of the data being processed. Clustering is critical in applications such as network intrusion detection or customer segmentation in marketing and advertising. Due to the huge amount of data that must be processed by such applications (up to millions of events per second), centralized solutions are usually unable to cope with timing restrictions and recur to shedding techniques where data is discarded during load peaks. To avoid discarding of data, processing of streams (such as clustering) must be distributed and adapted to environments where information is distributed. In streaming, research does not only focus on designing for general tasks, such as clustering, but also in finding new approaches that fit bests with particular scenarios. As an example, an ad-hoc grouping mechanism turns out to be more adequate than k-means for defense against Distributed Denial of Service (DDoS). This thesis contributes to the data stream mining clustering technique both for centralized and distributed environments. We present a centralized clustering algorithm showing capabilities to discover clusters of high quality in low time and we provide a comparison with existing state of the art solutions. We have worked on a data structure that significantly reduces memory requirements while controlling the error of the clusters statistics. We also provide two distributed clustering protocols. We focus on the analysis of two key features: the impact on the clustering quality when computation is distributed and the requirements for reducing the processing time compared to the centralized solution. Finally, with respect to ad-hoc grouping techniques, we have developed a DDoS detection framework based on clustering.We have characterized the attacks detected and we have evaluated the efficiency and effectiveness of mitigating the attack impact.

Oprimización y paralelización de un algoritmo de sincronización mediante el uso de GPUs y la tecnología CUDA

En el presente documento se hablará acerca del desarrollo de un proyecto para la mejora de un programa de análisis de señales; con ese fin, se hará uso de técnicas de optimización del software y de tecnologías de aceleración, mediante el aprovechamiento del paralelismo del programa. Además se hará un análisis de acerca del uso de dos tecnologías basadas en diferentes paradigmas de programación paralela; una mediante múltiples hilos con memoria compartida y la otra mediante el uso de GPUs como dispositivos de coprocesamiento. This paper will talk about the development of a Project to improve a program that does signals analysis; to that end, it will make use of software optimization techniques and acceleration technologies by exploiting parallelism in the program. In Addition will be done an analysis on the use of two technologies based on two different paradigms; one using multiple threads with shared memory and the other using GPU as co-processing devices.

Estudio y aplicación del algoritmo de Davidon a la optimización del gobierno en tiempo mínimo de sistemas lineales

Un método algorítmico de minimización será eficaz cuando esté concebido de manera que converja en todo momento y que, al llegar a la vecindad del mínimo, se adapte a la geografía de segundo grado para converger ya con rapidez cuadrática. El método de Davidon pertenece a esta clase.

Algoritmo para el análisis del Comportamiento de fresas periféricas en condiciones variables

La simulación de procesos de mecanizado supone hoy en día una herramienta de gran interés para predecir el comportamiento de la herramienta en las operaciones de corte y por lo tanto, la posibilidad de optimizar estas operaciones, permitiendo alcanzar una mayor productividad en los procesos de fabricación. Los algoritmos que actualmente se están utilizando para la predicción de fuerzas de corte son variados y su eficiencia diferente. La mayoría de los algoritmos desarrollados se centran en determinar la evolución de las fuerzas de corte en cada vuelta de la herramienta sin variar las condiciones de mecanizado en este intervalo. En este sentido, se ha desarrollado un algoritmo para fresado periférico basado en el espesor de viruta medio, que permite simplificar el algoritmo de estimación de fuerzas y ser ejecutado con una mayor velocidad, manteniendo el mismo nivel de precisión en la estimación. Con este nuevo modelo es posible realizar la estimación de fuerzas en fresado no solo cuando las condiciones de corte son uniformes sino también cuando se producen cambios en la configuración del corte.

Nuevo algoritmo de relajación para motores de cuerpos sólidos

Con el fin de conocer mejor a las bacterias, en la actualidad se han desarrollado aplicaciones que permite simular el comportamiento de las colonias formadas por este tipo de organismos. Una de las piezas más importantes que tienen estos simuladores es el motor de físicas. Éste es el encargado de resolver todas las fuerzas producidas entre las bacterias y conseguir que todas queden correctamente colocadas y distribuidas a lo largo de la colonia, tratando de asemejarse lo más posible a la realidad. En una simulación de éstas características, todas las bacterias, además de estar en contacto entre sí, crecen en un pequeño porcentaje durante cada fotograma. Ello produce una gran cantidad de solapamiento a lo largo de toda la colonia que el motor de físicas tiene que resolver. El trabajo que se describe en este documento surge de la ineficiencia del proceso actual para distribuir el solapamiento originado en el interior de la colonia, hasta su exterior. Es importante señalar que la física se lleva el 99% del tiempo de procesado de la simulación de una colonia, con lo que una mejora en el motor de físicas conseguiría incrementar en gran medida la capacidad de simulación. El objetivo no es otro que poder simular más cantidad de bacterias en menos tiempo, facilitando el estudio de esta área tan reciente como es la biología sintética. ---ABSTRACT---In order to better understand bacteria, new applications have been developed to simulate the behavior of colonies formed by these organisms. One of the most important parts of these simulators is the physics engine. This module is responsible for solving all the forces produced between bacteria and ensure that they are properly located and distributed throughout the colony, trying to be as close as possible to reality. In a simulation with these features, all bacteria, besides being in contact with each other, grow in a small percentage at each frame. This produces a large amount of overlap along the entire colony that the physics engine must solve. The work described in this document arises from the inefficiency of the current process to distribute the overlap originated at the core of the colony outwards. Importantly, physics takes up 99% of the processing time of the simulation of a colony. Therefore, improving the physics engine would translate in a drastic increase in the throughput of the simulation. The goal is simply to be able to simulate more bacteria in less time, making the study of the recent area, synthetic biology, much easier.

Diseño e implementación de un algoritmo para la detección de la negación de textos clínicos en español

Vivimos en una época en la que cada vez existe una mayor cantidad de información. En el dominio de la salud la historia clínica digital ha permitido digitalizar toda la información de los pacientes. Estas historias clínicas digitales contienen una gran cantidad de información valiosa escrita en forma narrativa que sólo podremos extraer recurriendo a técnicas de procesado de lenguaje natural. No obstante, si se quiere realizar búsquedas sobre estos textos es importante analizar que la información relativa a síntomas, enfermedades, tratamientos etc. se puede refererir al propio paciente o a sus antecentes familiares, y que ciertos términos pueden aparecer negados o ser hipotéticos. A pesar de que el español ocupa la segunda posición en el listado de idiomas más hablados con más de 500 millones de hispano hablantes, hasta donde tenemos de detección de la negación, probabilidad e histórico en textos clínicos en español. Por tanto, este Trabajo Fin de Grado presenta una implementación basada en el algoritmo ConText para la detección de la negación, probabilidad e histórico en textos clínicos escritos en español. El algoritmo se ha validado con 454 oraciones que incluían un total de 1897 disparadores obteniendo unos resultado de 83.5 %, 96.1 %, 96.9 %, 99.7% y 93.4% de exactitud con condiciones afirmados, negados, probable, probable negado e histórico respectivamente. ---ABSTRACT---We live in an era in which there is a huge amount of information. In the domain of health, the electronic health record has allowed to digitize all the information of the patients. These electronic health records contain valuable information written in narrative form that can only be extracted using techniques of natural language processing. However, if you want to search on these texts is important to analyze if the relative information about symptoms, diseases, treatments, etc. are referred to the patient or family casework, and that certain terms may appear negated or be hypothesis. Although Spanish is the second spoken language with more than 500 million speakers, there seems to be no method of detection of negation, hypothesis or historical in medical texts written in Spanish. Thus, this bachelor’s final degree presents an implementation based on the ConText algorithm for the detection of negation, hypothesis and historical in medical texts written in Spanish. The algorithm has been validated with 454 sentences that included a total of 1897 triggers getting a result of 83.5 %, 96.1 %, 96.9 %, 99.7% and 93.4% accuracy with affirmed, negated, hypothesis, negated hypothesis and historical respectively.

Optimización y paralelización de algoritmo de búsqueda aleatoria para su aplicación en la búsqueda de fuentes MEG

El problema inverso de la búsqueda de fuentes MEG consiste en la obtención de la distribución de los dipolos de corriente (fuentes) en el interior de la cabeza de un paciente a partir de las mediciones de campo electromagnético obtenidas en la superficie (magnetoencefalograma, MEG). Para obtener estos datos, en el ámbito científico se utiliza el algoritmo beamforming, comúnmente aceptado, cuyos resultados ofrecen un pequeño margen de error debido a la naturaleza del problema. Esta memoria desarrolla el trabajo realizado para optimizar un algoritmo de búsqueda aleatoria, Solis-Wets, utilizado para investigar la posibilidad de su aplicación en el ámbito científico, en sustitución del anteriormente mencionado, beamforming. También se estudiará la acción de encadenar ambos algoritmos, tomando como datos de entrada del algoritmo Solis-Wets aquellos proporcionados como solución por el algoritmo beamforming con objeto de minimizar el error en el que éste incurre. Esta optimización es necesaria para que la alternativa sea viable debido al tiempo necesario en su ejecución, e incluye el uso de bibliotecas auxiliares, así como la paralelización del código. Para la evaluación del algoritmo se han medido tanto la velocidad de generación de soluciones como el error de la mejor solución tras un número determinado de soluciones generadas. Como variables para esta evaluación se han tomado distintos compiladores, distintas soluciones de partida, precisión de los datos, así como el uso de distintas bibliotecas matemáticas disponibles.

Plataforma de conocimiento evolutivo para detección temprana de transtornos del lenguaje

Este Proyecto Fin de Grado, es el primer paso para abordar la construcción de una plataforma de conocimiento evolutivo para dos sistemas que facilitan la detección precoz de trastornos del lenguaje en niños de 0 a 6 años. Concretamente, el objetivo principal de este proyecto es el diseño, desarrollo y puesta en explotación de un sistema de recogida de propuestas de mejora sobre la base de conocimiento de los sistemas de ayuda a la toma de decisiones Gades y Pegaso. Este sistema está formado fundamentalmente por una aplicación diseñada y construida mediante una arquitectura de componentes de software modular y reutilizable. La aplicación será usada por los usuarios de las plataformas Pegaso y Gades para realizar las propuestas de cambio sobre la base de conocimiento de dichos sistemas. El sistema es accesible vía web y almacena toda la información que maneja en una base de datos. Asimismo, expone un estudio de aplicaciones orientadas al trabajo colaborativo (CSCW) y a la toma de decisiones colaborativa, como paso previo al desarrollo de una funcionalidad futura del propio sistema. ABSTRACT. This Final Degree Project, is the first step to address the construction of a platform for two evolutionary knowledge systems that facilitate early detection of language disorders in children aged 0-6 years. Specifically, the main objective of this project is the design, development and start-up of a system that collect improvement proposals about the knowledge of decision support systems Gades and Pegaso. This system consists mainly of an application designed and built by a modular component architecture and reusable software. The application will be used by users of the Pegaso and Gades platforms for change proposals on the basis of knowledge of such systems. The system is accessible via web and stores all the information managed in a database. It also presents a study of collaborative work oriented applications (CSCW) and collaborative decision making, prior to the development of a future system functionality.