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.

Diversity and Physiological Characterization of D-Xylose-Fermenting Yeasts Isolated from the Brazilian Amazonian Forest

Background: This study is the first to investigate the Brazilian Amazonian Forest to identify new D-xylose-fermenting yeasts that might potentially be used in the production of ethanol from sugarcane bagasse hemicellulosic hydrolysates. Methodology/Principal Findings: A total of 224 yeast strains were isolated from rotting wood samples collected in two Amazonian forest reserve sites. These samples were cultured in yeast nitrogen base (YNB)-D-xylose or YNB-xylan media. Candida tropicalis, Asterotremella humicola, Candida boidinii and Debaryomyces hansenii were the most frequently isolated yeasts. Among D-xylose-fermenting yeasts, six strains of Spathaspora passalidarum, two of Scheffersomyces stipitis, and representatives of five new species were identified. The new species included Candida amazonensis of the Scheffersomyces clade and Spathaspora sp. 1, Spathaspora sp. 2, Spathaspora sp. 3, and Candida sp. 1 of the Spathaspora clade. In fermentation assays using D-xylose (50 g/L) culture medium, S. passalidarum strains showed the highest ethanol yields (0.31 g/g to 0.37 g/g) and productivities (0.62 g/L.h to 0.75 g/L.h). Candida amazonensis exhibited a virtually complete D-xylose consumption and the highest xylitol yields (0.55 g/g to 0.59 g/g), with concentrations up to 25.2 g/L. The new Spathaspora species produced ethanol and/or xylitol in different concentrations as the main fermentation products. In sugarcane bagasse hemicellulosic fermentation assays, S. stipitis UFMG-XMD-15.2 generated the highest ethanol yield (0.34 g/g) and productivity (0.2 g/L.h), while the new species Spathaspora sp. 1 UFMG-XMD-16.2 and Spathaspora sp. 2 UFMG-XMD-23.2 were very good xylitol producers. Conclusions/Significance: This study demonstrates the promise of using new D-xylose-fermenting yeast strains from the Brazilian Amazonian Forest for ethanol or xylitol production from sugarcane bagasse hemicellulosic hydrolysates.

EFFICIENT FAULT LOCATION IN UNDERGROUND DISTRIBUTION SYSTEMS THROUGH OPTIMUM-PATH FOREST

In this article we propose an efficient and accurate method for fault location in underground distribution systems by means of an Optimum-Path Forest (OPF) classifier. We applied the time domains reflectometry method for signal acquisition, which was further analyzed by OPF and several other well-known pattern recognition techniques. The results indicated that OPF and support vector machines outperformed artificial neural networks and a Bayesian classifier, but OPF was much more efficient than all classifiers for training, and the second fastest for classification.