294
Hugh Possingham, Ian Ball, and Sandy Andelman
determined by eye. No other set of two sites conserves all species, although there
are plenty of three-site reserve systems that conserve all the species. In the
language of mathematical programming, the optimal solution is sites 3 and 5, the
optimal value is 2.
There are some interesting lessons from this Columbia Plateau example. First,
note that the optimal solution, select sites 3 and 5, and its associated value, two
sites, can be obtained by inspection. For bigger data sets, it is not hard to imagine
that a solution by inspection will be difficult to find. Given this problem, early
workers in the field devised algorithms for finding the minimum set. These
algorithms involve selecting complementary sites sequentially, until the objective
of representing all species is attained. The most obvious approach to representing
every species is to add sites to the reserve system sequentially by selecting the site
that adds the most unprotected species to the set that has already been selected.
This algorithm is often called the “greedy” algorithm because it greedily attempts
to maximize the rate of progress toward the objective at each step. Assuming that
initially there are no sites in the reserve system, this algorithm would first select
site 1, because it would protect eight species. Once site 1 has been selected, we see
that each of sites 2, 3, and 5 will add a single additional species. Regardless of
which of the three is chosen first, two more sites are needed to cover every
species. The solution is suboptimal because it has three sites. This simple algorithm fails because the final reserve system is inefficient, when compared
against the optimal reserve system.
Notice that one of the species in Table 17.1 is only represented in one site. The
only place to find Forster’s Tern is in site 3. This means site 3 is essential. So, an
alternative approach is to first select any sites that are essential and then select
sites that add the most unprotected species to the reserve system. This approach,
sometimes termed the rarity approach, targets rare species first and then builds a
complementary set from there. In this case, once site 3 is selected, the site that
adds the most species to site 3 is site 5, which then completes a reserve system of
just two sites.
It is interesting to try to devise different sorts of algorithms to solve these types
of problems, and many have been tried (Margules et al. 1988; Rebelo and
Siegfried 1992; Nicholls and Margules 1993; Pressey et al. 1997). All the algorithms that choose sites sequentially are, however, inefficient in that they are
not guaranteed to find the optimal solution.
Consider a second example from the Columbia Plateau, with an expanded data
set containing more species and sites (Table 17.2). Again, the minimum set
problem is to find the smallest number of sites that will represent every species.
The first point is that now it is no longer possible to see the optimal solution by
inspection, as it was in Table 17.1. In this case, the minimum set reserve system is
sites 3, 9, and 10. No other set of three sites conserves all species, although there
are plenty of four-site reserve systems that conserve all the species.
Some insight into why sequential algorithms are inefficient can be gained by
considering the number of possible reserve systems for any problem. For example, in Table 17.1 there are eight sites, each of which could be in or out of the
Hugh Possingham, Ian Ball, and Sandy Andelman
determined by eye. No other set of two sites conserves all species, although there
are plenty of three-site reserve systems that conserve all the species. In the
language of mathematical programming, the optimal solution is sites 3 and 5, the
optimal value is 2.
There are some interesting lessons from this Columbia Plateau example. First,
note that the optimal solution, select sites 3 and 5, and its associated value, two
sites, can be obtained by inspection. For bigger data sets, it is not hard to imagine
that a solution by inspection will be difficult to find. Given this problem, early
workers in the field devised algorithms for finding the minimum set. These
algorithms involve selecting complementary sites sequentially, until the objective
of representing all species is attained. The most obvious approach to representing
every species is to add sites to the reserve system sequentially by selecting the site
that adds the most unprotected species to the set that has already been selected.
This algorithm is often called the “greedy” algorithm because it greedily attempts
to maximize the rate of progress toward the objective at each step. Assuming that
initially there are no sites in the reserve system, this algorithm would first select
site 1, because it would protect eight species. Once site 1 has been selected, we see
that each of sites 2, 3, and 5 will add a single additional species. Regardless of
which of the three is chosen first, two more sites are needed to cover every
species. The solution is suboptimal because it has three sites. This simple algorithm fails because the final reserve system is inefficient, when compared
against the optimal reserve system.
Notice that one of the species in Table 17.1 is only represented in one site. The
only place to find Forster’s Tern is in site 3. This means site 3 is essential. So, an
alternative approach is to first select any sites that are essential and then select
sites that add the most unprotected species to the reserve system. This approach,
sometimes termed the rarity approach, targets rare species first and then builds a
complementary set from there. In this case, once site 3 is selected, the site that
adds the most species to site 3 is site 5, which then completes a reserve system of
just two sites.
It is interesting to try to devise different sorts of algorithms to solve these types
of problems, and many have been tried (Margules et al. 1988; Rebelo and
Siegfried 1992; Nicholls and Margules 1993; Pressey et al. 1997). All the algorithms that choose sites sequentially are, however, inefficient in that they are
not guaranteed to find the optimal solution.
Consider a second example from the Columbia Plateau, with an expanded data
set containing more species and sites (Table 17.2). Again, the minimum set
problem is to find the smallest number of sites that will represent every species.
The first point is that now it is no longer possible to see the optimal solution by
inspection, as it was in Table 17.1. In this case, the minimum set reserve system is
sites 3, 9, and 10. No other set of three sites conserves all species, although there
are plenty of four-site reserve systems that conserve all the species.
Some insight into why sequential algorithms are inefficient can be gained by
considering the number of possible reserve systems for any problem. For example, in Table 17.1 there are eight sites, each of which could be in or out of the