UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Evolution programs, simulated annealing and hill climbing applied to harvest scheduling problems Liu, Guoliang

Abstract

To protect non-timber resources such as wildlife, water quality and aesthetics, harvesting regulations have been introduced that limit opening size, and set minimum green-up times. Many constraints have been introduced to long-term, multiple-use forest planning problems. Proper scheduling of cut blocks for the large-scale integrated forest planning is important in order to produce the maximum amount of timber from the land base without violating the constraints. Also, these problems are difficult to solve due to the problem size and the constraint structure. These non-linear combinatorial optimization problems are difficult and even impossible to solve to optimality with present- day computers. In this thesis, three models based on evolution programs, simulated annealing and hill climbing were developed with C and C++ for solving forest planning problems. Both evolution programs an d simulated annealing are probabilistic algorithms that will accept inferior moves within the search space as a means of searching out global optima. They differ from hill climbing algorithms that only accept superior solutions, and often stall at local optima. Evolution programs simultaneously work with a population of solutions, while simulated annealing is a specific case where the population size is reduced to one. Evolution programs and simulated annealing are applicable to a broad range of problems for which very little prior knowledge is available. However, many opportunities exist for improving the performance of these algorithms by incorporating problem specific knowledge and heuristics. This is the first time that simulated annealing theory is used on a problem- specific gene recombination operator working on individual chromosomes. It is believed that the evolution programs can be applied to many more problems. It was found that all solutions generated by all these methods were within 3.12% of the best solution found. All the solutions found by simulated annealing are within 1.00%; evolution programs, 2.54% and hill climbing, 3.12% of this best solution. However, simulated annealing converged much faster on the optimum than did the evolution program. Using a 486/50 MHz computer, the evolution program took 378 minutes with a population of 30 chromosomes, 431 harvest blocks and 10,000 generations. Simulated annealing took only 36.8 minutes, while hill climbing took 32.7 minutes on the same problem.

Item Media

Item Citations and Data

Rights

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.