# Generating Loop Patterns with a Genetic Algorithm and a Probabilistic Cellular Automata Rule
## 2 Generating Loop Patterns with a Genetic Algorithm
### Genetic Algorithm  
In the first stage, we use a GA to find optimal patterns with respect to a global fitness function and defined by tiles. The main purpose here is to validate that a certain set of designed tiles define the patterns that are aimed at the user and that can be used later by the CA rule in the second stage. The algorithm used is given in Algorithm 1. A possible solution (an individual) is a tuple (_Pattern, Fitness_). An array/list of \(M\) solutions is the data and output that is manipulated by the algorithm. (1) The pattern list is initialized randomly. (2) The while loop is repeated until a termination condition becomes true, i.e., the number of iterations reaches a certain limit, and / or another global condition, like a certain fitness level or certain pattern features. (3) In each block, better solutions are searched for. For each current existing individual (tentative solution), an offspring (a new individual) is generated by crossover and mutation. The current individual is replaced by the offspring if it has higher fitness. (4) A mate \(S_{j}\) is selected at random from the list. (5) A new offspring pattern is computed by crossing over \(S_{i}\) with \(S_{j}\), and then applying a mutation. (6) The fitness of the offspring pattern is computed and stored within the offspring. (7) The offspring replaces the current individual \(S_{i}\) if its fitness is higher. (8) The list of solutions is sorted for output. The _fitness_ function computes the number of tile matches that occurs within a pattern. At every site of the pattern, all tiles from the given set are tested if they match locally, i.e., test if all tile pixels (aligned to the tile's anchor/center) are equal to the pattern values in the local neighborhood. A null tile pixel (do not care) excludes the testing of the corresponding pattern value. The used GA is a simple form using the classical GA algorithm basics. The goal was to generate optimal patterns in a simple way and not to optimize the algorithm itself, which is a topic for further research. Only one list of individuals is used and not two (old and new generation). \begin{table}
\begin{tabular}{c c c} \hline \hline
**Pixel \(p_{1}\)** & **Pixel \(p_{2}\)** & **Result** \\ \hline
0 & 0 & 0 \\
0/1/- & - & - \\
1 & 0 & forbidden \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The result of overlaying two pixels. ```
Types: \(Pattern=array\)\([0\;\ldots\;n_{1}-1,0\;\ldots\;n_{2}-1]\) of \(\{0,1\}\) \(Solution=(Pattern,Fitness)\) Data and Output: \(S\) is an array [1... \(M\)] of Solution Temporary:  Offspring is a Solution (1) \(S.Pattern\leftarrow\) RandomPatterns (2) while not TerminationCondition (3) foreach\(S_{i}\) in \(S\) (4) Select randomly a Mate \(S_{j}\) (5) Offspring.Pattern = Mutate (Crossover \((S_{i},S_{j})\)) (6) Offspring.Fitness \(\leftarrow\) fitness (Offspring.Pattern) (7) if Offspring.Pattern \(\
ot\in S.Pattern\) and Offspring.Fitness \(>S_{i}\): Fitness then\(S_{i}\leftarrow\) Offspring (3) foreach end (2) while end (8) \(S\gets SortByFitness\)
```  
**Algorithm 1**Generating a Binary Pattern with a Genetic Algorithm  
Algorithm 1 that generates patterns with a maximal number of tile matches. The fitness function computes the number of matches. Every site of the pattern field is tested if there is a match of a tile out of a given set of tiles. Each individual is treated separately and is expected to improve by crossover with any other individual, not depending on their fitness. Thereby a high diversity is supported, though the speed of improvements may not be so high. Crossover is performed in the following way (uniform crossover with a certain probability): (1) Each bit of the offspring \(Crossover(S_{i},S_{j})\) (without mutation) is taken from the mate \(S_{j}\) with probability \(p_{1}\) otherwise unchanged from the parent \(S_{i}\). (2) Then, mutation is performed on each bit with probability \(p_{2}\) yielding \(Mutate(Crossover(S_{i},S_{j}))\). Then, the fitness of the offspring was computed and used for replacement in the case of improvement.