Otimização com restrições de complementaridade: algoritmos e aplicações

Tese de Doutoramento em Engenharia Industrial e de Sistemas (PDEIS)

Retroanálise de parâmetros geomecânicos baseada em algoritmos de otimização

Dissertação de mestrado integrado em Engenharia Civil

Desarrollo de Algoritmos Numéricos para el Estudio de la Propagación no Lineal de Ondas en Aplicaciones Aeroespaciales y Astrofísicas. Develop to Numerical Algorithms to Study non-Linear Waves Propagation in Aerospace and Astrophysics Applications.

En este proyecto se desarrollarán algoritmos numéricos para sistemas no lineales hiperbólicos-parabólicos de ecuaciones diferenciales en derivadas parciales. Dichos sistemas tienen aplicación en propagación de ondas en ámbitos aeroespaciales y astrofísicos.Objetivos generales: 1)Desarrollo y mejora de algoritmos numéricos con la finalidad de incrementar la calidad en la simulación de propagación e interacción de ondas gasdinámicas y magnetogasdinámicas no lineales. 2)Desarrollo de códigos computacionales con la finalidad de simular flujos gasdinámicos de elevada entalpía incluyendo cambios químicos, efectos dispersivos y difusivos.3)Desarrollo de códigos computacionales con la finalidad de simular flujos magnetogasdinámicos ideales y reales.4)Aplicación de los nuevos algoritmos y códigos computacionales a la solución del flujo aerotermodinámico alrededor de cuerpos que ingresan en la atmósfera terrestre. 5)Aplicación de los nuevos algoritmos y códigos computacionales a la simulación del comportamiento dinámico no lineal de arcos magnéticos en la corona solar. 6)Desarrollo de nuevos modelos para describir el comportamiento no lineal de arcos magnéticos en la corona solar.Este proyecto presenta como objetivo principal la introducción de mejoras en algoritmos numéricos para simular la propagación e interacción de ondas no lineales en dos medios gaseosos: aquellos que no poseen carga eléctrica libre (flujos gasdinámicos) y aquellos que tienen carga eléctrica libre (flujos magnetogasdinámicos). Al mismo tiempo se desarrollarán códigos computacionales que implementen las mejoras de las técnicas numéricas.Los algoritmos numéricos se aplicarán con la finalidad de incrementar el conocimiento en tópicos de interés en la ingeniería aeroespacial como es el cálculo del flujo de calor y fuerzas aerotermodinámicas que soportan objetos que ingresan a la atmósfera terrestre y en temas de astrofísica como la propagación e interacción de ondas, tanto para la transferencia de energía como para la generación de inestabilidades en arcos magnéticos de la corona solar. Estos dos temas poseen en común las técnicas y algoritmos numéricos con los que serán tratados. Las ecuaciones gasdinámicas y magnetogasdinámicas ideales conforman sistemas hiperbólicos de ecuaciones diferenciales y pueden ser solucionados utilizando "Riemann solvers" junto con el método de volúmenes finitos (Toro 1999; Udrea 1999; LeVeque 1992 y 2005). La inclusión de efectos difusivos genera que los sistemas de ecuaciones resulten hiperbólicos-parabólicos. La contribución parabólica puede ser considerada como términos fuentes y tratada adicionalmente tanto en forma explícita como implícita (Udrea 1999; LeVeque 2005).Para analizar el flujo alrededor de cuerpos que ingresan en la atmósfera se utilizarán las ecuaciones de Navier-Stokes químicamente activas, mientras la temperatura no supere los 6000K. Para mayores temperaturas es necesario considerar efectos de ionización (Anderson, 1989). Tanto los efectos difusivos como los cambios químicos serán considerados como términos fuentes en las ecuaciones de Euler. Para tratar la propagación de ondas, transferencia de energía e inestabilidades en arcos magnéticos de la corona solar se utilizarán las ecuaciones de la magnetogasdinámica ideal y real. En este caso será también conveniente implementar términos fuente para el tratamiento de fenómenos de transporte como el flujo de calor y el de radiación. Los códigos utilizarán la técnica de volúmenes finitos, junto con esquemas "Total Variation Disminishing - TVD" sobre mallas estructuradas y no estructuradas.

