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.

PHYSICO-CHEMICAL, SPECTROSCOPICAL AND THERMAL CHARACTERIZATION OF BIODIESEL OBTAINED BY ENZYMATIC ROUTE AS A TOOL TO SELECT THE MOST EFFICIENT IMMOBILIZED LIPASE

Two microbial lipases from Burkholderia cepacia and Pseudomonas fluorescens were evaluated as catalysts for the enzymatic transesterification of beef tallow with ethanol and the most efficient lipase source was selected by taking into account the properties of the product to be used as fuel. Both lipases were immobilized on an epoxy silica-polyvinyl alcohol composite by covalent immobilization and used to perform the reactions under the following operational conditions: beef tallow-to-ethanol molar ratio of 1:9, 45 degrees C and 400 units of enzymatic activity per gram of fat. Products, characterized using Fourier Transform Infrared spectroscopy (FTIR), viscosimetry, thermogravimetry and H-1 NMR spectroscopy, suggested that the biodiesel sample obtained in the reaction catalyzed by Burkholderia cepacia lipase has the best set of properties for fuel usage.

Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size

Let k and l be positive integers. With a graph G, we associate the quantity c(k,l)(G), the number of k-colourings of the edge set of G with no monochromatic matching of size l. Consider the function c(k,l) : N --> N given by c(k,l)(n) = max {c(k,l)(G): vertical bar V(G)vertical bar = n}, the maximum of c(k,l)(G) over all graphs G on n vertices. In this paper, we determine c(k,l)(n) and the corresponding extremal graphs for all large n and all fixed values of k and l.

EDGE-PRESERVING SPECKLE TEXTURE REMOVAL BY INTERFERENCE-BASED SPECKLE FILTERING FOLLOWED BY ANISOTROPIC DIFFUSION

Ultrasonography has an inherent noise pattern, called speckle, which is known to hamper object recognition for both humans and computers. Speckle noise is produced by the mutual interference of a set of scattered wavefronts. Depending on the phase of the wavefronts, the interference may be constructive or destructive, which results in brighter or darker pixels, respectively. We propose a filter that minimizes noise fluctuation while simultaneously preserving local gray level information. It is based on steps to attenuate the destructive and constructive interference present in ultrasound images. This filter, called interference-based speckle filter followed by anisotropic diffusion (ISFAD), was developed to remove speckle texture from B-mode ultrasound images, while preserving the edges and the gray level of the region. The ISFAD performance was compared with 10 other filters. The evaluation was based on their application to images simulated by Field II (developed by Jensen et al.) and the proposed filter presented the greatest structural similarity, 0.95. Functional improvement of the segmentation task was also measured, comparing rates of true positive, false positive and accuracy. Using three different segmentation techniques, ISFAD also presented the best accuracy rate (greater than 90% for structures with well-defined borders). (E-mail: fernando.okara@gmail.com) (C) 2012 World Federation for Ultrasound in Medicine & Biology.

Physico-chemical, spectroscopical and thermal characterization of biodiesel obtained by enzymatic route as a tool to select the most efficient immobilized lipase

Two microbial lipases from Burkholderia cepacia and Pseudomonas fluorescens were evaluated as catalysts for the enzymatic transesterification of beef tallow with ethanol and the most efficient lipase source was selected by taking into account the properties of the product to be used as fuel. Both lipases were immobilized on an epoxy silica-polyvinyl alcohol composite by covalent immobilization and used to perform the reactions under the following operational conditions: beef tallow-to-ethanol molar ratio of 1:9, 45ºC and 400 units of enzymatic activity per gram of fat. Products, characterized using Fourier Transform Infrared spectroscopy (FTIR), viscosimetry, thermogravimetry and ¹H NMR spectroscopy, suggested that the biodiesel sample obtained in the reaction catalyzed by Burkholderia cepacia lipase has the best set of properties for fuel usage.

A contribution for developing more efficient dynamic modelling algorithms of parallel robots

Parallel kinematic structures are considered very adequate architectures for positioning and orienti ng the tools of robotic mechanisms. However, developing dynamic models for this kind of systems is sometimes a difficult task. In fact, the direct application of traditional methods of robotics, for modelling and analysing such systems, usually does not lead to efficient and systematic algorithms. This work addre sses this issue: to present a modular approach to generate the dynamic model and through some convenient modifications, how we can make these methods more applicable to parallel structures as well. Kane’s formulati on to obtain the dynamic equations is shown to be one of the easiest ways to deal with redundant coordinates and kinematic constraints, so that a suitable c hoice of a set of coordinates allows the remaining of the modelling procedure to be computer aided. The advantages of this approach are discussed in the modelling of a 3-dof parallel asymmetric mechanisms.

CID: an efficient complexity-invariant distance for time series

The ubiquity of time series data across almost all human endeavors has produced a great interest in time series data mining in the last decade. While dozens of classification algorithms have been applied to time series, recent empirical evidence strongly suggests that simple nearest neighbor classification is exceptionally difficult to beat. The choice of distance measure used by the nearest neighbor algorithm is important, and depends on the invariances required by the domain. For example, motion capture data typically requires invariance to warping, and cardiology data requires invariance to the baseline (the mean value). Similarly, recent work suggests that for time series clustering, the choice of clustering algorithm is much less important than the choice of distance measure used.In this work we make a somewhat surprising claim. There is an invariance that the community seems to have missed, complexity invariance. Intuitively, the problem is that in many domains the different classes may have different complexities, and pairs of complex objects, even those which subjectively may seem very similar to the human eye, tend to be further apart under current distance measures than pairs of simple objects. This fact introduces errors in nearest neighbor classification, where some complex objects may be incorrectly assigned to a simpler class. Similarly, for clustering this effect can introduce errors by “suggesting” to the clustering algorithm that subjectively similar, but complex objects belong in a sparser and larger diameter cluster than is truly warranted.We introduce the first complexity-invariant distance measure for time series, and show that it generally produces significant improvements in classification and clustering accuracy. We further show that this improvement does not compromise efficiency, since we can lower bound the measure and use a modification of triangular inequality, thus making use of most existing indexing and data mining algorithms. We evaluate our ideas with the largest and most comprehensive set of time series mining experiments ever attempted in a single work, and show that complexity-invariant distance measures can produce improvements in classification and clustering in the vast majority of cases.