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.

Transcriptional profiling of Saccharomyces cerevisiae exposed to propolis

Abstract Background Propolis is a natural product of plant resins collected by honeybees (Apis mellifera) from various plant sources. Our previous studies indicated that propolis sensitivity is dependent on the mitochondrial function and that vacuolar acidification and autophagy are important for yeast cell death caused by propolis. Here, we extended our understanding of propolis-mediated cell death in the yeast Saccharomyces cerevisiae by applying systems biology tools to analyze the transcriptional profiling of cells exposed to propolis. Methods We have used transcriptional profiling of S. cerevisiae exposed to propolis. We validated our findings by using real-time PCR of selected genes. Systems biology tools (physical protein-protein interaction [PPPI] network) were applied to analyse the propolis-induced transcriptional bevavior, aiming to identify which pathways are modulated by propolis in S. cerevisiae and potentially influencing cell death. Results We were able to observe 1,339 genes modulated in at least one time point when compared to the reference time (propolis untreated samples) (t-test, p-value 0.01). Enrichment analysis performed by Gene Ontology (GO) Term finder tool showed enrichment for several biological categories among the genes up-regulated in the microarray hybridization such as transport and transmembrane transport and response to stress. Real-time RT-PCR analysis of selected genes showed by our microarray hybridization approach was capable of providing information about S. cerevisiae gene expression modulation with a considerably high level of confidence. Finally, a physical protein-protein (PPPI) network design and global topological analysis stressed the importance of these pathways in response of S. cerevisiae to propolis and were correlated with the transcriptional data obtained thorough the microarray analysis. Conclusions In summary, our data indicate that propolis is largely affecting several pathways in the eukaryotic cell. However, the most prominent pathways are related to oxidative stress, mitochondrial electron transport chain, vacuolar acidification, regulation of macroautophagy associated with protein target to vacuole, cellular response to starvation, and negative regulation of transcription from RNA polymerase II promoter. Our work emphasizes again the importance of S. cerevisiae as a model system to understand at molecular level the mechanism whereby propolis causes cell death in this organism at the concentration herein tested. Our study is the first one that investigates systematically by using functional genomics how propolis influences and modulates the mRNA abundance of an organism and may stimulate further work on the propolis-mediated cell death mechanisms in fungi.

Accelerating benders decomposition with heuristicmaster problem solutions

In this paper, a general scheme for generating extra cuts during the execution of a Benders decomposition algorithm is presented. These cuts are based on feasible and infeasible master problem solutions generated by means of a heuristic. This article includes general guidelines and a case study with a fixed charge network design problem. Computational tests with instances of this problem show the efficiency of the strategy. The most important aspect of the proposed ideas is their generality, which allows them to be used in virtually any Benders decomposition implementation.

Symmetry insights for design of supercomputer network topologies: roots and weights lattices

We present a family of networks whose local interconnection topologies are generated by the root vectors of a semi-simple complex Lie algebra. Cartan classification theorem of those algebras ensures those families of interconnection topologies to be exhaustive. The global arrangement of the network is defined in terms of integer or half-integer weight lattices. The mesh or torus topologies that network millions of processing cores, such as those in the IBM BlueGene series, are the simplest member of that category. The symmetries of the root systems of an algebra, manifested by their Weyl group, lends great convenience for the design and analysis of hardware architecture, algorithms and programs.

Application of discriminant analysis-based model for prediction of risk of low back disorders due to workplace design in industrial jobs

The occupational exposure limits of different risk factors for development of low back disorders (LBDs) have not yet been established. One of the main problems in setting such guidelines is the limited understanding of how different risk factors for LBDs interact in causing injury, since the nature and mechanism of these disorders are relatively unknown phenomena. Industrial ergonomists' role becomes further complicated because the potential risk factors that may contribute towards the onset of LBDs interact in a complex manner, which makes it difficult to discriminate in detail among the jobs that place workers at high or low risk of LBDs. The purpose of this paper was to develop a comparative study between predictions based on the neural network-based model proposed by Zurada, Karwowski & Marras (1997) and a linear discriminant analysis model, for making predictions about industrial jobs according to their potential risk of low back disorders due to workplace design. The results obtained through applying the discriminant analysis-based model proved that it is as effective as the neural network-based model. Moreover, the discriminant analysis-based model proved to be more advantageous regarding cost and time savings for future data gathering.

Brazilian psychiatric brain bank: a new contribution tool to network studies

There is an urgent need for expanding the number of brain banks serving psychiatric research. We describe here the Psychiatric Disorders arm of the Brain Bank of the Brazilian Aging Brain Study Group (Psy-BBBABSG), which is focused in bipolar disorder (BD) and obsessive compulsive disorder (OCD). Our protocol was designed to minimize limitations faced by previous initiatives, and to enable design-based neurostereological analyses. The Psy-BBBABSG first milestone is the collection of 10 brains each of BD and OCD patients, and matched controls. The brains are sourced from a population-based autopsy service. The clinical and psychiatric assessments were done by an expert team including psychiatrists, through an informant. One hemisphere was perfused-fixed to render an optimal fixation for conducting neurostereological studies. The other hemisphere was comprehensively dissected and frozen for molecular studies. In 20 months, we collected 36 brains. A final report was completed for 14 cases: 3 BDs, 4 major depressive disorders, 1 substance use disorder, 1 mood disorder NOS, 3 obsessive compulsive spectrum symptoms, 1 OCD and 1 schizophrenia. The majority were male (64%), and the average age at death was 67.2 +/- 9.0 years. The average postmortem interval was 16 h. Three matched controls were collected. The pilot stage confirmed that the protocols are well fitted to reach our goals. Our unique autopsy source makes possible to collect a fairly number of high quality cases in a short time. Such a collection offers an additional to the international research community to advance the understanding on neuropsychiatric diseases.

