Evolving Distributed Algorithms with Genetic Programming

Distributed systems are one of the most vital components of the economy. The most prominent example is probably the internet, a constituent element of our knowledge society. During the recent years, the number of novel network types has steadily increased. Amongst others, sensor networks, distributed systems composed of tiny computational devices with scarce resources, have emerged. The further development and heterogeneous connection of such systems imposes new requirements on the software development process. Mobile and wireless networks, for instance, have to organize themselves autonomously and must be able to react to changes in the environment and to failing nodes alike. Researching new approaches for the design of distributed algorithms may lead to methods with which these requirements can be met efficiently. In this thesis, one such method is developed, tested, and discussed in respect of its practical utility. Our new design approach for distributed algorithms is based on Genetic Programming, a member of the family of evolutionary algorithms. Evolutionary algorithms are metaheuristic optimization methods which copy principles from natural evolution. They use a population of solution candidates which they try to refine step by step in order to attain optimal values for predefined objective functions. The synthesis of an algorithm with our approach starts with an analysis step in which the wanted global behavior of the distributed system is specified. From this specification, objective functions are derived which steer a Genetic Programming process where the solution candidates are distributed programs. The objective functions rate how close these programs approximate the goal behavior in multiple randomized network simulations. The evolutionary process step by step selects the most promising solution candidates and modifies and combines them with mutation and crossover operators. This way, a description of the global behavior of a distributed system is translated automatically to programs which, if executed locally on the nodes of the system, exhibit this behavior. In our work, we test six different ways for representing distributed programs, comprising adaptations and extensions of well-known Genetic Programming methods (SGP, eSGP, and LGP), one bio-inspired approach (Fraglets), and two new program representations called Rule-based Genetic Programming (RBGP, eRBGP) designed by us. We breed programs in these representations for three well-known example problems in distributed systems: election algorithms, the distributed mutual exclusion at a critical section, and the distributed computation of the greatest common divisor of a set of numbers. Synthesizing distributed programs the evolutionary way does not necessarily lead to the envisaged results. In a detailed analysis, we discuss the problematic features which make this form of Genetic Programming particularly hard. The two Rule-based Genetic Programming approaches have been developed especially in order to mitigate these difficulties. In our experiments, at least one of them (eRBGP) turned out to be a very efficient approach and in most cases, was superior to the other representations.

Validating Co-Training Models for Web Image Classification

Co-training is a semi-supervised learning method that is designed to take advantage of the redundancy that is present when the object to be identified has multiple descriptions. Co-training is known to work well when the multiple descriptions are conditional independent given the class of the object. The presence of multiple descriptions of objects in the form of text, images, audio and video in multimedia applications appears to provide redundancy in the form that may be suitable for co-training. In this paper, we investigate the suitability of utilizing text and image data from the Web for co-training. We perform measurements to find indications of conditional independence in the texts and images obtained from the Web. Our measurements suggest that conditional independence is likely to be present in the data. Our experiments, within a relevance feedback framework to test whether a method that exploits the conditional independence outperforms methods that do not, also indicate that better performance can indeed be obtained by designing algorithms that exploit this form of the redundancy when it is present.

Robust fault detection using consistency techniques for uncertainty handling

Often practical performance of analytical redundancy for fault detection and diagnosis is decreased by uncertainties prevailing not only in the system model, but also in the measurements. In this paper, the problem of fault detection is stated as a constraint satisfaction problem over continuous domains with a big number of variables and constraints. This problem can be solved using modal interval analysis and consistency techniques. Consistency techniques are then shown to be particularly efficient to check the consistency of the analytical redundancy relations (ARRs), dealing with uncertain measurements and parameters. Through the work presented in this paper, it can be observed that consistency techniques can be used to increase the performance of a robust fault detection tool, which is based on interval arithmetic. The proposed method is illustrated using a nonlinear dynamic model of a hydraulic system

SQualTrack: A Tool for Robust Fault Detection

One of the techniques used to detect faults in dynamic systems is analytical redundancy. An important difficulty in applying this technique to real systems is dealing with the uncertainties associated with the system itself and with the measurements. In this paper, this uncertainty is taken into account by the use of intervals for the parameters of the model and for the measurements. The method that is proposed in this paper checks the consistency between the system's behavior, obtained from the measurements, and the model's behavior; if they are inconsistent, then there is a fault. The problem of detecting faults is stated as a quantified real constraint satisfaction problem, which can be solved using the modal interval analysis (MIA). MIA is used because it provides powerful tools to extend the calculations over real functions to intervals. To improve the results of the detection of the faults, the simultaneous use of several sliding time windows is proposed. The result of implementing this method is semiqualitative tracking (SQualTrack), a fault-detection tool that is robust in the sense that it does not generate false alarms, i.e., if there are false alarms, they indicate either that the interval model does not represent the system adequately or that the interval measurements do not represent the true values of the variables adequately. SQualTrack is currently being used to detect faults in real processes. Some of these applications using real data have been developed within the European project advanced decision support system for chemical/petrochemical manufacturing processes and are also described in this paper

