Made available in DSpace on 2016-06-02T19:06:07Z (GMT). No. of bitstreams: 1 5428.pdf: 4673420 bytes, checksum: 83314c7f075f21d0c118b9716342077e (MD5) Previous issue date: 2013-06-03 / Universidade Federal de Sao Carlos / The techniques of computer vision have been used more and more by the industries in order to aid the automation of their processes; however, the implementation of computer vision techniques has several difficulties according with the application. Such techniques are limited to the computational cost along with its complexity. Problems of elements identification in industrial sceneries are examples of an application that can generate a larger complexity in the process automation. Researches are accomplished using several techniques for solving those difficulties. This work approaches the field of computer vision through the use of artificial intelligence techniques. Here, methods are evaluated for creation and replication of binary images filters through the use of the genetic programming with the objective of elements identification in an industrial scenery. Two methods that possess different approaches are evaluated; one uses operations between pixels and other mathematical morphology for objects detection. The results are presented qualitatively as well as quantitatively through comparative images of the evaluated methods and statistical measures, respectively. Through the GPLab toolbox together with Matlab, the automatic creation of filters for objects identification was possible, so the detection and deletion of elements in images can be used by other support systems to automatic operation in an industrial environment. The results established a efficient way of filter creation with the use of the genetic programming. / As técnicas de visão computacional têm sido utilizadas cada vez mais pelas indústrias para o auxílio da automação de seus processos, porém, a implementação das técnicas de visão computacional encontra diversas dificuldades de acordo com a aplicação. Tais técnicas são limitadas ao custo computacional de acordo com sua complexidade. Problemas de identificação de elementos em cenários industriais são exemplos de uma aplicação que pode gerar uma maior complexidade na automação do processo. Pesquisas são realizadas utilizando diversas técnicas para a solução dessas dificuldades. Este trabalho aborda o campo de visão computacional através da utilização de técnicas de inteligência artificial. Aqui são avaliados métodos para criação e replicação de filtros de imagens binárias através da utilização da programação genética com o objetivo de identificação de elementos em um cenário industrial. São avaliados dois métodos que possuem abordagens diferentes, um utiliza operações entre pixels e outra morfologia matemática para a detecção de objetos. Os resultados são apresentados tanto qualitativamente quanto quantitativamente através de imagens comparativas dos métodos avaliados e das medidas estatísticas, respectivamente. Através da utilização de toolbox GPLab em conjunto com o Matlab, foi possível a criação de filtros de forma automática para identificação de objetos, de forma que a detecção e remoção de elementos em imagens possa ser utilizada por outros sistemas de apoio ao funcionamento automático em um ambiente industrial. Os resultados estabeleceram uma forma de criação de filtros eficiente a partir da utilização da programação genética.

Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2017-05-04T18:13:43Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Teste - Péricles Miranda.pdf: 1959669 bytes, checksum: 8b0b1e3f94dd3295bce6153865564a12 (MD5) / Made available in DSpace on 2017-05-04T18:13:43Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Teste - Péricles Miranda.pdf: 1959669 bytes, checksum: 8b0b1e3f94dd3295bce6153865564a12 (MD5) Previous issue date: 2016-08-22 / A escolha de algoritmos ou heurísticas para a resolução de um dado problema é uma tarefa desafiadora devido à variedade de possíveis escolhas de variações/configurações de algoritmos e a falta de auxílio em como escolhê-las ou combiná-las. Por exemplo, o desempenho de algoritmo de otimização depende da escolha dos seus operadores de busca e do ajuste adequado de seus hiper-parâmetros, cada um deles com muitas possibilidades de opções a serem escolhidas. Por este motivo, existe um interesse de pesquisa crescente na automatização da otimização de algoritmos de modo a tornar esta tarefa mais independente da interação humana. Diferentes abordagens têm lidado com a tarefa de ajuste de algoritmos como sendo outro problema de (meta)otimização. Estas abordagens são comumente chamadas de hiper-heurísticas, onde cada solução do espaço de busca, neste caso, é um possível algoritmo avaliado em um dado problema. Inicialmente, hiper-heurísticas foram aplicadas na seleção de valores de hiper-parâmetros em um espaço de busca pré-definido e limitado. No entanto, recentemente, hiper-heurísticas têm sido desenvolvidas para gerar algoritmos a partir de componentes e funções especificados. Hiperheurísticas de geração são consideradas mais flexíveis que as de seleção devido à sua capacidade de criar algoritmos novos e personalizados para um dado problema. As hiper-heurísticas têm sido largamente utilizadas na otimização de meta-heurísticas. No entanto, o processo de busca torna-se bastante custoso, pois a avaliação das soluções trata-se da execução do algoritmo no problema de entrada. Neste trabalho, uma nova hiper-heurística foi desenvolvida para a otimização de algoritmos considerando um dado problema. Esta solução visa prover algoritmos otimizados que sejam adequados para o problema dado e reduzir o custo computacional do processo de geração significativamente quando comparado ao de outras hiper-heurísticas. A hiper-heurística proposta combina uma abordagem de seleção de algoritmos com uma hiper-heurística de geração. A hiperheurística de geração é responsável por criar uma base de conhecimento, que contém algoritmos que foram gerados para um conjunto de problemas. Uma vez que esta base de conhecimento esteja disponível, ela é usada como fonte de algoritmos a serem recomendados pela abordagem de seleção de algoritmos. A ideia é reusar algoritmos previamente construídos pela hiper-heurística de geração em problemas similares. Vale salientar que a criação de hiper-heurísticas visando reduzir o custo de geração de algoritmos sem comprometer a qualidade destes algoritmos não foi estudada na literatura. Além disso, hiper-heurísticas híbridas que combinam de abordagens de seleção de algoritmos e hiper-heurísticas de geração para a otimização de algoritmos, proposta nesta tese, é novidade. Para avaliar o algoritmo proposto, foi considerada como estudo de caso a otimização do algoritmo baseado em enxames (PSO). Nos experimentos realizados, foram considerados 32 problemas de otimização. O algoritmo proposto foi avaliado quanto à sua capacidade de recomendar bons algoritmos para problemas de entrada, se estes algoritmos atingem resultados competitivos frente à literatura. Além disso, o sistema foi avaliado quanto à sua precisão na recomendação, ou seja, se o algoritmo recomendado seria, de fato, o melhor a ser selecionado. Os resultados mostraram que a hiper-heurística proposta é capaz de recomendar algoritmos úteis para os problemas de entrada e de forma eficiente. Adicionalmente, os algoritmos recomendados atingiram resultados competitivos quando comparados com algoritmos estado da arte e a recomendação dos algoritmos atingiu um alto percentual de precisão. / Designing an algorithm or heuristic to solve a given problem is a challenging task due to the variety of possible design choices and the lack of clear guidelines on how to choose and/or combine them. For instance, the performance of an optimization algorithm depends on the designofitssearchoperatorsaswellasanadequatesettingofspecifichyper-parameters,eachof them with many possible options to choose from. Because of that, there is a growing research interest in automating the design of algorithms by exploring mainly optimization and machine learningapproaches,aimingtomakethealgorithmdesignprocessmoreindependentfromhuman interaction. Different approaches have dealt with the task of optimizing algorithms as another (meta)optimization problem. These approaches are commonly called hyper-heuristics, where each solution of the search space is a possible algorithm. Initially, hyper-heuristics were applied for the selection of parameters in a predefined and limited search space. Nonetheless, recently, generation hyper-heuristics have been developed to generate algorithms from a set of specified components and functions. Generation hyper-heuristics are considered more flexible than the selection ones due to its capacity to create new and customized algorithms for a given problem. Hyper-heuristics have been widely used for the optimization of meta-heuristics. However, the search process becomes expensive because the evaluation of each solution depends on the execution of an algorithm in a problem. In this work, a novel hyper-heuristic was developed to optimize algorithms considering a given problem. The proposed approach aims to provide optimizedalgorithmsfortheinputproblemandreducethecomputationalcostoftheoptimization process significantly when compared to other hyper-heuristics. The proposed hyper-heuristics combines an automated algorithm selection method with a generation hyper-heuristic. The generation hyper-heuristic is responsible for the creation of the knowledge base, which contains previously built algorithms for a set of problems. Once the knowledge base is available, it is used as a source of algorithms to be recommended by the automated algorithm selection method. The idea is to reuse the algorithms already built by the generation hyper-heuristic on similar problems. It is worth mentioning that the creation of hyper-heuristics aiming to reduce the cost of the algorithm generation without harming the quality of these algorithms were not studied yet. Besides, hybrid hyper-heuristics which combine an algorithm selection approach with a generation hyper-heuristic for the algorithm optimization, proposed in this thesis, are a novelty. To evaluate the proposed algorithm, it was considered as case study the optimization of the Particle Swarm Optimization algorithm (PSO). In our experiments, we considered 32 optimizationproblems.Theproposedsystemwasevaluatedregardingitscapacitytorecommend adequate algorithms for an input problem, the quality of the recommended algorithms, and, finally, regarding its accuracy to recommend algorithms. The results showed that the proposed system recommends useful algorithms for the input problem. Besides, the algorithms achieved competitive results when compared to state-of-the-art algorithms, and also, the system presented a high percentage of accuracy in the recommendation.

