Evolving Classifiers - Evolutionary Algorithms in Data Mining

Data mining means to summarize information from large amounts of raw data. It is one of the key technologies in many areas of economy, science, administration and the internet. In this report we introduce an approach for utilizing evolutionary algorithms to breed fuzzy classifier systems. This approach was exercised as part of a structured procedure by the students Achler, Göb and Voigtmann as contribution to the 2006 Data-Mining-Cup contest, yielding encouragingly positive results.

Dynamic Niche Clustering: a fuzzy variable radius niching technique for multimodal optimisation in GAs

This paper describes the recent developments and improvements made to the variable radius niching technique called Dynamic Niche Clustering (DNC). DNC is fitness sharing based technique that employs a separate population of overlapping fuzzy niches with independent radii which operate in the decoded parameter space, and are maintained alongside the normal GA population. We describe a speedup process that can be applied to the initial generation which greatly reduces the complexity of the initial stages. A split operator is also introduced that is designed to counteract the excessive growth of niches, and it is shown that this improves the overall robustness of the technique. Finally, the effect of local elitism is documented and compared to the performance of the basic DNC technique on a selection of 2D test functions. The paper is concluded with a view to future work to be undertaken on the technique.

Finiteness theorem for topological contact equivalence of map germs

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

K-bi-Lipschitz equivalence of real function-germs

In this paper we prove that the set of equivalence classes of germs of real polynomials of degree less than or equal to k, with respect to K-bi-Lipschitz equivalence, is finite.

Evolutionary modeling of larval dispersal in blowflies using non-uniform cellular automata

When the food supply flnishes, or when the larvae of blowflies complete their development and migrate prior to the total removal of the larval substrate, they disperse to find adequate places for pupation, a process known as post-feeding larval dispersal. Based on experimental data of the Initial and final configuration of the dispersion, the reproduction of such spatio-temporal behavior is achieved here by means of the evolutionary search for cellular automata with a distinct transition rule associated with each cell, also known as a nonuniform cellular automata, and with two states per cell in the lattice. Two-dimensional regular lattices and multivalued states will be considered and a practical question is the necessity of discovering a proper set of transition rules. Given that the number of rules is related to the number of cells in the lattice, the search space is very large and an evolution strategy is then considered to optimize the parameters of the transition rules, with two transition rules per cell. As the parameters to be optimized admit a physical interpretation, the obtained computational model can be analyzed to raise some hypothetical explanation of the observed spatiotemporal behavior. © 2006 IEEE.

Investigação de propriedades quantitativas de relações simbólicas em quatro estudos experimentais envolvendo o paradigma de equivalência de estímulos

Este trabalho apresenta quatro estudos experimentais que avaliaram a transferência de funções de faces expressando emoções para figuras abstratas equivalentes a elas. Os objetivos específicos de cada estudo podem ser articulados em torno de uma proposta de investigação de propriedades quantitativas de relações de equivalência. O Capítulo 1 descreve um experimento conduzido para investigar se o grau de transferência de funções pode ser afetado pela apresentação atrasada dos estímulos de comparação em tarefas de emparelhamento ao modelo (matching atrasado). Foi constatado que sim: parece haver maior transferência quando os estímulos de comparação são apresentados com atraso. O estudo descrito no Capítulo 2 manipulou, além do emparelhamento atrasado, o número de estímulos mediadores das relações estabelecidas entre as faces e as figuras. O aumento no número de estímulos mediadores dificultou a formação de classes de equivalência e diminuiu a transferência de funções, mas esse efeito foi menos pronunciado quando as relações foram treinadas com emparelhamento atrasado ao modelo. O Capítulo 3 apresenta um experimento conduzido para verificar se figuras abstratas adquirem propriedades de expressões faciais apresentadas sempre muito rapidamente. Nesse delineamento, a transferência de funções ocorreu em grau menor do que quando as faces são apresentadas por períodos mais longos. O Capítulo 4 apresenta um estudo que avaliou o tempo que os participantes gastavam para encontrar figuras abstratas equivalentes a certos padrões faciais expressivos descritos como mais rapidamente localizáveis. Os resultados replicaram apenas parcialmente a transferência de funções demonstrada em um estudo anterior. Os estudos que compõem este trabalho fornecem evidências de que o grau de transferência de funções pode variar sistematicamente de acordo com os parâmetros experimentais adotados. Variações na transferência de funções indicam variações no grau de relacionamento de estímulos equivalentes.

