## 2 Materials and Methods
### Random Tree Pruning Based Search
For example, if the number of iterations after the best found solution has not improved is 2 times larger than the number of iterations when improvement has happened. Consequently, if improvement happened at the 30 th iteration, we stop at the 60 th iteration if no new improvement has happened. If new improvement has happened after the 50 th iteration, we slide the last iteration forward to the 100 th iteration. The GA has one additional parameter: mutation probability. A single iteration of the random search is described as the following pseudocode (Algorithm 1):  
```
1: Create randomly pruned trees batch. 2: Find the minimal set cover for each tree. 3: Find the tree with the smallest minimal set cover. 4:if (the size of smallest minimal cover \(<\) the size of best solution minimal cover) then
5: Update the best solution. 6: Update the iteration when the best solution has improved. 7:endif
```  
**Algorithm 1**Algorithm of a single iteration of the random search  
The stopping criterion for the random search is met when two conditions are fulfilled: the minimal number of iterations has happened and the number of iterations after the best found solution has not improved. The crossover and mutation operators for the GA are the following. For each layer of the tree, we record the set of chosen node indices after pruning for the layer is finished. The crossover performs the pruning information exchange and is described as the following pseudocode (Algorithm 2):  
```
1: Find the deepest equal layer between the two solutions (trees). 2: {First solution unique indices set} \(\leftarrow\) {first solution indices set} \(\setminus\) {second solution indices set}. 3: {Second solution unique indices set} \(\leftarrow\) {second solution indices set} \(\setminus\) {first solution indices set}. 4: {Common between the two solutions indices set} \(\leftarrow\) {first solution indices set} \(\cap\) {first solution indices set}. 5: Crossover point \(\leftarrow\) uniformly randomly chosen integer number between 1 and the size of first solution unique indices set. 6: Swap parts of unique indices sets for the two solutions between 1 and crossover point inclusively. 7: {First solution indices set} \(\leftarrow\) {common between the two solutions indices set} \(\cup\) {first solution unique indices set}. 8: {Second solution indices set} \(\leftarrow\) {common between the two solutions indices set} \(\cup\) {second solution unique indices set}. 9: Discard all the layers after the deepest equal layer for the first solution. 10: Discard all the layers after the deepest equal layer for the second solution. 11: Using the new chosen sets for pruning, regenerate the next layer after the deepest equal for the first solution. 12: For the first solution, regenerate other layers with random pruning. 13: Using the new chosen sets for pruning, regenerate the next layer after the deepest equal for the second solution. 14: For the second solution, regenerate other layers with random pruning. ```  
**Algorithm 2**Algorithm of the pruning information exchange  
Mutation discards all of the crossover results and creates new random pruning information. The mutation after crossover is performed as in the following pseudocode (Algorithm 3):  
```
1: Take the deepest equal layer from the crossover. 2: Discard all the layers after the deepest equal layer. 3: Regenerate the tree after the deepest equal layer with random pruning. ```  
**Algorithm 3**Algorithm of the mutation after crossover  
Performing crossover and mutation starting from the next layer after the deepest equal layer, we preserve the pruning information for the previous layers. For the starting random population, the deepest equal layer is equal to one. It is the layer with all the lines. With crossover, we can evolve the next layer to obtain trees with smaller minimal set covers. However, the layers after the next one are pruned randomly.