Desarrollo de una aplicación de computador para analizar parámetros estadísticos genético-poblacionales de microsatélites en poblaciones humanas

La información y los datos genéticos que emanan hoy de las investigaciones del genoma humano demandan el desarrollo de herramientas informáticas capaces de procesar la gran cantidad de información disponible. La mayor cantidad de datos genéticos es el resultado de equipos que realizan el análisis simultáneo de cientos o miles de polimorfismos o variaciones genéticas, de nuevas técnicas de laboratorio de mayor rendimiento que, en conjunto, ofrecen una mayor disponibilidad de información en un corto espacio de tiempo. Esta problemática conduce a la necesidad de desarrollar nuevas herramientas informáticas capaces de lidiar con este mayor volumen de datos genéticos. En el caso de la genética de poblaciones, a pesar de que existen herramientas informáticas que permiten procesar y facilitar el análisis de los datos, estas tienen limitaciones como la falta de conocimiento de los usuarios de algunos lenguajes de programación para alimentar la información y otras herramientas informáticas no realizan todas las estimaciones que se requieren y otros presentan limitaciones en cuanto al número de datos que pueden incorporar o manejar. En algunos casos hay redundancia al tener que usarse dos o más herramientas para poder procesar un conjunto de datos de información genética. El presente trabajo tiene por objetivo el desarrollo de una herramienta informática basada en aplicaciones de computador comunes, en este caso Microsoft Excel® y que resuelva todos los problemas y las limitaciones descritas antes. El desarrollo del conjunto de subprogramas que constituyen a Lustro; permiten superar lo anterior, presentar los resultados en un ambiente sencillo, conocido y fácil de operar, simplificando de esta forma el proceso de adaptación del usuario del programa, sin entrenamiento previo, obteniéndose en corto tiempo el procesamiento de la información genética de interés.

Big Data or Right Data?

Abstract Big data nowadays is a fashionable topic, independently of what people mean when they use this term. But being big is just a matter of volume, although there is no clear agreement in the size threshold. On the other hand, it is easy to capture large amounts of data using a brute force approach. So the real goal should not be big data but to ask ourselves, for a given problem, what is the right data and how much of it is needed. For some problems this would imply big data, but for the majority of the problems much less data will and is needed. In this talk we explore the trade-offs involved and the main problems that come with big data using the Web as case study: scalability, redundancy, bias, noise, spam, and privacy. Speaker Biography Ricardo Baeza-Yates Ricardo Baeza-Yates is VP of Research for Yahoo Labs leading teams in United States, Europe and Latin America since 2006 and based in Sunnyvale, California, since August 2014. During this time he has lead the labs in Barcelona and Santiago de Chile. Between 2008 and 2012 he also oversaw the Haifa lab. He is also part time Professor at the Dept. of Information and Communication Technologies of the Universitat Pompeu Fabra, in Barcelona, Spain. During 2005 he was an ICREA research professor at the same university. Until 2004 he was Professor and before founder and Director of the Center for Web Research at the Dept. of Computing Science of the University of Chile (in leave of absence until today). He obtained a Ph.D. in CS from the University of Waterloo, Canada, in 1989. Before he obtained two masters (M.Sc. CS & M.Eng. EE) and the electronics engineer degree from the University of Chile in Santiago. He is co-author of the best-seller Modern Information Retrieval textbook, published in 1999 by Addison-Wesley with a second enlarged edition in 2011, that won the ASIST 2012 Book of the Year award. He is also co-author of the 2nd edition of the Handbook of Algorithms and Data Structures, Addison-Wesley, 1991; and co-editor of Information Retrieval: Algorithms and Data Structures, Prentice-Hall, 1992, among more than 500 other publications. From 2002 to 2004 he was elected to the board of governors of the IEEE Computer Society and in 2012 he was elected for the ACM Council. He has received the Organization of American States award for young researchers in exact sciences (1993), the Graham Medal for innovation in computing given by the University of Waterloo to distinguished ex-alumni (2007), the CLEI Latin American distinction for contributions to CS in the region (2009), and the National Award of the Chilean Association of Engineers (2010), among other distinctions. In 2003 he was the first computer scientist to be elected to the Chilean Academy of Sciences and since 2010 is a founding member of the Chilean Academy of Engineering. In 2009 he was named ACM Fellow and in 2011 IEEE Fellow.