Orientador: Ricardo da Silva Torres / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T22:04:09Z (GMT). No. of bitstreams: 1 Ferreira_CristianoDalmaschio_M.pdf: 3661487 bytes, checksum: 589a6834c502d67559dbb716e1dd4645 (MD5) Previous issue date: 2007 / Resumo: A técnica de realimentação de relevância tem sido utilizada com o intuito de incorporar a subjetividade da percepção visual de usuários à recuperação de imagens por conteúdo. Basicamente, o processo de realimentação de relevância consiste na: (i) exibição de um pequeno conjunto de imagens; (ii) rotulação dessas imagens pelo usuário, indicando quais são relevantes ou não; (iii) e finalmente, aprendizado das preferências do usuário a partir das imagens rotuladas e seleção de um novo conjunto de imagens para exibição. O processo se repete até que o usuário esteja satisfeito. Esta dissertação apresenta dois arcabouços para recuperação de imagens por conteúdo com realimentação de relevância. Esses arcabouços utilizam programação genética para assimilar a percepção visual do usuário por meio de uma combinação de descritores. A utilização de programação genética é motivada pela sua capacidade exploratória do espaço de busca uma vez que esse espaço se adequa ao objetivo principal dos arcabouços propostos: encontrar, dentre todas as possíveis funções de combinação de descritores, aquela que melhor representa as características visuais que um usuário deseja ressaltar na realização de uma consulta. Os arcabouços desenvolvidos foram validados por meio de uma série de experimentos, envolvendo três diferentes bases de imagens e descritores de cor, forma e textura para a caracterização do conteúdo dessas imagens. Os arcabouços propostos foram comparados com três outros métodos de recuperação de imagens por conteúdo com realimentação de relevância, considerando-se a eficiência e a efetividade no processo de recuperação. Os resultados experimentais mostraram a superioridade dos arcabouços propostos. As contribuições dessa dissertação são: (i) estudo sobre diferentes técnicas de realimentação de relevância; (ii) proposta de dois arcabouços para recuperação de imagens por conteúdo com realimentação de relevância baseado em programação genética; (iii) implementação dos métodos propostos, validando-os por meio de uma série de experimentos e comparações com outros métodos / Abstract: Relevance Feedback has been used to incorporate the subjectivity of user visual perception in content-based image retrieval tasks. The relevance feedback process consists in the following steps: (i) showing a small set of images; (ii) indication of relevant or irrelevant images by the user; (iii) and finally, learning the user needs from her feedback, and selecting a new set of images to be showed. This procedure is repeated until the user is satisfied. This dissertation presents two content-based image retrieval frameworks with relevance feedback. These frameworks employ Genetic Programming to discover a combination of descriptors that characterize the user perception of image similarity. The use of genetic programming is motivated by its capability of exploring the search space, which deals with the major goal of the proposed frameworks: find, among all combination functions of descriptors, the one that best represents the user needs. Several experiments were conducted to validate the proposed frameworks. These experiments employed three different images databases and color, shape and texture descriptors to represent the content of database images. The proposed frameworks were compared with three other content-based image retrieval methods regarding their efficiency and effectiveness in the retrieval process. Experiment results demonstrate the superiority of the proposed methods. The contributions of this work are: (i) study of different relevance feedback techniques; (ii) proposal of two content-based image retrieval frameworks with relevance feedback, based on genetic programming; (ii) implementation of the proposed methods and their validation with several experiments, and comparison with other methods / Mestrado / Banco de Dados / Mestre em Ciência da Computação

