Search

Exploratory data analysis methods are essential for getting insight into data. Identifying the most important variables and detecting quasi-homogenous groups of data are problems of interest in this context. Solving such problems is a difficult task, mainly due to the unsupervised nature of the underlying learning process. Unsupervised feature selection and unsupervised clustering can be successfully approached as optimization problems by means of global optimization heuristics if an appropriate objective function is considered. This paper introduces an objective function capable of efficiently guiding the search for significant features and simultaneously for the respective optimal partitions. Experiments conducted on complex synthetic data suggest that the function we propose is unbiased with respect to both the number of clusters and the number of features.

The current paper presents a method to deliver non- linear projections of a data set that discriminate between existing labeled groups of data items. Inspired from traditional linear Pro- jection Pursuit and Linear Discriminant Analysis, the new method seeks nonlinear combinations of attributes as polynomials that maximize Fisher's criterion. The search for the monomials in a polynomial is conducted in a logarithmic space in order to reduce computational complexity. The selection of monomials and the optimization of weights that conduct to the nonlinear projection are performed with a multi-modal Genetic Algorithm hybridized with Differential Evolution. By alleviating the drawbacks driven from the linearity assumptions in traditional Projection Pursuit, the new method could gain a wide applicability in both unsuper- vised and supervised data analysis.

This paper proposes a new method to identify interesting structures in data based on the projection pursuit methodology. Past work reported in literature uses projection pursuit methods as means to visualize high-dimensional data, or to identify linear combinations of attributes that reveal grouping tendencies or outliers. The framework of projection pursuit is generally formulated as an optimization problem aiming at finding projection axes that minimize/maximize a projection index. With regard to identifying interesting structure, the existing approaches suffer from obvious limitations: linear models are not able to catch more general structures in data like circular/curved clusters or any structure that is the result of a polynomial/nonlinear generative model. This paper extends linear projection pursuit to nonlinear projections while allowing at the same time for the preservation of the general methodology employed in the search of projections. In addition, an algorithmic framework based on multi-modal genetic algorithms is proposed in order to deal with the large search space and to allow for the use of non-differentiable projection indices. Experiments conducted on synthetic data demonstrate the ability of the new approach to identify clusters of various shapes that otherwise are undetectable with linear projection pursuit or popular clustering methods like k-Means.

Clustering is a fundamental and hence widely studied problem in data analysis. In a multi-objective perspective, this paper combines principles from two different clustering paradigms: the connectivity principle from density-based methods is integrated into the partitional clustering approach. The standard k-Means algorithm is hybridized with Particle Swarm Optimization. The new method (PSO-kMeans) benefits from both a local and a global view on data and alleviates some drawbacks of the k-Means algorithm; thus, it is able to spot types of clusters which are otherwise difficult to obtain (elongated shapes, non-similar volumes). Our experimental results show that PSO-kMeans improves the performance of standard k-Means in all test cases and performs at least comparable to state-of-the-art methods in the worst case. PSO-kMeans is robust to outliers. This comes at a cost: the preprocessing step for finding the nearest neighbors for each data item is required, which increases the initial linear complexity of k-Means to quadratic complexity.

The paper presents a study on the application of messy genetic algorithms for the winner determination problem in the combinatorial auction realm. Messy genetic algorithms operate explicitly on building blocks in order to obtain good solutions. Since the winner determination is a constrained problem, the Ordering Messy Genetic Algorithm is used in order to preserve the validity of chromosomes. Experiments on instances generated with the CATS system are presented to illustrate and compare the effectiveness of the approach. The approach is compared against a simple genetic algorithm, which is a random-key genetic algorithm. Other well-known algorithms from literature are used in experiments. Conclusions are drawn on the advantages of using a messy genetic algorithm for this problem.

The protein structure prediction problem consists in finding good computational algorithms for prediction of protein native states. This paper applies the Particle Swarm Optimization (PSO) algorithm to predict the tertiary structure of proteins in lattice models. We propose a novel discrete PSO variant designed for lattice-based protein folding models. We present three lattice based models and two folding encodings, which are tested in different combinations on six proteins. The results indicate that the new algorithm performs very efficient and finds very good proteins conformations.

