Computação evolucionária para indução de regras de autômatos celulares multidimensionais

• Ano de defesa: 2010
• Autor(a) principal: Weinert, Wagner Rodrigo
• Orientador(a): Lopes, Heitor Silvério
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Tecnológica Federal do Paraná; Curitiba
• Programa de Pós-Graduação: Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial
• Palavras-chave em Português: Automatos; Computação evolutiva; Inteligência artificial; Algoritmos paralelos; Engenharia elétrica; Evolutionary computation; Artificial intelligence; Parallel algorithms; Electric engineering
• Link de acesso: http://repositorio.utfpr.edu.br/jspui/handle/1/104

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.