Network Topologies for Cellular Automata Computation

The density classification problem aims to find automata able to correctly classify the density of the initial configuration. This problem is highly challenging as the desired computation requires global coordination while Cellular Automata (CAs) rules rely on the local interaction of simple components. Instead of using the standard CA topology of regular lattice, the current chapter focuses on network topologies that can be used in connection with a simple fixed rule in CA computation. The state of a cell evolves according to the majority of its neighbors in the network. In this chapter, we propose a hill-climbing approach to find good network topologies for the density classification problem starting from initial small-world networks. The network solution space is searched in a random hill-climbing manner based on a simple mutation operator changing the network each iteration. Experiments emphasize the identification of network topologies with a good performance for CA computation. The best identified networks are further studied under a dynamic framework to test their robustness against failures and changes that might occur in the network. Results confirm a good sustained performance of networks identified using hill-climbing search.