A stochastic multi-state cellular automata model and its application in scheduling and density classification problems

Detalhes bibliográficos
Ano de defesa: 2020
Autor(a) principal: Carvalho, Tiago Ismailer de
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Universidade Federal de Uberlândia
Brasil
Programa de Pós-graduação em Ciência da Computação
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://repositorio.ufu.br/handle/123456789/41171
http://doi.org/10.14393/ufu.te.2023.7062
Resumo: Cellular automata (CA) consist of identical components (cells), which change states through time according to a transition rule that considers local information. CA are very simple but possess an impressive computing capacity and present complex behaviour. CA are applied to various applications, such as simulation of natural phenomena or for performing a specific task. The central CA component is the rule that govern the change in cell states. This rule can be manually designed for a specific problem or discovered through search methods. However, as the number of states in the cells increases (in the case of multi-state CA), the size and complexity of the rule grow exponentially, which makes CA employment difficult. As a solution to this difficulty, this thesis proposes the ‘Stochastic CA with Reduce and Mapping' (SCA-RM), a model in which the size of CA rules remains unchanged, regardless of the number of states. This is achieved through the use of three key components in the proposed CA: (I) Reduce, which converts any configuration of states into two states (binary); (II) A traditional CA rule that operates with only two states; (III) Mapping, which translates the output state from the binary rule into an arbitrary state chosen from the original applications set of states. As a consequence, proposed model rules are much simpler than traditional CA rules. Initially, we employed this model to task scheduling, and the results indicate that the proposed CA significantly outperforms the state-of-the-art solutions based on traditional and totalistic CAs. This result is due to the efficient simplification of CA rules provided by SCA-RM. Next, when tested in the multi-state density classification problem, SCA-RM significantly outperforms the traditional CA model. Therefore, results strongly support SCA-RM as the best solution for addressing multi-state CA applications. By simplifying CA rules, SCA-RM opens up new possibilities for the application of cellular automata in a wide range of applications involving many states.