"Forestry, Faculty of"@en . "DSpace"@en . "UBCV"@en . "Liu, Guoliang"@en . "2009-01-10T01:13:14Z"@en . "1995"@en . "Master of Forestry - MF"@en . "University of British Columbia"@en . "To protect non-timber resources such as wildlife, water quality and \r\naesthetics, harvesting regulations have been introduced that limit opening size, \r\nand set minimum green-up times. Many constraints have been introduced to \r\nlong-term, multiple-use forest planning problems. Proper scheduling of cut \r\nblocks for the large-scale integrated forest planning is important in order to \r\nproduce the maximum amount of timber from the land base without violating \r\nthe constraints. Also, these problems are difficult to solve due to the problem \r\nsize and the constraint structure. These non-linear combinatorial optimization \r\nproblems are difficult and even impossible to solve to optimality with present-\r\nday computers. \r\n\r\nIn this thesis, three models based on evolution programs, simulated \r\nannealing and hill climbing were developed with C and C++ for solving forest \r\nplanning problems. Both evolution programs an d simulated annealing are \r\nprobabilistic 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. \r\n\r\nThis is the first time that simulated annealing theory is used on a problem-\r\nspecific gene recombination operator working on individual chromosomes. It is \r\nbelieved 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."@en . "https://circle.library.ubc.ca/rest/handle/2429/3525?expand=metadata"@en . "2540501 bytes"@en . "application/pdf"@en . "EVOLUTION PROGRAMS, SIMULATED ANNEALING AND HILL CLIMBING APPLIED TO HARVEST SCHEDULING PROBLEMS by G U O L I A N G LIU B. Sc. Mechanical Engineering Northeast Forestry University of China, 1985 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF FORESTRY in THE FACULTY OF GRADUATE STUDIES FOREST RESOURCES MANAGEMENT We accept this thesis as confirming tojhe required^stajadard THE UNIVERSITY OF BRITISH COLUMBIA Jan., 1995 \u00C2\u00A9 Guoliang L i u , 1995 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of forest Res&twcM lAcwa^zmmi. The University of British Columbia Vancouver, Canada Date Jan, II. <=90, all adjacent blocks at least 20 years of age). From Figure 3.1 and Table 3.1, only blocks 4, 9, 10 and 12 are eligible for position 1. We then randomly assign one of these blocks (say 12) to position 1. At this point, the age of block 12 is set to zero, and its neighbours are excluded due to the green-up requirement Next, position 2 is filled in a similar manner. The process continues until no more blocks are eligible for the first partition. At this point, gene positions in the subsequent partitions are filled using the same procedure. The second partition represents the second period, which begins 20 years (green-up time) after the first period. Spacing the periods by green-up time ensures that no blocks are excluded from harvest due to period 1 green-up requirements. This procedure is repeated for periods 3 and 4. Partitions need not be of equal length, and in fact they frequently change length during subsequent genetic operations. All blocks that could not be cut 26 in any of the partitions are appended to the end of the chromosome (residual partition). 3.3 Solution Evaluation To evaluate the chromosomes (the harvesting schedule), additional block attributes (Table 3.1, Figure 3.2) are used to calculate the timber volume produced from each block, the road construction costs, the transportation costs, total volume, and the total profit for this solution. The roads are treated as attributes of the blocks, eliminating the need for a large road network data base. This method requires that only the block harvest schedule needs to be represented on the chromosome, and it allows for rapid calculation of objective function value. 3.4 Genetic Operations There are three genetic operators available; 1) new population selection, 2) crossover, and 3) an operator between partitions which is named the \" pushing'' operator. These operators are described in more detail in the following sections. 27 3 . 4 . 1 New P o p u l a t i o n S e l e c t i o n T h e b a s i c s t e p s i n n e w p o p u l a t i o n s e l e c t i o n a r e : 1 ) c a l c u l a t e t h e p r o b a b i l i t y o f s e l e c t i o n f o r e a c h s o l u t i o n b a s e d o n i t s f i t n e s s , 2 ) c a l c u l a t e t h e c u m u l a t i v e p r o b a b i l i t y d i s t r i b u t i o n f o r t h e s o l u t i o n s , 3 ) g e n e r a t e a p o p u l a t i o n o f r a n d o m n u m b e r s o n t h e i n t e r v a l [ 0 - 1 ] a n d 4 ) s e l e c t s o l u t i o n s f o r t h e n e w p o p u l a t i o n b y m a t c h i n g t h e r a n d o m n u m b e r s w i t h t h e c u m u l a t i v e p r o b a b i l i t y d i s t r i b u t i o n . T h i s p r o c e d u r e i s b e s t i l l u s t r a t e d u s i n g a n e x a m p l e w i t h a p o p u l a t i o n o f 4 c h r o m o s o m e s . T a b l e 3 . 2 N e w p o p u l a t i o n s e l e c t i o n m e t h o d d e m o n s t r a t e d w i t h a n e x a m p l e o f f o u r s o l u t i o n s i n t h e p o p u l a t i o n . S o l u t i o n s i n C u r r e n t P o p u l a t i o n F i t n e s s o f P a r e n t P r o b a b i l i t y o f S e l e c t i o n C u m u l a t i v e P r o b a b i l i t y R a n g e R a n d o m N u m b e r [ 0 , 1 ] S o l u t i o n s i n N e w P o p u l a t i o n 1 1 0 0 . 1 0 . 0 0 - 0 . 1 0 0 . 3 5 3 2 2 0 0 . 2 0 . 1 1 - 0 . 3 0 0 . 8 8 4 3 4 0 0 . 4 0 . 3 1 - 0 . 7 0 0 . 6 7 3 4 3 0 0 . 3 0 . 7 1 - 1 . 0 0 0 . 2 5 2 T o t a l 1 0 0 T h e t o t a l f i t n e s s o f t h e f o u r c h r o m o s o m e s i n t h i s e x a m p l e i s 1 0 0 . T h e p r o b a b i l i t y o f s e l e c t i n g e a c h c h r o m o s o m e i s b a s e d o n i t s f i t n e s s r e l a t i v e t o t h e t o t a l f i t n e s s o f a l l s o l u t i o n s . T h e s e p r o b a b i l i t i e s c a n t h e n b e r e p r e s e n t e d a s a c u m u l a t i v e p r o b a b i l i t y d i s t r i b u t i o n . F o u r r a n d o m n u m b e r s i n t h e i n t e r v a l [ 0 - 1 ] a r e t h e n 28 g e n e r a t e d , a n d e a c h t i m e a s i n g l e c h r o m o s o m e i s s e l e c t e d f o r t h e n e w p o p u l a t i o n . T h e f i r s t n u m b e r , 0 . 3 5 , f a l l s i n t h e c u m u l a t i v e p r o b a b i l i t y d i s t r i b u t i o n r a n g e f o r s o l u t i o n 3 . T h e s e c o n d n u m b e r , 0 . 8 8 , f a l l s i n t h e r a n g e f o r s o l u t i o n 4 . C o n t i n u i n g t h r o u g h t h e r e m a i n i n g r a n d o m n u m b e r s r e s u l t s i n t h e n e w p o p u l a t i o n w i t h t h e f o l l o w i n g s o l u t i o n s : 3 , 4 , 3 , 2 . T h i s m e t h o d i s r e f e r r e d t o a s f i t n e s s - p r o p o r t i o n a t e n e w p o p u l a t i o n s e l e c t i o n , a n d i t i s d e s i g n e d t o p r o m o t e t h e s u r v i v a l o f t h e f i t t e s t N o t e i n t h e a b o v e e x a m p l e t h a t s o l u t i o n 1 , w i t h t h e l o w e s t f i t n e s s , i s n o t i n t h e n e w p o p u l a t i o n ( i t d i e d ) . T h e n e w p o p u l a t i o n c o n t a i n s o n l y s o l u t i o n s 2 , 3 , a n d 4 , w i t h s o l u t i o n 3 a p p e a r i n g t w i c e , t h u s g i v i n g t h e s o l u t i o n s w i t h t h e h i g h e s t f i t n e s s t h e g r e a t e s t o p p o r t u n i t y t o c o n t r i b u t e t o f u t u r e g e n e r a t i o n s . 3.4.2 C r o s s o v e r , R e p a i r a n d G r e e d y P u s h i n g S o m e p a r e n t c h r o m o s o m e s a r e t h e n r a n d o m l y m a t e d t o e x c h a n g e g e n e t i c m a t e r i a l . W h e n u s i n g c r o s s o v e r , f i r s t , d e c i d e h o w m a n y c o u p l e s w i l l u n d e r g o c r o s s o v e r . I f t h e p o p u l a t i o n s i z e i s 3 0 a n d t h e c r o s s o v e r r a t e = 0 . 1 4 , t h e n 4 . 2 ( 3 0 * 0 . 1 4 ) o r 4 c o u p l e s ( 8 c h r o m o s o m e s ) w i l l u n d e r g o c r o s s o v e r f o r t h i s g e n e r a t i o n . T h e c r o s s o v e r o f e a c h c o u p l e c a n b e d e s c r i b e d a s f o l l o w s : R a n d o m l y s e l e c t 2 p a r e n t c h r o m o s o m e s a n d r a n d o m l y e x c h a n g e s o m e m a t e r i a l . T h e p r o b l e m s p e c i f i c k n o w l e d g e i n t h i s o p e r a t o r i s t h a t t h e m a t e r i a l h a s b e e n e x c h a n g e d b e t w e e n t h e s a m e p a r t i t i o n s o f t h e t w o p a r e n t c h r o m o s o m e s i n o r d e r t o 29 easily follow the minimum harvesting age constraint However, this operator can violate the adjacency constraints, and the chromosomes must be fixed. A \"greedy repair\" is used to push as many high volume or high profit blocks as possible to the earlier periods. After the crossover operation, replace the two parents in the population with the two offspring. I present the process in detail using the sample forest Chromosome 1 and chromosome 2 are selected for crossover. There are 6 steps in the crossover procedure. Chromosome 1 Partition No. 1 2 3 4 Residual Blocks (Gene) 1 2 9 4 1 0 7 6 3 1 1 2 8 5 1 Chromosome 2 Partition No. 1 2 3 4 Residual Blocks (Gene) 1 0 4 5 1 1 6 1 2 9 3 7 2 1 8 Step 1 . Randomly identify the partition number for crossover by generating a random number among { 1 , 2 , 3 , 4 } . Let the number be 3 in this example. Step 2a. Randomly identify the crossover edge on partition 3 of chromosome 1 . There are 2 edges ( 6 - 3 and 3 - 11) on partition 3 of chromosome 1 , so a random number among { 1 , 2 } is generated. For this example, let the number be 2, in which case, the crossover edge is the second edge, between block 3 and 11. Step 2b. Randomly identify the crossover edge on partition 3 of chromosome 2. There are 3 edges ( 6 - 12 , 1 2 - 9 and 9 - 3 ) on partition 3 of chromosome 2, so a 30 random number among {1, 2, 3} is generated. For this example, the number is 1, so, that means the crossover edge is the first edge, between blocks 6 and 12. The section after the crossover edge in partition 3 of chromosome 1 is named section X, and the section after the crossover edge in partition 3 of chromosome 2 is named section Y. Chromosome 1 Partition No. 1 2 3 4 Residual Blocks (Gene) 12 9 4 10 7 6 3 1100 2 8 5 1 Chromosome 2 Partition No. 1 2 3 4 Residual Blocks (Gene) 10 4 5 11 6 12 9 3m 7 2 1 8 Step 3, Merge section X and section Y and try to keep X and Y in partition 3 of both chromosome 1 and chromosome 2. Chromosome 1 Partition No. 1 2 3 4 Residual Blocks (Gene) 12 9 4 10 7 6 3 1100 12 9 3(Y) 2 8 5 1 Chromosome 2 Partition No. 1 2 3 4 Residual Blocks (Gene) 10 4 5 11 6 12 9 3(Y) 11(X) 7 2 1 8 Step 3a. Keep section Y in partition 3 of chromosome 1 and check section X of partition 3 on chromosome 1. Block 11 can not stay in partition 3 because it is adjacent to blocks 12 and 9, so move 11 to the residual partition residual of chromosome 1. 31 Step 3b. Keep section X on partition 3 of chromosome 2 and check section Y on chromosome 2. Blocks 9 and 1 2 can not stay in partition 3 of chromosome 2 because they are adjacent to block 11, so move them to the residual partition 2. Chromosome 1 Partition No. 1 2 3 4 Residual Blocks (Gene) 1 2 9 4 1 0 7 6 3 1 2 9 3m 2 8 5 1 1 1 Chromosome 2 Partition No. 1 2 3 4 Residual Blocks (Gene) 1 0 4 5 1 1 6 3 ( Y ) 1 1 0 0 7 2 1 1 2 9 8 Step 4. Keep sections X and Y, and remove any duplicate blocks resulting from the partition 3 crossover. Chromosome 1 Partition No. 1 2 3 4 Residual Blocks (Gene) 4 1 0 7 6 1 2 9 3m 2 8 5 1 1 1 Chromosome 2 Partition No. 1 2 3 4 Residual Blocks (Gene) 1 0 4 5 6 3m nrx) 7 2 1 1 2 9 8 Step 5. Cleaning these two chromosomes, we get Chromosome 1 Partition No. 1 2 3 4 Residual Blocks (Gene) 4 1 0 7 6 1 2 9 3 2 8 5 1 1 1 Chromosome 2 Partition No. 1 2 3 4 Residual Blocks (Gene) 1 0 4 5 6 3 1 1 7 2 1 1 2 9 8 32 S t e p 6 . P u s h e v e r y e l i g i b l e b l o c k t o t h e e a r l i e r p a r t i t i o n s o n t h e s e t w o c h r o m o s o m e s . S t e p 6 a . P u s h c h r o m o s o m e 1 : C h r o m o s o m e 1 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 4 1 0 7 6 1 2 9 3 2 8 5 1 1 1 S t e p 6 a . 1 . P u s h e v e r y e l i g i b l e b l o c k ( a g e > = 9 0 a n d a g e s o f a d j a c e n c y > = 2 0 ) f r o m p a r t i t i o n 2 , 3 , 4 a n d t h e r e s i d u a l t o p a r t i t i o n 1 . B l o c k s 4 , 1 0 a n d 1 2 g o t o p a r t i t i o n 1 f r o m p a r t i t i o n 2 a n d 3 . C h r o m o s o m e 1 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 4 1 2 1 0 7 6 9 3 2 8 5 1 1 1 S t e p 6 a . 2 . P u s h e v e r y e l i g i b l e b l o c k f r o m p a r t i t i o n 3 , 4 a n d t h e r e s i d u a l p a r t i t i o n t o p a r t i t i o n 2 . B l o c k s 9 a n d 3 g o t o p a r t i t i o n 2 . C h r o m o s o m e 1 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 4 1 2 1 0 9 3 7 6 2 8 5 1 1 1 S t e p 6 a . 3 . P u s h e v e r y e l i g i b l e b l o c k f r o m p a r t i t i o n 4 a n d t h e r e s i d u a l p a r t i t i o n t o p a r t i t i o n 3 . B l o c k 1 1 g o e s t o p a r t i t i o n 3 f r o m t h e r e s i d u a l p a r t i t i o n . C h r o m o s o m e 1 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 4 1 2 1 0 9 3 7 6 1 1 2 8 5 1 S t e p 6 a . 4 . P u s h e v e r y e l i g i b l e b l o c k f r o m t h e r e s i d u a l p a r t i t i o n t o p a r t i t i o n 4 . N o b l o c k s a r e e l i g i b l e , a n d t h i s t e r m i n a t e s t h e p u s h i n g o p e r a t i o n f o r c h r o m o s o m e 1 . 33 S t e p 6 b . P u s h c h r o m o s o m e 2 : C h r o m o s o m e 2 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 1 0 4 5 6 3 1 1 7 2 1 1 2 9 8 S t e p 6 b . 1 . P u s h e v e r y e l i g i b l e b l o c k ( a g e > = 9 0 a n d a g e s o f a d j a c e n c y > = 2 0 ) f r o m p a r t i t i o n 2 , 3 , 4 a n d t h e r e s i d u a l p a r t i t i o n t o p a r t i t i o n 1 . N o b l o c k s a r e e l i g i b l e . C h r o m o s o m e 2 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 1 0 4 5 6 3 1 1 7 2 1 1 2 9 8 S t e p 6 b . 2 . P u s h e v e r y e l i g i b l e b l o c k f r o m p a r t i t i o n 3 , 4 a n d t h e r e s i d u a l p a r t i t i o n t o p a r t i t i o n 2 . B l o c k 1 1 g o e s t o p a r t i t i o n 2 . C h r o m o s o m e 2 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( g e n e ) 1 0 4 5 1 1 6 3 7 2 1 1 2 9 8 S t e p 6 b . 3 . P u s h e v e r y e l i g i b l e b l o c k f r o m p a r t i t i o n 4 a n d t h e r e s i d u a l p a r t i t i o n t o p a r t i t i o n 3 . B l o c k 1 1 g o e s t o p a r t i t i o n 3 f r o m t h e r e s i d u a l p a r t i t i o n . C h r o m o s o m e 2 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 1 0 4 5 1 1 6 1 2 9 3 7 2 1 8 S t e p 6 b . 4 . P u s h e v e r y e l i g i b l e b l o c k f r o m t h e r e s i d u a l p a r t i t i o n t o p a r t i t i o n 4 . N o b l o c k s a r e e l i g i b l e , a n d t h e p u s h i n g o p e r a t i o n i s t e r m i n a t e d f o r c h r o m o s o m e 2 . 34 T h e r e s u l t i n g o f f s p r i n g a r e : C h r o m o s o m e 1 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 4 1 2 1 0 9 3 7 6 1 1 2 8 5 1 C h r o m o s o m e 2 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 1 0 4 5 1 1 6 1 2 9 3 7 2 1 8 T h e s e t w o o f f s p r i n g a l w a y s r e p l a c e t h e i r p a r e n t s ( s h o w n b e l o w ) i n t h e p o p u l a t i o n : C h r o m o s o m e 1 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 1 2 9 4 1 0 7 6 3 1 1 2 8 5 1 C h r o m o s o m e 2 P a r t i t i o n N o . 1 2 3 4 R e s i d u a l B l o c k s ( G e n e ) 1 0 4 5 1 1 6 1 2 9 3 7 2 1 8 C o m p a r i n g t h e p a r e n t c h r o m o s o m e s t o t h e o f f s p r i n g , c h r o m o s o m e 1 h a s c h a n g e d a l o t , h o w e v e r , t h e o f f s p r i n g o f c h r o m o s o m e 2 i s i d e n t i c a l t o i t s p a r e n t c h r o m o s o m e . T h e s a m p l e p r o b l e m i s v e r y s m a l l , s o i t i s n o t u n u s u a l t o s e e i d e n t i c a l s o l u t i o n s o c c u r r i n g . W i t h l a r g e r p r o b l e m s , t h i s r e p l i c a t i o n i s l e s s l i k e l y t o o c c u r . 3 . 4 . 3 P u s h i n g O p e r a t i o n o n I n d i v i d u a l C h r o m o s o m e s T h i s o p e r a t o r , l i k e t h e g r e e d y r e p a i r o p e r a t o r u s e d f o l l o w i n g t h e c r o s s o v e r , f o l l o w s t h e a d j a c e n c y r u l e s , m a i n t a i n s s o l u t i o n f e a s i b i l i t y , a n d t r i e s t o p u s h b l o c k s t o t h e e a r l i e r p e r i o d s . B e f o r e t h e p u s h i n g o p e r a t i o n , i t m u s t b e d e c i d e d h o w m a n y c h r o m o s o m e s w i l l u n d e r g o t h i s o p e r a t i o n . F o r e x a m p l e , w i t h a p o p u l a t i o n o f 3 0 , a c h r o m o s o m e l e n g t h o f 4 3 1 a n d a p u s h i n g r a t e o f 0 . 0 5 % , ( 3 0 * 4 3 1 * 0 . 0 5 % = 6 ) g e n e s 35 will undergo the pushing operation. The pushing operation of each chromosome uses the following 3-step procedure: Step 1. Randomly identify a partition (named A) which will receive one new block from a later period (a higher numbered partition). Step 2. Randomly identify a partition (named B) which will provide the block to partition A. Now randomly select one of the eligible blocks in partition B, and randomly insert it in partition A. This move can violate adjacency constraints which requires chromosome repair. A \"greedy repair\" is used to satisfy the constraints, and to push as many high volume blocks as possible to early periods. Step 3. Evaluate the new solution and decide whether it is accepted or rejected. Note how solutions must pass this acceptance test, unlike crossover where children always replace their parents in the population. Simulated annealing theory is used to control the acceptance probability for this pushing operation. This is a new point I found in my studies. The probability acceptance equation derived for this study is: P = l forE 2^E 1 , p = e r f2(N) forE2 "Thesis/Dissertation"@en . "1995-05"@en . "10.14288/1.0075216"@en . "eng"@en . "Forestry"@en . "Vancouver : University of British Columbia Library"@en . "University of British Columbia"@en . "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."@en . "Graduate"@en . "Evolution programs, simulated annealing and hill climbing applied to harvest scheduling problems"@en . "Text"@en . "http://hdl.handle.net/2429/3525"@en .