A proposal for the diagnosis of uncertain dynamic systems based on interval models

The performance of a model-based diagnosis system could be affected by several uncertainty sources, such as,model errors,uncertainty in measurements, and disturbances. This uncertainty can be handled by mean of interval models.The aim of this thesis is to propose a methodology for fault detection, isolation and identification based on interval models. The methodology includes some algorithms to obtain in an automatic way the symbolic expression of the residual generators enhancing the structural isolability of the faults, in order to design the fault detection tests. These algorithms are based on the structural model of the system. The stages of fault detection, isolation, and identification are stated as constraint satisfaction problems in continuous domains and solved by means of interval based consistency techniques. The qualitative fault isolation is enhanced by a reasoning in which the signs of the symptoms are derived from analytical redundancy relations or bond graph models of the system. An initial and empirical analysis regarding the differences between interval-based and statistical-based techniques is presented in this thesis. The performance and efficiency of the contributions are illustrated through several application examples, covering different levels of complexity.

Reading hybrid texts : remarks on text/image transitions

The reading of printed materials implies the visual processing of information originated in two distinct semiotic systems. The rapid identification of redundancy, complementation or contradiction rhetoric strategies between the two information types may be crucial for an adequate interpretation of bimodal materials. Hybrid texts (verbal and visual) are particular instances of bimodal materials, where the redundant information is often neglected while the complementary and the contradictory ones are essential.Studies using the 504 ASL eye-tracking system while reading either additive or exhibiting captions (Baptista, 2009) revealed fixations on the verbal material and transitions between the written and the pictorial in a much higher number and duration than the initially foreseen as necessary to read the verbal text. We therefore hypothesized that confirmation strategies of the written information are taking place, by using information available in the other semiotic system.Such eye-gaze patterns obtained from denotative texts and pictures seem to contradict some of the scarce existing data on visual processing of texts and images, namely cartoons (Carroll, Young and Guertain, 1992), descriptive captions (Hegarty, 1992 a and b), and advertising images with descriptive and explanatory texts (cf. Rayner and Rotello, 2001, who refer to a previous reading of the whole text before looking at the image, or even Rayner, Miller and Rotello, 2008 who refer to an earlier and longer look at the picture) and seem to consolidate findings of Radach et al. (2003) on systematic transitions between text and image.By framing interest areas in the printed pictorial material of non redundant hybrid texts, we have identified the specific areas where transitions take place after fixations in the verbal text. The way those transitions are processed brings a new interest to further research.

Edaphic influences on plant community adaptation in the Chiquibul forest of Belize

Edaphic variables figure significantly in plant community adaptations in tropical ecosystems but are often difficult to resolve because of the confounding influence of climate. Within the Chiquibul forest of Belize, large areas of Ultisols and Inceptisols occur juxtaposed within a larger zone of similar climate, permitting unambiguous assessment of edaphic contributions to forest composition. Wet chemical analyses, X-ray diffraction and X-ray fluorescence spectroscopy were employed to derive chemical (pH, exchangeable cations, CEC, total and organic C, total trace elements) and physical (texture, mineralogy) properties of four granite-derived Ustults from the Mountain Pine Ridge plateau and four limestone-derived Ustepts from the San Pastor region. The soils of these two regions support two distinct forests, each possessing a species composition reflecting the many contrasting physicochemical properties of the underlying soil. Within the Mountain Pine Ridge forest, species abundance and diversity is constrained by nutrient deficiencies and water-holding limitations imposed by the coarse textured, highly weathered Ultisols. As a consequence, the forest is highly adapted to seasonal drought, frequent fires and the significant input of atmospherically derived nutrients. The nutrient-rich Inceptisols of the San Pastor region, conversely, support an abundant and diverse evergreen forest, dominated by Sabal mauritiiformis, Cryosophila stauracantha and Manilkara spp. Moreover, the deep, fine textured soils in the depressions of the karstic San Pastor landscape collect and retain during the wet season much available water, thereby serving as refugia during particularly long periods of severe drought. To the extent that the soils of the Chiquibul region promote and maintain forest diversity, they also confer redundancy and resilience to these same forests and, to the broader ecosystem, of which they are a central part. (C) 2005 Elsevier B.V. All rights reserved.

Improving flood models using LiDAR: progress and problems

