Made available in DSpace on 2016-03-15T19:37:38Z (GMT). No. of bitstreams: 1 Mateus Interciso.pdf: 1720671 bytes, checksum: aa67cff2cc9f7abe5fb3b48bead6b38d (MD5) Previous issue date: 2011-08-23 / Fundo Mackenzie de Pesquisa / The search for cellular automata (CAs) rules capable of executing a determined task can be impossible to be achieve manually, given the huge size of the search space usually involved. A method for being able to find rules capable of executing the task at hand has been the usage of genetic algorithms (GAs) to evolve an initially random population, until the desired objective; each individual of those GAs are usually represented by a candidate transition rule. In problems formulated for the resolution by a binary cellular automaton, a recently used modification on the representation of the individuals was the usage of templates with the presence of an extra symbol, capable of representing every other valid symbol. Such schema of ternary representation is used on the present work, aiming for it s net effect on the search process on the GAs. This study is made for two classical tasks of binary unidimensional cellular automata, the density classification task and the parity problem, both traditional in the context of using GAs for searching transition rules with high performance. By comparing the results of the original GAs and their versions implemented with the ternary representation, it s shown that the ternary representation is able to improve the quality of the results. Particularly, it is analized the condition in which the usage of the ternary representation presents to be more effective, as well as some effects of the actual implementation. Possible future works are presented at the end. / A busca por regras de autômatos celulares que efetuem corretamente uma determinada tarefa pode ser impossível de ser efetuada manualmente, dado o enorme tamanho dos espaços de busca usualmente envolvidos. Uma forma para conseguir encontrar boas regras para a execução do problema em questão tem sido a utilização de algoritmos genéticos (AGs) para evoluir uma população inicialmente aleatória, até o objetivo desejado; nesses AGs cada indivíduo é normalmente representado como uma regra de transição candidata. Em problemas formulados para resolução por um autômato celular binário, uma alteração recentemente estudada na literatura para a representação dos indivíduos foi a utilização de templates (moldes) com a presença de um símbolo extra, capaz de representar os demais símbolos. Tal esquema de representação ternária é utilizada no presente trabalho, visando avaliar seu efeito no processo de busca realizado por AGs. O estudo é feito para duas tarefas clássicas de autômatos celulares unidimensionais binários, a tarefa de classificação da densidade e o problema da paridade, ambas tradicionais no contexto da utilização de AGs para encontrar regras de transição com alta performance. Ao comparar os resultados de AGs originais encontrados na literatura com suas versões implementadas com representação ternária, mostra-se que a representação ternária é capaz de melhorar a qualidade dos resultados. Em particular, analisam-se condições em que o uso da representação ternária se mostra mais efetivo, bem como apontam-se efeitos de alguns aspectos de implementação. Possíveis trabalhos futuros pertinentes ao estudo são discutidos ao final.

Made available in DSpace on 2016-03-15T19:37:41Z (GMT). No. of bitstreams: 1 Mateus Interciso.pdf: 1732926 bytes, checksum: f29787f421b0b5f1d6dedd2c1eb4e0fc (MD5) Previous issue date: 2011-09-23 / Fundo Mackenzie de Pesquisa / The search for cellular automata (CAs) rules capable of executing a determined task can be impossible to be achieve manually, given the huge size of the search space usually involved. A method for being able to find rules capable of executing the task at hand has been the usage of genetic algorithms (GAs) to evolve an initially random population, until the desired objective; each individual of those GAs are usually represented by a candidate transition rule. In problems formulated for the resolution by a binary cellular automaton, a recently used modification on the representation of the individuals was the usage of templates with the presence of an extra symbol, capable of representing every other valid symbol. Such schema of ternary representation is used on the present work, aiming for it s net effect on the search process on the GAs. This study is made for two classical tasks of binary unidimensional cellular automata, the density classification task and the parity problem, both traditional in the context of using GAs for searching transition rules with high performance. By comparing the results of the original GAs and their versions implemented with the ternary representation, it s shown that the ternary representation is able to improve the quality of the results. Particularly, it is analized the condition in which the usage of the ternary representation presents to be more effective, as well as some effects of the actual implementation. Possible future works are presented at the end. / A busca por regras de autômatos celulares que efetuem corretamente uma determinada tarefa pode ser impossível de ser efetuada manualmente, dado o enorme tamanho dos espaços de busca usualmente envolvidos. Uma forma para conseguir encontrar boas regras para a execução do problema em questão tem sido a utilização de algoritmos genéticos(AGs) para evoluir uma população inicialmente aleatória, até o objetivo desejado; nesses AGs cada indivíduo é normalmente representado como uma regra de transição candidata. Em problemas formulados para resolução por um autômato celular binário, uma alteração recentemente estudada na literatura para a representação dos indivíduos foi a utilização de templates (moldes) com a presença de um símbolo extra, capaz de representar os demais símbolos. Tal esquema de representação ternária é utilizada no presente trabalho, visando avaliar seu efeito no processo de busca realizado por AGs. O estudo é feito para duas tarefas clássicas de autômatos celulares unidimensionais binários, a tarefa de classificação da densidade e o problema da paridade, ambas tradicionais no contexto da utilização de AGs para encontrar regras de transição com alta performance. Ao comparar os resultados de AGs originais encontrados na literatura com suas versões implementadas com representação ternária, mostra-se que a representação ternária é capaz de melhorar a qualidade dos resultados. Em particular, analisam-se condições em que o uso da representação ternária se mostra mais efetivo, bem como apontam-se efeitos de alguns aspectos de implementação. Possíveis trabalhos futuros pertinentes ao estudo são discutidos ao final.

