Evolutionary computation of forests with Degree- and Role-Constrained Minimum Spanning Trees

Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode these forests. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight different evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm, generational genetic algorithm, steady-state genetic algorithm, covariance matrix adaptation evolution strategy, differential evolution, elitist evolution strategy, non-elitist evolution strategy and particle swarm optimization. The best results are for the estimation of distribution algorithms and both types of genetic algorithms, although the genetic algorithms are significantly faster.

Computación evolutiva de bosques de expansión mínimos con restricción de grado y de rol

Encontrar el árbol de expansión mínimo con restricción de grado de un grafo (DCMST por sus siglas en inglés) es un problema NP-complejo ampliamente estudiado. Una de sus aplicaciones más importantes es el dise~no de redes. Aquí nosotros tratamos una nueva variante del problema DCMST, que consiste en encontrar el árbol de expansión mínimo no solo con restricciones de grado, sino también con restricciones de rol (DRCMST), es decir, a~nadimos restricciones para restringir el rol que los nodos tienen en el árbol. Estos roles pueden ser nodo raíz, nodo intermedio o nodo hoja. Por otra parte, no limitamos el número de nodos raíz a uno, por lo que, en general, construiremos bosques de DRCMSTs. El modelado en los problemas de dise~no de redes puede beneficiarse de la posibilidad de generar más de un árbol y determinar el rol de los nodos en la red. Proponemos una nueva representación basada en permutaciones para codificar los bosques de DRCMSTs. En esta nueva representación, una permutación codifica simultáneamente todos los árboles que se construirán. Nosotros simulamos una amplia variedad de problemas DRCMST que optimizamos utilizando ocho algoritmos de computación evolutiva diferentes que codifican los individuos de la población utilizando la representación propuesta. Los algoritmos que utilizamos son: algoritmo de estimación de distribuciones (EDA), algoritmo genético generacional (gGA), algoritmo genético de estado estacionario (ssGA), estrategia evolutiva basada en la matriz de covarianzas (CMAES), evolución diferencial (DE), estrategia evolutiva elitista (ElitistES), estrategia evolutiva no elitista (NonElitistES) y optimización por enjambre de partículas (PSO). Los mejores resultados fueron para el algoritmo de estimación de distribuciones utilizado y ambos tipos de algoritmos genéticos, aunque los algoritmos genéticos fueron significativamente más rápidos.---ABSTRACT---Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode the forest of DRCMSTs. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight diferent evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm (EDA), generational genetic algorithm (gGA), steady-state genetic algorithm (ssGA), covariance matrix adaptation evolution strategy (CMAES), diferential evolution (DE), elitist evolution strategy (ElististES), non-elitist evolution strategy (NonElististES) and particle swarm optimization (PSO). The best results are for the estimation of distribution algorithm and both types of genetic algorithms, although the genetic algorithms are significantly faster. iv

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.

Searching oligo sets of human chromosome 12 using evolutionary strategies

DNA Microarray is a powerful tool to measure the level of a mixed population of nucleic acids at one time, which has great impact in many aspects of life sciences research. In order to distinguish nucleic acids with very similar composition by hybridization, it is necessary to design microarray probes with high specificities and sensitivities. Highly specific probes correspond to probes having unique DNA sequences; whereas highly sensitive probes correspond to those with melting temperature within a desired range and having no secondary structure. The selection of these probes from a set of functional DNA sequences (exons) constitutes a computationally expensive discrete non-linear search problem. We delegate the search task to a simple yet effective Evolution Strategy algorithm. The computational efficiency is also greatly improved by making use of an available bioinformatics tool.

Correlated evolution of mating strategy and inbreeding depression within and among populations of the hermaphroditic snail Physa acuta