Airborne scanning laser altimetry (LiDAR) is an important new data source for river flood modelling. LiDAR can give dense and accurate DTMs of floodplains for use as model bathymetry. Spatial resolutions of 0.5m or less are possible, with a height accuracy of 0.15m. LiDAR gives a Digital Surface Model (DSM), so vegetation removal software (e.g. TERRASCAN) must be used to obtain a DTM. An example used to illustrate the current state of the art will be the LiDAR data provided by the EA, which has been processed by their in-house software to convert the raw data to a ground DTM and separate vegetation height map. Their method distinguishes trees from buildings on the basis of object size. EA data products include the DTM with or without buildings removed, a vegetation height map, a DTM with bridges removed, etc. Most vegetation removal software ignores short vegetation less than say 1m high. We have attempted to extend vegetation height measurement to short vegetation using local height texture. Typically most of a floodplain may be covered in such vegetation. The idea is to assign friction coefficients depending on local vegetation height, so that friction is spatially varying. This obviates the need to calibrate a global floodplain friction coefficient. It’s not clear at present if the method is useful, but it’s worth testing further. The LiDAR DTM is usually determined by looking for local minima in the raw data, then interpolating between these to form a space-filling height surface. This is a low pass filtering operation, in which objects of high spatial frequency such as buildings, river embankments and walls may be incorrectly classed as vegetation. The problem is particularly acute in urban areas. A solution may be to apply pattern recognition techniques to LiDAR height data fused with other data types such as LiDAR intensity or multispectral CASI data. We are attempting to use digital map data (Mastermap structured topography data) to help to distinguish buildings from trees, and roads from areas of short vegetation. The problems involved in doing this will be discussed. A related problem of how best to merge historic river cross-section data with a LiDAR DTM will also be considered. LiDAR data may also be used to help generate a finite element mesh. In rural area we have decomposed a floodplain mesh according to taller vegetation features such as hedges and trees, so that e.g. hedge elements can be assigned higher friction coefficients than those in adjacent fields. We are attempting to extend this approach to urban area, so that the mesh is decomposed in the vicinity of buildings, roads, etc as well as trees and hedges. A dominant points algorithm is used to identify points of high curvature on a building or road, which act as initial nodes in the meshing process. A difficulty is that the resulting mesh may contain a very large number of nodes. However, the mesh generated may be useful to allow a high resolution FE model to act as a benchmark for a more practical lower resolution model. A further problem discussed will be how best to exploit data redundancy due to the high resolution of the LiDAR compared to that of a typical flood model. Problems occur if features have dimensions smaller than the model cell size e.g. for a 5m-wide embankment within a raster grid model with 15m cell size, the maximum height of the embankment locally could be assigned to each cell covering the embankment. But how could a 5m-wide ditch be represented? Again, this redundancy has been exploited to improve wetting/drying algorithms using the sub-grid-scale LiDAR heights within finite elements at the waterline.

Redundant coordinates in harmonic force-field calculations

Redundancy relations between vibrational coordinates may be linear (as for rectilinear coordinates used in deriving a G matrix), or non-linear (as for curvilinear coordinates used in formulating model force fields). It is shown that geometrically defined internal coordinates are necessarily curvilinear. Hence it is shown that linear force constants can occur in model force field calculations involving redundant coordinates, in disagreement with the recent proposal of Gussoni and Zerbi.

Taxonomical vs. functional responses of bee communities to fire in two contrasting climatic regions

Valuable insights into mechanisms of community responses to environmental change can be gained by analysing in tandem the variation in functional and taxonomic composition along environmental gradients. We assess the changes in species and functional trait composition (i.e. dominant traits and functional diversity) of diverse bee communities in contrasting fire-driven systems in two climatic regions: Mediterranean (scrub habitats in Israel) and temperate (chestnut forests in southern Switzerland). In both climatic regions, there were shifts in species diversity and composition related to post-fire age. In the temperate region, functional composition responded markedly to fire; however, in the Mediterranean, the taxonomic response to fire was not matched by functional replacement. These results suggest that greater functional stability to fire in the Mediterranean is achieved by replacement of functionally similar species (i.e. functional redundancy) which dominate under different environmental conditions in the heterogeneous landscapes of the region. In contrast, the greater functional response in the temperate region was attributed to a more rapid post-fire vegetation recovery and shorter time-window when favourable habitat was available relative to the Mediterranean. Bee traits can be used to predict the functional responses of bee communities to environmental changes in habitats of conservation importance in different regions with distinct disturbance regimes. However, predictions cannot be generalized from one climatic region to another where distinct habitat configurations occur.

Macroevolutionary patterns in the origin of mutualisms involving ants