Optimización en el cómputos de algoritmos de cuadratura para funciones especiales. Optimization of quadrature algorithms for special functions.

En nuestro proyecto anterior aproximamos el cálculo de una integral definida con integrandos de grandes variaciones funcionales. Nuestra aproximación paraleliza el algoritmo de cómputo de un método adaptivo de cuadratura, basado en reglas de Newton-Cote. Los primeros resultados obtenidos fueron comunicados en distintos congresos nacionales e internacionales; ellos nos permintieron comenzar con una tipificación de las reglas de cuadratura existentes y una clasificación de algunas funciones utilizadas como funciones de prueba. Estas tareas de clasificación y tipificación no las hemos finalizado, por lo que pretendemos darle continuidad a fin de poder informar sobre la conveniencia o no de utilizar nuestra técnica. Para llevar adelante esta tarea se buscará una base de funciones de prueba y se ampliará el espectro de reglas de cuadraturas a utilizar. Además, nos proponemos re-estructurar el cálculo de algunas rutinas que intervienen en el cómputo de la mínima energía de una molécula. Este programa ya existe en su versión secuencial y está modelizado utilizando la aproximación LCAO. El mismo obtiene resultados exitosos en cuanto a precisión, comparado con otras publicaciones internacionales similares, pero requiere de un tiempo de cálculo significativamente alto. Nuestra propuesta es paralelizar el algoritmo mencionado abordándolo al menos en dos niveles: 1- decidir si conviene distribuir el cálculo de una integral entre varios procesadores o si será mejor distribuir distintas integrales entre diferentes procesadores. Debemos recordar que en los entornos de arquitecturas paralelas basadas en redes (típicamente redes de área local, LAN) el tiempo que ocupa el envío de mensajes entre los procesadores es muy significativo medido en cantidad de operaciones de cálculo que un procesador puede completar. 2- de ser necesario, paralelizar el cálculo de integrales dobles y/o triples. Para el desarrollo de nuestra propuesta se desarrollarán heurísticas para verificar y construir modelos en los casos mencionados tendientes a mejorar las rutinas de cálculo ya conocidas. A la vez que se testearán los algoritmos con casos de prueba. La metodología a utilizar es la habitual en Cálculo Numérico. Con cada propuesta se requiere: a) Implementar un algoritmo de cálculo tratando de lograr versiones superadoras de las ya existentes. b) Realizar los ejercicios de comparación con las rutinas existentes para confirmar o desechar una mejor perfomance numérica. c) Realizar estudios teóricos de error vinculados al método y a la implementación. Se conformó un equipo interdisciplinario integrado por investigadores tanto de Ciencias de la Computación como de Matemática. Metas a alcanzar Se espera obtener una caracterización de las reglas de cuadratura según su efectividad, con funciones de comportamiento oscilatorio y con decaimiento exponencial, y desarrollar implementaciones computacionales adecuadas, optimizadas y basadas en arquitecturas paralelas.

Estudios evolutivos en especies de plantas nativas.

