- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Evolution programs, simulated annealing and hill climbing...
Open Collections
UBC Theses and Dissertations
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 Metadata
Title |
Evolution programs, simulated annealing and hill climbing applied to harvest scheduling problems
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
1995
|
Description |
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.
|
Extent |
2540501 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-01-10
|
Provider |
Vancouver : University of British Columbia Library
|
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.
|
DOI |
10.14288/1.0075216
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
1995-05
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
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.