Ants are a diverse and abundant insect group that form mutualistic associations with a number of different organisms from fungi to insects and plants. Here, we use a phylogenetic approach to identify ecological factors that explain macroevolutionary trends in the mutualism between ants and honeydew-producing Homoptera. We also consider association between ant-Homoptera, ant-fungi and ant-plant mutualisms. Homoptera-tending ants are more likely to be forest dwelling, polygynous, ecologically dominant and arboreal nesting with large colonies of 10(4)-10(5) individuals. Mutualistic ants (including those that garden fungi and inhabit ant-plants) are found in under half of the formicid subfamilies. At the genus level, however, we find a negative association between ant-Homoptera and ant-fungi mutualisms, whereas there is a positive association between ant-Homoptera and ant-plant mutualisms. We suggest that species can only specialize in multiple mutualisms simultaneously when there is no trade-off in requirements from the different partners and no redundancy of rewards.

Novel high-resolution characterization of ancient DNA reveals C > U-type base modification events as the sole cause of post mortem miscoding lesions

Ancient DNA (aDNA) research has long depended on the power of PCR to amplify trace amounts of surviving genetic material from preserved specimens. While PCR permits specific loci to be targeted and amplified, in many ways it can be intrinsically unsuited to damaged and degraded aDNA templates. PCR amplification of aDNA can produce highly-skewed distributions with significant contributions from miscoding lesion damage and non-authentic sequence artefacts. As traditional PCR-based approaches have been unable to fully resolve the molecular nature of aDNA damage over many years, we have developed a novel single primer extension (SPEX)-based approach to generate more accurate sequence information. SPEX targets selected template strands at defined loci and can generate a quantifiable redundancy of coverage; providing new insights into the molecular nature of aDNA damage and fragmentation. SPEX sequence data reveals inherent limitations in both traditional and metagenomic PCR-based approaches to aDNA, which can make current damage analyses and correct genotyping of ancient specimens problematic. In contrast to previous aDNA studies, SPEX provides strong quantitative evidence that C U-type base modifications are the sole cause of authentic endogenous damage-derived miscoding lesions. This new approach could allow ancient specimens to be genotyped with unprecedented accuracy.

Mechanisms and function of flower and inflorescence reversion

Flower and inflorescence reversion involve a switch from floral development back to vegetative development, thus rendering flowering a phase in an ongoing growth pattern rather than a terminal act of the meristem. Although it can be considered an unusual event, reversion raises questions about the nature and function of flowering. It is linked to environmental conditions and is most often a response to conditions opposite to those that induce flowering. Research on molecular genetic mechanisms underlying plant development over the last 15 years has pinpointed some of the key genes involved in the transition to flowering and flower development. Such investigations have also uncovered mutations which reduce floral maintenance or alter the balance between vegetative and floral features of the plant. How this information contributes to an understanding of floral reversion is assessed here. One issue that arises is whether floral commitment (defined as the ability to continue flowering when inductive conditions no longer exist) is a developmental switch affecting the whole plant or is a mechanism which assigns autonomy to individual meristems. A related question is whether floral or vegetative development is the underlying default pathway of the plant. This review begins by considering how studies of flowering in Arabidopsis thaliana have aided understanding of mechanisms of floral maintenance. Arabidopsis has not been found to revert to leaf production in any of the conditions or genetic backgrounds analysed to date. A clear-cut reversion to leaf production has, however, been described in Impatiens balsamina. It is proposed that a single gene controls whether Impatiens reverts or can maintain flowering when inductive conditions are removed, and it is inferred that this gene functions to control the synthesis or transport of a leaf-generated signal. But it is also argued that the susceptibility of Impatiens to reversion is a consequence of the meristem-based mechanisms controlling development of the flower in this species. Thus, in Impatiens, a leaf-derived signal is critical for completion of flowering and can be considered to be the basis of a plant-wide floral commitment that is achieved without accompanying meristem autonomy. The evidence, derived from in vitro and other studies, that similar mechanisms operate in other species is assessed. It is concluded that most species (including Arabidopsis) are less prone to reversion because signals from the leaf are less ephemeral, and the pathways driving flower development have a high level of redundancy that generates meristem autonomy even when leaf-derived signals are weak. This gives stability to the flowering process, even where its initiation is dependent on environmental cues. On this interpretation, Impatiens reversion appears as an anomaly resulting from an unusual combination of leaf signalling and meristem regulation. Nevertheless, it is shown that the ability to revert can serve a function in the life history strategy (perenniality) or reproductive habit (pseudovivipary) of many plants. In these instances reversion has been assimilated into regular plant development and plays a crucial role there.