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.

Genetic variability and demographic history of Heliothis virescens (Lepidoptera: Noctuidae) populations from Brazil inferred by mtDNA sequences

Intra-and inter-population genetic variability and the demographic history of Heliothis virescens (F.) populations were evaluated by using mtDNA markers (coxI, coxII and nad6) with samples from the major cotton-and soybean-producing regions in Brazil in the growing seasons 2007/08, 2008/09 and 2009/10. AMOVA indicated low and non-significant genetic structure, regardless of geographical scale, growing season or crop, with most of genetic variation occurring within populations. Clustering analyzes also indicated low genetic differentiation. The haplotype network obtained with combined datasets resulted in 35 haplotypes, with 28 exclusive occurrences, four of them sampled only from soybean fields. The minimum spanning network showed star-shaped structures typical of populations that underwent a recent demographic expansion. The recent expansion was supported by other demographic analyzes, such as the Bayesian skyline plot, the unimodal distribution of paired differences among mitochondrial sequences, and negative and significant values of neutrality tests for the Tajima's D and Fu's F-S parameters. In addition, high values of haplotype diversity ((H) over cap) and low values of nucleotide diversity (pi), combined with a high number of low frequency haplotypes and values of theta(pi)<theta(W), suggested a recent demographic expansion of H. virescens populations in Brazil. This demographic event could be responsible for the low genetic structure currently found; however, haplotypes present uniquely at the same geographic regions and from one specific host plant suggest an initial differentiation among H. virescens populations within Brazil.

Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.

Analog circuit synthesis performing fast Pareto frontier exploration and analysis through 3D graphs

This paper presents a technique for performing analog design synthesis at circuit level providing feedback to the designer through the exploration of the Pareto frontier. A modified simulated annealing which is able to perform crossover with past anchor points when a local minimum is found which is used as the optimization algorithm on the initial synthesis procedure. After all specifications are met, the algorithm searches for the extreme points of the Pareto frontier in order to obtain a non-exhaustive exploration of the Pareto front. Finally, multi-objective particle swarm optimization is used to spread the results and to find a more accurate frontier. Piecewise linear functions are used as single-objective cost functions to produce a smooth and equal convergence of all measurements to the desired specifications during the composition of the aggregate objective function. To verify the presented technique two circuits were designed, which are: a Miller amplifier with 96 dB Voltage gain, 15.48 MHz unity gain frequency, slew rate of 19.2 V/mu s with a current supply of 385.15 mu A, and a complementary folded cascode with 104.25 dB Voltage gain, 18.15 MHz of unity gain frequency and a slew rate of 13.370 MV/mu s. These circuits were synthesized using a 0.35 mu m technology. The results show that the method provides a fast approach for good solutions using the modified SA and further good Pareto front exploration through its connection to the particle swarm optimization algorithm.

Dynamic texture segmentation based on deterministic partially self-avoiding walks

Recently there has been a considerable interest in dynamic textures due to the explosive growth of multimedia databases. In addition, dynamic texture appears in a wide range of videos, which makes it very important in applications concerning to model physical phenomena. Thus, dynamic textures have emerged as a new field of investigation that extends the static or spatial textures to the spatio-temporal domain. In this paper, we propose a novel approach for dynamic texture segmentation based on automata theory and k-means algorithm. In this approach, a feature vector is extracted for each pixel by applying deterministic partially self-avoiding walks on three orthogonal planes of the video. Then, these feature vectors are clustered by the well-known k-means algorithm. Although the k-means algorithm has shown interesting results, it only ensures its convergence to a local minimum, which affects the final result of segmentation. In order to overcome this drawback, we compare six methods of initialization of the k-means. The experimental results have demonstrated the effectiveness of our proposed approach compared to the state-of-the-art segmentation methods.

Variation in liana abundance and biomass along an elevational gradient in the tropical Atlantic Forest (Brazil)

Lianas play a key role in forest structure, species diversity, as well as functional aspects of tropical forests. Although the study of lianas in the tropics has increased dramatically in recent years, basic information on liana communities for the Brazilian Atlantic Forest is still scarce. To understand general patterns of liana abundance and biomass along an elevational gradient (0-1,100 m asl) of coastal Atlantic Forest, we carried out a standard census for lianas a parts per thousand yen1 cm in five 1-ha plots distributed across different forest sites. On average, we found a twofold variation in liana abundance and biomass between lowland and other forest types. Large lianas (a parts per thousand yen10 cm) accounted for 26-35% of total liana biomass at lower elevations, but they were not recorded in montane forests. Although the abundance of lianas displayed strong spatial structure at short distances, the present local forest structure played a minor role structuring liana communities at the scale of 0.01 ha. Compared to similar moist and wet Neotropical forests, lianas are slightly less abundant in the Atlantic Forest, but the total biomass is similar. Our study highlights two important points: (1) despite some studies have shown the importance of small-scale canopy disturbance and support availability, the spatial scale of the relationships between lianas and forest structure can vary greatly among tropical forests; (2) our results add to the evidence that past canopy disturbance levels and minimum temperature variation exert influence on the structure of liana communities in tropical moist forests, particularly along short and steep elevational gradients.

Testing the Performance of Fourteen Native Tropical Tree Species in Two Abandoned Pastures of the Lacandon Rainforest Region of Chiapas, Mexico

The rainforest of Mexico has been degraded and severely fragmented, and urgently require restoration. However, the practice of restoration has been limited by the lack of species-specific data on survival and growth responses to local environmental variation. This study explores the differential performance of 14 wet tropical early-, mid- or late-successional tree species that were grown in two abandoned pastures with contrasting land-use histories. After 18 months, seedling survival and growth of at least 7 of the 14 tree species studied were significantly higher in the site with a much longer history of land use (site 2). Saplings of the three early-successional species showed exceptional growth rates. However, differences in performance were noted in relation to the differential soil properties between the experimental sites. Mid-successional species generally showed slow growth rates but high seedling survival, whereas late-successional species exhibited poor seedling survival at both the study sites. Stepwise linear regressions revealed that the species integrated response index combining survivorship and growth measurements, was influenced mostly by differences in soil pH between the two abandoned pastures. Our results suggest that local environmental variation among abandoned pastures of contrasting land-use histories influences sapling survival and growth. Furthermore, the similarity of responses among species with the same successional status allowed us to make some preliminary site and species-specific silvicultural recommendations. Future field experiments should extend the number of species and the range of environmental conditions to identify site generalists or more narrowly adapted species, that we would call sensitive.

Hierarchical multi-label classification using local neural networks

Hierarchical multi-label classification is a complex classification task where the classes involved in the problem are hierarchically structured and each example may simultaneously belong to more than one class in each hierarchical level. In this paper, we extend our previous works, where we investigated a new local-based classification method that incrementally trains a multi-layer perceptron for each level of the classification hierarchy. Predictions made by a neural network in a given level are used as inputs to the neural network responsible for the prediction in the next level. We compare the proposed method with one state-of-the-art decision-tree induction method and two decision-tree induction methods, using several hierarchical multi-label classification datasets. We perform a thorough experimental analysis, showing that our method obtains competitive results to a robust global method regarding both precision and recall evaluation measures.