Biology Reference
In-Depth Information
NNI, SPR, and TBR can be viewed as examining neighbors of a
given tree in the tree space. It can be shown that NNI is a special case of
SPR, which in turn is a special case of TBR. This means that NNI covers
a subset of the neighbors visited by SPR.
3.2.4. Reduce best-fitting subtree (RBFS)
This heuristic is different from the ones presented above. The idea of RBFS
is as follows. A score is computed for each subtree, which indicates whether
the subtree is fitting well or not. A subtree with a high score means that its
contribution to the error is small (and hence our efforts should be con-
centrated in other parts of the tree). Those subtrees which score the best
are reduced to a single leaf. Now, the local search heuristics or other more
comprehensive heuristics can be applied to the reduced tree. In Sec. 4.3,
we show in detail how this idea (in particular, the scoring and reduction
steps) can be applied to WLS tree construction.
3.2.5. Tree fusing (TF)
The final heuristic falls a bit outside the general scheme in the sense that
it uses more than one tree to produce a better candidate. The idea is sim-
ple: identify the largest subtrees over the same leaves in different trees
which do not have the same topology. If such a pair is found, most likely
swapping them will produce an improvement in one of the new trees.
A strong motivation to use this heuristic is that randomized constructors
can produce many candidate trees, so we have a large population of good
trees that can be used.
The heuristics described in this chapter, and in general, are likely to
converge to a local minimum and “get stuck” at this minimum. The larger
the neighborhood they explore (and hence the more time they consume),
the more likely they will not end up in a small local minimum. There is
a trade-off between making the heuristics explore large neighborhoods in
the hope of jumping out of a local minimum and running several opti-
mizations by restarting from a random solution using a randomized con-
structor. Our experience indicates that it is more efficient to look for local
minima not too hard and in exchange start from many random initial
Search WWH ::




Custom Search