In this paper we describe a new heuristic strategy designed to find optimal (parsimonious) trees for data sets with large numbers of taxa and characters. This new strategy uses an iterative searching process of branch swapping with equally weighted characters, followed by swapping with reweighted characters. This process increases the efficiency of the search because, after each round of swapping with reweighted characters, the subsequent swapping with equal weights will start from a different group (island) of trees that are only slightly, if at all, less optimal. In contrast, conventional heuristic searching with constant equal weighting can become trapped on islands of suboptimal trees. We test the new strategy against a conventional strategy and a modified conventional strategy and show that, within a given time, the new strategy finds trees that are markedly more parsimonious. We also compare our new strategy with a recent, independently developed strategy known as the Parsimony Ratchet.