Made available in DSpace on 2019-03-29T23:23:07Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-12-21 / A remarkable progress has been recently achieved in the area of data clustering, in part due to the development of clustering ensemble methods. In a nutshell, this approach aims at combining multiple partitions produced over the same dataset into a single consensus partition. Although promising, this approach is still restrictive in the sense that obtaining a single solution (partition) as result limits the knowledge that could be grasped from the data, which could contain several meaningful alternative solutions. On the other hand, there exist several validation criteria to assess the data partitions, each considering a distinct viewpoint. This permits to model the data clustering task as a typical multiobjective optimization problem. This strategy, which has also gained much attention in the last years, is known as multiobjective clustering. In this context, this study presents a novel hybrid approach, based on multiobjective genetic programming, aiming at the automatic design of novel hierarchical fusion operators for clustering ensembles. By this means, an initial set of partitions obtained via the application of different clustering techniques could be continuously refined through a population of hierarchies of fusion operators, which select and combine the original partitions, using different quality criteria as objective functions. To validate the new approach in terms of efficiency and effectiveness, we have implemented a prototype and conducted a comparative study including other clustering algorithms (three of which are of clustering ensembles and two are multiobjective in nature) over 10 different datasets. The experiments indicate that, in general, the idea of having a fusion hierarchy together with the correct selection of the data partitions can provide significant gains in terms of effectiveness and robustness. Keywords: Data Clustering. Clustering Ensembles. Hierarchical Fusion. Multiobjective Evolutionary Algorithms, Genetic Programming. / Um notável avanço vem sendo recentemente obtido na área de agrupamento de dados mediante o desenvolvimento de métodos de fusão de partições. Essa abordagem, conhecida como clustering ensembles, consiste em combinar os resultados de múltiplos agrupamentos de uma mesma base de dados em uma única partição-consenso. Embora promissora, essa abordagem ainda é restritiva, já que uma única resposta para um problema limita a aquisição do conhecimento que poderia ser obtido considerando outras possíveis soluções (partições). Por outro lado, devido à existência de vários critérios de avaliação da qualidade de agrupamentos, pode-se modelar essa tarefa como um problema típico de otimização multiobjetivo. Nesse contexto, o presente estudo apresenta uma nova abordagem, baseada em programação genética multiobjetivo, que projeta automaticamente novos operadores hierárquicos de fusão de partições. Desse modo, um conjunto inicial de partições, obtido via a aplicação de diferentes técnicas de agrupamento, pode ser continuamente refinado através de uma população de hierarquias de fusores, que selecionam e combinam as partições originais, utilizando diferentes critérios de qualidade como funções-objetivo. Para validar a nova abordagem, em termos de eficiência e eficácia, foi implementado um protótipo e conduzido um estudo comparativo, envolvendo outros algoritmos de agrupamento (dentre os quais três são de clustering ensembles e dois são multiobjetivo), sobre 10 diferentes bases de dados. Os experimentos demonstram que, em geral, a ideia de se ter uma hierarquia de fusores aliada à correta seleção das partições pode proporcionar ganhos significativos em termos de eficácia e robustez. Palavras-chave: Agrupamento de Dados. Clustering Ensembles. Fusão Hierárquica de Partições. Algoritmos Evolutivos Multiobjetivos. Programação Genética.

