Computational Methods in Conservation Planning
The algorithms to solve the aforementioned Problems 1–5 are those that are guaranteed to produce an optimal solution, often referred to as exact algorithms, and those that are not. The former includes algorithms that are based on integer programming and dynamic programming, whereas the latter comprise greedy algorithms, approximation algorithms and algorithms based on simulated annealing. We will start with greedy algorithms, as they are simple and probably most widely applied in conservation planning.
Greedy algorithms are a simple and general heuristic strategy but, usually, do not guarantee optimal solutions. Kirkpatrick (1983) was probably the first to apply a greedy algorithm to find a solution to Problem 4, the simple reserve selection, but under the species richness concept. His greedy algorithm coined “complementarity principle” first identifies the most species-rich area. In the second step, it finds the area, which “adds” the most numbers of new species to the firstly chosen area. This is repeated until k areas are obtained. Such a complementarity principle has been applied to maximize PD (Faith 1992) and also applied elsewhere (e.g., Vane-Wright et al. 1991; Pressey et al. 1997). Recently, Bordewich and Semple (2008) have proven that the greedy algorithm applied to Problem 5 under PD will generate a solution that has at least ~63 % of the PD of the optimal solution, which is the best possible approximation ratio.
The only case, where a greedy algorithm delivers the optimal solution is the taxon selection (Problem 1) under PD on trees (Pardi and Goldman 2005; Steel 2005). An efficient implementation of such a greedy algorithm (Minh et al. 2006) finds a solution for trees with millions of taxa within seconds on a standard PC. Greedy algorithms have been further examined in conservation biology (Moulton et al. 2007; Bordewich et al. 2008).
Obviously greedy algorithms can be applied for Problems 1–5 to maximize SD. The general idea is to start with one target (either taxon or area) having the highest SD. We then choose the second target “adding” the most SD while still satisfying the constraints (budget or viability constraints). We repeat this step until no further target can be added (e.g., exceeding k targets for Problem 1, 3, and 4 or exceeding the budget for Problem 2 and 5). As an illustration the greedy algorithm is applied for Problem 4 to find four countries showing the highest pheasant SD for the split network (Fig. 2b) and known geographical distribution (Table 1) as follows. Malaysia is first selected as it contains the highest SD. Philippines, Indonesia, and India are selected in the next steps. In this particular example the greedy algorithm happens to obtain the optimal set of four countries (Table 2).