Se indagará principalmente acerca del rol de los procesos neutrales, como la deriva génica, de procesos selectivos, como la selección natural mediada por polinizadores y de procesos históricos (geológicos y climáticos del pasado) en la diversificación floral tanto a escala microevolutiva como macroevolutiva. La heterogeneidad ambiental que se presenta en amplios rangos geográficos puede promover la diferenciación entre poblaciones debido a las diferencias en condiciones físicas y biológicas. De esta manera, especies ampliamente distribuidas ofrecen la oportunidad de explorar la dinámica de los procesos evolutivos que tienen lugar a nivel interpoblacional (Dobzhansky 1970, Thompson 1999). El estudio comparativo entre especies hermanas permite comprender cómo la selección natural (adaptación) y la inercia filogenética (herencia ancestral) han modelado los rasgos de las especies que observamos en la actualidad (Díaz 2002, Schluter 2000, Futuyma 2005). Uno de los usos más importantes de la información filogenética es el de reconstruir la historia del cambio evolutivo en caracteres adaptativos mediante su mapeo en la filogenia y la reconstrucción del estado de estos caracteres en el ancestro. Así, la asociación entre transición de caracteres y transiciones en grupos funcionales es una evidencia directa de la hipótesis adaptativa de que los rasgos son seleccionados por grupos funcionales de polinizadores. Una aproximación filogenética puede permitir identificar la dirección y el tiempo de evolución. Todos estos aspectos señalan la necesidad de adoptar una perspectiva conceptualmente integrada (morfológica, genética, filogenética, filogeográfica y ecológica) en el estudio de la biología evolutiva de las flores. Estudiar como actúan los procesos micro- y macroevolutivos en las interacciones planta-polinizador, en una dimensión espacial y temporal, arrojará resultados importantes tanto en el campo teórico como en el de la conservación. Por una parte, permitirá poner a prueba hipótesis relevantes sobre la adaptación de caracteres, mientras que explorará los procesos evolutivos que subyacen a las tramas de las interacciones planta-polinizador; por otro lado, comprender el rol de los cambios climáticos pasados en la diversificación biológica es interesante tanto desde una aproximación evolutiva como desde la biología de la conservación (Avise 2000; Moritz et al. 2000; Petit et al. 2003; Hewitt 2004). Géneros a ser estudiados en este proyecto: 1- Anarthrophyllum (Fabaceae,15 spp), 2- Monttea (Plantaginaceae, 3 spp), 3- Caleolaria (Calceolariaceae 3 spp), 4- Centris (Apidae, 1 spp), 5- Jaborosa (Solanaceae, 23 spp). Metodología: Mapeado de las poblaciones. Elenco de polinizadores, frecuencia. Obtención y medición de caracteres fenotípicos florales. Néctar: concentración y vol. Aceites (peso); Morfometría geométrica (Zelditch et al. 2005). Éxito reproductivo (Dafni & Kevan 2003). Caracteres genéticos: extracción, amplificación y secuenciación: en Calceolaria se utilizarán 2 genes de cloroplasto trnH-psbA y trnS-trnG y genes anónimos nucleares de copia única (scnADN), para Jaborosa se utilizarán 3 genes de cloroplasto (trnH-psbA, TrnD-trnT y ndhF-rp32) y el gen nuclear GBSSI waxy. Finalmente para Centris cineraria se usaría el tRNA ILE y NADH Deshidrogenada subunidad 2. Análisis filogenéticos de parsimonia (Goloboff et al. 2000, Kitching et al. 1998, Nixon 2002, Farris et al. 1996, Sorenson 1999); Filogeografía: reconstrucción de redes por parsimonia (Clement et al. 2000; Posada et al. 2000), análisis de clados anidados (NCPA). Se usarán las claves de inferencia (Templeton 2004). Para todos estos análisis se utilizarán los siguientes programas: DnaSP, Network, Arlequin, MrBayes, Paup, ModelTest, Beast, TNT, WinClada TCS y GeoDis. Estadística multivariada: Los diferentes rasgos florales mencionados se analizarán utilizando distancias de Gower (datos cualitativos) y euclídeas (datos cuantitativos) mediante la técnica multivariada ACoP.

Aceleración de Algoritmos en Procesadores Multicore, GPGPU y FPGA. Algorithm Acceleration with Multicore, GPGPU and FPGA Processors.

