A new adaptive fast cellular automaton neighborhood detection and rule identification algorithm

An important step in the identification of cellular automata(CA) is to detect the correct neighborhood before parameter estimation.Many authors have suggested procedures based on the removal of redundantneighbors from a very large initial neighborhood one by one tofind the real model, but this often induces ill conditioning and overfitting.This is true particularly for a large initial neighborhood where there arefew significant terms, and this will be demonstrated by an example inthis paper. By introducing a new criteria and three new techniques, thispaper proposes a new adaptive fast CA orthogonal-least-square (Adaptive-FCA-OLS) algorithm, which cannot only adaptively search for the correctneighborhood without any preset tolerance but can also considerably reducethe computational complexity and memory usage. Several numericalexamples demonstrate that the Adaptive-FCA-OLS algorithm has betterrobustness to noise and to the size of the initial neighborhood than otherrecently developed neighborhood detection methods in the identification ofbinary CA.

IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 42(4), 1283–1287. Institute of Electrical and Electronics Engineers (IEEE)