Inbreeding depression is one of the main forces opposing the evolution of self-fertilization. Of central importance is the hypothesis that inbreeding depression and selfing coevolve antagonistically, generating either low selfing rate and high inbreeding depression or vice versa. However, there is limited evidence for this coevolution within species. We investigated this topic in the hermaphroditic snail Physa acuta. In this species, isolated individuals delay the onset of egg laying compared to individuals having access to mates. Longer delays (''waiting times'') indicate more intense selfing avoidance. We measured inbreeding depression and waiting time in a large quantitative-genetic experiment (281 outbred families derived from 26 natural populations). We observed large genetic variance for both traits and a strong positive genetic covariance between them, most of which resided within rather than among populations. It means that, within populations, individuals with higher mutation load avoided selfing more strongly on average. This genetic covariance may result from pleiotropy and/or linkage disequilibrium. Whatever its genetic architecture, the fact it emerges specifically when individuals are deprived of mates suggests it is not fortuitous and rather reflects the action of natural selection. We conclude that a diversity of mating strategies can arise within populations subjected to variation in inbreeding depression.

The evolution of strategy: thinking war from antiquity to the present

Latin had no word for "strategy", but the East Romans, whom we call the Byzantines, did. This book tracks the evolution of the concept of warfare being subjected to higher political aims from Antiquity to the Present, using Greek, Latin, French, Spanish, Italian, English and German sources. It tracks the rise, fall, and resurrection of the belief in the Roman and later the medieval and early modern world that warfare was only legitimate if it pursued the higher goal of a just peace, which in the 19th century gave way to a blinkered concentration on military victory as only war aim. It explains why one school of thought, from Antiquity to the present, emphasised eternal principles of warfare, while others emphasised, in Clausewitz's term, the "changing character of war". It tracks ideas from land warfare to naval warfare to air power and nuclear thinking, but it also stresses great leaps and discontinuities in thinking about strategy. It covers asymmetric wars both from the point of view of the weaker power seeking to overthrow a stronger power, and from the stronger power dealing with insurgents and other numerically inferior forces. It concludes with a commentary of the long-known problems of bureaucratic politics, non-centralised command and inter-service rivalry, which since the 16th century or earlier has created obstacles to coherent strategy making.

First-best technological strategy in an Nth-BEST economic context: a case-study of the evolution of the Acindar steelplant in Rosario, Argentina""

Includes bibliography

A two-phase strategy for detecting recombination in nucleotide sequences

Genetic recombination can produce heterogeneous phylogenetic histories within a set of homologous genes. Delineating recombination events is important in the study of molecular evolution, as inference of such events provides a clearer picture of the phylogenetic relationships among different gene sequences or genomes. Nevertheless, detecting recombination events can be a daunting task, as the performance of different recombination-detecting approaches can vary, depending on evolutionary events that take place after recombination. We previously evaluated the effects of post-recombination events on the prediction accuracy of recombination-detecting approaches using simulated nucleotide sequence data. The main conclusion, supported by other studies, is that one should not depend on a single method when searching for recombination events. In this paper, we introduce a two-phase strategy, applying three statistical measures to detect the occurrence of recombination events, and a Bayesian phylogenetic approach to delineate breakpoints of such events in nucleotide sequences. We evaluate the performance of these approaches using simulated data, and demonstrate the applicability of this strategy to empirical data. The two-phase strategy proves to be time-efficient when applied to large datasets, and yields high-confidence results.

A Practical Teaching Course in Directed Protein Evolution Using the Green Fluorescent Protein as a Model

Protein engineering is a powerful tool, which correlates protein structure with specific functions, both in applied biotechnology and in basic research. Here, we present a practical teaching course for engineering the green fluorescent protein (GFP) from Aequorea victoria by a random mutagenesis strategy using error-prone polymerase chain reaction. Screening of bacterial colonies transformed with random mutant libraries identified GFP variants with increased fluorescence yields. Mapping the three-dimensional structure of these mutants demonstrated how alterations in structural features such as the environment around the fluorophore and properties of the protein surface can influence functional properties such as the intensity of fluorescence and protein solubility.

MRI based diffusion and perfusion predictive model to estimate stroke evolution

