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.

A survey of evolutionary algorithms for decision-tree induction

This paper presents a survey of evolutionary algorithms that are designed for decision-tree induction. In this context, most of the paper focuses on approaches that evolve decision trees as an alternate heuristics to the traditional top-down divide-and-conquer approach. Additionally, we present some alternative methods that make use of evolutionary algorithms to improve particular components of decision-tree classifiers. The paper's original contributions are the following. First, it provides an up-to-date overview that is fully focused on evolutionary algorithms and decision trees and does not concentrate on any specific evolutionary approach. Second, it provides a taxonomy, which addresses works that evolve decision trees and works that design decision-tree components by the use of evolutionary algorithms. Finally, a number of references are provided that describe applications of evolutionary algorithms for decision-tree induction in different domains. At the end of this paper, we address some important issues and open questions that can be the subject of future research.

Evolutionary Insights from Bat Trypanosomes: Morphological, Developmental and Phylogenetic Evidence of a New Species, Trypanosoma (Schizotrypanum) erneyi sp nov., in African Bats Closely Related to Trypanosoma (Schizotrypanum) cruzi and Allied Species

Parasites of the genus Trypanosoma are common in bats and those of the subgenus Schizotrypanum are restricted to bats throughout the world, with the exception of Trypanosoma (Schizotrypanum) cruzi that also infects other mammals and is restricted to the American Continent. We have characterized trypanosome isolates from Molossidae bats captured in Mozambique, Africa. Morphology and behaviour in culture, supported by phylogenetic inferences using SSU (small subunit) rRNA, gGAPDH (glycosomal glyceraldehyde 3-phosphate dehydrogenase) and Cyt b (cytochrome b) genes, allowed to classify the isolates as a new Schizotrypanum species named Trypanosoma (Schizotrypanum) erneyi sp. nov. This is the first report of a Schizotrypanum species from African bats cultured, characterized morphologically and biologically, and positioned in phylogenetic trees. The unprecedented finding of a new species of the subgenus Schizotrypanum from Africa that is closest related to the America-restricted Trypanosoma (Schizotrypanum) cruzi marinkellei and T. cruzi provides new insights into the origin and evolutionary history of T. cruzi and closely related bat trypanosomes. Altogether, data from our study support the hypothesis of an ancestor trypanosome parasite of bats evolving to infect other mammals, even humans, and adapted to transmission by triatomine bugs in the evolutionary history of T. cruzi in the New World. (c) 2012 Elsevier GmbH. All rights reserved.

Phylogenetic relationship of dengue virus type 3 isolated in Brazil and Paraguay and global evolutionary divergence dynamics

Background: Dengue is the most important mosquito-borne viral disease worldwide. Dengue virus comprises four antigenically related viruses named dengue virus type 1 to 4 (DENV1-4). DENV-3 was re-introduced into the Americas in 1994 causing outbreaks in Nicaragua and Panama. DENV-3 was introduced in Brazil in 2000 and then spread to most of the Brazilian States, reaching the neighboring country, Paraguay in 2002. In this study, we have analyzed the phylogenetic relationship of DENV-3 isolated in Brazil and Paraguay with viruses isolated worldwide. We have also analyzed the evolutionary divergence dynamics of DENV-3 viruses. Results: The entire open reading frame (ORF) of thirteen DENV-3 isolated in Brazil (n = 9) and Paraguay (n = 4) were sequenced for phylogenetic analysis. DENV-3 grouped into three main genotypes (I, II and III). Several internal clades were found within each genotype that we called lineage and sub-lineage. Viruses included in this study belong to genotype III and grouped together with viruses isolated in the Americas within the lineage III. The Brazilian viruses were further segregated into two different sub-lineage, A and B, and the Paraguayan into the sub-lineage B. All three genotypes showed internal grouping. The nucleotide divergence was in average 6.7% for genotypes, 2.7% for lineages and 1.5% for sub-lineages. Phylogenetic trees constructed with any of the protein gene sequences showed the same segregation of the DENV-3 in three genotypes. Conclusion: Our results showed that two groups of DENV-3 genotypes III circulated in Brazil during 2002-2009, suggesting different events of introduction of the virus through different regions of the country. In Paraguay, only one group DENV-3 genotype III is circulating that is very closely related to the Brazilian viruses of sub-lineage B. Different degree of grouping can be observed for DENV-3 and each group showed a characteristic evolutionary divergence. Finally, we have observed that any protein gene sequence can be used to identify the virus genotype.

Evolving decision trees with beam search-based initialization and lexicographic multi-objective evaluation

Decision tree induction algorithms represent one of the most popular techniques for dealing with classification problems. However, traditional decision-tree induction algorithms implement a greedy approach for node splitting that is inherently susceptible to local optima convergence. Evolutionary algorithms can avoid the problems associated with a greedy search and have been successfully employed to the induction of decision trees. Previously, we proposed a lexicographic multi-objective genetic algorithm for decision-tree induction, named LEGAL-Tree. In this work, we propose extending this approach substantially, particularly w.r.t. two important evolutionary aspects: the initialization of the population and the fitness function. We carry out a comprehensive set of experiments to validate our extended algorithm. The experimental results suggest that it is able to outperform both traditional algorithms for decision-tree induction and another evolutionary algorithm in a variety of application domains.