El avance en la potencia de cómputo en nuestros días viene dado por la paralelización del procesamiento, dadas las características que disponen las nuevas arquitecturas de hardware. Utilizar convenientemente este hardware impacta en la aceleración de los algoritmos en ejecución (programas). Sin embargo, convertir de forma adecuada el algoritmo en su forma paralela es complejo, y a su vez, esta forma, es específica para cada tipo de hardware paralelo. En la actualidad los procesadores de uso general más comunes son los multicore, procesadores paralelos, también denominados Symmetric Multi-Processors (SMP). Hoy en día es difícil hallar un procesador para computadoras de escritorio que no tengan algún tipo de paralelismo del caracterizado por los SMP, siendo la tendencia de desarrollo, que cada día nos encontremos con procesadores con mayor numero de cores disponibles. Por otro lado, los dispositivos de procesamiento de video (Graphics Processor Units - GPU), a su vez, han ido desarrollando su potencia de cómputo por medio de disponer de múltiples unidades de procesamiento dentro de su composición electrónica, a tal punto que en la actualidad no es difícil encontrar placas de GPU con capacidad de 200 a 400 hilos de procesamiento paralelo. Estos procesadores son muy veloces y específicos para la tarea que fueron desarrollados, principalmente el procesamiento de video. Sin embargo, como este tipo de procesadores tiene muchos puntos en común con el procesamiento científico, estos dispositivos han ido reorientándose con el nombre de General Processing Graphics Processor Unit (GPGPU). A diferencia de los procesadores SMP señalados anteriormente, las GPGPU no son de propósito general y tienen sus complicaciones para uso general debido al límite en la cantidad de memoria que cada placa puede disponer y al tipo de procesamiento paralelo que debe realizar para poder ser productiva su utilización. Los dispositivos de lógica programable, FPGA, son dispositivos capaces de realizar grandes cantidades de operaciones en paralelo, por lo que pueden ser usados para la implementación de algoritmos específicos, aprovechando el paralelismo que estas ofrecen. Su inconveniente viene derivado de la complejidad para la programación y el testing del algoritmo instanciado en el dispositivo. Ante esta diversidad de procesadores paralelos, el objetivo de nuestro trabajo está enfocado en analizar las características especificas que cada uno de estos tienen, y su impacto en la estructura de los algoritmos para que su utilización pueda obtener rendimientos de procesamiento acordes al número de recursos utilizados y combinarlos de forma tal que su complementación sea benéfica. Específicamente, partiendo desde las características del hardware, determinar las propiedades que el algoritmo paralelo debe tener para poder ser acelerado. Las características de los algoritmos paralelos determinará a su vez cuál de estos nuevos tipos de hardware son los mas adecuados para su instanciación. En particular serán tenidos en cuenta el nivel de dependencia de datos, la necesidad de realizar sincronizaciones durante el procesamiento paralelo, el tamaño de datos a procesar y la complejidad de la programación paralela en cada tipo de hardware. Today´s advances in high-performance computing are driven by parallel processing capabilities of available hardware architectures. These architectures enable the acceleration of algorithms when thes ealgorithms are properly parallelized and exploit the specific processing power of the underneath architecture. Most current processors are targeted for general pruposes and integrate several processor cores on a single chip, resulting in what is known as a Symmetric Multiprocessing (SMP) unit. Nowadays even desktop computers make use of multicore processors. Meanwhile, the industry trend is to increase the number of integrated rocessor cores as technology matures. On the other hand, Graphics Processor Units (GPU), originally designed to handle only video processing, have emerged as interesting alternatives to implement algorithm acceleration. Current available GPUs are able to implement from 200 to 400 threads for parallel processing. Scientific computing can be implemented in these hardware thanks to the programability of new GPUs that have been denoted as General Processing Graphics Processor Units (GPGPU).However, GPGPU offer little memory with respect to that available for general-prupose processors; thus, the implementation of algorithms need to be addressed carefully. Finally, Field Programmable Gate Arrays (FPGA) are programmable devices which can implement hardware logic with low latency, high parallelism and deep pipelines. Thes devices can be used to implement specific algorithms that need to run at very high speeds. However, their programmability is harder that software approaches and debugging is typically time-consuming. In this context where several alternatives for speeding up algorithms are available, our work aims at determining the main features of thes architectures and developing the required know-how to accelerate algorithm execution on them. We look at identifying those algorithms that may fit better on a given architecture as well as compleme

Utilidad del Dímero-D en los algoritmos diagnósticos de trombosis venosa profunda: análisis según edad y tiempo de evolución

El diagnòstic de la Trombosi Venosa Profunda pot ser difícil degut a una clínica poc específica. S’han desenvolupat diversos algoritmes en què el Dímer-D té un important paper, degut al seu elevat valor predictiu negatiu. El Dímer-D augmenta amb l’edat i disminueix des de l’aparició dels símptomes, si ajustem el seu punt de tall tenint en compte aquests dos paràmetres, és possible augmentar el seu rendiment diagnòstic. Segons els nostres resultats, als subjectes majors de 70 anys i als que presenten una clínica inferior a 14 dies, es podria utilitzar un punt de tall de 1000 ng/mL

Dependencia de los algoritmos con el consumo de energía en sistemas HPC