Formação de classes de equivalência através de reforçamento específico em crianças com dificuldades de aprendizagem

Na Análise do Comportamento, vários estudos são realizados a fim de entender como comportamentos podem produtivamente ser controlados por eventos arbitrariamente relacionados, através da formação classes de equivalência. A inclusão de estímulos reforçadores nas classes tem sido apontada como um possível facilitador de sua formação. O presente estudo teve como objetivos avaliar a formação de classes de equivalência mediada por estímulos reforçadores específicos em crianças que apresentam baixo rendimento escolar. Usando crianças com desenvolvimento típico e em maior número, comparado com a literatura, pretendeu-se obter dados com menor variabilidade intersujeitos que é comumente encontrada nesse tipo de pesquisa. Para isso, foram utilizados reforçadores específicos com quatorze crianças (no Experimento I) que apresentam dificuldades de aprendizagem. O procedimento do Experimento 1 foi dividido em 10 fases. Em todas as fases, houve reforçadores específicos (frutas ou brinquedos) para cada uma das classes potenciais que se pretendia verificar. Inicialmente foi realizado um treino de pareamento por identidade com os estímulos dos Conjuntos A (A I e A2), B (B 1 e B2) e C (C I e C2) com reforçamento contínuo, seguido do mesmo treino com Reforçamento Intermitente. Logo após esses treinos foram realizados os testes de relações emergentes AB/BA, ACICA e BCICB. Antes de cada teste foi feito o retorno às discriminações de linha de base. Os dados do Experimento I evidenciam grande variabilidade intersujeitos nos testes de formação de classes. O Experimento 2 pretendeu investigar o efeito de dois tipos de pré-treino sobre o desempenho nos testes de formação de classes. Foi realizado com seis crianças e subdividido em dois grupos. O Grupo I foi submetido a um pré-treino de pareamento por identidade e o Grupo 2 a um pré-treino de pareamento arbitrário. Os resultados confirmam parcialmente a hipótese de que pré-treino de pareamento arbitrário pode reduzir a variabilidade inter-sujeitos nesse tipo estudos, pois altas taxas de variabilidade persistem no presente estudo. .Estudos posteriores deverão explorar essa possibilidade mais sistematicamente.

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.

Constraint-based analysis of gene interactions using restricted boolean networks and time-series data

Abstract Background A popular model for gene regulatory networks is the Boolean network model. In this paper, we propose an algorithm to perform an analysis of gene regulatory interactions using the Boolean network model and time-series data. Actually, the Boolean network is restricted in the sense that only a subset of all possible Boolean functions are considered. We explore some mathematical properties of the restricted Boolean networks in order to avoid the full search approach. The problem is modeled as a Constraint Satisfaction Problem (CSP) and CSP techniques are used to solve it. Results We applied the proposed algorithm in two data sets. First, we used an artificial dataset obtained from a model for the budding yeast cell cycle. The second data set is derived from experiments performed using HeLa cells. The results show that some interactions can be fully or, at least, partially determined under the Boolean model considered. Conclusions The algorithm proposed can be used as a first step for detection of gene/protein interactions. It is able to infer gene relationships from time-series data of gene expression, and this inference process can be aided by a priori knowledge available.

Investigation on the evolution of an indoor robotic localization system based on wireless networks

This work addresses the evolution of an artificial neural network (ANN) to assist in the problem of indoor robotic localization. We investigate the design and building of an autonomous localization system based on information gathered from wireless networks (WN). The article focuses on the evolved ANN, which provides the position of a robot in a space, as in a Cartesian coordinate system, corroborating with the evolutionary robotic research area and showing its practical viability. The proposed system was tested in several experiments, evaluating not only the impact of different evolutionary computation parameters but also the role of the transfer functions on the evolution of the ANN. Results show that slight variations in the parameters lead to significant differences on the evolution process and, therefore, in the accuracy of the robot position.