# Three Metaheuristic Approaches for Tumor Phylogeny Inference: An Experimental Comparison
## 3 Methods
### Genetic Programming
#### 3.2.3 Selection  
The selection operator in GP determines which individuals will produce offspring in the next generation, based on their fitness. More precisely, individuals with higher fitness have a higher probability of being selected. Additionally, we employ an elitist strategy, where a few (in our case, one) highly fit individuals are directly passed to the new generation, while the selection process is applied to the remaining individuals to determine the rest of the population in the new generation. The individuals directly passed to the new generations are referred to as _elite_, while the others are classified as _non-elite_. The main effect of the elitist strategy is an emphasis on the exploitation phase. However, both elite and non-elite individuals play an equal role in the subsequent phases of the GP algorithm.  
The selection procedure has a huge impact on the balance between the exploration phase, which focuses on finding new solutions, and the exploitation phase, which concentrates on the portion of the search space that has already been visited in the exploration phase. Finding an optimal balance between exploration and exploitation is crucial for the effectiveness of the GP algorithm.  
The literature on selection operators [53] for GA and GP is rich and includes roulette wheel selection, ranking selection, and tournament selection. In this paper, we employ FGTS (fine-grained tournament selection [54]), which is an enhanced version of the standard tournament selection.  
In the standard tournament selection, a tournament round is conducted for each non-elite individual that needs to be selected for the next generation. In each tournament round, a random subset of \(N_{\mathit{Iour}}\) non-elite individuals is chosen, and the fittest individual among them is selected as the winner. The winner is then passed on to the next generation, and a new tournament round begins. This process continues until the selection is complete. Notice that an individual can participate in multiple tournaments within a generation, which allows for fair competition among individuals and provides opportunities for selection based on their fitness in different contexts.  
The tournament size \(N_{\mathit{Iour}}\) is typically an integer value that determines the balance between exploration and exploitation. Choosing an appropriate value for \(N_{\mathit{Iour}}\) can be challenging, as smaller sizes lead to slower convergence, while larger sizes result in faster convergence. To overcome this problem, FGTS introduces a rational (i.e., not necessarily integral) parameter \(F_{\mathit{Iour}}\), which represents the desired _average_ tournament size. In FGTS, tournaments can have different sizes, but the average size is maintained close to \(F_{\mathit{Iour}}\). In our implementation, we have set \(F_{\mathit{Iour}}=2.4\). The pseudocode for the selection operator is Algorithm 3.  
```
Data: A population \(pop\); the desired average tournament size \(F_{\mathit{Iour}}\) Result:\(pop^{*}\): the selected population; // the number of selected individuals is \(|\)\(pop\)\(|\)\(-\)1 \(n\leftarrow\)\(|\)\(pop\)\(|\); \(F_{\mathit{Iour}}^{\leftarrow}\)\([F_{\mathit{Iour}}]\); \(F_{\mathit{Iour}}^{+}\leftarrow\)\([F_{\mathit{Iour}}]\); \(\mathit{\Pi}\leftarrow\)\([n(F_{\mathit{Iour}}^{+}-F_{\mathit{Iour}})]\); \(pop^{*}\leftarrow\emptyset\); for\(i\gets 2\)to\(m\)do \(X\leftarrow F_{\mathit{Iour}}^{-}\) random elements from \(pop\);  Append to \(pop^{*}\) the fittest individual in \(X\); for\(i\gets m+1\)to\(n\)do \(X\gets F_{\mathit{Iour}}^{+}\) random elements from \(pop\);  Append to \(pop^{*}\) the fittest individual in \(X\); return\(pop^{*}\)
```  
**Algorithm 3**Fine-grained tournament selection (FGTS)