# Generating Loop Patterns with a Genetic Algorithm and a Probabilistic Cellular Automata Rule
## 3 Generating Loop Patterns with a Probabilistic Cellular Automata Rule
### Choosing the Type of the Rule  
The simulation of a CA is very simple, that is one reason why CA are so popular. Nevertheless, there are different types of CA and we need to choose the best-suited one for our application. There are two important properties we have to choose: (i) _synchronous_ or _asynchronous_ updating, and (ii) a _deterministic_ or a _probabilistic_ rule.  
(i) Synchronous or Asynchronous Updating.
* _Synchronous updating._ (Phase 1) For every cell \((x,y)\) its new state \(s^{\prime}\) is computed by a local rule and buffered in the _new state_ variable \(s_{new}\). \[\forall(x,y):s_{new}(x,y)\gets s^{\prime}(x,y)=f(s(x,y),s(neighbor_{1}(x,y)),s( neighbor_{2}(x,y)),\ldots)\] We use \(z\gets v\) to denote that a variable \(z\) (with memory) is used to store the value \(v\). (Phase 2) The state of each cell is updated (replaced) by its new state. \[\forall(x,y):s(x,y)\gets s^{\prime}(x,y)\] It is important to notice that the order in which the cells are processed in phase 1 and in phase 2 does not matter, but the phases must be separated. This model can easily be implemented in software, or in clocked hardware using d-flipflops (internally supplying a master and a slave memory).
* _Asynchronous updating._ There are several schemes. In the pure case, there are no phases. A cell \((x,y)\) is selected at random, \(s_{new}\) is computed, and then immediately updated: \(s\gets s_{new}\).  
Figure 8: GA-evolved loop patterns of size \(10\times 10\) in quad representation. Repeating \(10\times 10\) structures are marked. (**a1–a6**) Patterns with one loop. (**b1–b5**) Patterns with two loops. (**b6**) Three loops. (**c1–c6**) Connected loops.  
We want to use the following scheme. A time step \(t\to t+1\) is considered as a block of \(N=n_{1}\times n_{2}\) micro time steps \(\tau\to\tau+1\). A selected cell is processed during one micro time step. For each time step, we select the cells sequentially in a different random order (elements are mutually exclusive). During one time step, each cell is updated once, but the order is random. We display CA configurations at time steps. This scheme is called _random sequence_ or _random new sweep_.  
(ii) Deterministic or Probabilistic Rule. A _deterministic_ rule always computes the same next state for a given input (the combined state of all neighbors). A _probabilistic_ rule computes different next states with certain associated probabilities for a given input.  
Combination. In principle, we can combine _synchronous_ or _asynchronous_ updating with a _deterministic_ or a _probabilistic_ rule. This makes four options: (1) synchronous updating and deterministic rule; (2) synchronous updating and probabilistic rule; (3) asynchronous updating and deterministic rule; (4) asynchronous updating and probabilistic rule.  
_Option 1:_ Until now, it was not possible to design such a rule that can produce loop patterns. The problem is that the evolving patterns may get stuck in non-desired patterns or oscillating structures such as we know from the _Game of Life_. It remains an open question if it is possible to find such a rule.  
_Options 2-4:_ These options are related because the computation of a new configuration is stochastic. It seems that they can be transformed into each other to a certain extent. We decided to use option 4 (random sequence together with a probabilistic rule) as in our former work [1; 2; 3; 5]. With asynchronous updating, we do not need buffered storage elements and a central clock for synchronization, which is closer to the modeling of natural processes.