Explorando o uso de regras de correspondência condicional na busca evolutiva por autômatos celulares classificadores de densidade binária
Resumo
Autômatos celulares (ACs) são sistemas discretos, fundamentados em interações locais que, mesmo simples, podem ser capazes de computabilidade universal. Um problema clássico de estudo da capacidade computacional dos ACs é a tarefa de classificação da densidade, na qual se objetiva determinar o bit predominante em uma sequência binária arbitrária. Investigou-se aqui a eficácia que uma representação de regras de ACs recentemente proposta na literatura poderia ter nessa tarefa, já que a nova estrutura do espaço de busca, induzida pela nova representação, poderia ser benéfica. Buscas evolutivas realizadas em diferentes formulações do problema, inclusive em maiores dimensionalidades do espaço, evidenciaram impacto restrito na eficácia das regras encontradas. Tal resultado contrasta com os disponíveis na literatura, apontando
limitações do esquema de representação utilizado.
Referências
de Oliveira, P. P. (2014). On density determination with cellular automata: Results, constructions and directions. Journal of Cellular Automata, 9(5-6):357–385.
Fatès, N. (2015). Remarks on the cellular automaton global synchronisation problem. In International Workshop on Cellular Automata and Discrete Complex Systems, pages 113–126. Springer.
Fuks, H. and Procyk, R. (2020). Explorations of ternary cellular automata and ternary density classification problems. arXiv preprint arXiv:2002.08924.
Land, M. and Belew, R. (1995). No perfect two-state cellular automata for density classification exists. Physical review letters, 74:5148–5150.
Peper, F., Lee, J., Adachi, S., and Isokawa, T. (2009). Cellular nanocomputers: a focused review. International Journal of Nanotechnology and Molecular Computation (IJNMC), 1(1):33–49.
Sahu, S., Oono, H., Ghosh, S., Bandyopadhyay, A., Fujita, D., Peper, F., Isokawa, T., and Pati, R. (2012). On cellular automata rules of molecular arrays. Natural Computing, 11(2):311–321.
Sipper, M. (1994). Studying artificial life using a simple, general cellular model. Artificial Life, 2(1):1–35.
Wolfram, S. (2002). A new kind of science, volume 5. Wolfram media Champaign, IL.
Wolz, D. and de Oliveira, P. P. B. (2008). Very effective evolutionary techniques for searching cellular automata rule spaces. J. Cellular Automata, 3:289–312.