El consumo energético es un aspecto cada vez más importante en el diseño de microprocesadores. Este trabajo experimenta con una técnica de control del consumo, el escalado dinámico de tensión y frecuencia (DVFS, siglas en inglés), para determinar cuan efectiva es la misma en la ejecución de programas con diferentes cargas de trabajo, intensivas en cómputo o memoria. Además, se ha extendido la experimentación a varios núcleos de ejecución, permitiendo comprobar en que medida las características de la ejecución en una arquitectura multicore afecta al desempeño de dicha técnica.

Problemas en la implementación de algoritmos de routing de alta complejidad en dispositivos móviles: el caso Itiner@

La aparición de terminales de telefonía móvil cada vez más potentes abre un nuevo abanico de posibilidades en cuanto a usos y aplicaciones. Sin embargo, y dadas las limitaciones tanto de memoria como de CPU que tienen estos dispositivos, algunas de las aplicaciones potenciales resultan muy difíciles o incluso imposibles de llevar a la práctica. Este es el caso, por ejemplo, de aplicaciones de cálculo de rutas. En el contexto del proyecto Itiner@, un asistente para rutas turísticas completamente autónomo que debe funcionar incluso sin conexión a Internet, todos los procesos deben ejecutarse íntegramente de forma local en el dispositivo móvil. Dado que es un proyecto orientado al ocio, es importante que la experiencia del usuario sea satisfactoria, por lo que además de poder ejecutar el algoritmo de cálculo de rutas, el sistema debe hacerlo de forma rápida. En este sentido, los algoritmos recursivos habituales son demasiado costosos o lentos para su uso en Itiner@ y ha sido necesario reinventar este tipo de algoritmos en función de las limitaciones que tienen estos dispositivos. En el presente trabajo se presenta el proceso seguido y las dificultades encontradas para implementar un algoritmo recursivo de cálculo de rutas que se ejecute íntegramente en un dispositivo móvil Android de forma eficiente. Así, finalmente se llega a un algoritmo recursivo de cálculo de rutas para dispositivos móviles que se ejecuta de forma más eficiente frente a algoritmos directamente portados a dispositivos móviles. La principal contribución del trabajo es doble: por un lado ofrece algunas guías útiles al desarrollo de algoritmos más eficientes para dispositivos móviles; y por el otro, muestra un algoritmo de cálculo de rutas que funciona con un tiempo de respuesta aceptable, en un entorno exigente, como es el de las aplicaciones de turismo en móviles

Infraestructura de comunicaciones para algoritmos colaborativos

Este proyecto intenta crear un sistema cliente/servidor de comunicaciones para distintas máquinas paralelas en C++ utilizando WCF como tecnología en el servidor.

Comunicador para personas con discapacidad. Entregable 4. Evolutivos maquetas y prototipos

Entregable del convenio C-08197 con la empresa B&J adaptaciones

Epidemiologia Molecular, Evolução Viral e Perfil de Resistência aos Antirretrovirais em uma População de Pacientes Infectados por Hiv-1 e/ou Hiv-2 Residentes em Diferentes Ilhas do Arquipélago de Cabo Verde

