# Generating Loop Patterns with a Genetic Algorithm and a Probabilistic Cellular Automata Rule
## 1 Introduction
### Related Work  
_Own Previous Work._ Complex patterns were constructed in a local way by moving CA agents [4]. The agents use a finite state machine evolved by a GA. Though the results are impressive, it takes quite some effort to train the agents. In addition, it is very difficult to train them for small and large grid sizes at the same time in order to make them work for any grid size. It would be a new and interesting task to train them for forming loop patterns and to find out the limitations. Then, a probabilistic CA rule was used to generate point patterns [1], sensor point patterns [3], and domino patterns [2; 5]. It was possible to aim at a maximal or a minimal number of dominos by injecting noise depending on the level of tile overlapping. In this paper, the idea of using a probabilistic CA is also followed. The rule here was adapted to a new set of tiles and uses an additional logical condition in order to evolve loop patterns _only_. _Genetic Algorithm for Pattern Generation._ In our internal research work, we used for several years a GA to generate patterns with a global fitness function based on local conditions and local pattern matchings. This method is first published in this article. GA is a generally accepted method for optimization. It dates back to [PERSON] [6; 7] and overviews are given in [8; 9]. We just used the classical techniques (crossover, mutation, selection) in a simple way, i.e., we randomly selected the second parent (the mate) without giving preference to parents with high fitness. This was sufficient for our purpose and it was not the intention to find a more efficient evolutionary algorithm or heuristic. _Overlapping Tiles and Loops._ The recommendable book [10] provides much information about tilings but it does not deal with overlapping tiles. Overlapping 1D tilings are treated theoretically in the context of recognizable languages, monoids, and two-way automata [11], and it was partly motivated by an application in computational music theory. This paper is a good basis for further studies and extensions to the \(n\)-dimensional case. There are a lot of applications for overlapping tilings, like the dense parking of cars in a parking lot or constructing a sieve for maximal particle flow (using domino tiles) [5], optimizing task scheduling (overlapping communication and computation) [12], or building nanostructures [13]. Our problem is related to open and closed (loop) _space-filling curves_[14; 15; 16]. In principle, such loops can be generated with our approaches (GA and CA), among others. The wave loop (Figure 11 (fourth in the second row)) is a space-filling wave loop. It is also an open space-filling curve if the horizontal wrap-around of the torus is not used. The wave loop (Figure 11 (second in the first row)) is a space-filling wave loop in the torus. The proposed GA could be tuned (by additional global fitness measures) to generate such curves only. Generating _only_ space-filling curves by a CA rule is a task that has to be performed. For space-filling curves, the field size has to be considered with respect to the possible solutions. Note that in our approach, the space between loops is not constant 1, it can vary between 1 and 2 (or even more if allowing uncovered cells). So our loops can be arranged in a more flexible way for any grid size, they can keep a suitable distance out of a certain range. This feature is also valuable for describing particles that can attract and repulse. Hamiltonian cycles can algorithmically be computed in grid graphs. In [17], the grid graph is interpreted as a field of cells as here, whereas in [18] a checkerboard marked grid graph is used. In [19], families of intersecting closed curves (connected loops) are discussed in the context of string topologies. This paper could be of interest for further work on generating connected loops. _Cellular Automata._ A CA is a grid of automata (cells). Every cell changes its state depending on its own state and the state of its local neighbors according to a local rule.