Very Effective Evolutionary Techniques for Searching Cellular Automata Rule Spaces
Dietmar Wolz and Pedro P.B. de Oliveira
The main benchmark problems in the cellular automata literature related to discovering rules able to exhibit given target behaviours have been the density classification task and the parity problem, in which the rule must decide about global properties of the number of bits in the initial configuration of binary cellular automata. Here a suitable combination of evolutionary computation techniques is presented and discussed that led to unparalleled good results in the standard formulation of the density classification, with the discovery of a few thousand rules with higher efficacy than the best currently known rule. Furthermore, the same basic techniques were also very successfully applied to the parity problem and to density classification in two and three dimensions, so that, for all these cases, the quality of the results achieved also seem to constitute, by far, the best ones currently available for all these computational tasks.