Hybrid evolutionary algorithm for the Capacitated Centered Clustering Problem

The Capacitated Centered Clustering Problem (CCCP) consists of defining a set of p groups with minimum dissimilarity on a network with n points. Demand values are associated with each point and each group has a demand capacity. The problem is well known to be NP-hard and has many practical applications. In this paper, the hybrid method Clustering Search (CS) is implemented to solve the CCCP. This method identifies promising regions of the search space by generating solutions with a metaheuristic, such as Genetic Algorithm, and clustering them into clusters that are then explored further with local search heuristics. Computational results considering instances available in the literature are presented to demonstrate the efficacy of CS. (C) 2010 Elsevier Ltd. All rights reserved.

Strong selection against hybrids at a hybrid zone in the Ensatina ring species complex and its evolutionary implications

The analysis of interactions between lineages at varying levels of genetic divergence can provide insights into the process of speciation through the accumulation of incompatible mutations. Ring species, and especially the Ensatina eschscholtzii system exemplify this approach. The plethodontid salamanders E. eschscholtzii xanthoptica and E. eschscholtzii platensis hybridize in the central Sierran foothills of California. We compared the genetic structure across two transects (southern and northern Calaveras Co.), one of which was resampled over 20 years, and examined diagnostic molecular markers (eight allozyme loci and mitochondrial DNA) and a diagnostic quantitative trait (color pattern). Key results across all studies were: (1) cline centers for all markers were coincident and the zones were narrow, with width estimates of 730 m to 2000 m; (2) cline centers at the northern Calaveras transect were coincident between 1981 and 2001, demonstrating repeatability over five generations; (3) there were very few if any putative F1s, but a relatively high number of backcrossed individuals in the central portion of transects: and (4) we found substantial linkage disequilibrium in all three studies and strong heterozygote deficit both in northern Calaveras, in 2001, and southern Calaveras. Both linkage disequilibrium and heterozygote deficit showed maximum values near the center of the zones. Using estimates of cline width and dispersal, we infer strong selection against hybrids. This is sufficient to promote accumulation of differences at loci that are neutral or under divergent selection, but would still allow for introgression of adaptive alleles. The evidence for strong but incomplete isolation across this centrally located contact is consistent with theory suggesting a gradual increase in postzygotic incompatibility between allopatric populations subject to divergent selection and reinforces the value of Ensatina as a system for the study of divergence and speciation at multiple stages. © 2005 The Society for the Study of Evolution. All rights reserved.

First radiation hybrid map of the river buffalo X chromosome (BBUX) and comparison with BTAX

We report the first radiation hybrid map of the river buffalo X chromosome generated from a recently constructed river buffalo (Bubalus bubalis) whole-genome radiation hybrid panel (BBURH5000). This map contains a total of 33 cattle-derived markers, including 10 genes, four ESTs and 19 microsatellites. The markers are distributed in two linkage groups: LG1 contains eight markers spanning 125.6 cR, and LG2 contains 25 markers spanning 366.3 cR. LG1 contains six markers in common with bovine sequence assembly BUILD 3.1. With the exception of BMS2152, the order of these markers on our BBUX map is shuffled when compared to the cow X chromosome (Bos taurus; BTAX). From LG2, two markers (AMELX and BL22) map to a more distal portion of BTAX compared to BBUX. In addition, two pairs of LG2 markers exhibit inversions compared to BTAX (ILSTS017 and ATRX; XBM38 and PPEF1). Alternatively, when compared to the most recent bovine RH map (Bov-Gen 3000rads), BL1098 and BMS2227 from LG1 as well as PLS3 and BMS1820 from LG2 showed inverted positions on the BBUX map. These discrepancies in buffalo and cattle maps may reflect evolutionary divergence of the chromosomes or mapping errors in one of the two species. Although the set of mapped markers does not cover the entire X chromosome, this map is a starting point for the construction of a high-resolution map, which is necessary for characterization of small rearrangements that might have occurred between the Bubalus bubalis and Bos taurus X chromosomes.

Programmable PFC based hybrid multipulse power rectifier for ultra clean power application

A novel hybrid three-phase rectifier is proposed. It is capable to achieve high input power factor (PF) and low total harmonic input currents distortion (THDI). The proposed hybrid high power rectifier is composed by a standard three-phase six-pulse diode rectifier (Graetz bridge) with a parallel connection of single-phase Sepic rectifiers in each three-phase rectifier leg. Such topology results in a structure capable of programming the input current waveform and providing conditions for obtaining high input power factor and low harmonic current distortion. In order to validate the proposed hybrid rectifier, this work describes its principles, with detailed operation, simulation, experimental results, and discussions on power rating of the required Sepic converters as related to the desired total harmonic current distortion. It is demonstrated that only a fraction of the output power is processed through the Sepic converters, making the proposed solution economically viable for very high power installations, with fast investment payback. Moreover, retrofitting to existing installations is also feasible since the parallel path can be easily controlled by integration with the existing dc-link. A prototype has been implemented in the laboratory and it was fully demonstrated to both operate with excellent performance and be feasibly implemented in higher power applications.

