# Three Metaheuristic Approaches for Tumor Phylogeny Inference: An Experimental Comparison
## 3 Methods
### Variable Neighbourhood Programming  
Genetic Programming and Particle Swarm Optimization are two population-based metaheuristics that explore the search space to find a near-optimal solution. However, they often converge slowly to a such a solution [59]. To address this issue, local search-based algorithms--where we apply a sequence of local changes to the current solution--have been developed. Variable Neighbourhood Programming (VNP) [60] is such a technique. VNP is inspired by automatic programming solution representation and Variable Neighbourhood Search (VNS) metaheuristics, combining the concept of neighborhood change with local search methods to ensure the discovery of local optima. Since VNP is based on non-binary representations, it should be more suited to problems on tree-like objects. The main idea of VNS [46] and VNP is to change neighborhoods as the search progresses and incorporate local search methods to guarantee the identification of local optima. We refer the interested reader to [61]. The neighborhood structure plays a crucial role in defining the search space, both during the descent to local minima and in the escape from the valleys which contain them. A fundamental ingredient of VNS and VNP is to define a suitable neighborhood structure for the solution space. In our case, we define four different neighborhoods for a given tumor phylogeny \(T\). The first neighborhood, denoted by \(N^{1}(T)\), consists of all valid Dollo-\(k\) phylogenies that differ from \(T\) in a subtree whose root is a leaf, or a parent of a leaf, or a grandparent of a leaf. In other words, the root of such subtree has distance of at most 2 to a leaf. The second and third neighborhoods, \(N^{2}(T)\) and \(N^{3}(T)\) respectively, consist of all valid Dollo-\(k\) phylogenies that differ from \(T\) in a subtree whose root has a maximum distance of 5 (resp. 8) to a leaf. Finally, the last neighborhood, denoted as \(N^{4}(T)\), consists of all valid Dollo-\(k\) phylogenies. Notice that the cardinality of the neighborhoods decreases with increasing index (that is, \(|N^{s}(T)|<|N^{s+1}(T)|\) for each \(1\leq s\leq 3\)). To facilitate the presentation of the algorithm, we introduce the function \(z()\), where \(z(1)=2\), \(z(2)=5\,z(3)=8\), and \(z(4)=+\infty\). Each set \(N^{s}(T)\) consists of all valid Dollo-\(k\) phylogenies that differ from \(T\) only in nodes with a distance at most \(z(s)\) to a leaf in \(T\). The main idea of VNP is alternating exploration of the current neighborhood through a local search, and the shaking, where we move to another neighborhood and different parts of the solution space can be explored. The pseudocode of VNP is given in Algorithm 5. ```
Result:\(T\): the phylogeny computed \(s\gets 1\); \(T\leftarrow\) a random Dollo-\(k\) phylogeny; whilehalting condition not reacheddo \(T_{1}\leftarrow\) shaking\((T,s)\);// See Algorithm 6 \(T_{2}\gets\) local\(\_\)search\((T_{1})\);// See Algorithm 7 \(s\leftarrow\) (s mod 4) + 1; if\(fit(T_{2})>fit(T)\)then \(T\gets T_{2}\); \(s\gets 1\); return\(T\)
```  
**Algorithm 5**Variable Neighbourhood Programming  
The VNP follows a main loop that is iterated until a halting condition is met. Usually, this condition includes a limit on the number of iterations and a timeout for the overall execution time. In our case, the timeout is set to 3000 s for all instances. An important invariant of the algorithm is that \(T\) always is the best solution visited so far. The main loop consists of two phases: the shaking phase and the local search. In the shaking phase, a new solution \(T_{1}\) is generated by exploring the current neighborhood, while the local search produces a solution \(T_{2}\). If \(T_{2}\) is better than \(T\), then \(T_{2}\) becomes the new incumbent and the next search begins at the first neighborhood \(N^{1}\). However, if \(T_{2}\) does not improveupon \(T\), the algorithm progresses to the next neighborhood in the sequence to attempt further improvement.