# Application of Genetic Algorithms for Periodicity Recognition and Finite Sequences Sorting
## 4 Genetic Algorithm
### MakePeriod Method  
Finding all the periodicity variations for a larger sequence size did not show a very good result in time. More specifically, for the sequence size \(n>30\), the algorithm did not find solutions for more than 30% of the total and got stuck for a very long time. In this regard, it was decided to optimize the algorithm. Thus, an additional MakePeriod method (Algorithm 3) was created, which performs a modification operation of a binary list in order to provide a certain periodic behavior inside this list. This method is used to create a periodic structure, ensuring that the elements of the list correspond to an alternating pattern in a given period \(P\).  
```
for index \(\gets 0\) to \((N-\text{Period})\)do if\(\text{sequence}[\text{index}]\
eq\text{sequence}[\text{index}+\text{Period}]\)then if\(\text{sequence}[\text{index}]=1\)then \(\text{sequence}[\text{index}+\text{Period}]\gets 1\) else \(\text{sequence}[\text{index}+\text{Period}]\gets 0\) endif endif endfor return sequence
```  
**Algorithm 3** Function MakePeriod(sequence, Period)  
Figure 8: Example of mutation by reversion.  
Figure 7: Example of mutation by exchange.  
As a result of executing this method, the elements of the _sequence_ list will be modified in such a way as to provide a given sequence periodic for a certain \(P\). That is, this operation will allow the algorithm to change individuals who are nonperiodic to periodic ones, which significantly reduces the search time for a solution.  
**Example 1**.: _Let the sequence be nonperiodic, and we will check it for the value of period 3, that is, \(s_{n}=1001010,P=3\)._  
_Starting from the third element, we see that the periodicity rule for 3 is not fulfilled for this sequence (the values of the elements in indexes 3 and 5 are different). However, we can change the value in index 5 to the opposite one, which has index 3 (Figure 9)._  
This will avoid generating additional individuals and their checks, because without the MakePeriod method, our algorithm would simply not consider this sequence, since it is nonperiodic. Thus, a new sequence will be added to the area of potential solutions, which will allow us to narrow the search area of the solution and reduce the time.  
The proposed algorithm is iterative; then it is known that a breakpoint must be determined to stop it. We need to find the number of possible sequences that are periodic. Experimentally, for the initial values of the periods, we obtained a pattern that these are two to the power of the period value under consideration (\(2^{p}\)). Given the fact that we will not consider the sequence as a solution that consists of identical elements (such sequences are 2), we have the following formula:  
\[k=2^{p}-2 \tag{3}\]  
This Formula (4) determines the breakpoint; that is, if the number of solutions found is equal to this value, then the genetic algorithm stops working. It is important to note that determining the specific value of the breakpoint is one of the reasons for further research in this direction. The complete scheme of operation of the algorithm in question is indicated in the form of a block diagram (Figure 10).  
As can be seen from the diagram, each individual is checked for periodicity during selection; those that are really periodic are added to the list of solutions, and for those that are not periodic, the MakePeriod operation is performed. When executing the MakePeriod operation for a given sequence, if it meets the periodicity condition and is distinct within the list of solutions, it is also added to the list of solutions. If the above conditions are not met, then the crossover and mutation operations occur sequentially. After that, the stop condition is checked. If the number of solutions is equal to \(k\), which is determined by Formula (1), then the algorithm stops working; if not, a selection operation is performed for already-changed individuals.  
Figure 9: Example of the MakePeriod method.