8. CONCLUSIONS
In this work, we introduced four meaningful neighborhood structures for the CTP, whereof Step and Rotate are adopted from approaches for deriving phylogenetic trees,SPRr is a restricted variant of SPR and Swap is a speci c form of two Step moves and has not been described before. A previously presented evolutionary algorithm using the ne-grained TreeRank similarity measure has been extended to several memetic algorithm variants by embedding a randomized local search utilizing these neighborhood structures. Thereof the variant using the simple progressive search, which changes the neighborhoods over time, performs best. Furthermore, a variable neighborhood descent procedure that also uses these neighborhood structures has been developed and embedded in a variable neighborhood search. The latter performs shaking by applying an increasing number of random Step moves. The evaluation of neighborhoods could be substantially sped up by implementing a (partly) incremental scheme through updates of the Up-