Made available in DSpace on 2019-03-29T23:38:45Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-09-17 / Identify references in a text and group them into coreference chains is the main purpose of a coreference resolution system. This paper reports a systematic experimental study on the use of an approach based on genetic programming (GP) for automatic resolution of this prominent task of natural language processing (NLP). Although various methods for the identification of references are described in the literature, including those based on machine learning (ML), and for the assessment of results generated by coreference resolution systems through the use of custom metrics, the results obtained until the present moment are still below expectations. Therefore, we investigated the possibility of adopting an evolutionary approach based on GP, since the class of evolutionary algorithms has successfully solved several complex problems of machine learning and text mining. In this particular study, we investigated the impact of the use of different evaluation metrics (MUC, B$^3$, CEAF$_e$ and BLANC) as the fitness function of the individuals (classifiers) generated by GP. Moreover, the performance of different schemes of combination of genetic programs into committee machines was investigated, aimed to increase performance. For validation of the proposed methodology, a comprehensive empirical study was conducted on the English corpus made available in recent international competitions organized by the CoNLL (Conference on Computational Natural Language Learning), which is the main conference on the theme ``AM + PLN". The performance results obtained by the generated ensembles of genetic programs was generally satisfactory, although less significant than those obtained by the best ranked coreference resolution systems in CoNLL contests. On the other hand, the comparative study on the effect of using the different evaluation metrics as the fitness function of GP showed that this choice has an impact on the performance of the genetic programs generated. Besides, there is a strong correlation between the performance profiles generated by some metrics. In particular, the BLANC's capability in differentiating solutions is very similar to the exhibited by the metric used in CoNLL competitions. Keywords: coreference analysis, coreference resolution, genetic programming, genetic programming ensembles. / Identificar menções em um texto e agrupá-las formando cadeias de correferência é o principal objetivo de um sistema de resolução de correferências (RC). O presente trabalho relata um estudo experimental sistemático acerca do uso de uma abordagem baseada em programação genética (PG) para a resolução automática dessa proeminente tarefa de processamento de linguagem natural (PLN). Apesar da existência na literatura de vários métodos destinados à identificação de menções e ao agrupamento de menções, dentre os quais aqueles baseados em aprendizado de máquina (AM), bem como à avaliação dos resultados gerados por sistemas de RC mediante o uso de métricas customizadas, o fato é que os resultados alcançados até o presente ainda estão aquém do esperado. Nesse contexto, passou-se a investigar o potencial de se adotar uma abordagem evolucionária baseada em PG, tendo em vista que a classe de algoritmos evolucionários vem obtendo êxito na resolução de vários problemas complexos de aprendizado de máquina e mineração de textos. Neste estudo, em particular, investigou-se o impacto de se adotar diferentes métricas de avaliação (MUC, B³, CEAFe e BLANC) atuando como função de aptidão dos indivíduos (classificadores) gerados pela PG. Ademais, investigou-se o desempenho de diferentes esquemas de combinação de programas genéticos em comitês de máquinas, almejando-se um incremento no desempenho. Para fins de validação da metodologia proposta, foi conduzido um estudo empírico abrangente sobre o corpus de língua inglesa utilizado em recentes competições internacionais organizadas pela CoNLL (Conferência Computacional de Aprendizado em Linguagem Natural), que é a principal conferência acerca do tema "AM + PLN". Os resultados de desempenho obtidos pelos comitês de programas genéticos gerados foram em geral satisfatórios, não alcançando, porém, aqueles obtidos pelos sistemas de RC mais bem ranqueados nas competições do CoNLL. Por outro lado, o estudo comparativo acerca do efeito das métricas de avaliação como função de aptidão da PG evidenciou que há sim um impacto dessa escolha sobre o desempenho exibido pelos programas genéticos gerados. Além disso, há fortes correlações entre os perfis de desempenho gerados por algumas das métricas, sendo que a sensibilidade de discriminação das soluções exibida pela métrica BLANC é a que mais se assemelha à daquela exibida pela métrica efetivamente utilizada nas competições do CoNLL. Palavras-chave: Análise de correferência, resolução de correferência, programação genética, comitês de programas genéticos.

No description available.

No description available.

Resumo: A Computação Evolucionária (CE) introduz um novo paradigma para resolver problemas em Inteligência Artificial, representando candidatos à solução como indivíduos e evoluindo-os com base na Teoria da Seleção Natural de Darwin. Algoritmos Genéticos (AG) e Programação Genética (PG), duas importantes técnicas de CE, têm sido aplicadas com sucesso tanto em cenários teóricos quanto em situações práticas. Este trabalho discute o ajuste automático dos parâmetros que controlam o processo de busca neste tipo de algoritmo. Baseado em uma pesquisa recente, um método que controla o tamanho da população em AG é adaptado e implementado em PG. Uma série de experimentos clássicos foi realizada, antes e depois das modificações, mostrando que este método pode aumentar a robustez e a confiabilidade no algoritmo. Os dados permitem uma discussão sobre o método e a importância da adaptação de parâmetros em algoritmos de CE.

