Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions

This work deals with the problem of minimizing the waste of space that occurs on a rotational placement of a set of irregular two dimensional polygons inside a two dimensional container. This problem is approached with an heuristic based on simulated annealing. Traditional 14 external penalization"" techniques are avoided through the application of the no-fit polygon, that determinates the collision free area for each polygon before its placement. The simulated annealing controls: the rotation applied, the placement and the sequence of placement of the polygons. For each non placed polygon, a limited depth binary search is performed to find a scale factor that when applied to the polygon, would allow it to be fitted in the container. It is proposed a crystallization heuristic, in order to increase the number of accepted solutions. The bottom left and larger first deterministic heuristics were also studied. The proposed process is suited for non convex polygons and containers, the containers can have holes inside. (C) 2009 Elsevier Ltd. All rights reserved.

Placement over containers with fixed dimensions solved with adaptive neighborhood simulated annealing

This work deals with the problem of minimizing the waste of space that occurs on a rotational placement of a set of irregular bi-dimensional items inside a bi-dimensional container. This problem is approached with a heuristic based on Simulated Annealing (SA) with adaptive neighborhood. The objective function is evaluated in a constructive approach, where the items are placed sequentially. The placement is governed by three different types of parameters: sequence of placement, the rotation angle and the translation. The rotation applied and the translation of the polygon are cyclic continuous parameters, and the sequence of placement defines a combinatorial problem. This way, it is necessary to control cyclic continuous and discrete parameters. The approaches described in the literature deal with only type of parameter (sequence of placement or translation). In the proposed SA algorithm, the sensibility of each continuous parameter is evaluated at each iteration increasing the number of accepted solutions. The sensibility of each parameter is associated to its probability distribution in the definition of the next candidate.

Hybrid Algorithms for Routing and Assignment Wavelengths in Optical Networks

This paper presents a strategy for the solution of the WDM optical networks planning. Specifically, the problem of Routing and Wavelength Allocation (RWA) in order to minimize the amount of wavelengths used. In this case, the problem is known as the Min-RWA. Two meta-heuristics (Tabu Search and Simulated Annealing) are applied to take solutions of good quality and high performance. The key point is the degradation of the maximum load on the virtual links in favor of minimization of number of wavelengths used; the objective is to find a good compromise between the metrics of virtual topology (load in Gb/s) and of the physical topology (quantity of wavelengths). The simulations suggest good results when compared to some existing in the literature.

Reconfiguration of distribution networks to minimize loss and disruption costs using genetic algorithms

In this paper a computational implementation of an evolutionary algorithm (EA) is shown in order to tackle the problem of reconfiguring radial distribution systems. The developed module considers power quality indices such as long duration interruptions and customer process disruptions due to voltage sags, by using the Monte Carlo simulation method. Power quality costs are modeled into the mathematical problem formulation, which are added to the cost of network losses. As for the EA codification proposed, a decimal representation is used. The EA operators, namely selection, recombination and mutation, which are considered for the reconfiguration algorithm, are herein analyzed. A number of selection procedures are analyzed, namely tournament, elitism and a mixed technique using both elitism and tournament. The recombination operator was developed by considering a chromosome structure representation that maps the network branches and system radiality, and another structure that takes into account the network topology and feasibility of network operation to exchange genetic material. The topologies regarding the initial population are randomly produced so as radial configurations are produced through the Prim and Kruskal algorithms that rapidly build minimum spanning trees. (C) 2009 Elsevier B.V. All rights reserved.

GOOAL: A routine based on Genetic Algorithms to track harmonics in electric power systems

Voltage and current waveforms of a distribution or transmission power system are not pure sinusoids. There are distortions in these waveforms that can be represented as a combination of the fundamental frequency, harmonics and high frequency transients. This paper presents a novel approach to identifying harmonics in power system distorted waveforms. The proposed method is based on Genetic Algorithms, which is an optimization technique inspired by genetics and natural evolution. GOOAL, a specially designed intelligent algorithm for optimization problems, was successfully implemented and tested. Two kinds of representations concerning chromosomes are utilized: binary and real. The results show that the proposed method is more precise than the traditional Fourier Transform, especially considering the real representation of the chromosomes.

Simulated annealing with adaptive neighborhood: A case study in off-line robot path planning

Simulated annealing (SA) is an optimization technique that can process cost functions with degrees of nonlinearities, discontinuities and stochasticity. It can process arbitrary boundary conditions and constraints imposed on these cost functions. The SA technique is applied to the problem of robot path planning. Three situations are considered here: the path is represented as a polyline; as a Bezier curve; and as a spline interpolated curve. In the proposed SA algorithm, the sensitivity of each continuous parameter is evaluated at each iteration increasing the number of accepted solutions. The sensitivity of each parameter is associated to its probability distribution in the definition of the next candidate. (C) 2010 Elsevier Ltd. All rights reserved.

