Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design

The design of a network is a solution to several engineering and science problems. Several network design problems are known to be NP-hard, and population-based metaheuristics like evolutionary algorithms (EAs) have been largely investigated for such problems. Such optimization methods simultaneously generate a large number of potential solutions to investigate the search space in breadth and, consequently, to avoid local optima. Obtaining a potential solution usually involves the construction and maintenance of several spanning trees, or more generally, spanning forests. To efficiently explore the search space, special data structures have been developed to provide operations that manipulate a set of spanning trees (population). For a tree with n nodes, the most efficient data structures available in the literature require time O(n) to generate a new spanning tree that modifies an existing one and to store the new solution. We propose a new data structure, called node-depth-degree representation (NDDR), and we demonstrate that using this encoding, generating a new spanning forest requires average time O(root n). Experiments with an EA based on NDDR applied to large-scale instances of the degree-constrained minimum spanning tree problem have shown that the implementation adds small constants and lower order terms to the theoretical bound.

Detecting an abnormality in a recovery boiler using dynamic multivariate data analysis with parallel coordinate plots

Data visualization techniques are powerful in the handling and analysis of multivariate systems. One such technique known as parallel coordinates was used to support the diagnosis of an event, detected by a neural network-based monitoring system, in a boiler at a Brazilian Kraft pulp mill. Its attractiveness is the possibility of the visualization of several variables simultaneously. The diagnostic procedure was carried out step-by-step going through exploratory, explanatory, confirmatory, and communicative goals. This tool allowed the visualization of the boiler dynamics in an easier way, compared to commonly used univariate trend plots. In addition it facilitated analysis of other aspects, namely relationships among process variables, distinct modes of operation and discrepant data. The whole analysis revealed firstly that the period involving the detected event was associated with a transition between two distinct normal modes of operation, and secondly the presence of unusual changes in process variables at this time.

DETERMINATION OF THE E/G RATIO OF WOOD LOGS USING TRANSVERSE VIBRATION

The Bernoulli's model for vibration of beams is often used to make predictions of bending modulus of elasticity when using dynamic tests. However this model ignores the rotary inertia and shear. Such effects can be added to the solution of Bernoulli's equation by means of the correction proposed by Goens (1931) or by Timoshenko (1953). But to apply these corrections it is necessary to know the E/G ratio of the material. The objective of this paper is the determination of the E/G ratio of wood logs by adjusting the analytical solution of the Timoshenko beam model to the dynamic testing data of 20 Eucalyptus citriodora logs. The dynamic testing was performed with the logs in free-free suspension. To find the stiffness properties of the logs, the residue minimization was carried out using the Genetic Algorithm (GA). From the result analysis one can reasonably assume E/G = 20 for wood logs.

Use of a Single L1 GPS Receiver for Monitoring Structures: First Results of the Detection of Millimetric Dynamic Oscillations

This paper presents preliminary results to determine small displacements of a global positioning system (GPS) antenna fastened to a structure using only one L1 GPS receiver. Vibrations, periodic or not, are common in large structures, such as bridges, footbridges, tall buildings, and towers under dynamic loads. The behavior in time and frequency leads to structural analysis studies. The hypothesis of this article is that any large structure that presents vibrations in the centimeter-to-millimeter range can be monitored by phase measurements of a single L1 receiver with a high data rate, as long as the direction of the displacement is pointing to a particular satellite. Within this scenario, the carrier phase will be modulated by antenna displacement. During a period of a few dozen seconds, the relative displacement to the satellite, the satellite clock, and the atmospheric phase delays can be assumed as a polynomial time function. The residuals from a polynomial adjustment contain the phase modulation owing to small displacements, random noise, receiver clock short time instabilities, and multipath. The results showed that it is possible to detect displacements of centimeters in the phase data of a single satellite and millimeters in the difference between the phases of two satellites. After applying a periodic nonsinusoidal displacement of 10 m to the antenna, it is clearly recovered in the difference of the residuals. The time domain spectrum obtained by the fast Fourier transform (FFT) exhibited a defined peak of the third harmonic much more than the random noise using the proposed third-degree polynomial model. DOI: 10.1061/(ASCE)SU.1943-5428.0000070. (C) 2012 American Society of Civil Engineers.

Evolution of extrafloral nectaries: adaptive process and selective regime changes from forest to savanna

Much effort has been devoted to understanding the function of extrafloral nectaries (EFNs) for antplantherbivore interactions. However, the pattern of evolution of such structures throughout the history of plant lineages remains unexplored. In this study, we used empirical knowledge on plant defences mediated by ants as a theoretical framework to test specific hypotheses about the adaptive role of EFNs during plant evolution. Emphasis was given to different processes (neutral or adaptive) and factors (habitat change and trade-offs with new trichomes) that may have affected the evolution of antplant associations. We measured seven EFN quantitative traits in all 105 species included in a well-supported phylogeny of the tribe Bignonieae (Bignoniaceae) and collected field data on antEFN interactions in 32 species. We identified a positive association between ant visitation (a surrogate of ant guarding) and the abundance of EFNs in vegetative plant parts and rejected the hypothesis of phylogenetic conservatism of EFNs, with most traits presenting K-values < 1. Modelling the evolution of EFN traits using maximum likelihood approaches further suggested adaptive evolution, with static-optimum models showing a better fit than purely drift models. In addition, the abundance of EFNs was associated with habitat shifts (with a decrease in the abundance of EFNs from forest to savannas), and a potential trade-off was detected between the abundance of EFNs and estipitate glandular trichomes (i.e. trichomes with sticky secretion). These evolutionary associations suggest divergent selection between species as well as explains K-values < 1. Experimental studies with multiple lineages of forest and savanna taxa may improve our understanding of the role of nectaries in plants. Overall, our results suggest that the evolution of EFNs was likely associated with the adaptive process which probably played an important role in the diversification of this plant group.