Phenol biodegradation by a microbial consortium: application of artificial neural network (ANN) modelling

In this study, an effective microbial consortium for the biodegradation of phenol was grown under different operational conditions, and the effects of phosphate concentration (1.4 g L-1, 2.8 g L-1, 4.2 g L-1), temperature (25 degrees C, 30 degrees C, 35 degrees C), agitation (150 rpm, 200 rpm, 250 rpm) and pH (6, 7, 8) on phenol degradation were investigated, whereupon an artificial neural network (ANN) model was developed in order to predict degradation. The learning, recall and generalization characteristics of neural networks were studied using data from the phenol degradation system. The efficiency of the model generated by the ANN was then tested and compared with the experimental results obtained. In both cases, the results corroborate the idea that aeration and temperature are crucial to increasing the efficiency of biodegradation.

Influence of pattern gradation on the design of piezocomposite energy harvesting devices using topology optimization

Piezoelectric materials can be used to convert oscillatory mechanical energy into electrical energy. Energy harvesting devices are designed to capture the ambient energy surrounding the electronics and convert it into usable electrical energy. The design of energy harvesting devices is not obvious, requiring optimization procedures. This paper investigates the influence of pattern gradation using topology optimization on the design of piezocomposite energy harvesting devices based on bending behavior. The objective function consists of maximizing the electric power generated in a load resistor. A projection scheme is employed to compute the element densities from design variables and control the length scale of the material density. Examples of two-dimensional piezocomposite energy harvesting devices are presented and discussed using the proposed method. The numerical results illustrate that pattern gradation constraints help to increase the electric power generated in a load resistor and guides the problem toward a more stable solution. (C) 2012 Elsevier Ltd. All rights reserved.

Design methodology of piezoelectric energy-harvesting skin using topology optimization

Abstract This paper describes a design methodology for piezoelectric energy harvester s that thinly encapsulate the mechanical devices and expl oit resonances from higher- order vibrational modes. The direction of polarization determines the sign of the pi ezoelectric tensor to avoid cancellations of electric fields from opposite polarizations in the same circuit. The resultant modified equations of state are solved by finite element method (FEM). Com- bining this method with the solid isotropic material with penalization (SIMP) method for piezoelectric material, we have developed an optimization methodology that optimizes the piezoelectric material layout and polarization direc- tion. Updating the density function of the SIMP method is performed based on sensitivity analysis, the sequen- tial linear programming on the early stage of the opti- mization, and the phase field method on the latter stage

Multi-objective evolutionary algorithm for single and multiple fault service restoration in large-scale distribution systems

Network reconfiguration for service restoration (SR) in distribution systems is a complex optimization problem. For large-scale distribution systems, it is computationally hard to find adequate SR plans in real time since the problem is combinatorial and non-linear, involving several constraints and objectives. Two Multi-Objective Evolutionary Algorithms that use Node-Depth Encoding (NDE) have proved able to efficiently generate adequate SR plans for large distribution systems: (i) one of them is the hybridization of the Non-Dominated Sorting Genetic Algorithm-II (NSGA-II) with NDE, named NSGA-N; (ii) the other is a Multi-Objective Evolutionary Algorithm based on subpopulation tables that uses NDE, named MEAN. Further challenges are faced now, i.e. the design of SR plans for larger systems as good as those for relatively smaller ones and for multiple faults as good as those for one fault (single fault). In order to tackle both challenges, this paper proposes a method that results from the combination of NSGA-N, MEAN and a new heuristic. Such a heuristic focuses on the application of NDE operators to alarming network zones according to technical constraints. The method generates similar quality SR plans in distribution systems of significantly different sizes (from 3860 to 30,880 buses). Moreover, the number of switching operations required to implement the SR plans generated by the proposed method increases in a moderate way with the number of faults.

Programmable logic design of a compact Genetic Algorithm for phasor estimation in real-time

The main objective of this work is to present an efficient method for phasor estimation based on a compact Genetic Algorithm (cGA) implemented in Field Programmable Gate Array (FPGA). To validate the proposed method, an Electrical Power System (EPS) simulated by the Alternative Transients Program (ATP) provides data to be used by the cGA. This data is as close as possible to the actual data provided by the EPS. Real life situations such as islanding, sudden load increase and permanent faults were considered. The implementation aims to take advantage of the inherent parallelism in Genetic Algorithms in a compact and optimized way, making them an attractive option for practical applications in real-time estimations concerning Phasor Measurement Units (PMUs).