Planning of secondary distribution circuits through evolutionary algorithms

In this work, the planning of secondary distribution circuits is approached as a mixed integer nonlinear programming problem (MINLP). In order to solve this problem, a dedicated evolutionary algorithm (EA) is proposed. This algorithm uses a codification scheme, genetic operators, and control parameters, projected and managed to consider the specific characteristics of the secondary network planning. The codification scheme maps the possible solutions that satisfy the requirements in order to obtain an effective and low-cost projected system-the conductors' adequate dimensioning, load balancing among phases, and the transformer placed at the center of the secondary system loads. An effective algorithm for three-phase power flow is used as an auxiliary methodology of the EA for the calculation of the fitness function proposed for solutions of each topology. Results for two secondary distribution circuits are presented, whereas one presents radial topology and the other a weakly meshed topology. © 2005 IEEE.

Programmable PFC based hybrid multipulse power rectifier for utility interface of power electronic converters

In this paper it is proposed a novel hybrid three-phase rectifier capable to achieve high input power factor (PF), and low total harmonic distortion in the input currents (THDI). The proposed hybrid high power rectifier is composed by a standard three-phase 6-pulses diode rectifier (Graetz bridge) with a parallel connection of single-phase Boost rectifiers in each three-phase rectifier leg. Such topology results in a structure capable of programming the input current waveform and providing conditions for obtaining high input power factor and low harmonic current distortion. In order to validate the proposed hybrid rectifier, this paper describes its principles of operation, with detailed experimental results and discussions on power rating of the required Boost converters as related to the desired total harmonic current distortion. It is demonstrated that only a fraction of the output power is processed through the Boost converters, making the proposed solution economically viable for very high power installations, with fast pay back of the investment. Moreover, retrofitting to existing installations is also feasible since the parallel path can be easily controlled by integration with the existing de-link. A prototype rated at 6 kW has been implemented in laboratory and fully demonstrated its operation, performance and feasibility to high power applications. © 2005 IEEE.

Evolutionary heuristic to determine future land use

In the spatial electric load forecasting, the future land use determination is one of the most important tasks, and one of the most difficult, because of the stochastic nature of the city growth. This paper proposes a fast and efficient algorithm to find out the future land use for the vacant land in the utility service area, using ideas from knowledge extraction and evolutionary algorithms. The methodology was implemented into a full simulation software for spatial electric load forecasting, showing a high rate of success when the results are compared to information gathered from specialists. The importance of this methodology lies in the reduced set of data needed to perform the task and the simplicity for implementation, which is a great plus for most of the electric utilities without specialized tools for this planning activity. © 2008 IEEE.

A multi-objective programming approach for the optimal operation of distributed generation considering uncertainty

Due to the renewed interest in distributed generation (DG), the number of DG units incorporated in distribution systems has been rapidly increasing in the past few years. This situation requires new analysis tools for understanding system performance, and taking advantage of the potential benefits of DG. This paper presents an evolutionary multi-objective programming approach to determine the optimal operation of DG in distribution systems. The objectives are the minimization of the system power losses and operation cost of the DG units. The proposed approach also considers the inherent stochasticity of DG technologies powered by renewable resources. Some tests were carried out on the IEEE 34 bus distribution test system showing the robustness and applicability of the proposed methodology. © 2011 IEEE.

A hybrid multi-population genetic algorithm applied to solve the multi-level capacitated lot sizing problem with backlogging

The present paper proposes a new hybrid multi-population genetic algorithm (HMPGA) as an approach to solve the multi-level capacitated lot sizing problem with backlogging. This method combines a multi-population based metaheuristic using fix-and-optimize heuristic and mathematical programming techniques. A total of four test sets from the MULTILSB (Multi-Item Lot-Sizing with Backlogging) library are solved and the results are compared with those reached by two other methods recently published. The results have shown that HMPGA had a better performance for most of the test sets solved, specially when longer computing time is given. © 2012 Elsevier Ltd.

Genetic algorithm, MIP and improvement heuristic applied to the MLCLP with backlogging

The present paper solves the multi-level capacitated lot sizing problem with backlogging (MLCLSPB) combining a genetic algorithm with the solution of mixed-integer programming models and the improvement heuristic fix and optimize. This approach is evaluated over sets of benchmark instances and compared to methods from literature. Computational results indicate competitive results applying the proposed method when compared with other literature approaches. © 2013 IEEE.

A hybrid image restoration algorithm based on Projections onto Convex Sets and Harmony Search

Image restoration is a research field that attempts to recover a blurred and noisy image. Since it can be modeled as a linear system, we propose in this paper to use the meta-heuristics optimization algorithm Harmony Search (HS) to find out near-optimal solutions in a Projections Onto Convex Sets-based formulation to solve this problem. The experiments using HS and four of its variants have shown that we can obtain near-optimal and faster restored images than other evolutionary optimization approach. © 2013 IEEE.

A genetic algorithm/mathematical programming approach to solve a two-level soft drink production problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

A hybrid method for the probabilistic maximal covering location-allocation problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)