A hybrid approach to learn with imbalanced classes using evolutionary algorithms

There is an increasing interest in the application of Evolutionary Algorithms (EAs) to induce classification rules. This hybrid approach can benefit areas where classical methods for rule induction have not been very successful. One example is the induction of classification rules in imbalanced domains. Imbalanced data occur when one or more classes heavily outnumber other classes. Frequently, classical machine learning (ML) classifiers are not able to learn in the presence of imbalanced data sets, inducing classification models that always predict the most numerous classes. In this work, we propose a novel hybrid approach to deal with this problem. We create several balanced data sets with all minority class cases and a random sample of majority class cases. These balanced data sets are fed to classical ML systems that produce rule sets. The rule sets are combined creating a pool of rules and an EA is used to build a classifier from this pool of rules. This hybrid approach has some advantages over undersampling, since it reduces the amount of discarded information, and some advantages over oversampling, since it avoids overfitting. The proposed approach was experimentally analysed and the experimental results show an improvement in the classification performance measured as the area under the receiver operating characteristics (ROC) curve.

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.

Extending the use of canonical and microcanonical Monte Carlo algorithms to spin models

We describe the canonical and microcanonical Monte Carlo algorithms for different systems that can be described by spin models. Sites of the lattice, chosen at random, interchange their spin values, provided they are different. The canonical ensemble is generated by performing exchanges according to the Metropolis prescription whereas in the microcanonical ensemble, exchanges are performed as long as the total energy remains constant. A systematic finite size analysis of intensive quantities and a comparison with results obtained from distinct ensembles are performed and the quality of results reveal that the present approach may be an useful tool for the study of phase transitions, specially first-order transitions. (C) 2009 Elsevier B.V. All rights reserved.

Thermoluminescence properties of natural zoisite mineral under gamma-irradiations and high temperature annealing

Natural silicate mineral of zoisite, Ca(2)Al(3)(SiO(4))(Si(2)O(7))O(OH), has been investigated concerning gamma-radiation, UV-radiation and high temperature annealing effects on thermoluminescence (TL). X-ray diffraction (XRD) measurement confirmed zoisite structure and X-ray fluorescence (XRF) analysis revealed besides Si, Al and Ca that are the main crystal components, other oxides of Fe, Mg, Cr, Na, K, Sr, Ti, Ba and Mn which are present in more than 0.05 wt%. The TL glow curve of natural sample contains (130-150), (340-370) and (435-475)degrees C peaks. Their shapes indicated a possibility that they are result of composition of two or more peaks strongly superposed, a fact confirmed by deconvolution method. Once pre-annealed at 600 degrees C for 1 h, the shape of the glow curves change and the zoisite acquires high sensitivity. Several peaks between 100 and 400 degrees C appear superposed, and the high temperature peak around 435 degrees C cannot be seen. The ultraviolet radiation, on the other hand, produces one TL peak around 130 degrees C and the second one around 200 degrees C and no more. (C) 2010 Elsevier B.V. All rights reserved.

In situ impedance spectroscopy study of the electrochemical corrosion of Ti and Ti-6Al-4V in simulated body fluid at 25 degrees C and 37 degrees C

The corrosion resistance of Ti and Ti-6Al-4V was investigated through electrochemical impedance spectroscopy, EIS, potentiodynamic polarisation curves and UV-Vis spectrophotometry. The tests were done in Hank solution at 25 degrees C and 37 degrees C. The EIS measurements were done at the open circuit potential at specific immersion times. An increase of the resistance as a function of the immersion time was observed, for Ti (at 25 degrees C and 37 degrees C), and for Ti-6Al-4V (at 25 degrees C), which was interpreted as the formation and growth of a passive film on the metallic surfaces. (C) 2009 Elsevier Ltd. All rights reserved.

Thickness and Annealing Temperature Effects on the Optical Properties and Surface Morphology of Layer-by-Layer Poly(p-phenyline vinylene) plus Dodecylbenzenesulfonate Films

The fabrication of controlled molecular architectures is essential for organic devices, as is the case of emission of polarized light for the information industry. In this study, we show that optimized conditions can be established to allow layer-by-layer (LbL) films of poly(p-phenylene vinylene) (PPV)+dodecylbenzenesulfonate (DBS) to be obtained with anisotropic properties. Films with five layers and converted at 110 degrees C had a dichroic ratio delta = 2.3 and order parameter r = 34%, as indicated in optical spectroscopy and emission ellipsometry data. This anisotropy was decreased with the number of layers deposited, with delta = 1.0 for a 75-layer LbL PPV + DBS film. The analysis with atomic force microscopy showed the formation of polymer clusters in a random growth process with the normalized height distribution being represented by a Gaussian function. In spite of this randomness in film growth, the self-covariance function pointed to a correlation between clusters, especially for thick films. In summary, the LbL method may be exploited to obtain both anisotropic films with polarized emission and regular, nanostructured surfaces. (c) 2010 Wiley Periodicals, Inc. J Polym Sci Part B: Polym Phys 49: 206-213, 2011

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Synthesis of L1(0) Fe-Pd films by electrodeposition and thermal annealing

Fe-Pd alloy films have been prepared by electrochemical deposition from an alkaline electrolyte containing Fe sulfate, Pd chloride and 5-sulfosalicylic acid onto polycrystalline titanium substrates. The as-deposited films were nanocrystalline and magnetically soft (coercivity similar to 25 Oe). L1(0) Fe-Pd films with a (111) preferred orientation were obtained by post-deposition thermal annealing of films with composition about 37 at% Fe in an (Ar + 5% H-2) gas flow at 500 degrees C. Such films exhibit hard magnetic properties, with a coercivity up to 1880 Oe, and a slightly anisotropic magnetic response, with a larger in-plane remanence. Preliminary magnetic investigations support magnetization switching through pinning of domain walls. (c) 2008 Elsevier B.V. All rights reserved.