Optimal subdivision of land in agrarian reform projects: an analysis using genetic algorithms

J.A. Ferreira Neto, E.C. Santos Junior, U. Fra Paleo, D. Miranda Barros, and M.C.O. Moreira. 2011. Optimal subdivision of land in agrarian reform projects: an analysis using genetic algorithms. Cien. Inv. Agr. 38(2): 169-178. The objective of this manuscript is to develop a new procedure to achieve optimal land subdivision using genetic algorithms (GA). The genetic algorithm was tested in the rural settlement of Veredas, located in Minas Gerais, Brazil. This implementation was based on the land aptitude and its productivity index. The sequence of tests in the study was carried out in two areas with eight different agricultural aptitude classes, including one area of 391.88 ha subdivided into 12 lots and another of 404.1763 ha subdivided into 14 lots. The effectiveness of the method was measured using the shunting line standard value of a parceled area lot`s productivity index. To evaluate each parameter, a sequence of 15 calculations was performed to record the best individual fitness average (MMI) found for each parameter variation. The best parameter combination found in testing and used to generate the new parceling with the GA was the following: 320 as the generation number, a population of 40 individuals, 0.8 mutation tax, and a 0.3 renewal tax. The solution generated rather homogeneous lots in terms of productive capacity.

Geometric morphometrics of the wing as a tool for assigning genetic lineages and geographic origin to Melipona beecheii (Hymenoptera: Meliponini)

The stingless bee Melipona beecheii presents great variability and is considered a complex of species. In order to better understand this species complex, we need to evaluate its diversity and develop methods that allow geographic traceability of the populations. Here we present a fast, efficient, and inexpensive means to accomplish this using geometric morphometrics of wings. We collected samples from Mexico, Guatemala, El Salvador, Nicaragua, and Costa Rica and we were able to correctly assign 87.1% of the colonies to their sampling sites and 92.4% to their haplotype. We propose that geometric morphometrics of the wing could be used as a first step analysis leaving the more expensive molecular analysis only to doubtful cases.

Vascular Endothelial Growth Factor Genetic Polymorphisms and Haplotypes in Women with Migraine

Vascular endothelial growth factor (VEGF) production is regulated by growth factors and inflammatory cytokines, and VEGF plays a role in migraine. We examined for the first time whether three functional polymorphisms in the promoter region of VEGF gene (C(-2578)A, G(-1154A), and G(-634C)) and VEGF haplotypes are associated with migraine. We studied 114 healthy women without migraine and 175 women with migraine (129 without aura, and 46 with aura). We found no differences in the distributions of VEGF genotypes and alleles (p > 0.05). However, the CAC haplotype was more frequent in controls than in migraine patients, and the AGC haplotype was more frequent in patients with migraine with aura than in controls (both p < 0.05). These findings suggest that VEGF haplotypes affect susceptibility to migraine.

A New Mouse Model for Marfan Syndrome Presents Phenotypic Variability Associated with the Genetic Background and Overall Levels of Fbn1 Expression

Marfan syndrome is an autosomal dominant disease of connective tissue caused by mutations in the fibrillin-1 encoding gene FBN1. Patients present cardiovascular, ocular and skeletal manifestations, and although being fully penetrant, MFS is characterized by a wide clinical variability both within and between families. Here we describe a new mouse model of MFS that recapitulates the clinical heterogeneity of the syndrome in humans. Heterozygotes for the mutant Fbn1 allele mg Delta(loxPneo), carrying the same internal deletion of exons 19-24 as the mg Delta mouse model, present defective microfibrillar deposition, emphysema, deterioration of aortic wall and kyphosis. However, the onset of a clinical phenotypes is earlier in the 129/Sv than in C57BL/6 background, indicating the existence of genetic modifiers of MFS between these two mouse strains. In addition, we characterized a wide clinical variability within the 129/Sv congenic heterozygotes, suggesting involvement of epigenetic factors in disease severity. Finally, we show a strong negative correlation between overall levels of Fbn1 expression and the severity of the phenotypes, corroborating the suggested protective role of normal fibrillin-1 in MFS pathogenesis, and supporting the development of therapies based on increasing Fbn1 expression.

Genetic variability and natural selection at the ligand domain of the Duffy binding protein in brazilian Plasmodium vivax populations

Background: Plasmodium vivax malaria is a major public health challenge in Latin America, Asia and Oceania, with 130-435 million clinical cases per year worldwide. Invasion of host blood cells by P. vivax mainly depends on a type I membrane protein called Duffy binding protein (PvDBP). The erythrocyte-binding motif of PvDBP is a 170 amino-acid stretch located in its cysteine-rich region II (PvDBP(II)), which is the most variable segment of the protein. Methods: To test whether diversifying natural selection has shaped the nucleotide diversity of PvDBP(II) in Brazilian populations, this region was sequenced in 122 isolates from six different geographic areas. A Bayesian method was applied to test for the action of natural selection under a population genetic model that incorporates recombination. The analysis was integrated with a structural model of PvDBP(II), and T-and B-cell epitopes were localized on the 3-D structure. Results: The results suggest that: (i) recombination plays an important role in determining the haplotype structure of PvDBP(II), and (ii) PvDBP(II) appears to contain neutrally evolving codons as well as codons evolving under natural selection. Diversifying selection preferentially acts on sites identified as epitopes, particularly on amino acid residues 417, 419, and 424, which show strong linkage disequilibrium. Conclusions: This study shows that some polymorphisms of PvDBP(II) are present near the erythrocyte-binding domain and might serve to elude antibodies that inhibit cell invasion. Therefore, these polymorphisms should be taken into account when designing vaccines aimed at eliciting antibodies to inhibit erythrocyte invasion.

COMPETITION AMONG EUCALYPTUS TREES DEPENDS ON GENETIC VARIATION AND RESOURCE SUPPLY

Genetic variation and environmental heterogeneity fundamentally shape the interactions between plants of the same species. According to the resource partitioning hypothesis, competition between neighbors intensifies as their similarity increases. Such competition may change in response to increasing supplies of limiting resources. We tested the resource partitioning hypothesis in stands of genetically identical (clone-origin) and genetically diverse (seed-origin) Eucalyptus trees with different water and nutrient supplies, using individual-based tree growth models. We found that genetic variation greatly reduced competitive interactions between neighboring trees, supporting the resource partitioning hypothesis. The importance of genetic variation for Eucalyptus growth patterns depended strongly on local stand structure and focal tree size. This suggests that spatial and temporal variation in the strength of species interactions leads to reversals in the growth rank of seed-origin and clone-origin trees. This study is one of the first to experimentally test the resource partitioning hypothesis for intergenotypic vs. intragenotypic interactions in trees. We provide evidence that variation at the level of genes, and not just species, is functionally important for driving individual and community-level processes in forested ecosystems.

Genetic structure and biology of Xylella fastidiosa strains causing disease in citrus and coffee in Brazil

Xylella fastidiosa is a vector-borne, plant-pathogenic bacterium that causes disease in citrus (citrus variegated chlorosis [CVC]) and coffee (coffee leaf scorch [CLS]) plants in Brazil. CVC and CLS occur sympatrically and share leafhopper vectors; thus, determining whether X. fastidiosa isolates can be dispersed from one crop to another and cause disease is of epidemiological importance. We sought to clarify the genetic and biological relationships between CVC- and CLS-causing X. fastidiosa isolates. We used cross-inoculation bioassays and microsatellite and multilocus sequence typing (MLST) approaches to determine the host range and genetic structure of 26 CVC and 20 CLS isolates collected from different regions in Brazil. Our results show that citrus and coffee X. fastidiosa isolates are biologically distinct. Cross-inoculation tests showed that isolates causing CVC and CLS in the field were able to colonize citrus and coffee plants, respectively, but not the other host, indicating biological isolation between the strains. The microsatellite analysis separated most X. fastidiosa populations tested on the basis of the host plant from which they were isolated. However, recombination among isolates was detected and a lack of congruency among phylogenetic trees was observed for the loci used in the MLST scheme. Altogether, our study indicates that CVC and CLS are caused by two biologically distinct strains of X. fastidiosa that have diverged but are genetically homogenized by frequent recombination.

Genetic structure and mating system of Euterpe edulis Mart. populations: A comparative analysis using microsatellite and allozyme markers

A comparative study between microsatellite and allozyme markers was conducted on the genetic structure and mating system in natural populations of Euterpe edulis Mart. Three cohorts, including seedlings, saplings, and adults, were examined in 4 populations using 10 allozyme loci and 10 microsatellite loci. As expected, microsatellite markers had a much higher degree of polymorphism than allozymes, but estimates of multilocus outcrossing rate ((t) over cap (m) = 1.00), as well as estimates of genetic structure (F(IS), G(ST)), were similar for the 2 sets of markers. Estimates of R(ST), for microsatellites, were higher than those of GST, but results of both statistics revealed a close agreement for the genetic structure of the species. This study provides support for the important conclusion that allozymes are still useful and reliable markers to estimate population genetic parameters. Effects of sample size on estimates from hypervariable loci are also discussed in this paper.