# Generating Loop Patterns with a Genetic Algorithm and a Probabilistic Cellular Automata Rule
## 2 Generating Loop Patterns with a Genetic Algorithm
### Loop Patterns Generated by GA  
Let us consider generated patterns of size \(n\times n\). We consider patterns as 'equal' if they are equivalent under rotation, shift, or mirroring. For \(n=2\), there exists only the loop pattern \( \begin{smallmatrix}0&0\\ 0&1\end{smallmatrix} \), and \( \begin{smallmatrix}1&0&0\\ 0&1\end{smallmatrix} \) for \(n=3\). Note that a straight line of one-pixels forms a loop under cyclic boundary conditions. For \(n=3\), there exist five patterns as shown in Figure 5a1-a5. All patterns contain one loop, except (a2), which contains two loops. Patterns (a4) and (a5) use two cyclic connections each, one horizontal and one vertical. The patterns (b) are the patterns (a), doubled vertically and horizontally, altogether they form quadruplicates, and that is why we call them _quad patterns_ or simply _quads_. Figure 4: A \(6\times 6\) loop pattern. (**a**) The field boundary is marked in red. Pixels outside the boundary wrap around and thus make the field fully covered. (**b**) The used tiles and their connections. Arrows mark pixels (and their associated tiles) that overlay. Dotted arrows show adjacent pixels/tiles that connect but do not overlay. Figure 3: (**a**) The twelve tiles defining loop patterns. (**b**) A small open square compound tile. (**c**) A larger open square compound tile (“open” means here not fully surrounded by zeroes). For \(n=6\), some of the GA evolved patterns are shown in Figure 6 as quads. The patterns (a) have the same number of 1- and 0-pixels, and therefore, we can call them _balanced_. They are also very _dense_ if we consider 0-pixels as space between the 1-pixel loops. Patterns (b, c) are less dense, because their loops are more commodiously embedded in the space. The used GA favors dense patterns, but it could be modified to aim at low-density loop patterns. Figure 6a3,b1,b4 show two loops, and the other patterns only one. Patterns (b5, c1-c4) contain plane loops. Pattern (a3) contains a plane and a straight loop, (b1) a wave and a straight loop, and (a1, a2, a4, a5, b2, b3, b4, c5) are wave loop patterns. The GA does not always produce loop patterns (Figure 7). GA generated _optimal_ patterns are patterns with a maximal number of tile matchings. Such patterns correspond to dense loops, as shown in Figure 6a1-a5, and their number of one- and zero-pixels is balanced (may differ by one if the whole number of pixels is not even). The generated non-optimal patterns, in which the number of tile matches is not maximal, can be (a) loop  
Figure 5: GA evolved loop patterns of size \(4\times 4\). The _quad_ patterns (**b1–b5**) repeat the patterns (**a1–a5**) horizontally twice and vertically twice in order to exhibit the inherent cyclic structures. The cyclic connections relevant for the loops in (**a1–a5**) are noted. (**a1**) is a plane loop, (**a2**) shows two straight loops, and (**a3–a5**) are wave loops. Figure 6: GA evolved loop patterns of size \(6\times 6\), depicted in quad representation. Patterns (**a1–a5**) consist of 18 one-pixels (blue) and 18 zero-pixels (green). Patterns (**b1–b5,c1–c4**) have 16 one-pixels. Pattern (**c5**) has only 14 pixels. patterns, or (b) faulty loop patterns. We can observe special types of faults that may appear in combination (Figure 7). * (UFC) Uncovered cell. The given space is only partially filled with tiles. The isolated and marked blue cells in Figure 7a1,a2 are such cells. The GA generates for such uncovered cells either 0 or 1. Such cells can automatically be detected and then shown in a distinct color (e.g., white or green). * (TCN) Touching corners. There exists a pair of one-pixels that touch each other on a diagonal. * (3 PC) 3-pin-connector. There exists a 3-pin connector in a loop path (Figure 7a5,b2,b5). * (4 PC) 4-pin-connector. Such a connector exists in a loop path (Figure 7b1). * (ART) Artifact. There exist other black pixel structures that may be a part of a possible loop or an appendix of a loop. Typical such structures are: a line, a partial rectangle, or a branch (Figure 7b2-b5).