Orientadora: Profª. Drª. Aurora Pozo / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 10/03/2017 / Inclui referências / Área de concentração: Ciência da Computação / Resumo: O desempenho de algoritmos bio-inspirados está diretamente relacionado a uma escolha adequada de componentes e parâmetros de projeto. Para aumentar a robustez destes métodos e facilitar a sua utilização para usuário comum, pesquisas recentes focam no estudo de estratégias que automaticamente configurem algoritmos. Uma das principais abordagens utilizadas é a Programação Genética (PG), baseada em algoritmos evolutivos, ela evolui uma população de programas de computador através da aplicação de operadores de cruzamento e mutação para resolver o problema em questão. A Evolução Gramatical (GE) é um tipo de PG que utiliza gramáticas livres de contexto para a definição dos componentes do programa. Outra alternativa de configuração automática de algoritmos é a utilização de algoritmos de otimização: diversas ferramentas têm sido desenvolvidas neste contexto, entre elas destacam-se a Iterated Race (IRACE), um framework que utiliza conceitos de uma "corrida" entre os candidatos para selecionar as melhores configurações. Nesta dissertação o foco de estudo é a configuração automática de algoritmos e como caso de estudo escolhemos o algoritmo de Otimização por Enxame de Partículas Multiobjetivo (MOPSO). O MOPSO, assim como outros algoritmos de otimização estudados no nosso grupo de pesquisa, possui diversos componentes que podem ser alterados de acordo com a necessidade do usuário e o problema considerado. As duas técnicas Evolução Gramatical e o IRACE serão utilizadas. Experimentos foram realizados para avaliar ambas as técnicas na geração de projetos de MOPSO e verificar se os algoritmos gerados conseguem superar o desempenho de algoritmos refinados manualmente. Os resultados obtidos indicam que é possível gerar projetos MOPSO com desempenho similar e resultados competitivos. Palavras-cha e: evolução gramatical, projeto automático de algoritmos, otimização por enxame de partículas. / Abstract: The performance of bio-inspired algorithms is directly related to an appropriate choice of components and design parameters. To increase the robustness of these methods and simplify their use for ordinary users, recent research focuses on the study of strategies that automatically configure algorithms. One of the main approaches used is Genetic Programming (GP), based on evolutionary algorithms, it evolves a population of computer programs through the application of crossover and mutation operators to solve the problem in question. Grammatical Evolution (GE) is a type of GP that uses context-free grammars to define program components. Another alternative of automatic algorithm configuration is the use of optimization algorithms, several tools have been developed in this context, among them Iterated Race (IRACE), a framework that uses concepts of a "race" among the candidates to select the best settings. In this dissertation the focus of study is the automatic configuration of algorithms and as a case study we chose the Multi-objective Particle Swarm Optimization algorithm (MOPSO). The MOPSO, as well as other optimization algorithms studied in our research group, has several components that can be modified according to the user needs and the problem considered. The two techniques Grammatical Evolution and IRACE will be used. Experiments were performed to evaluate both techniques in the generation of MOPSO designs and to verify if the generated algorithms can outperform manually tunned algorithms. The results indicate that it is possible to generate MOPSO designs with similar performance and competitive results. Keywords: grammatical evolution, automatic design, particle swarm optimization.