O diagnóstico sorológico da infecção pelo HIV-1 e HIV-2 teve início em Cabo Verde em 1987, mas pouco se sabe a respeito da diversidade genética desses vírus nessas ilhas, localizadas na costa Ocidental Africana. Neste estudo, caracterizamos a epidemiologia molecular do HIV-1 e HIV-2 em Cabo Verde, analisamos a origem dos principais clados de HIV introduzidos no país e descrevemos a ocorrência de mutações de resistência aos antirretrovirais (DRM) em indivíduos virgens de tratamento (ARTn) e pacientes em tratamento (ARTexp) oriundos das diferentes ilhas. Amostras de sangue, dados sociodemográfico e clínico-laboratoriais foram obtidos de 221 indivíduos HIV positivos entre 2010-2011. As amostras foram sequenciadas na região da polimerase (1300 pares de bases) e análises filogenéticas e de bootscan foram realizadas para a subtipagem viral. Os algoritmos disponibilizados nos sites Stanford HIV Database e HIV-GRADE e.V. Algorithm Homepage foram utilizados para avaliar a existência de DRM em pacientes positivos para HIV-1 e HIV-2, respectivamente. Os estudos evolutivos e filogeográficos foram realizados através do programa BEAST. Entre os 221 pacientes analisados, sendo 169 (76,5%) HIV-1, 43 (19,5%) HIV-2 e 9 de (4,1%) co-infectados pelo HIV-1 e pelo HIV-2, 67% eram do sexo feminino. As medianas de idade foram de 34 (IQR = 1-75) e 47 (IQR = 12-84) para o HIV-1 e HIV-2, respectivamente. A infecção pelo HIV-1 é causada pelo subtipo G (36,6%), CRF02_AG (30,6%), subtipo F1, (9,7%), URFs (10,4%), subtipo B (5,2%), CRF05_DF (3,0%), subtipo C (2,2%), CRF06_cpx (0,7%), CRF25_cpx (0,7%) e CRF49_cpx (0,7%), e todas as infecções por HIV-2 pertencem ao grupo A. De acordo com as análises filogeográficas e de origem do HIV, estima-se que o HIV-2 foi o primeiro tipo viral introduzido em Cabo Verde e possui relações filogenéticas com sequências referências de Portugal. O HIV-1 entrou no país mais tarde, primeiramente pelo subtipo G, evidenciando relações com sequências da África Central e de Portugal. Transmissão de DRM (TDRM) foi observada em 3,4% (2/58) de pacientes HIV-1 ARTn (1,7% NRTI, NNRTI 1,7%), mas não entre os infectados com HIV-2. Entre os pacientes ARTexp, DRM foi observada em 47,8% (33/69) dos infectados pelo HIV-1 (37,7% NRTI, NNRTI 37,7%, 7,4% de PI, 33,3% para duas classes) e 17,6% (3/17) nos infectados pelo HIV-2 (17,6%, 11,8% NRTI PI, 11,8% para ambas as classes). Este estudo indica que Cabo Verde tem um cenário epidemiológico molecular complexo e único dominado pelo HIV-1 subtipo G, CRF02_AG e F1 e HIV-2 grupo A, sendo esse o primeiro tipo viral introduzido em Cabo Verde. A ocorrência de TDRM e o nível relativamente elevado de DRM entre os pacientes tratados constituem uma preocupação, pelo que o monitoramento contínuo dos pacientes em ARTexp, incluindo genotipagem são políticas públicas a serem implementadas.

Aptidão agrícola e algoritmos genéticos na organização espacial em projetos de reforma agrária

A definição das parcelas familiares em projetos de reforma agrária envolve questões técnicas e sociais. Essas questões estão associadas principalmente às diferentes aptidões agrícolas do solo nestes projetos. O objetivo deste trabalho foi apresentar método para realizar o processo de ordenamento territorial em assentamentos de reforma agrária empregando Algoritmo Genético (AG). O AG foi testado no Projeto de Assentamento Veredas, em Minas Gerais, e implementado com base no sistema de aptidão agrícola das terras.

Comparação dos algoritmos delineação rápida em cadeia e seriação, para a construção de mapas genéticos

O objetivo deste trabalho foi avaliar a eficiência, na construção de mapas genéticos, dos algoritmos seriação e delineação rápida em cadeia, além dos critérios para avaliação de ordens: produto mínimo das frações de recombinação adjacentes, soma mínima das frações de recombinação adjacentes e soma máxima dos LOD Scores adjacentes, quando usados com o algoritmo de verificação de erros " ripple" . Foi simulado um mapa com 24 marcadores, posicionados aleatoriamente a distâncias variadas, com média 10 cM. Por meio do método Monte Carlo, foram obtidas 1.000 populações de retrocruzamento e 1.000 populações F2, com 200 indivíduos cada, e diferentes combinações de marcadores dominantes e co-dominantes (100% co-dominantes, 100% dominantes e mistura com 50% co-dominantes e 50% dominantes). Foi, também, simulada a perda de 25, 50 e 75% dos dados. Observou-se que os dois algoritmos avaliados tiveram desempenho semelhante e foram sensíveis à presença de dados perdidos e à presença de marcadores dominantes; esta última dificultou a obtenção de estimativas com boa acurácia, tanto da ordem quanto da distância. Além disso, observou-se que o algoritmo " ripple" geralmente aumenta o número de ordens corretas e pode ser combinado com os critérios soma mínima das frações de recombinação adjacentes e produto mínimo das frações de recombinação adjacentes.

Algoritmos genéticos para la anonimización de grafos

Peer-reviewed