The Role of the Substrate in CA-based Evolutionary Algorithms

Abstract # ↰

Cellular automata (CA) are a convenient way to describe the distributed evolution of a dynamical system over discrete time and space. They can be used to express evolutionary algorithms (EAs), where the time is the flow of iterations and the space is where the population is hosted. When the CA evolves over a finite grid of cells, the substrate, each cell hosts an individual and the CA rule applies variation operators using the local and neighbor individuals. In this paper, we explore the possibility of enforcing a structure on the substrate. Instead of a flat toroidal grid, we use substrates where some empty cells never host individuals. These cells may act as barriers, slowing down the propagation of genetic traits and hence potentially improving the population diversity, eventually mitigating the risk of premature convergence. We experimentally evaluate the impact of these substrates using a simple CA-based EA on multi-modal and multi-objective problems. We find evidence of a positive impact in some circumstances; on multi-modal problems, convergence is slightly faster and the EA more often reaches all the targets.