Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/104| Título: | Computação evolucionária para indução de regras de autômatos celulares multidimensionais |
| Autor(es): | Weinert, Wagner Rodrigo |
| Orientador(es): | Lopes, Heitor Silvério |
| Palavras-chave: | Automatos Computação evolutiva Inteligência artificial Algoritmos paralelos Engenharia elétrica Evolutionary computation Artificial intelligence Parallel algorithms Electric engineering |
| Data do documento: | 2010 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Curitiba |
| Citação: | WEINERT, Wagner Rodrigo. Computação evolucionária para indução de regras de autômatos celulares multidimensionais. 2010. 167 f. Tese (Doutorado em Engenharia Elétrica e Informática Industrial) – Universidade Tecnológica Federal do Paraná, Curitiba, 2010. |
| Resumo: | Um autômato celular é um sistema dinâmico discreto que evolui pela iteração de regras. Os valores das variáveis do sistema mudam em função de seus valores correntes. Os autômatos celulares podem ser aplicados na resolução de diversos problemas. A tarefa de encontrar uma regra de transição que solucione um determinado problema pode ser generalizada como um problema de indução de regras para autômatos celulares. Várias abordagens baseadas em técnicas de computação evolucionária vêm sendo empregadas neste problema. No entanto, estas restringem-se a aplicações específicas. A principal contribuição deste trabalho é a proposição de uma metodologia genérica para indução de regras de autômatos celulares. Para alcançar este objetivo a pesquisa foi segmentada em quatro etapas. Na primeira etapa avaliou-se o desempenho de alguns parâmetros de previsão de comportamento calculados em função de regras de transição. Os resultados obtidos nesta etapa indicaram que os parâmetros de previsão de comportamento dinâmico devem ser utilizados de forma criteriosa. Este cuidado reside na possibilidade de se obter soluções válidas, porém, não satisfatórias. Ressalta-se também a necessidade da existência de parâmetros de referência que para a maioria dos problemas reais, não está disponível. Na segunda etapa apresentou-se um novo método para a previsão do comportamento dinâmico. Este método considera a regra de transição e a configuração inicial do autômato celular. Para a previsão utilizou-se como referência os padrões de comportamento dinâmico qualitativos descritos por Wolfram. O método mostrou-se eficiente para regras de comportamento nulo. Como o processo de simulação da dinâmica de um sistema pode ter um custo computacional elevado, desenvolveu-se uma terceira metodologia. Nesta metodologia implementou-se uma arquitetura baseada no conceito de hardware/software co-design com a finalidade de contornar problemas referentes a tempo de processamento. Esta arquitetura realiza a evolução de autômatos celulares utilizando lógica reconfigurável. A arquitetura diminuiu o tempo de processamento por centenas de vezes, mas algumas restrições do modelo, como número limitado de células lógicas e reprogramações do hardware inviabilizaram seu uso. Considerando-se as restrições impostas pela arquitetura implementada, iniciou-se a quarta etapa da pesquisa onde foi desenvolvida uma nova arquitetura paralela fundamentada no paradigma mestre-escravo. Neste paradigma um processo mestre implementa o algoritmo evolucionário e um conjunto de processos escravos dividem a tarefa de validação das regras obtidas. O sistema é executado em um cluster composto por 120 núcleos de processamento que se interligam por meio de uma rede ethernet. A estratégia co-evolucionária baseada em um modelo insular permitiu a busca por soluções que apresentam um melhor valor para função de fitness. O sistema genérico implementado sobre um ambiente paralelo foi capaz de solucionar os problemas abordados. Uma análise de distribuição de tarefas entre vários processadores enfatizou os benefícios do processamento paralelo. Os experimentos também indicaram um conjunto de parâmetros evolucionários de referência que podem ser utilizados para configurar o sistema. As contribuições deste trabalho foram tanto teóricas, com as avaliações realizadas sobre os parâmetros e os diferentes métodos de previsão de comportamento dinâmico, quanto metodológicas, pois desenvolveu-se a proposta de duas arquiteturas de processamento distintas. |
| Abstract: | A cellular automata is a discrete dynamic system that evolves thought interactions of rules and can be applied to solve several complex problems. The task to find the transition rule to solve a problem can be generalized as a problem of rule induction for cellular automata. Several approaches, based on evolutionary computation techniques, have been proposed to solve this problem. However, there is no generic methodology capable of being applied to a large range of problems. The main contribution of this work is a generic methodology for rule induction for cellular automata. This research was done in four steps to achieve this objective. In the first step we evaluated the performance of some dynamic behavior forecasting parameters calculated as function of a transition rule. The obtained results indicated that those parameters can be used in a careful way. This is due to the possibility of obtaining valid, but insatisfactory solutions. We stress the importance of considering reference parameters, which for the majority of real problems, are not available. In the second research step we proposed a new method to forecast the dynamic behavior. This method considers the transition rule and the initial configuration of the cellular automata. We used the qualitative dynamic behavior patterns described by Wolfram as reference to the forecast. This method was efficient for null behavior rules. Since the process of dynamic simulation can have a high computational cost, we developed a third methodology: an architecture based on the concept of hardware/software co-design to accelerate the processing time. This architecture implements the evolution of cellular automata using reconfigurable logic and was able to decrease hundreds of times the processing time. In the fourth step we developed a new parallel architecture based on the master-slave paradigm. In this paradigm, the master process implements the evolutionary algorithm and a set of slaves processes divide the task of validating the obtained rules. The system runs in a cluster with 120 processing cores connected by a local area network. The co-evolutionary strategy based on an insular model allowed the search for high quality solutions. The generic system implemented over a parallel environment was able to solve the problems proposed. A task distribution analyses among several processors emphasized the benefits of parallel processing. The experiments also indicated a set of reference parameters that can be used to configure the system. The contributions of this work were theoretical and methodological. The former refers to the evaluations done and the different methods for dynamic behavior forecasting parameters. The latter is about the development of two architectures for processing. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/104 |
| Aparece nas coleções: | CT - Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| CT_CPGEI_D_Weinert, Wagner Rodrigo_2010.pdf | 1,8 MB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