Resumo: A PG (Programação Genetica) e aplicada com sucesso em Classicação. Entretanto, a pesquisa voltada a aplicação de PG para OCC (One-Class Classication) encontra-se em estagios iniciais, pois os poucos trabalhos relacionados existentes estão repletos de mudancas que não foram individualmente avaliadas e cujos propositos estão em resolver problemas provenientes do metodo de geracão de anomalias empregado e tambem na redução do tempo computacional da etapa de treino. Nesse contexto, e notavel que para tornar a PG em algoritmo de excelência para OCC o primeiro passo e avaliar sua abordagem convencional para o problema, algo que ainda no foi realizado, e objetivo central do presente trabalho, pois a introdução de novas ideias somente se justica ao se conhecer as limitações e os resultados obtidos pelo algoritmo convencional. Contudo, a aplicação de PG para OCC requer que o problema seja transformado em classicação binaria, cujas duas classes que compõem o conjunto de dados de treino são compostas por exemplos de perl normal e anormal. Porem, em diversos problemas de OCC e impraticavel obter exemplos anormais, por isto neste trabalho enfatiza-se a avaliacão de algoritmos para gerar exemplos anormais, algo que tambem ainda não foi realizado para PG. Entre os algoritmos de geração de anomalia estudados, selecionou-se o metodo pro- posto por Banhalmi et al. [6] que baseia-se em exemplos mais distantes da classe normal, o algoritmo baseado no conceito de hiperesfera proposto por Tax e Duin [38] e a tecnica RNS (Real-valued Negative Selection) inspirada em sistemas imunologicos proposta por Gonzales et al. [19] [20]. Um estudo comparativo entre eles foi realizado, para avaliar o desempenho de classicação obtido por um classicador induzido por PG convencio- nal sob uma abordagem de classicacão binaria. Vericou-se que o metodo proposto por Banhalmi et al. possibilitou a obtencão dos melhores resultados. O algoritmo de geracão de anomalias com melhor avaliacão foi empregado aos demais experimentos do presente trabalho, entre eles, um estudo comparativo entre a PG pro- posta no presente trabalho e as abordagens da literatura para OCC. Nesse experimento, vericou-se que a PG proposta neste trabalho obteve melhores resultados de classicacão em dois problemas OCC, em outros três obteve desempenho similar e em um deles foi in- ferior. Portanto, atesta-se a hipotese de que e possvel resolver OCC usando um algoritmo de PG convencional utilizando o algoritmo adequado para geracão de anomalias. O impacto de certos parâmetros da PG tambem foi avaliado. Entre eles o tamanho da populacão, que apresentou maior impacto no desempenho de classicacão em um problema OCC comparado a diferentes ajustes no tamanho da arvore e na taxa de mutacão. Alem disso, diferentes funcões de aptidão tambem foram experimentadas. Vericou-se que a funcão composta pela media das taxas individuais de acerto em cada classe apresentou melhor desempenho de classicacão OCC quando comparada ao uso da metrica AUC (Area Under the Receiver Operation Characteristic Curve). A taxa WMW (Wilcoxon- Mann-Whitney), considerada um estimador da AUC com custo computacional inferior, tambem foi aplicada como funcão de aptidão e apresentou resultado semelhante ao uso da AUC.

Made available in DSpace on 2016-06-02T19:06:11Z (GMT). No. of bitstreams: 1 5870.pdf: 4537760 bytes, checksum: 7cb33109ce64766270c2f7d7c5f3dddb (MD5) Previous issue date: 2013-12-20 / The tools offered by the area of Mathematical Morphology are very effective when applied to the analysis of binary images, which it is of great importance in areas such as: robotic vision, visual inspection, among others. Such tools, beside to Evolutionary Computation and based on genotype-phenotypes mappings allow computational tasks be performed automatically without explicit programming, which leads to the motivation, in the search of a way of reducing the degree of difficulty often found by human experts in performing tasks of selecting linear operators to be used in morphological filters. Moreover, if such tasks require fast processing on the images, it is necessary the use of architectures implemented in hardware, which it is not too trivial to be done. In this work, a hardware architecture simulator has been implemented for image processing, based on Cartesian Genetic Programming, which automatically builds filters for processing binary images, i.e., automatically build a sequence of logical and morphological operators that produces filters to obtain an approximate of the desired images. The results obtained from several experiments of transformation of these images are presented and comparatively analyzed in relation to previous results available in the literature. Based on these results, it will be possible to study the behavior of such architecture, through the variation of the parameters of the genetic procedure in the simulator environment. Thus, it will be possible to infer if the architecture is suitable or not for a desired application, so facilitating the process of design and implementation of it in hardware. / As ferramentas oferecidas pela área de Morfologia Matemática são muito eficientes quando aplicadas na análise de imagens binárias, o que é de grande importância em áreas como: visão robótica, inspeção visual, entre outras. Tais ferramentas aliadas à Computação Evolucionária e baseadas em mapeamentos genótipo-fenótipo permite que as tarefas computacionais possam ser executadas de forma automática, sem programações explicitas, o que leva a uma motivação na busca de uma forma de redução do grau de dificuldade, muitas vezes encontrado pelos especialistas na realização de tarefas de seleção de operadores de imagem para serem utilizados em tarefas de análise. Além disso, se tais tarefas necessitarem de processamentos rápidos sobre as imagens, faz-se necessário o uso de arquiteturas implementadas em hardware, o que também não é muito trivial de serem projetadas. Assim, neste trabalho, implementa-se um simulador de arquiteturas de hardware para processamento de imagens, com base na metodologia de Programação Genética Cartesiana, que gera automaticamente filtros para o processamento de imagens binárias, ou seja, constrói-se automaticamente uma sequência de operadores lógicos e morfológicos que produzem os filtros para as imagens desejadas. Os resultados obtidos a partir de diversos estudos de casos de transformação dessas imagens são apresentados e analisadoscomparativamente em relação aos resultados anteriores disponíveis na literatura. Com base nestes resultados, é possível estudar o comportamento de tal arquitetura, através da variação dos parâmetros do procedimento genético no ambiente do simulador. Assim, é possível inferir se a arquitetura modelada será ou não adequada à aplicação desejada, logo, facilitando-se o processo de projeto e implementação em hardware.

