# Generating Loop Patterns with a Genetic Algorithm and a Probabilistic Cellular Automata Rule
## 3 Generating Loop Patterns with a Probabilistic Cellular Automata Rule
### The CA Rule  
The following rule is able to evolve CA loop patterns. The main idea is to inject noise if no template hit is recognized in order to drive the evolution to a stable pattern. In such a pattern, there is everywhere a template hit, i.e., every CA cell is either equal to the center of a tile or it is a part (a pixel) of a tile, corresponding to the center of a template.  
The default value of the new state \(s^{\prime}\) is the current state \(s\). All templates \(A_{i}\) are tested against the current CA neighborhood at the selected site \((x,y)\) where the template center is excluded from the test. If there is a template hit, the center of the template defines the new state. (Either the CA neighborhood corresponds fully to the template or only the center is false and then it is corrected). Noise is injected under certain conditions including certain probabilities. The main condition is \(C_{0}\), which becomes true if there is no hit. The condition \(C_{1}\) takes toggling uncovered cells of the NESW-neighborhood into account in order to dissolve them. The additional condition \(C_{2}\) excludes faulty loop patterns.  
\[s^{\prime}(x,y)=\left\{\begin{array}{ll}s(x,y)&\textbf{default }no\ change&(a)\\ center(A_{i_{\mathit{lastbit}}})&\exists\ hit(A_{i},(x,y))&(b)\\ random\in\{0,1\}&\textbf{if }C_{0}\lor C_{1}\lor C_{2}&(c)\end{array}\right.\]
**where**  
* _hit()_ is a test whether a template \(A_{i}\) matches in the current CA neighborhood of the selected CA cell \((x,y)\): \[hit(A_{i},(x,y)))=\left\{\begin{array}{ll}1&\textbf{if }template\ A_{i}\ matches in the CA neighborhood of (x,y)\\ 0&\textbf{else}\end{array}\right.\]  
_Remark._ For specialized rules, it may be useful to store the number of template hits in the state of the cell: \(h(x,y)=\sum_{i}hit(A_{i},(x,y)))\). Certain values of \(h\) were used to inject additional noise [2; 5] in order to find a minimal or maximal number of dominos covering a space.
* _center_\((A_{i_{\mathit{lastbit}}})\) is the value of the center pixel of a template match. Here, the value of the last hit is used, if there are several hits. It would be possible to use the value of the first hit or that of any hit randomly. To which extent the choice matters is a topic of further research.
* \(C_{0}=Decision(\pi_{0})\wedge(hit=0)\) is the main basic condition that drives the evolution through injecting noise if there is no hit, which means that such a cell is not covered by a tile pixel.
* \(Decision(\pi)\) is a function that is TRUE if a trial is successful under probability \(\pi\), otherwise FALSE. In Python, the function can be defined as: \"def decision(probability): return random() < probability\"
* \(C_{1}=Decision(\pi_{1})\wedge(sum(NESW,hit=0)>0)\) This additional condition avoids lonely uncovered cells that cannot be destroyed by \(C_{1}\). This problem will further be discussed in Section 3.5.
* \(NESW=\{(0,-1),(1,0),(0,1),(-1,0)\}\) is the North-East-South-West-Neighborhood (relative indexes)
* \(sum(Neighborhood,ConditionForANeighbor)\in\{0..|Neighborhood|\}\) is a function that tests for each neighbor in the _Neighborhood_ (set of relative positions of the neighbors) a local condition \(ConditionForANeighbor\) and counts the fulfilled conditions.
* \(C_{2}=Decision(\pi_{2})\wedge(sum(NESW,s=1)\
eq 2)\) These additional conditions realize the loop path condition. Thereby faulty loops are excluded (see end of Section 3.6).
* \(C_{2}=Decision(\pi_{2})\wedge(sum(NESW,s=1)<2)\) This alternative additional condition allows unconnected and connected loops.  
The behavior of the CA rule depends on the probabilities \(\pi_{0},\pi_{1},\pi_{2}\). We can use them as parameters in the general rule: \(Rule(\pi_{0},\pi_{1},\pi_{2})\). Note that the conditions \(\pi_{0},\pi_{1}>0\) have to be fulfilled to drive the evolution to a stable pattern by destroying uncovered cells. The condition \(C_{2}\) can be deactivated by setting \(\pi_{2}=0\).