This paper is concerned with feature weighting/selection in the context of unsupervised clustering. Since different subspaces of the feature space may lead to different partitions of the data set, an efficient algorithm to tackle multi-modal environments is needed. In this context, the Multi-Niche Crowding Genetic Algorithm is used for searching relevant feature subsets. The proposed method is designed to deal with the inherent biases regarding the number of clusters and the number of features that appear in an unsupervised framework. The first one is eliminated with the aid of a new unsupervised clustering criterion, while the second is tackled with the aid of cross-projection normalization. The method delivers a vector of weights which offers a ranking of features in accordance with their relevance to clustering.

This paper compares two particle swarm optimization (PSO) hybrids on the problem of searching ground states of Ising spin glasses. The Ising model is one of the most widely used models for disordered systems in statistical physics. Finding the ground state of an Ising spin glass can be expressed as the problem of determining the minimum weighted cut in a graph. We tackle this problem with canonical PSO, a hill climber and two hybrid algorithms. The results show that both hybrids obtain better results than the classical heuristics they are built upon, one of the hybrids significantly outperforming the others. Hybrid methods created as a combination of PSO with a local search procedure provide promising results for this class of problems.

This paper discusses ways of exploiting knowledge extracted from the optimization process, in order to assist an evolutionary solver in its path towards solution. In the context of NK fitness landscapes, we identify two facets of the difficulty of an optimization problem: the intrinsic combinatorial difficulty and its hybridization with random-search. For the experimental part, a particular case of NK fitness landscape is considered; traditional genetic algorithms and Integrated-Adaptive Genetic Algorithms (IAGA), which provide broad adaption mechanisms for most of GA’s components, are compared. We add to IAGA a learn-as-you-go system which allows operators to self-tune their behavior by inspecting the effect they produce on offspring. This system demonstrates that information derived from failures is as valuable as information obtained from positive experience. These results suggest that an appropriately designed adaptive system can be a tool for tackling problem difficulty caused by random-search hybridization.

This paper presents an attempt to transform PSO into a self-adaptive algorithm based on specific swarm-inspired operators. New features are introduced: spatial expansion intended to overcome premature convergence (an algorithm called improved PSO, IPSO) and auto-adaptation (an algorithm called adaptive PSO, APSO). Experiments show that APSO and IPSO outperform the basic PSO on benchmark problems, proving their efficiency especially on multimodal functions.

Evolutionary techniques have been widely accepted as an effective meta-heuristic for a wide variety of problems in different domains. The main purpose of this paper is to present a symbolic technique based on the evolutionary paradigm gene expression programming (GEP) for solving Fredholm first type integral equations. We present the main traits of the gene expression algorithm (GEA), and our implementation for solving first kind integral equations of Fredholm type. The results obtained on four model problems using the symbolic technique described in this paper prove it to be suitable to handle this class of problems.

The problem of classification can be stated as: "Given a set of a attributes and the characterization of n objects by means of a attribute values for each object, find an optimal classification (partition) of the n objects into classes". The first step in supervised classification is to find k, the number of classes into which the objects have to be split in order to obtain the optimum classification. The dynamic kernels algorithm searches for a classification which maximizes B [=/spl Sigma//sub j=1//sup k/n/sub j/d(G/sub j/,G), where d(G/sub j/,G) denotes the distance between the points G/sub j/ and G, G is the center of gravity of the n given points and G/sub j/ are the centers of gravity of the k classes]. Unfortunately, the maximum value of B is not the same for different values of k, so the Huygens theorem can only be used for comparing classifications of the given objects into a fixed number of classes. We propose an evolution program for this problem. It simultaneously searches for both the optimum number of classes and the optimal classification. So far, we have implemented our approach for the case of two attributes with continuous values. Straightforward adaptations are under way for allowing the user to input any reasonable number of (continuous or discrete) attributes. >

The current work proposes and investigates a new method to identify outliers in multivariate numerical data, driving its roots in projection pursuit. Projection pursuit is basically a method to deliver meaningful linear combinations of attributes. The novelty of our approach resides in introducing nonlinear combinations, able to model more complex interactions among attributes. The exponential increase of the search space with the increase of the polynomial degree is tackled with a genetic algorithm that performs monomial selection. Synthetic test cases highlight the benefits of the new approach over classical linear projection pursuit.

The aim of this paper is to present two heuristics vaguely inspired from the evolution of star systems. These methods are simple and can produce a good solution in a short time. While for small dimensional search spaces they can work alone, for large dimensional spaces their results can be used as an initial solution for some other heuristics. We study the effects of the initial solutions generated with these methods on the local search heuristics and on a genetic algorithm. Experimental results show that good solutions can be obtained with a combination of these methods.