In this study we present a novel automated strategy for predicting infarct evolution, based on MR diffusion and perfusion images acquired in the acute stage of stroke. The validity of this methodology was tested on novel patient data including data acquired from an independent stroke clinic. Regions-of-interest (ROIs) defining the initial diffusion lesion and tissue with abnormal hemodynamic function as defined by the mean transit time (MTT) abnormality were automatically extracted from DWI/PI maps. Quantitative measures of cerebral blood flow (CBF) and volume (CBV) along with ratio measures defined relative to the contralateral hemisphere (r(a)CBF and r(a)CBV) were calculated for the MTT ROIs. A parametric normal classifier algorithm incorporating these measures was used to predict infarct growth. The mean r(a)CBF and r(a)CBV values for eventually infarcted MTT tissue were 0.70 +/-0.19 and 1.20 +/-0.36. For recovered tissue the mean values were 0.99 +/-0.25 and 1.87 +/-0.71, respectively. There was a significant difference between these two regions for both measures (P

Temporal evolution and spatial distribution of maternal death

OBJECTIVE To analyze the temporal evolution of maternal mortality and its spatial distribution.METHODS Ecological study with a sample made up of 845 maternal deaths in women between 10 and 49 years, registered from 1999 to 2008 in the state of Rio Grande do Sul, Southern Brazil. Data were obtained from Information System on Mortality of Ministry of Health. The maternal mortality ratio and the specific maternal mortality ratio were calculated from records, and analyzed by the Poisson regression model. In the spatial distribution, three maps of the state were built with the rates in the geographical macro-regions, in 1999, 2003, and 2008.RESULTS There was an increase of 2.0% in the period of ten years (95%CI 1.00;1.04; p = 0.01), with no significant change in the magnitude of the maternal mortality ratio. The Serra macro-region presented the highest maternal mortality ratio (1.15, 95%CI 1.08;1.21; p < 0.001). Most deaths in Rio Grande do Sul were of white women over 40 years, with a lower level of education. The time of delivery/abortion and postpartum are times of increased maternal risk, with a greater negative impact of direct causes such as hypertension and bleeding.CONCLUSIONS The lack of improvement in maternal mortality ratio indicates that public policies had no impact on women’s reproductive and maternal health. It is needed to qualify the attention to women’s health, especially in the prenatal period, seeking to identify and prevent risk factors, as a strategy of reducing maternal death.

Portuguese strategy for occupational safety and health 2008-2012 for public administration : priorites for action, progress in the implementation of the proposed measures and their impact on occupational safety outcomes

Apresentação realizada no OH&S Forum 2011 - International Forum on Occupational Health and Safety: Policies, profiles and services, na Finlândia de, 20 a 22 Junho de 2011.

One-step preparation of optically transparent Ni-Fe oxide film electrocatalyst for oxygen evolution reaction

Optically transparent cocatalyst film materials is very desirable for improved photoelectrochemical (PEC)oxygen evolution reaction (OER) over light harvesting photoelectrodes which require the exciting light to irradiate through the cocatalyst side, i.e., front-side illumination. In view of the reaction overpotential at electrode/electrolyte interface, the OER electrocatalysts have been extensively used as cocatalysts for PEC water oxidation on photoanode. In this work, the feasibility of a one-step fabrication of the transparent thin film catalyst for efficient electrochemical OER is investigated. The Ni-Fe bimetal oxide films, 200 nm in thickness, are used for study. Using a reactive magnetron co-sputtering technique, transparent(> 50% in wavelength range 500-2000 nm) Ni-Fe oxide films with high electrocatalytic activities were successfully prepared at room temperature. Upon optimization, the as-prepared bimetal oxide film with atomic ratio of Fe/Ni = 3:7 demonstrates the lowest overpotential for the OER in aqueous KOH solution, as low as 329 mV at current density of 2 mA cm 2, which is 135 and 108 mV lower than that of as-sputtered FeOx and NiOx thin films, respectively. It appears that this fabrication strategy is very promising to deposit optically transparent cocatalyst films on photoabsorbers for efficient PEC water splitting.

IPTV data reduction strategy to measure real users’ behaviours

Dissertação para obtenção do Grau de Mestre em Engenharia Informática