17. Mathematical Methods for Identifying Representative Reserve Networks
297
branch-and-bound method and found optimal solutions for a reduced version of
the original data set of Pressey and associates. The comparison showed that,
although solutions obtained with heuristics can be as much as 20% worse than the
optimal solution, if a variety of methods are tried, one can probably guarantee
being within 5% of the optimum for problems of moderate size. However, ILP
fails when the number of reserves is moderately large (more than about 20 or 30),
because the problem becomes too big for a solution to be found in reasonable
time. Thus, heuristics are fast and easy to understand but may deliver inefficient
solutions, whereas integer linear programming methods are likely to fail on large
problems. ILPs also have the disadvantage of producing a single optimal solution,
whereas in a conservation context, flexibility may be advantageous. It might be
useful to identify not one but a range of possible solutions that could meet a
particular reservation goal. In the following section, we describe an alternative
approach to some of these problems.
Simulated Annealing Solutions: A Comparison
Simulated annealing is a minimization method based on the process of annealing
metals and glass (Metropolis et al. 1953; Kirkpatrick et al. 1983). It begins by
generating a completely random reserve system. Next, it iteratively explores trial
solutions by making sequential random changes to this system. Either a randomly
selected site, not yet included in the reserve system, is selected, or a site already in
the system is deleted. At each step, the new solution is compared with the previous
solution, and the best one is accepted. The advantage of this approach is that
potentially it can avoid getting trapped in local optima. It allows the reserve
system to move temporarily through suboptimal solution space and thus increases
the number of routes by which the global minimum might be reached. Initially,
any change to the system is accepted, whether it increases or decreases the value
of the system. As time progresses, the algorithm is more and more choosy about
which changes it accepts, rejecting those changes that would increase the value of
the system by too large an amount. By the end of a simulated annealing run, only
changes that improve (i.e., decrease) the value of the system are accepted. At this
point, the system soon reaches a local minimum. To reiterate, the central idea
behind simulated annealing is that, by allowing bad changes as well as good, local
minima are avoided.
The simulated annealing method works as follows:
1. Set input parameters and the maximum number of iterations.
2. Generate an initial reserve system consisting of sites selected at random, and
compute objective function.
3. Randomly select a site to add to or delete from the system.
4. Evaluate the resulting change in the objective function: if e (
−change
acceptance level
) <
random number, then accept the change, otherwise reject it.
5. Decrease the acceptance level, and repeat steps 3–5 for the given number of
iterations.
297
branch-and-bound method and found optimal solutions for a reduced version of
the original data set of Pressey and associates. The comparison showed that,
although solutions obtained with heuristics can be as much as 20% worse than the
optimal solution, if a variety of methods are tried, one can probably guarantee
being within 5% of the optimum for problems of moderate size. However, ILP
fails when the number of reserves is moderately large (more than about 20 or 30),
because the problem becomes too big for a solution to be found in reasonable
time. Thus, heuristics are fast and easy to understand but may deliver inefficient
solutions, whereas integer linear programming methods are likely to fail on large
problems. ILPs also have the disadvantage of producing a single optimal solution,
whereas in a conservation context, flexibility may be advantageous. It might be
useful to identify not one but a range of possible solutions that could meet a
particular reservation goal. In the following section, we describe an alternative
approach to some of these problems.
Simulated Annealing Solutions: A Comparison
Simulated annealing is a minimization method based on the process of annealing
metals and glass (Metropolis et al. 1953; Kirkpatrick et al. 1983). It begins by
generating a completely random reserve system. Next, it iteratively explores trial
solutions by making sequential random changes to this system. Either a randomly
selected site, not yet included in the reserve system, is selected, or a site already in
the system is deleted. At each step, the new solution is compared with the previous
solution, and the best one is accepted. The advantage of this approach is that
potentially it can avoid getting trapped in local optima. It allows the reserve
system to move temporarily through suboptimal solution space and thus increases
the number of routes by which the global minimum might be reached. Initially,
any change to the system is accepted, whether it increases or decreases the value
of the system. As time progresses, the algorithm is more and more choosy about
which changes it accepts, rejecting those changes that would increase the value of
the system by too large an amount. By the end of a simulated annealing run, only
changes that improve (i.e., decrease) the value of the system are accepted. At this
point, the system soon reaches a local minimum. To reiterate, the central idea
behind simulated annealing is that, by allowing bad changes as well as good, local
minima are avoided.
The simulated annealing method works as follows:
1. Set input parameters and the maximum number of iterations.
2. Generate an initial reserve system consisting of sites selected at random, and
compute objective function.
3. Randomly select a site to add to or delete from the system.
4. Evaluate the resulting change in the objective function: if e (
−change
acceptance level
) <
random number, then accept the change, otherwise reject it.
5. Decrease the acceptance level, and repeat steps 3–5 for the given number of
iterations.