Representação ternária em algoritmos evolutivos para a obtenção de autômatos celulares binários

AUTOR(ES)

Mateus Interciso

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

23/09/2011

RESUMO

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.

ASSUNTO(S)

engenharia eletrica autômatos celulares algoritmos genéticos tarefa da classificação da densidade problema da paridade representação ternária cellular automata genectic algorithms density classification task parity problem ternary representation

Documentos Relacionados

• Representação ternária em algoritmos evolutivos para a obtenção de autômatos celulares binários
• Automatizando a obtenção da complexidade baseada em linguagem regular de autômatos celulares elementares
• Previsão de séries temporais epidemiológicas usando autômatos celulares e algoritmos genéticos
• Método Criptográco Baseado em Autômatos Celulares Bidimensionais para Cifragem de Imagens
• Abordagens baseadas em autômatos celulares síncronos para o escalonamento estático de tarefas em multiprocessadores