Made available in DSpace on 2016-03-15T19:38:09Z (GMT). No. of bitstreams: 1 Fernando Faria.pdf: 516281 bytes, checksum: fc784946b9c2438b3c18c34593a182cb (MD5) Previous issue date: 2008-03-11 / Wolfram Research, Inc. / Cellular automata are discrete dynamical systems composed of simple, locally connected structures (the cells), general in terms of their computational power, and that display complex patterns of behaviour. The purpose of this work was to expand previous studies by Zanon (2006), on non-uniform, one-dimensional cellular automata with nonlocal neighbourhood, in order to verify the existence of rules of these kinds of automata to solve the density classification task, that is, the determination of the predominant bit in a binary string. Our concern here was to look for solutions of the problem mainly by evolutionary computation means, to solve it in a non-trivial fashion, i.e., without including in the solution the majority rule over the entire lattice, and, at the same time, with the target of inferring common features for the solutions that would be found. The results achieved led to an expansion in the quantity of perfect solutions available in the literature, but it became clear that all of them have at least one of the rules involved able to account for the entire lattice at once, an evidence that solutions without rules with global action may not exist. Furthermore, the following observations have been made for the type of automata we considered: even distinct automata may have the same temporal evolution; a certain degree of flexibility is allowed in the total balancing of the rules present in a solution of the density classification task; and, in principle, no common patterns seem to exist between solutions for lattices with 3 and 5 cells, thereby suggesting the impossibility of constructing a solution to the problem from another of a smaller lattice. / Autômatos celulares são sistemas dinâmicos discretos, formados por estruturas simples (as células) conectadas localmente entre si, gerais em termos de seu poder computacional, e que apresentam padrões de comportamento bastante complexos. O intuito deste trabalho foi expandir estudos anteriores de Zanon (2006), sobre autômatos celulares unidimensionais não-uniformes, com vizinhança não-local, visando verificar a existência de autômatos desse tipo na resolução da tarefa da classificação de densidade, isto é, a determinação do bit predominante em uma cadeia binária. Interessou-nos aqui descobrir soluções do problema principalmente por meio de buscas evolutivas, resolvê-lo de forma não trivial, isto é, sem a necessidade da regra da maioria sobre todo o reticulado, e objetivando inferir características necessárias para as soluções que viessem a resolver o problema. Os resultados obtidos levaram a uma expansão da quantidade de soluções perfeitas reportadas na literatura, mas observou-se que todas elas contém pelo menos uma das regras envolvidas tomando todo o reticulado como base de ação, uma evidência da impossibilidade de existir soluções sem regras individuais de ação global. Adicionalmente, as seguintes constatações foram feitas para os autômatos celulares do tipo considerado: mesmo autômatos distintos entre si podem ter a mesma evolução temporal; uma flexibilização do balanceamento total das regras na solução do problema da classificação de densidade é conseguida; e, em princípio, não há padrões nas soluções perfeitas para reticulados de 3 e 5 células, sugerindo a impossibilidade de se construir uma solução a partir de outra de menor tamanho de reticulado.