# A Cellular Automata-Based Crossover Operator for Binary Chromosome Population Genetic Algorithms
## 3 The Cellular Automata
: _A cellular automaton is defined by a function \(\gamma:L^{V}\to L^{V}\) that satisfies the property \(\gamma(f)(g)=\varphi(g^{-1}\cdot f)|_{M})\), with memory set \(M\) and local function \(\varphi\), \(\forall f\in L^{V}\), \(g\in V\) and where \(|_{M}\) denotes the restriction to \(M\) of a configuration in \(L^{V}\)._  
**Remark 1** (Elementary cellular automaton ECA 1D CA): _The elementary cellular automaton represents a one-dimensional cellular automaton (1D CA) with two states (\(L=\{0,1\}\)), and the transition rule in a new state of a cell depends only on the neighborhood formed with the adjacent cells (the current cell and the left and right neighbors of the cell)._  
_An ECA capable of universal computation due to the property of simulating any Turing machine, thus allowing the system to recognize or decide other sets of data manipulation rules, is a one-dimensional CA corresponding to rule 110 of the Wolfram code, establishing the resulting states for the eight possible configurations associated with a cell with its two adjacent neighbors._  
_To establish the particular case of the ECA, the settings corresponding to the one-dimensional case with two cell states are considered by \(V=\mathbb{Z}\) and \(L=\{0,1\}\). With these conditions, the configuration space is \(L^{V}=L^{\mathbb{Z}}=\{f:\mathbb{Z}\to L\}\), \(L^{\mathbb{Z}}=\{\ldots,f^{-n},f^{-(n-1)},\ldots,f^{-2},f^{-1},f^{0},f^{1},f^{2 },\ldots,f^{n},\ldots\}\), where \(f^{i}=\{\ldots,f_{-m},f_{-(m-1)},\ldots,f_{-2},f_{-1},f_{0},f_{1},f_{2},\ldots,\)\(f_{m-1},f_{m},\ldots\}\), \(f_{i}=f(i)\), \(\forall i\in\mathbb{Z}\), and \(f(i)\) represents the value of the image of \(i\) by the function \(f^{i}\), \(n,m\in\mathbb{N}\). In this case, the shift action of \(r\in\mathbb{Z}\) on \(L^{\mathbb{Z}}\) can be written by the following relation: \(r\cdot f=\{\ldots,f_{-r-m},f_{-(r+m-1)},\ldots,f_{-r-2},f_{-r-1},f_{-r},f_{-r+ 1},f_{-r+2},\ldots,f_{-r+m-1},f_{-r+m},\ldots\}\)._  
_Also, the memory set \(M\) is established based on the pattern associated with the neighborhood used for the cells of the automaton by \(M=\{-1,0,1\}\), and the local function of the automaton is defined by \(\varphi:L^{M}\to L\) (\(\varphi:\{0,1\}^{\{-1,0,1\}}\to\{0,1\}\))._  
_The cellular automaton is defined based on set memory \(M\) and the local function \(\varphi\) through the function \(\gamma:\{0,1\}^{\mathbb{Z}}\to\{0,1\}^{\mathbb{Z}}\) that satisfies the property \(\gamma(f)(j)=\varphi(j^{-1}\cdot f)|_{M})\), \(\forall f\in\{0,1\}^{\mathbb{Z}}\), \(j\in\mathbb{Z}\), and where \(|_{M}\) denotes the restriction to \(M=\{-1,0,1\}\) of a configuration in \(\{0,1\}^{\mathbb{Z}}\)._  
_Using the Wolfram code and choosing rule 110 and rule 90 for the local function \(\varphi\), the ECA can be written according to the values specified in Table 1 (ECA110) and Table 2 (ECA90), respectively, in which both the state values of the neighboring cells and the output values associated with rule 110 and rule 90 (with binary representation \(110_{2}=01101110\) and \(90_{2}=01011010\)) are shown. The results of ECA 110 for \(nr=10\) generations of evolution of cell states of a cellular automaton with \(n=16\) cells are shown in Table 3. The results of ECA 90 for \(nr=10\) generations of evolution of cell states of a cellular automaton with \(n=16\) cells are shown in Table 4._  
_Table 5 shows the binary images associated with the state values of the elementary automata cells corresponding to rules 30, 90, 99, and 110, respectively, 158 (denoted by E 30, E 90, E 99, and E 110, respectively, E 158) after \(150\) generations of cell evolution and by using \(31\) cells in the initial sequence._  
**Remark 2** (Two-dimensional cellular automata 2D CA): _There are several approaches in the field to define two-dimensional cellular automata (2D CA). As in the case of ECA, the components of a cellular automaton are the lattice (set of cells--each one in a state), the neighborhood, and the local transition rules.