A morfologia matemática fornece ferramentas poderosas para a realização de análise de imagens em baixo nível e tem encontrado aplicações em diversas áreas, tais como: visão robótica, inspeção visual, medicina, análise de textura, entre outras. Muitas dessas aplicações requerem processamento em tempo real e para sua execução de forma eficiente freqüentemente é utilizado hardware dedicado. Também, a tarefa de projetar operadores morfológicos manualmente para uma dada aplicação não é trivial na prática. A programação genética, que é um ramo relativamente novo em computação evolucionária, está se consolidando como um método promissor em aplicações envolvendo processamento de imagens digitais. Seu objetivo primordial é descobrir como os computadores podem aprender a resolver problemas sem, no entanto, serem programados para essa tarefa. Essa área ainda não foi muito explorada no contexto de construção automática de operadores morfológicos. Assim, neste trabalho, desenvolve-se e implementa-se uma arquitetura original, de baixo custo, reconfigurável por meio de instruções morfológicas e lógicas geradas automaticamente através de uma aproximação linear baseada em programação genética, visando-se o processamento morfológico de imagens em tempo real utilizando FPGAs de alta complexidade, com objetivos de filtragem, reconhecimento de padrões e emulação de filtros desconhecidos de softwares comerciais, para citar somente algumas aplicações. Exemplos de aplicações práticas envolvendo imagens binárias, em níveis de cinza e coloridas são fornecidos e seus resultados são comparados com outras formas de implementação. / Mathematical morphology supplies powerful tools for low level image analysis, with applications in robotic vision, visual inspection, medicine, texture analysis and many other areas. Many of the mentioned applications require dedicated hardware for real time execution. The task of designing manually morphological operators for a given application isnot always a trivial one. Genetic programming is a relatively new branch of evolutionary computing and it is consolidating as a promising method for applications of digital image processing. The main objective of genetic programming is to discover how computers can learn to solve problems without being programmed for that. In the literature little has been found about the automatic morphological operators construction using genetic programming. In this work, the development of an original reconfigurable architecture using logical and morphological instructions generated automatically by a linear approach based on genetic programming is presented. The developed architecture is based on Field Programmable Gate Arrays (FPGAs) and has among the possible applications, image filtering, pattern recognition and filter emulation. Binary, gray level and color image practical applications using the developed architecture are presented and the results are compared with other implementation techniques.

Dissertação (mestrado) - Pontifícia Universidade Católica do Paraná, Curitiba, 2006 / Inclui bibliografia / O crescimento exponencial dos dados de expressão gênica provenientes da tecnologia de microarranjo de DNA é acompanhado pelo aumento da necessidade de ferramentas computacionais eficientes que auxiliem o processo de análise e interpretação desses dados. T