Submitted by Adriely Bruce (adriely_bruce@hotmail.com) on 2016-12-16T14:58:13Z No. of bitstreams: 1 Dissertação - Urique Hoffmann de Souza Almeida.pdf: 692636 bytes, checksum: c0255901a1a8d4253db69adb8d903141 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-12-22T14:11:38Z (GMT) No. of bitstreams: 1 Dissertação - Urique Hoffmann de Souza Almeida.pdf: 692636 bytes, checksum: c0255901a1a8d4253db69adb8d903141 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-12-22T14:14:43Z (GMT) No. of bitstreams: 1 Dissertação - Urique Hoffmann de Souza Almeida.pdf: 692636 bytes, checksum: c0255901a1a8d4253db69adb8d903141 (MD5) / Made available in DSpace on 2016-12-22T14:14:43Z (GMT). No. of bitstreams: 1 Dissertação - Urique Hoffmann de Souza Almeida.pdf: 692636 bytes, checksum: c0255901a1a8d4253db69adb8d903141 (MD5) Previous issue date: 2016-06-15 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / In this work, we describe a novel method we designed, implemented and tested to finding products that are similar alternatives to a given product in the catalog of an e-commerce site. By similar alternatives, we mean products that, although are not identical to a product of interest, have features that make them suitable alternatives for customers that look for it. Our motivation is to enable the recommendation of alternativeproductsbasedsolelyontheproduct’sfeatures,withoutrelyingonhistorical purchase data. By doing so, we address the so-called cold start problem, which is often found in product recommendation approaches, and that may lead to profit loss in ecommerce sites. Our method, we call GPClerk, uses Genetic Programming (GP) to learn functions for comparing two products and telling whether two products are similar alternatives or not. These functions are termed here as product comparison functions. To make our method feasible in typical e-commerce settings, we also propose an unsupervised strategy to generate training examples to be used in the learning process. Results of experiments we carried out and report here indicate that our method is capable of generating suitable product comparison functions and that our strategy for automatically generating training data is effective for this task. / Nesse trabalho, descrevemos um novo método que projetamos, implementamos e testamos para a tarefa de encontrar produtos que são alternativas similares a um dado produto em um catálogo de um site de comércio eletrônico. Nesse trabalho, consideramos como alternativas similares produtos que, apesar de não serem idênticos a um produto de interesse, têm características que os tornam boas alternativas a esse produto. Nossa motivação para esse trabalho é poder recomendar produtos similares com base apenas nas suas características, sem a necessidade da utilização do histórico de compras dos usuários. Assim, nesse trabalho lidamos com o chamado problema de cold start, que é comumente encontrado em abordagens de recomendação, e que pode levar a perda de lucro em sites de comércio eletrônico. Nosso método, chamado GPClerk, utiliza Programação Genética (GP) para aprender funções que comparam dois produtos, e dizem se estes são similares ou não. Essas funções são chamadas nesse trabalho de product comparison functions. Para tornar nosso método viável em um cenário típico de comércio eletrônico, propomos também uma estratégia não supervisionada para gerar exemplos de treino a serem utilizados no processo de aprendizagem. Resultados de experimentos que executamos e descrevemos nessa dissertação indicam que nosso método é capaz de gerar funções adequadas, e que nossa estratégia para geração automática de dados de treino é efetiva para essa tarefa.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-19T15:28:50Z No. of bitstreams: 1 igorlucasdesouzarusso.pdf: 2265113 bytes, checksum: 0eb7e55f7354359d8fb9419e6e6da17f (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-20T12:28:17Z (GMT) No. of bitstreams: 1 igorlucasdesouzarusso.pdf: 2265113 bytes, checksum: 0eb7e55f7354359d8fb9419e6e6da17f (MD5) / Made available in DSpace on 2017-04-20T12:28:17Z (GMT). No. of bitstreams: 1 igorlucasdesouzarusso.pdf: 2265113 bytes, checksum: 0eb7e55f7354359d8fb9419e6e6da17f (MD5) Previous issue date: 2017-01-26 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A área de Otimização envolve o estudo e emprego de métodos para determinação dos parâmetros que levam à obtenção de soluções ótimas, de acordo com critérios denominados objetivos. Um problema é classificado como multiobjetivo quando apresenta objetivos múltiplos e conflitantes, que devem ser otimizados simultaneamente. Recentemente tem crescido o interesse dos pesquisadores pela análise de pós-otimalidade, que consiste na busca por propriedades intrínsecas às soluções ótimas de problemas de otimização e que podem lançar uma nova luz à compreensão dos mesmos. Innovization (inovação através de otimização, do inglês innovation through optmization) é um processo de descoberta de conhecimento a partir de problemas de otimização na forma de relações matemáticas entre variáveis, objetivos, restrições e parâmetros. Dentre as técnicas de busca que podem ser utilizadas neste processo está a Programação Genética (PG), uma meta heurística bioinspirada capaz de evoluir programas de forma automatizada. Além de numericamente válidos, os modelos encontrados devem utilizar corretamente as variáveis de decisão em relação às unidades envolvidas, de forma a apresentar significado físico coerente. Neste trabalho é proposta uma alternativa para tratamento das unidades através de operações protegidas que ignoram os termos inválidos. Além disso, propõe-se aqui uma estratégia para evitar a obtenção de soluções triviais que não agregam conhecimento sobre o problema. Visando aumentar a diversidade dos modelos obtidos, propõe-se também a utilização de um arquivo externo para armazenar as soluções de interesse ao longo da busca. Experimentos computacionais são apresentados utilizando cinco estudos de caso em engenharia para verificar a influência das ideias propostas. Os problemas tratados aqui envolvem os projetos de: uma treliça de 2 barras, uma viga soldada, do corte de uma peça metálica, de engrenagens compostas e de uma treliça de 10 barras, sendo este último ainda não explorado na literatura de descoberta de conhecimento. Finalmente, o conhecimento inferido no estudo de caso da estrutura de 10 barras é utilizado para reduzir a dimensionalidade do problema. / The area of optimization involves the study and the use of methods to determine the parameters that lead to optimal solutions, according to criteria called objectives. A problem is classified as multiobjective when it presents multiple and conflicting objectives which must be simultaneously optimized. Recently, the interest of the researchers has grown in the analysis of post-optimality, which consists in the search for intrinsic properties of the optimal solutions of optimization problems. This can shed a new light on the understanding of the optimization problems. Innovization (from innovation through optimization) is a process of knowledge discovery from optimization problems in the form of mathematical relationships between variables, objectives, constraints, and parameters. Genetic Programming (GP), a search technique that can be used in this process, is a bio-inspired metaheuristic capable of evolving programs automatically. In addition to be numerically valid, the models found must correctly use the decision variables with respect to the units involved, in order to present coherent physical meaning. In this work, a method is proposed to handle the units through protected operations which ignore invalid terms. Also, a strategy is proposed here to avoid trivial solutions that do not add knowledge about the problem. In order to increase the diversity of the models obtained, it is also proposed the use of an external file to store the solutions of interest found during the search. Computational experiments are presented using five case studies in engineering to verify the influence of the proposed ideas. The problems dealt with here are the designs of: a 2-bar truss, a welded beam, the cutting of a metal part, composite gears, and a 10-bar truss. The latter was not previously explored in the knowledge discovery literature. Finally, the inferred knowledge in the case study of the 10-bar truss structure is used to reduce the dimensionality of that problem.

Orientadores: Fernando Jose Von Zuben, Jonatas Manzolli / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T18:37:39Z (GMT). No. of bitstreams: 1 Moroni_Artemis_D.pdf: 4233681 bytes, checksum: 0827bfd36d9807e5156b11bcffacf950 (MD5) Previous issue date: 2003 / Doutorado

Orientadores: Ariadne Maria Brito Rizzoni Carvalho, Ricardo da Silva Torres / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T12:42:46Z (GMT). No. of bitstreams: 1 Godoi_ThiagoAnzolinde_M.pdf: 1782345 bytes, checksum: d9ede100469835a7820e3cc67caae355 (MD5) Previous issue date: 2013 / Resumo: Este trabalho apresenta um novo método semiautomático para desambiguação de nomes que explora a utilização de iterações com realimentação de relevância. Uma etapa não supervisionada é utilizada para definir exemplos puros para o treinamento, e uma etapa híbrida supervisionada é empregada para aprender a função de classificação que irá atribuir autores a referências. O modelo combina um classificador por floresta de caminhos ótimos (OPF - Optimum-Path Forest) com uma função de similaridade complexa gerada por um algoritmo de Programação Genética (PG). As principais contribuições deste trabalho são: (i) proposta de um novo método para desambiguação de nomes de autores; (ii) avaliação em uma nova aplicação, da combinação entre os algoritmos OPF e PG, também conhecida como GOPF (Genetic Programming e Optimum-Path Forest), incrementada por uma etapa de realimentação de relevância; (iii) avaliação do algoritmo do GOPF em um problema de classificação multiclasse; e (iv) adaptação do algoritmo do GOPF para lidar com problemas de classificação de conjunto aberto, isto é, que não possuem todas as classes definidas previamente. O método proposto foi validado em duas coleções tradicionais muito utilizadas para avaliação de métodos de desambiguação de nomes de autores. A primeira é a coleção extraída da DBLP e que possui 4.287 referências associadas a 220 autores distintos; a segunda é chamada de KISTI, gerada pelo Korea Institute of Science Technology Information, e que contém os primeiros 1000 autores mais frequentes na versão do banco de dados da DBLP no final de 2007. Após 5 iterações de realimentação do usuário, nossa abordagem atingiu os melhores resultados para a desambiguação de nomes de autores quando comparado com os outros métodos existentes que utilizam somente as informações básicas da referência / Abstract: This work presents a new name disambiguation method that exploits user feedback on ambiguous references across iterations. An unsupervised step is used to define pure training samples, and a hybrid supervised step is employed to learn a classification model for assigning references to authors. Our disambiguation method combines the Optimum-Path Forest (OPF) classifier with complex reference similarity functions generated by a Genetic Programming (GP) framework. The main contributions of this work are: (i) proposal of a novel author name desambiguation method; (ii) evaluation in a new application of the combination between GP and OPF algorithms, also known as GOPF, in interaction learning systems; (iii) evaluation of the GOPF algorithm in a multi-class classification problem; and (iv) extension of the GOPF algorithm to handle open-set classification problems, i.e., classification problems in which class samples are not known in advance. The proposed method was validated with two traditional databases largely used for the evaluation of author name disambiguation methods: one is a collection extracted from DBLP which sums up 4,287 references associated with 220 distinct authors; the other is called KISTI and was built by the Korea Institute of Science and Technology Information; it contains the top 1000 most frequent author names from the late-2007 DBLP database. After 5 iterations of relevance feedback, our approach yielded the best results for author name disambiguation when compared with the state-of-the-art methods that just consider basic reference information, such as author names, publication title, and venue title / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Os algoritmos evolutivos são métodos heurísticos utilizados para a solução de problemas de otimização e que possuem mecanismos de busca inspirados nos conceitos da Teoria de Evolução das Espécies. Entre os algoritmos evolutivos mais populares, estão os Algoritmos Genéticos (GA) e a Programação Genética (GP). Essas duas técnicas possuem como ponto em comum o uso pesado do operador de recombinação, ou \"crossover\" - mecanismo pelo qual novas soluções são geradas a partir da combinação entre soluções existentes. O que as diferencia é a flexibilidade - enquanto que nos algoritmos genéticos as soluções são representadas por códigos binários, na programação genética essa representação é feita por algoritmos que podem assumir qualquer forma ou extensão. A preferência pelo operador de crossover não é simplesmente uma característica em comum das duas técnicas supracitadas, mas um poderoso diferencial. Na medida em que os indivíduos (as soluções) são selecionados de acordo com a respectiva qualidade, o uso do operador crossover tende a aumentar mais rapidamente a qualidade média da população se as partes boas de cada solução combinada (os \"building blocks\") forem preservadas. Holland [1975] prova matematicamente que sob determinadas condições esse efeito ocorrerá em algoritmos genéticos, em um resultado que ficou conhecido como \"Schema Theorem of GAs\". Entretanto, a implementação prática de GA (e, em especial, de GP) geralmente não ocorre segundo as condições supostas neste teorema. Diversos estudos têm mostrado que a extensão variável das estruturas utilizadas em GP dão um caráter de mutação ao operador de crossover, na medida em que a seleção aleatória dos pontos de combinação pode levar à destruição dos building blocks. Este trabalho propõe um novo operador de crossover, baseado em uma técnica de meta-controle que orienta a seleção dos pontos para a recombinação das soluções, respeitando o histórico de recombinação de cada ponto e a compatibilidade semântica entre as \"partes\" de cada solução que são \"trocadas\" neste processo. O método proposto é comparado ao crossover tradicional em um estudo empírico ligado à área Financeira, no qual o problema apresentado consiste em replicar a carteira de um fundo de investimentos setorial. Os resultados mostram que o método proposto possui performance claramente superior ao crossover tradicional, além de proporcionar a emergência de semântica entre as soluções ótimas. / Evolutionary algorithms are heuristic methods used to find solutions to optimization problems. These methods use stochastic search mechanisms inspired by Natural Selection Theory. Genetic Algorithms and Genetic Programming are two of the most popular evolutionary algorithms. These techniques make intensive use of crossover operators, a mechanism responsible for generating new individuals recombining parts of existing solutions. The choice of crossover operator to be used is very important for the algorithms´ performance. If individuals are selected according to the fitness, the use of crossover operator helps to quickly increase the average quality of the population. In GA we also observe the emergence of \"building blocks\", that is, encapsulated parts of good solutions that are often preserved during the recombination process. Holland [1975] proves that, under some conditions, this phenomenon will occur in GAs. This result is known as Schema Theorem of GAs. However, practical implementations of these algorithms may be far away from the conditions stated in Holland´s theorem. In these non-ideal conditions, several factor may contribute to higher rates of destructive crossover (building blocks destruction). This work proposes a new crossover operator, based on a meta-control technique that drives selection of crossover points according to recombination history and semantic compatibility between the code blocks to be switched. The proposed method is compared to common crossover in a case study concerning the replication of an investment fund. Our results show that the proposed method has better performance than the common crossover. Meta-control techniques also facilitate the emergence of building blocks that, in turn, give raise to emergent semantics that can be used to give meaning or interpretations to an optimal solution and its components.

A inferência gramatical lida com o problema de aprender um classificador capaz de reconhecer determinada construção ou característica em um conjunto qualquer de exemplos. Neste trabalho, um modelo de inferência gramatical baseado em uma variante de Programação Genética é proposto. A representação de cada indivíduo é baseada em uma lista ligada de árvores representando o conjunto de produções da gramática. A atuação dos operadores genéticos é feita de forma heurística. Além disto, dois novos operadores genéticos são apresentados. O primeiro, denominado Aprendizagem Incremental, é capaz de reconhecer, com base em exemplos, quais regras de produção estão faltando. O segundo, denominado Expansão, é capaz de prover a diversidade necessária. Em experimentos efetuados, o modelo proposto inferiu com sucesso seis gramáticas regulares e duas gramáticas livres de contexto: parênteses e palíndromos de quatro letras, tanto o comum quanto o disjunto, sendo superior a abordagens recentes. Atualmente, modelos de inferência gramatical têm sido aplicados a problemas de reconhecimento de sequências biológicas de DNA. Neste trabalho, dois problemas de identificação de padrão foram abordados: reconhecimento de promotores e splice-junction. Para o primeiro, o modelo proposto obteve resultado superior a outras abordagens. Para o segundo, o modelo proposto apresentou bons resultados. O modelo foi estendido para o uso de gramáticas fuzzy, mais especificamente, as gramáticas fuzzy fracionárias. Para tal, um método de estimação adequado dos valores da função de pertinência das produções da gramática é proposto. Os resultados obtidos na identificação de splice-junctions comprovam a utilidade do modelo de inferência gramatical fuzzy proposto. / Grammatical inference deals with the task of learning a classifier that can recognize a particular pattern in a set of examples. In this work, a new grammatical inference model based on a variant of Genetic Programming is proposed. In this approach, an individual is a list of structured trees representing their productions. Ordinary genetic operators are modified so as to bias the search and two new operators are proposed. The first one, called Incremental Learning, is able to recognize, based on examples, which productions are missing. The second, called Expansion is able to provide the diversity necessary to achieve convergence. In a suite of experiments performed, the proposed model successfully inferred six regular grammars and two context-free grammars: parentheses and palindromes with four letters, including the disjunct one. Results achieved were better than those obtained by recently published algorithms. Nowadays, grammatical inference has been applied to problems of recognition of biological sequences of DNA. In this work, two problems of this class were addressed: recognition of promoters and splice junction detection. In the former, the proposed model obtained results better than other published approaches. In the latter, the proposed model showed promising results. The model was extended to support fuzzy grammars, namely the fuzzy fractional grammars. Furthermore, an appropriate method of estimation of the values of the production's membership function is also proposed. Results obtained in the identification of splice junctions shows the utility of the fuzzy inference model proposed.

Esta dissertação apresenta um sistema de indução de classificadores fuzzy. Ao invés de utilizar a abordagem tradicional de sistemas fuzzy baseados em regras, foi utilizado o modelo de Árvore de Padrões Fuzzy(APF), que é um modelo hierárquico, com uma estrutura baseada em árvores que possuem como nós internos operadores lógicos fuzzy e as folhas são compostas pela associação de termos fuzzy com os atributos de entrada. O classificador foi obtido sintetizando uma árvore para cada classe, esta árvore será uma descrição lógica da classe o que permite analisar e interpretar como é feita a classificação. O método de aprendizado originalmente concebido para a APF foi substituído pela Programação Genética Cartesiana com o intuito de explorar melhor o espaço de busca. O classificador APF foi comparado com as Máquinas de Vetores de Suporte, K-Vizinhos mais próximos, florestas aleatórias e outros métodos Fuzzy-Genéticos em diversas bases de dados do UCI Machine Learning Repository e observou-se que o classificador APF apresenta resultados competitivos. Ele também foi comparado com o método de aprendizado original e obteve resultados comparáveis com árvores mais compactas e com um menor número de avaliações. / This work presents a system for induction of fuzzy classifiers. Instead of the traditional fuzzy based rules, it was used a model called Fuzzy Pattern Trees (FPT), which is a hierarchical tree-based model, having as internal nodes, fuzzy logical operators and the leaves are composed of a combination of fuzzy terms with the input attributes. The classifier was obtained by creating a tree for each class, this tree will be a logic class description which allows the interpretation of the results. The learning method originally designed for FPT was replaced by Cartesian Genetic Programming in order to provide a better exploration of the search space. The FPT classifier was compared against Support Vector Machines, K Nearest Neighbour, Random Forests and others Fuzzy-Genetics methods on several datasets from the UCI Machine Learning Repository and it presented competitive results. It was also compared with Fuzzy Pattern trees generated by the former learning method and presented comparable results with smaller trees and a lower number of functions evaluations.