Open Collections

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 1995

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_1995-0073.pdf [ 2.42MB ]
Metadata
JSON: 831-1.0075216.json
JSON-LD: 831-1.0075216-ld.json
RDF/XML (Pretty): 831-1.0075216-rdf.xml
RDF/JSON: 831-1.0075216-rdf.json
Turtle: 831-1.0075216-turtle.txt
N-Triples: 831-1.0075216-rdf-ntriples.txt
Original Record: 831-1.0075216-source.json
Full Text
831-1.0075216-fulltext.txt
Citation
831-1.0075216.ris

Full Text

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 © 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. <<?9£-DE-6 (2/88) 11 Abstract T o p r o t e c t n o n - t i m b e r r e s o u r c e s s u c h a s w i l d l i f e , w a t e r q u a l i t y a n d a e s t h e t i c s , h a r v e s t i n g r e g u l a t i o n s h a v e b e e n i n t r o d u c e d t h a t l i m i t o p e n i n g s i z e , a n d s e t m i n i m u m g r e e n - u p t i m e s . M a n y c o n s t r a i n t s h a v e b e e n i n t r o d u c e d t o l o n g - t e r m , m u l t i p l e - u s e f o r e s t p l a n n i n g p r o b l e m s . P r o p e r s c h e d u l i n g o f c u t b l o c k s f o r t h e l a r g e - s c a l e i n t e g r a t e d f o r e s t p l a n n i n g i s i m p o r t a n t i n o r d e r t o p r o d u c e t h e m a x i m u m a m o u n t o f t i m b e r f r o m t h e l a n d b a s e w i t h o u t v i o l a t i n g t h e c o n s t r a i n t s . A l s o , t h e s e p r o b l e m s a r e d i f f i c u l t t o s o l v e d u e t o t h e p r o b l e m s i z e a n d t h e c o n s t r a i n t s t r u c t u r e . T h e s e n o n - l i n e a r c o m b i n a t o r i a l o p t i m i z a t i o n p r o b l e m s a r e d i f f i c u l t a n d e v e n i m p o s s i b l e t o s o l v e t o o p t i m a l i t y w i t h p r e s e n t -d a y c o m p u t e r s . I n t h i s t h e s i s , t h r e e m o d e l s b a s e d o n e v o l u t i o n p r o g r a m s , s i m u l a t e d a n n e a l i n g a n d h i l l c l i m b i n g w e r e d e v e l o p e d w i t h C a n d C + + f o r s o l v i n g f o r e s t p l a n n i n g p r o b l e m s . B o t h e v o l u t i o n p r o g r a m s a n d s i m u l a t e d a n n e a l i n g a r e p r o b a b i l i s t i c a l g o r i t h m s t h a t w i l l a c c e p t i n f e r i o r m o v e s w i t h i n t h e s e a r c h s p a c e a s a m e a n s o f s e a r c h i n g o u t g l o b a l o p t i m a . T h e y d i f f e r f r o m h i l l c l i m b i n g a l g o r i t h m s t h a t o n l y a c c e p t s u p e r i o r s o l u t i o n s , a n d o f t e n s t a l l a t l o c a l o p t i m a . E v o l u t i o n p r o g r a m s s i m u l t a n e o u s l y w o r k w i t h a p o p u l a t i o n o f s o l u t i o n s , w h i l e s i m u l a t e d a n n e a l i n g i s a s p e c i f i c c a s e w h e r e t h e p o p u l a t i o n s i z e i s r e d u c e d t o o n e . E v o l u t i o n p r o g r a m s a n d s i m u l a t e d a n n e a l i n g a r e a p p l i c a b l e t o a b r o a d r a n g e o f p r o b l e m s f o r w h i c h v e r y l i t t l e p r i o r k n o w l e d g e i s a v a i l a b l e . H o w e v e r , m a n y o p p o r t u n i t i e s e x i s t f o r Ill i m p r o v i n g t h e p e r f o r m a n c e o f t h e s e a l g o r i t h m s b y i n c o r p o r a t i n g p r o b l e m s p e c i f i c k n o w l e d g e a n d h e u r i s t i c s . T h i s i s t h e f i r s t t i m e t h a t s i m u l a t e d a n n e a l i n g t h e o r y i s u s e d o n a p r o b l e m -s p e c i f i c g e n e r e c o m b i n a t i o n o p e r a t o r w o r k i n g o n i n d i v i d u a l c h r o m o s o m e s . I t i s b e l i e v e d t h a t t h e e v o l u t i o n p r o g r a m s c a n b e a p p l i e d t o m a n y m o r e p r o b l e m s . I t w a s f o u n d t h a t a l l s o l u t i o n s g e n e r a t e d b y a l l t h e s e m e t h o d s w e r e w i t h i n 3 . 1 2 % o f t h e b e s t s o l u t i o n f o u n d . A l l t h e s o l u t i o n s f o u n d b y s i m u l a t e d a n n e a l i n g a r e w i t h i n 1 . 0 0 % ; e v o l u t i o n p r o g r a m s , 2 . 5 4 % a n d h i l l c l i m b i n g , 3 . 1 2 % o f t h i s b e s t s o l u t i o n . H o w e v e r , s i m u l a t e d a n n e a l i n g c o n v e r g e d m u c h f a s t e r o n t h e o p t i m u m t h a n d i d t h e e v o l u t i o n p r o g r a m . U s i n g a 4 8 6 / 5 0 M H z c o m p u t e r , t h e e v o l u t i o n p r o g r a m t o o k 3 7 8 m i n u t e s w i t h a p o p u l a t i o n o f 3 0 c h r o m o s o m e s , 4 3 1 h a r v e s t b l o c k s a n d 1 0 , 0 0 0 g e n e r a t i o n s . S i m u l a t e d a n n e a l i n g t o o k o n l y 3 6 . 8 m i n u t e s , w h i l e h i l l c l i m b i n g t o o k 3 2 . 7 m i n u t e s o n t h e s a m e p r o b l e m . iv T A B L E O F C O N T E N T S A b s t r a c t i i T a b l e o f C o n t e n t s i v L i s t o f T a b l e s v i L i s t o f F i g u r e s • v i i A c k n o w l e d g e m e n t s v i i i C h a p t e r 1 . I n t r o d u c t i o n 1 1 . 1 G e n e r a l I n t r o d u c t i o n 1 1 . 2 I n t r o d u c t i o n t o E v o l u t i o n P r o g r a m s 3 C h a p t e r 2 . R e v i e w o f L i t e r a t u r e 9 2 . 1 M i x e d I n t e g e r P r o g r a m m i n g 1 0 2 . 2 H e u r i s t i c A p p r o a c h e s 1 3 2 . 3 I n t e r c h a n g e 1 5 2 . 4 S i m u l a t e d A n n e a l i n g 1 6 2 . 5 T a b u S e a r c h 1 7 2 . 6 G e n e t i c A l g o r i t h m s 1 8 C h a p t e r 3 . E x p l a n a t i o n o f E v o l u t i o n P r o g r a m s u s i n g a S a m p l e F o r e s t P l a i u i i n g P r o b l e m 2 0 3 . 1 S o l u t i o n R e p r e s e n t a t i o n 2 1 3 . 2 G r e e d y S o l u t i o n I n i t i a l i s a t i o n 2 5 3 . 3 S o l u t i o n E v a l u a t i o n 2 6 3 . 4 G e n e t i c O p e r a t i o n s 2 6 3 . 4 . 1 N e w P o p u l a t i o n S e l e c t i o n 2 7 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 2 8 3 . 4 . 3 P u s h i n g O p e r a t i o n o n S o m e I n d i v i d u a l C h r o m o s o m e s 3 4 C h a p t e r 4 . M o d i f i c a t i o n s f o r S i m u l a t e d A n n e a l i n g a n d H i l l C l i m b i n g 3 9 4 . 1 M o d i f i c a t i o n f o r S i m u l a t e d A n n e a l i n g 3 9 4 . 2 M o d i f i c a t i o n f o r H i l l C l i m b i n g 4 0 C h a p t e r 5 . T e s t o f t h e M o d e l s , R e s u l t s a n d D i s c u s s i o n s 4 2 C h a p t e r 6 . C o n c l u s i o n s a n d R e c o m m e n d a t i o n s 5 1 6 . 1 C o n c l u s i o n s 5 1 6 . 2 R e c o m m e n d a t i o n s f o r F u t u r e R e s e a r c h 5 2 L i t e r a t u r e C i t e d 5 5 v i List of Tables 3 . 1 B l o c k a t t r i b u t e s f o r t h e s a m p l e f o r e s t 2 4 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 2 7 3 . 3 R e s u l t s o f a s a m p l e c a l c u l a t i o n o f t h e a c c e p t a n c e p r o b a b i l i t y 3 8 5 . 1 E v o l u t i o n p r o g r a m p a r a m e t e r s f o r t h e H a r d w i c k I s l a n d p r o b l e m 4 2 5 . 2 M e a n v a l u e o f t h e o b j e c t i v e f u n c t i o n f o r 2 0 s o l u t i o n s g e n e r a t e d w i t h t h e e v o l u t i o n p r o g r a m , s i m u l a t e d a n n e a l i n g a n d h i l l d i m b i n g f o r t h e H a r d w i c k I s l a n d p r o b l e m 4 3 5 . 3 C o m p u t i n g t i m e f o r t h e e v o l u t i o n p r o g r a m , s i m u l a t e d a n n e a l i n g , a n d h i l l c l i m b i n g 4 4 5 . 4 . a C o m p a r i s o n o f s i m u l a t e d a n n e a l i n g a n d A T L A S f o r H a r d w i c k I s l a n d w h e n n o e v e n f l o w c o n s t r a i n t s a r e a p p l i e d ( 5 p l a n n i n g p e r i o d s ) 4 6 5 . 4 . b C o m p a r i s o n o f A T L A S a n d s i m u l a t e d a n n e a l i n g w h e n t h e i n i t i a l a g e o f a l l s t a n d s i s 9 0 y e a r s . S o l u t i o n s w i t h a n d w i t h o u t e v e n f l o w c o n s t r a i n t s a r e p r e s e n t e d ( 5 p l a n n i n g p e r i o d s ) 4 7 5 . 4 . c C o m p a r i s o n o f A T L A S a n d s i m u l a t e d a n n e a l i n g w h e n 4 p l a n n i n g p e r i o d s a r e u s e d . S o l u t i o n s w i t h a n d w i t h o u t e v e n f l o w c o n s t r a i n t s a r e s h o w n 4 8 List of Figures 3 . 1 A s a m p l e f o r e s t w i t h 1 2 b l o c k s 2 3 3 . 2 V o l u m e ( m 3 / h a ) g r o w t h a g a i n s t a g e c u r v e 2 3 3 . 3 B l o c k h a r v e s t s c h e d u l e f o r t h e s a m p l e f o r e s t r e p r e s e n t e d b y b l o c k s p l a c e d i n g e n e p o s i t i o n s o n a c h r o m o s o m e 2 4 3 . 4 T h e a c c e p t a n c e p r o b a b i l i t y f u n c t i o n P v a r i e s w i t h t h e i t e r a t i o n n u m b e r a n d t h e p e r c e n t a g e o f f i t n e s s d e c r e a s e d 3 6 5 . 1 T w e n t y s o l u t i o n s f o r t h e H a r d w i c k I s l a n d p r o b l e m g e n e r a t e d w i t h t h e e v o l u t i o n p r o g r a m , s i m u l a t e d a n n e a l i n g , a n d h i l l d i m b i n g 4 4 5 . 2 P e r f o r m a n c e o f t h e e v o l u t i o n p r o g r a m , s i m u l a t e d a n n e a l i n g , a n d h i l l c l i m b i n g 4 5 Vl l l Acknowledgment F i r s t I w o u l d l i k e t o t h a n k m y s u p e r v i s o r D r . J o h n N e l s o n , b e c a u s e i t w a s h e w h o l e d m e i n t o t h i s f i e l d . A b o u t a y e a r a g o , w h e n I s t a r t e d m y m a s t e r ' s p r o g r a m , I k n e w n o t h i n g a b o u t e v o l u t i o n p r o g r a m s , g e n e t i c a l g o r i t h m s a n d s i m u l a t e d a n n e a l i n g ; I k n e w n o t b i n g a b o u t C a n d C + + . I f i r s t l e a r n e d a b o u t C a n d C + + , a n d t h e n a b o u t g e n e t i c a l g o r i t h m s , e v o l u t i o n p r o g r a m s a n d s i m u l a t e d a n n e a l i n g u n d e r h i s g u i d a n c e . S e c o n d I l i k e t o t h a n k p r o f e s s o r G l e n Y o u n g f o r h i s m a n y v a l u a b l e s u g g e s t i o n s . I a p p r e c i a t e t h e i r p a t i e n c e i n a n s w e r i n g m y q u e s t i o n s a n d I h a v e n o d i f f i c u l t y i n a s k i n g t h e m q u e s t i o n s . F i n a l l y , I l i k e t o t h a n k D r . T o m M a n e s s f o r h i s m a n y g o o d s u g g e s t i o n s . F r o m t h e g r o w t h o f m y k n o w l e d g e , I h a v e c o m e t o r e a l i s e t h a t U B C i s o n e o f t h e b e s t u n i v e r s i t i e s i n t h e w o r l d . T h e p r o f e s s o r s l e a d t h e f i e l d i n t h e w o r l d ; t h e s t u d e n t s h a v e t h e b e s t c o m p u t e r s a n d s o f t w a r e i n t h e w o r l d ; a l s o , t h e p r o f e s s o r s a n d s t u d e n t s h a v e v e r y g o o d r e l a t i o n s h i p s . W i t h o u t t h e s e f a c t o r s , I c o u l d n o t h a v e l e a r n e d s o m u c h i n s o s h o r t t i m e . 1 Chapter 1 Introduction 1.1 General Introduction Modern management planning of forest lands must take numerous concerns and regulations into account before implementation of a management scheme. The purpose of these regulations is to help provide an equitable and sustainable management plan in a multiple-use forest environment. These must take into account the concerns of the timber industry, environmentalists, recreationalists, and ecosystem health. However, these regulations make forest planning very difficult, especially large-scale, long-term harvest scheduling problems. Frequently, solutions for these scheduling problems are beyond the limitations of current computing resources and techniques. There has been a number of different approaches used to solve these problems, however, no one particular solution approach has been generally accepted. Some random search techniques such as simulated annealing, genetic algorithms and evolution programs have been successfully applied in non-forest planning areas, such as traveling salesman problems, integrated computer circuit design, transportation network design and job scheduling. However, the application of evolution programs and genetic algorithms to forest planning has not been explored. 2 The objective of my study is to develop and test evolution programs, simulated annealing, and random hill climbing algorithms for forest planning problems. All these methods are random search techniques which start with feasible solutions and improve them gradually. Evolution programs simultaneously work with a population of solutions (chromosomes), while simulated annealing works with one solution at any given time. Unlike hill climbing, evolution programs and simulated annealing can accept inferior moves within the search space. In this study, I first present an overview of evolution programs. Then I review the literature related to forest planning problems (Chapter 2). Evolution programs are then explained using a sample forest problem (Chapter 3). Model modifications for simulated annealing and random hill climbing are then given (Chapter 4). The models are then tested on a data set from Hardwick Island on the west coast of British Columbia (Chapter 5). Finally, a general discussion is provided on the advantages and disadvantages of models and their potential for future applications. 3 1.2 Introduction to Evolution Programs The idea behind evolution programs and genetic algorithms is to do what nature does. In Z. Michalewicz's book (1987), a story explains how and why evolution programs and genetic algorithms work. "At any given time there is a population of rabbits. Some of them are faster, smarter and more healthy than other rabbits. These faster, smarter and more healthy rabbits are less likely to be eaten by foxes, and therefore more of them survive to do what rabbits do best: make more rabbits. Of course, some of the slower, less intelligent and less healthy rabbits can survive just because they are lucky. This surviving population of rabbits starts breeding. The breeding results in a good mixture of rabbit genetic material: some slow rabbits breed with fast rabbits, some fast with fast, some smart rabbits with less intelligent rabbits, and so on. And on the top of that, nature throws in a 'wild hare' every once in a while by mutating some of the rabbit genetic material. The resulting baby rabbits will (on the average) be faster, smarter and more healthy than these in the original population because more faster and smarter parents survived the foxes. It is a good thing that the foxes are undergoing a similar process, otherwise the rabbits might become too fast and smart for the foxes to catch any of them." Evolution programs and genetic algorithms follow a step-by-step procedure that closely matches the above story, and they use vocabulary borrowed from natural genetics. During the last 3 decades, there has been a growing interest in problem solving systems based on principles of evolution and hereditary: such systems maintain a population of potential solutions, they have some selection process based on fitness of individuals, and some recombination operators. The evolution program is a probabilistic algorithm which maintains a population of individuals for each iteration. Each individual represents a potential solution to 4 the problem at hand. Each solution is evaluated to give some measure of its "fitness". Then, a new population is formed by selecting the more fit individuals. Some members of the new population undergo transformations by means of "genetic" operators to form new solutions. After some number of generations the program converges - the best individual hopefully represents the optimum solution. The two typical operators are: 1) mutation, which introduces i new information into the population, and 2) crossover, which spreads the new information through the population. The general procedure of the evolution programs is: Step 1. initialize a population of chromosomes (potential solutions); Step 2. evaluate the chromosomes (objective function); Step 3. select the more fit individuals to form a new population; Step 4. transform some members by means of "genetic" operators to form new solutions; Step 5. compare the new solutions and old solutions, and decide to accept or reject the new solutions; and Step 6. if termination conditions are met, stop, otherwise go to step 3. In evolution programming, each individual chromosome in the population represents a potential solution to the problem. The evaluation function returns the fitness of each solution, distinguishing between the better and worse individuals. Several mutation operators can be designed which will transform a 5 single solution. A few crossover operators can be considered which combine the structure of two solutions into one. Very often such operators incorporate specific knowledge from the problem. Clearly, many evolution programs can be formulated for a given problem. Such programs may differ in many ways; they can use different data structures for encoding a single individual, different "genetic" operators for transforming individuals, different methods for creating an initial population, different methods for handling constraints of the problem, and different parameters (population size, probabilities of applying different operators, etc.). However, they share a common principle: a population of individuals undergoes some transformations, and during this evolution the individuals strive for survival. Evolution programs are based entirely on the idea of genetic algorithms; the difference is that evolution programs allow any data structure (i.e., chromosome representation) to be used together with any set of "genetic" operators. Classical genetic algorithms use a fixed-length binary string for the individuals and two operators: binary mutation and binary crossover. In other words, the structure of the genetic algorithm is the same as the structure of the evolution program and the differences are hidden on a lower level. Each chromosome need not be represented by a bit-string and the recombination process includes other "genetic" operators appropriate for the given structure and given problem. This is a relatively new direction. Recently, De Jong (1988) wrote: "What should one do when elements in space to be searched are most naturally represented by more complex data structures such as arrays, trees, 6 d i a g r a m s , e t c . S h o u l d o n e a t t e m p t t o ' l i n e a r i z e ' t h e m i n t o a s t r i n g r e p r e s e n t a t i o n o r a r e t h e r e w a y s t o c r e a t i v e l y r e d e f i n e c r o s s o v e r a n d m u t a t i o n t o w o r k d i r e c t l y o n s u c h s t r u c t u r e s ? I a m u n a w a r e o f a n y p r o g r e s s i n t h i s a r e a . " A " n a t u r a l " r e p r e s e n t a t i o n o f p o t e n t i a l s o l u t i o n s f o r a g i v e n p r o b l e m p l u s a f a m i l y o f a p p l i c a b l e " g e n e t i c " o p e r a t o r s a r e q u i t e u s e f u l i n t h e a p p r o x i m a t i o n o f s o l u t i o n s o f m a n y p r o b l e m s , a n d t h i s n a t u r e - m o d e l e d a p p r o a c h ( e v o l u t i o n p r o g r a m ) i s a p r o m i s i n g d i r e c t i o n f o r p r o b l e m s o l v i n g i n g e n e r a l . C o n s t r a i n t s t h a t c a n n o t b e v i o l a t e d c a n b e i m p l e m e n t e d b y i m p o s i n g g r e a t p e n a l t i e s o n i n d i v i d u a l s t h a t v i o l a t e t h e m ( L o c k w o o d a n d M o o r e , 1 9 9 3 ) , o r b y c r e a t i n g d e c o d e r s o f t h e r e p r e s e n t a t i o n t h a t a v o i d s c r e a t i n g i n d i v i d u a l s v i o l a t i n g t h e c o n s t r a i n t ( N e l s o n a n d L i u , 1 9 9 4 ) . E a c h m e t h o d h a s i t s a d v a n t a g e s a n d d i s a d v a n t a g e s . I f o n e i n c o r p o r a t e s a h i g h p e n a l t y i n t o t h e e v o l u t i o n p r o g r a m s , i t i s p o s s i b l e t h a t w h e n a l e g a l i n d i v i d u a l i s f o u n d , i t d r i v e s t h e o t h e r s o u t a n d t h e p o p u l a t i o n c o n v e r g e s w i t h o u t f i n d i n g b e t t e r i n d i v i d u a l s . T h i s u n d e s i r a b l e c o n v e r g e n c e o c c u r s b e c a u s e t h e l i k e l y p a t h s t o o t h e r l e g a l i n d i v i d u a l s r e q u i r e t h e p r o d u c t i o n o f i l l e g a l i n d i v i d u a l s a s i n t e r m e d i a t e s t r u c t u r e s , a n d t h e p e n a l t i e s f o r v i o l a t i n g t h e c o n s t r a i n t m a k e i t u n l i k e l y t h a t s u c h i n t e r m e d i a t e s t r u c t u r e s w i l l b e p r o d u c e d . I f o n e i m p o s e s m o d e r a t e p e n a l t i e s , t h e r e i s t h e r i s k o f c r e a t i n g a n e v o l u t i o n p r o g r a m t h a t s p e n d s m o s t o f i t s t i m e e v a l u a t i n g i l l e g a l i n d i v i d u a l s . I f o n e b u i l d s a " d e c o d e r " i n t o t h e e v o l u t i o n p r o c e d u r e t h a t i n t e l l i g e n t l y a v o i d s b u i l d i n g a n i l l e g a l i n d i v i d u a l , t h e r e s u l t i s f r e q u e n t l y c o m p u t a t i o n - i n t e n s i v e f o r h a n d l i n g t h e c o n s t r a i n t s . F u r t h e r , n o t a l l c o n s t r a i n t s c a n b e e a s i l y i m p l e m e n t e d 7 in this way, however, it saves a lot of computing time by not evaluating the illegal solutions. In evolution programming, the central issue is to select "the best" chromosome representation of solutions together with meaningful genetic operators to satisfy all constraints imposed by the problem. Any genetic operator should pass characteristic structures from parent to offspring, so the representation structure plays an important role in defining genetic operators. Moreover, different representation structures have different characteristics of suitability for constraint representation, which complicates the problem even more. These two components (representation and operators) influence each other, and every problem requires careful analysis in order to define appropriate representation for which there are meaningful genetic operators. During the last decade, the significance of optimization has grown even further, many large-scale combinatorial optimization problems and highly constrained engineering problems can only be solved approximately on present day computers. Evolution programs are ideal for such complex problems. While evolution programs belong to the class of probabilistic algorithms, they are very different from random algorithms in that they combine elements of both directed and stochastic searches. For this reason, the evolution program is more robust than existing directed search methods. Another important property of such genetic based search methods is that they maintain a population of potential solutions, whereas all other methods process a single point of the search space. 8 As mentioned earlier, the evolution program performs a multiple directional search by maintaining a population of potential solutions, and introduces new information and exchange between these search directions. The population undergoes a simulated evolution: at each generation the relatively "good" solutions reproduce, while the relatively "bad" solutions die. To distinguish between different solutions we use an objective function which plays the role of an environment. Then, a new population is formed by selecting the more fit individuals. Some members of this new population undergo reproduction by means of crossover and mutation, to form new solutions. Crossover combines the features of two parent chromosomes to form two similar offspring by swapping corresponding segments of parents. The intuition behind the applicability of the crossover operator is information exchange between different potential solutions. Mutation arbitrarily alters one or more genes of a selected chromosome, by a random change. The probability of accepting a new solution is usually 50%. In my models, the probability depends on the generation number and the relative decrease of fitness caused by the mutation. The intuition behind the mutation operator is the introduction of some extra variability into the population. 9 Chapter 2 Literature Review A c o m m o n o b j e c t i v e o f f o r e s t p l a n n i n g i s t o g e n e r a t e a l o n g t e r m h a r v e s t s c h e d u l e t h a t m a x i m i z e s t h e v o l u m e h a r v e s t e d ( o r t h e n e t p r o f i t ) , s u b j e c t t o n u m e r o u s c o n s t r a i n t s . T y p i c a l c o n s t r a i n t s a r e : 1 ) m i n i m u m h a r v e s t a g e , 2 ) a d j a c e n c y a n d g r e e n u p r u l e s , a n d 3 ) f o r e s t c o v e r c o n s t r a i n t s . I n a d d i t i o n , h a r v e s t f l o w a n d b u d g e t c o n s t r a i n t s a r e u s u a l l y a d d e d t o c o n t r o l r e s o u r c e s i n e a c h time p e r i o d . F u r t h e r c o m p l e x i t y i s a d d e d b y d y n a m i c g r o w t h o f t h e f o r e s t t h r o u g h time, b u t i t i s p r i m a r i l y t h e i n t e g e r s o l u t i o n r e q u i r e d b y t h e a d j a c e n c y r u l e t h a t m a k e s t h e s e p r o b l e m s e x c e p t i o n a l l y d i f f i c u l t t o s o l v e . T h e n e e d t o d e a l w i t h a d j a c e n c y c o n s t r a i n t s h a s b e e n p r e s e n t e d i n m a n y p a p e r s ( T h o m p s o n e t a l . , 1 9 9 0 , J a m n i c k a n d W a t e r s , 1 9 9 1 , J o n e s e t a l . , 1 9 9 1 b ) . M e a l e y e t a l . ( 1 9 8 2 ) p o i n t e d o u t t h a t t h e U S N a t i o n a l F o r e s t S e r v i c e i s m a n d a t e d t o e n s u r e h a b i t a t d i s p e r s i o n ( s e e a l s o J o n e s e t a l . , 1 9 9 1 b , T o r r e s e t a l . , 1 9 9 1 , B a r a h o n a e t a l . , 1 9 9 2 ) . N u m e r o u s a p p r o a c h e s h a v e b e e n u s e d f o r s o l v i n g t h e f o r e s t h a r v e s t s c h e d u l i n g p r o b l e m s . L i n e a r p r o g r a m m i n g ( L P ) w a s o n e o f t h e f i r s t m e t h o d s u s e d ( T h o m p s o n e t a l . , 1 9 7 3 ) a n d s o m e o t h e r l i n e a r p r o g r a m m i n g b a s e d a p p r o a c h e s h a v e d e v e l o p e d a s w e l l ( K i r b y e t a l . , 1 9 8 6 , J o n e s e t a l . , 1 9 9 1 a ) . I n t e g e r p r o g r a m m i n g ( I P ) a n d m i x e d i n t e g e r p r o g r a m m i n g ( M I P ) h a v e b e e n a p p l i e d , e v e n t h o u g h p r o b l e m s i z e i s a l i m i t i n g f a c t o r ( K i r b y e t a l . , 1 9 8 6 , N e l s o n a n d B r o d i e , 1 9 9 0 ) . 10 2.1 Mixed Integer Programming Detailed mathematical formulations for forest planning problems can be found in Kirby et al., 1986, Nelson and Brodie, 1990, and Nelson and Finn, 1991. The difficulty in formulating the problems and interpreting the results are well discussed in these papers. In order to understand the difficulty, I present a general formulation of the problem which is based on the work of Nelson and Brodie (1990) and Murray and Church (1993). First, the following notations have to be defined: j = index of road links (j=l,2,...,J); i = index of harvest blocks (i=l,2,...,I); t = index of time periods (t=l,2,...,T); a„ = discounted net revenue generated from harvesting block i in period t, (price - logging cost); blt = undiscounted revenue generated from harvesting block i in period t, (price - logging cost); cjt = discounted cost to build road link j in period t; djt = undiscounted cost to build road link j in period t; H, = upper bound on total volume harvest in period t; Lt = lower bound on total volume harvested in period t; LR, = lower bound on total undiscounted revenue generated in period t; p = harvest exclusion period length; Nj = set of harvest blocks adjacent to block i; M, = set of road links which must be built in order to build road link j; S, = set of road links which must be built in order to access block i; Decision variables: 1 i f block i is harvested in period t 0 otherwise 1 i f road i is built in period t 0 otherwise Maximize Z = ^ ^ a » x , . " 2 2 C" r" i t j t Subject to: ( 1 ) Limit block harvest to at most one time period, x,, *z 1 for all i, t; (2) Limit construction of each road link to at most one time period. ^ r„ s 1 for all j; t (3) Can not build road link j unless predecessor link k has been built. ^ ru * rjt forallj,t7kEM(; (4) Adjacency restrictions to prevent simultaneous harvest of neighboring blocks. xit + y \ t <z 1 for all i, t; 12 (5) Cannot harvest a block until necessary access roads are built. x,t s r(1 for all jE S,, t and 1 = 1, 2, 3, ...t; (6) Upper and lower bounds on harvest volume in each period. (a) X v» *" * L< (b) J v^ssH, for all t; i (7) Undiscounted revenue bound in each time period. J bltxlt-2 V^LR, for all t; ' i The objective of this formulation is to maximize discounted net revenue. Constraint (1) limits treatment activity in the appropriate time interval. Constraint (2) restricts the construction of a road to one time period. Constraint (3) imposes connectivity requirements for constructed road linkages. Constraint (4) imposes adjacency restrictions for harvested compartments. Simple adjacency conditions for two neighboring blocks i and k can be written as: Constraint (4) represents a special aggregated version, where one adjacency constraint is constructed for each compartment block in each time period. Various structures of constraint (4) is the subject of several papers (Torres and Brodie, 1990, Jones et al., 1991b, Murray and Church, 1993a, Murray and Church, 1993b). Constraint (5) establishes road link access to a harvest block before treatment can be carried out. Constraint (6) places lower and upper harvest volume bounds on each time period. Constraint (7) requires that undiscounted 13 n e t r e v e n u e i n e a c h t i m e p e r i o d b e g r e a t e r t h a n o r e q u a l t o a l o w e r l i m i t . T h e s i z e o f t h i s f o r m u l a t i o n i s r e l a t i v e l y c o m p a c t d u e t o t h e f o r m o f t h e a d j a c e n c y c o n s t r a i n t ( 4 ) . T h e l a r g e n u m b e r o f 0 - 1 i n t e g e r v a r i a b l e s i n t h e p r o g r a m m a k e t h e p r o b l e m t r e m e n d o u s l y d i f f i c u l t t o s o l v e . M B ? h a s h a d l i m i t e d s u c c e s s b e c a u s e m o s t p r o b l e m s o f o p e r a t i o n a l d i m e n s i o n s s t i l l r e m a i n o u t s i d e t h e l i m i t s o f r e a s o n a b l e c o m p u t i n g r e s o u r c e s . I n r e s p o n s e t o t h e s e l i m i t a t i o n s , t e c h n i q u e s d e s i g n e d f o r g e n e r a t i n g g o o d , a p p r o x i m a t e s o l u t i o n s , h a v e b e e n i n v e s t i g a t e d . 2 . 2 H e u r i s t i c A p p r o a c h e s T h e d i f f i c u l t y i n s o l v i n g t h e s e p r o b l e m s h a s r e s u l t e d i n e f f o r t s d i r e c t e d t o w a r d s h e u r i s t i c s o l u t i o n d e v e l o p m e n t ( N e l s o n a n d B r o d i e , 1 9 9 0 , D a h l i n a n d S a l i n a s , 1 9 9 3 ) . T h e h e u r i s t i c a p p r o a c h m u s t b e c a p a b l e o f p r o v i d i n g g o o d f e a s i b l e s o l u t i o n s , r e q u i r e l e s s c o m p u t e r r e s o u r c e s , a n d b e a b l e t o p r o d u c e n e a r o p t i m a l o r h i g h q u a l i t y s o l u t i o n s . O n e o f t h e m o s t s u c c e s s f u l m e t h o d s a m o n g h e u r i s t i c a p p r o a c h e s i s t h e s a m p l i n g h e u r i s t i c a p p r o a c h c a l l e d M o n t e C a r l o I n t e g e r P r o g r a m m i n g ( M C D ? ) ( N e l s o n a n d B r o d i e ( 1 9 9 0 ) , O ' H a r a e t . a l . ( 1 9 8 9 ) , C l e m e n t s e t . a l . ( 1 9 9 0 ) ) . T h i s a p p r o a c h i s b a s i c a l l y a b i a s e d s a m p l i n g s c h e m e d e s i g n e d t o g e n e r a t e f e a s i b l e s o l u t i o n a l t e r n a t i v e s . T h e s u c c e s s o f M o n t e C a r l o I n t e g e r P r o g r a m m i n g i s d i r e c t l y r e l a t e d t o t h e n u m b e r o f s a m p l e s o l u t i o n s g e n e r a t e d . I f t h e s a m p l e s i z e 14 i s v e r y l a r g e , i t i s m o r e l i k e l y t o o b t a i n n e a r o p t i m a l s o l u t i o n s . H o w e v e r , l a r g e r s a m p l e s i z e s r e q u i r e l o n g e r c o m p u t i n g t i m e s . T h e a d v a n t a g e o f M o n t e C a r l o I n t e g e r P r o g r a m m i n g i s i t s a b i l i t y t o g e n e r a t e f e a s i b l e s o l u t i o n s i n a s h o r t t i m e . O t h e r r a n d o m - b a s e d s e a r c h m e t h o d s b e g i n w i t h a s o l u t i o n a n d s u c c e s s i v e l y i m p r o v e u p o n i t . T h e s e i m p r o v e m e n t m e t h o d s l e a d t o n e a r o p t i m a l s o l u t i o n s , w i t h o u t t h e n e e d t o g e n e r a t e a l a r g e s a m p l e , a s i s t h e c a s e w i t h t h e M C I P a p p r o a c h . T h e t i m e n e e d e d t o i m p r o v e u p o n a n i n i t i a l s o l u t i o n i s s i g n i f i c a n t l y l e s s t h a n t h e t i m e n e e d e d t o g e n e r a t e a l a r g e n u m b e r o f M C I P s o l u t i o n s , s o t h e s e i m p r o v e m e n t m e t h o d s p r o v i d e h i g h q u a l i t y s o l u t i o n s i n r e l a t i v e l y s h o r t e r t i m e . R a n d o m s e a r c h e s a r e e x c e l l e n t e x p l o r a t o r y t o o l s , b u t t y p i c a l l y t h e y a r e i n e f f i c i e n t i n g e n e r a t i n g h i g h - v a l u e d s o l u t i o n s . A s m o r e p r o b l e m s p e c i f i c i n f o r m a t i o n b e c o m e s a v a i l a b l e , m o r e e f f i c i e n t a l g o r i t h m s c a n b e d e s i g n e d t o t a k e a d v a n t a g e o f s p e c i f i c s t r u c t u r e s . P r i o r i t i z i n g h a r v e s t u n i t s w i t h i n s i m u l a t i o n m o d e l s h a s p r o d u c e d g o o d r e s u l t s ( O ' H a r a e t a l . 1 9 8 9 , N e l s o n a n d F i n n , 1 9 9 1 ) . P r i o r i t i z e d s i m u l a t i o n c o m b i n e d w i t h r a n d o m s e a r c h m e t h o d s h a s a l s o b e e n a p p l i e d t o t a c t i c a l f o r e s t p l a n n i n g p r o b l e m s ( S e s s i o n s a n d S e s s i o n s , 1 9 9 1 ) . I n a n o t h e r a p p l i c a t i o n , a n o n l i n e a r p e n a l t y f u n c t i o n m e t h o d w a s u s e d t o a n a l y z e t h e s p a t i a l a r r a n g e m e n t o f s t a n d s ( R o i s e , 1 9 9 0 ) . P e n a l t y f u n c t i o n s w i t h i n s i m u l a t e d a n n e a l i n g a l g o r i t h m s h a v e a l s o p r o v e d p r o m i s i n g f o r t h e a d j a c e n c y p r o b l e m ( L o c k w o o d a n d M o o r e , 1 9 9 3 ) . O t h e r r e c e n t a p p l i c a t i o n s i n c l u d e i n t e r c h a n g e , s i m u l a t e d a n n e a l i n g , a n d T a b u s e a r c h e s ( M u r r a y a n d C h u r c h , 1 9 9 3 ) . T h e s e m e t h o d s h a v e t e n d e d t o u s e a n 15 element of randomness to globally search the solution space. The common thread in these algorithms is to occasionally accept inferior transformations in order to avoid convergence on local optima. 2.3 Interchange Interchange is one of the random search methods (Murray and Church, 1993) which is also called the hill climbing algorithm because only improvement transformations in the solution space can be accepted. There have been many successful applications of interchange procedures for 0-1 integer programming problems. The basic idea is to transform a current solution into an improved solution. The interchange process continues until no improved solution can be identified. The success of the interchange approach depends primarily on the starting point. The interchange process begins with a feasible solution and maintains feasibility at all times throughout solution transformations. This is done by evaluating the possible harvest of each non-harvested block in all time periods. If there is an adjacency constraint violation, then all violating blocks are set to non-harvest. Following this, the necessary roads are constructed. If the new solution maintains feasibility for all other constraints, then its objective function is evaluated. If the transformation results in an improvement, the new solution becomes the current solution. The process continues until no improved transformation is available. 16 T h e d i s a d v a n t a g e o f t h e i n t e r c h a n g e p r o c e d u r e i s t h a t i t i s l i k e l y t o g e t t r a p p e d a t a l o c a l o p t i m a . H o w e v e r , t h e m e t h o d i s r e l a t i v e l y f a s t , s o a l a r g e n u m b e r a l t e r n a t i v e s o l u t i o n s c a n b e g e n e r a t e d w i t h d i f f e r e n t s t a r t i n g p o i n t s . S t i l l , t h e i n h e r e n t n a t u r e o f t h e p r o c e s s i s w h a t l e a d s i t t o l o c a l o p t i m a , s i n c e o n l y t h e i m p r o v e d s o l u t i o n s a r e a c c e p t e d . 2.4 Simulated Annealing S i m u l a t e d a n n e a l i n g i s a r a n d o m s e a r c h t e c h n i q u e t h a t i s a n a l o g o u s t o m e t a l a n n e a l i n g . M e t a l a n n e a l i n g i s t h e p r o c e s s e s o f p a r t i c l e a r r a n g e m e n t w h e n m o v i n g f r o m a h i g h e n e r g y s t a t e t o l o w e n e r g y s t a t e . I n a h i g h e n e r g y s t a t e , p a r t i c l e s a r e a c t i v e a n d a b l e t o m o v e f r e e l y . A s t e m p e r a t u r e g r a d u a l l y d e c r e a s e s , t h e p a r t i c l e p o s i t i o n g r a d u a l l y f r e e z e s . I n 1 9 8 3 , K i r k p a t r i c k e t a l . f i r s t a p p l i e d s i m u l a t e d a n n e a l i n g a l g o r i t h m s t o c o m b i n a t o r i a l o p t i m i z a t i o n p r o b l e m s b a s e d o n t h e w o r k o f M e t r o p o l i s e t a l . ( 1 9 5 3 ) . S i n c e 1 9 8 0 , s i m u l a t e d a n n e a l i n g h a s b e e n u s e d i n m a n y f i e l d s s u c h a s t h e d e s i g n o f c o m p u t e r c i r c u i t s , a n d t h e t r a n s p o r t a t i o n n e t w o r k s . T h e k e y i s s u e i n a n n e a l i n g i s h o w t o c o n t r o l t h e c o o l i n g p r o c e s s i n o r d e r t o b r i n g t h e s o l i d t o a l o w e n e r g y s t a t e w h i l e m a i n t a i n i n g t h e d e s i r e d p a r t i c l e a r r a n g e m e n t . T w o i m p o r t a n t c o n c e r n s i n t h e a n n e a l i n g p r o c e s s a r e : 1 . t h e i n i t i a l t e m p e r a t u r e i s h i g h e n o u g h , a n d 17 2 . t h e c o o l i n g r a t e i s s u f f i c i e n t l y s l o w . T h e s i m u l a t e d a n n e a l i n g p r o c e s s i s s i m i l a r t o h i l l c l i m b i n g , w i t h t h e e x c e p t i o n o f t h e t r a n s f o r m a t i o n a c c e p t a n c e c r i t e r i o n . S i m u l a t e d a n n e a l i n g w a s f i r s t u s e d t o s o l v e f o r e s t p l a n n i n g p r o b l e m s b y L o c k w o o d a n d M o o r e ( 1 9 9 3 ) . N e l s o n a n d L i u ( 1 9 9 4 ) h a v e a l s o a p p l i e d s i m u l a t e d a n n e a l i n g t o t h e s e p r o b l e m s . B o t h t h e s e a p p l i c a t i o n s h a v e b e e n q u i t e s u c c e s s f u l i n s o l v i n g f o r e s t p l a n n i n g p r o b l e m s . L o c k w o o d a n d M o o r e ( 1 9 9 3 ) u s e d p e n a l t y f u n c t i o n s , b e g a n t h e i r p r o c e s s w i t h i n f e a s i b l e s o l u t i o n s a n d p r o c e e d t o w a r d f e a s i b l e a n d i m p r o v e d s o l u t i o n s . O n e d i s a d v a n t a g e o f t h e i r m e t h o d i s t h e d i f f i c u l t y i n i d e n t i f y i n g t h e p e n a l t y f u n c t i o n v a l u e s u s e d f o r c o n s t r a i n t v i o l a t i o n s . 2.5 Tabu Search T h e d i s a d v a n t a g e s a n d a d v a n t a g e s o f T a b u - s e a r c h h a v e b e e n d e s c r i b e d i n t h e w o r k o f M u r r a y a n d C h u r c h ( 1 9 9 3 ) : " T a b u s e a r c h h a s e n j o y e d n u m e r o u s s u c c e s s f u l a p p l i c a t i o n s i n a w i d e v a r i e t y o f p r o b l e m a r e a s ( G l o v e r , 1 9 8 9 , H e r t z a n d d e W e r r a , 1 9 9 0 ) . T a b u s e a r c h i s d e v i s e d t o o v e r c o m e l o c a l o p t i m a l i t y i n a m o r e o r d e r l y f a s h i o n t h a n s i m u l a t e d a n n e a l i n g ( d e W e r r a a n d H e r t z , 1 9 8 9 ) . R a t h e r t h a n r e l y i n g o n a f u n c t i o n a l p r o b a b i l i t y o f a c c e p t i n g n o n - i m p r o v e m e n t s o l u t i o n s , T a b u s e a r c h s y s t e m a t i c a l l y f o r c e s t h e p r o c e s s i n t o n e w r e g i o n s o f t h e s o l u t i o n s p a c e . T h i s i s a c c o m p l i s h e d b y e m p l o y i n g s h o r t - t e r m a n d l o n g - t e r m m e m o r y s e a r c h s t r a t e g i e s ( G l o v e r , 1 9 8 9 , G l o v e r , 1 9 9 0 ) . T h e s e s t r a t e g i e s h e l p t h e p r o c e s s t o s e a r c h t h e s o l u t i o n s p a c e f o r p o t e n t i a l l y b e t t e r s o l u t i o n s , w h i l e a v o i d i n g u n p r o d u c t i v e c y c l i n g ( m o v e m e n t b a c k a n d f o r t h b e t w e e n t h e s a m e s o l u t i o n s ) . T h e r e a r e t h r e e i m p o r t a n t e l e m e n t s o f T a b u S e a r c h : d e f i n i n g t h e n e i g h b o r h o o d , i n t e n s i f i c a t i o n a n d d i v e r s i f i c a t i o n ( G l o v e r , 1 9 8 9 , G l o v e r , 1 9 9 0 , H e r t z a n d d e W e r r a , 1 9 9 0 ) . T h e n e i g h b o r h o o d i s t h e s e t o f f e a s i b l e s o l u t i o n t r a n s i t i o n s . I n t e n s i f i c a t i o n c a n b e t h o u g h t o f a s t h e 18 a c c e p t a n c e o f p o s i t i v e o r h i l l - c l i m b i n g m o v e s . T h a t i s , f o c u s i s p l a c e d o n p r o g r e s s i n g t o w a r d s a o p t i m a . D i v e r s i f i c a t i o n m a y b e t h o u g h t o f a s a m e a n s o f g u i d i n g t h e s o l u t i o n i n t o n e w a r e a s o f t h e s o l u t i o n s p a c e , s p e c i f i c a l l y , m o v i n g o u t o f p o i n t s o f l o c a l o p t i m a a n d i n t o n e w r e g i o n s f o r e x p l o r a t i o n . D i v e r s i f i c a t i o n i s i m p o s e d t h r o u g h t h e u s e o f s h o r t a n d l o n g t e r m m e m o r y i n t h e s e a r c h p r o c e s s . S h o r t - t e r m m e m o r y k e e p s t h e p r o c e s s f r o m c y c l i n g b a c k i n t o a l o c a l l y o p t i m a l s o l u t i o n t h a t h a s b e e n i d e n t i f i e d , a n d l o n g - t e r m m e m o r y i s u s e d t o b o o s t t h e p r o c e s s i n t o a s o l u t i o n r e g i o n t h a t h a s n o t b e e n p r e v i o u s l y e n c o u n t e r e d . I n o t h e r w a r d s , l o n g - t e r m m e m o r y e n a b l e s t h e p r o c e s s t o m o v e a w a y f r o m a l o c a l o p t i m a l s o l u t i o n . " . I n t e r m s o f s h o r t a n d l o n g - m e m o r y o f T a b u s e a r c h , t h e e v o l u t i o n p r o g r a m s c a n p e r f o r m b e t t e r , b e c a u s e s o m e i n d i v i d u a l s i n t h e p o p u l a t i o n c a n s u r v i v e f o r m a n y g e n e r a t i o n s . T h i s l o n g - t e r m s u r v i v a l o f g o o d s o l u t i o n s c a n h e l p s e a r c h e s i n t h e f e a s i b l e r e g i o n . T a b u s e a r c h s y s t e m a t i c a l l y f o r c e s t h e p r o c e s s i n t o n e w r e g i o n s o f t h e s o l u t i o n s p a c e , h o w e v e r , t h e n e w r e g i o n c o u l d b e a w r o n g r e g i o n . I t v e r y o f t e n t a k e s m a n y s t e p s t o g e t t o t h e b e t t e r r e g i o n s f r o m t h e c u r r e n t r e g i o n s , a n d t h i s c a n e x c e e d t h e m e m o r y l i m i t s o f T a b u s e a r c h . I p e r s o n a l l y t h i n k t h a t t h e e v o l u t i o n p r o g r a m i s a m o r e i n t e l l i g e n t m e t h o d t h a n T a b u s e a r c h . 2.6 Genetic Algorithms A n o t h e r c a t e g o r y o f r a n d o m , m a t h e m a t i c a l p r o g r a m m i n g t h a t h a s r e c e i v e d m u c h a t t e n t i o n i n n o n - f o r e s t r y f i e l d s i s t h e g e n e t i c a l g o r i t h m ( G A ) . G e n e t i c a l g o r i t h m s h a v e b e e n a p p l i e d t o t r a v e l i n g s a l e s m a n p r o b l e m s ( W h i t e l y , 1 9 8 9 ) , t r a n s p o r t a t i o n p r o b l e m s ( V i g n a u x a n d M i c h a l e w i c z , 1 9 8 9 , 1 9 9 1 ) , r e s o u r c e 19 s c h e d u l i n g ( S y s w e r d a a n d P a l m u c c i , 1 9 9 1 ) , c o m m u n i c a t i o n n e t w o r k s ( M i c h a l e w i c z , 1 9 9 1 ) , a n d p r o d u c t i o n s c h e d u l i n g ( H u s b a n d s e t a l . 1 9 9 0 ) . T h e g e n e t i c a l g o r i t h m i s p a r t i c u l a r l y w e l l s u i t e d t o p r o b l e m s w h e r e t h e r e i s l i t t l e i n f o r m a t i o n a b o u t t h e p r o c e s s e s a n d i t e r a t i o n s , l i k e t h e f i e l d o f g e n e t i c s , w h e r e t h e a l g o r i t h m w a s d e v e l o p e d a n d d e r i v e d i t s n a m e . G e n e t i c a l g o r i t h m s a r e a b l e t o p e r f o r m f a i r l y e f f i c i e n t s e a r c h e s w h e n p r i o r p r o b l e m k n o w l e d g e i s l a c k i n g , a n d o n l y a n e v a l u a t i o n o f t h e o b j e c t i v e f u n c t i o n i s a v a i l a b l e . T h i s m a k e s t h e g e n e t i c a l g o r i t h m a u s e f u l s e a r c h t e c h n i q u e f o r m a n y p r o b l e m s . W h e n a d d i t i o n a l k n o w l e d g e a b o u t t h e p r o b l e m c a n b e i n c o r p o r a t e d , t h e e f f i c i e n c y o f g e n e t i c a l g o r i t h m c a n b e i m p r o v e d ( G r e f e n s t e t t e , 1 9 8 7 ; M i c h a l e w i c z , 1 9 9 2 ) . 20 Chapter 3 Explanation of Evolution Programs using a Sample Problem Integrated forest resource planning problems are similar to the travelling salesman problem, but they are much more difficult to solve due to problem size and constraint structure. Solutions must provide the following information: 1) blocks to be harvested during each period, 2) the total volume harvested during each period, 3) the amount of road to build in each period, 4) the transportation cost for each period, and 5) the profit produced during each period, and over the entire planning horizon. For any evolution program, there is a number of parameters that need to be defined. These include the population size, new population selection criterion, crossover rates and procedures, problem specific genetic operators, acceptance/rejection criteria for offspring, and temunation conditions. In most classical genetic algorithm studies, the chromosome which represents the potential solution is composed of a fixed length binary string. The initial population consists of entirely random structures, with a complete lack of knowledge about the search space. However, for our problems, mcorporating the problem specific knowledge into the solution representation, solution initialisation, 21 a n d g e n e t i c o p e r a t i o n m a k e s g e n e t i c a l g o r i t h m s m u c h m o r e e f f i c i e n t T h i s m o d e r n g e n e t i c a l g o r i t h m i s a l s o c a l l e d t h e e v o l u t i o n p r o g r a m ( M i c h a l e w i c z , Z , 1 9 9 2 ) . L i k e g e n e t i c a l g o r i t h m s , t h e e v o l u t i o n p r o g r a m m u s t h a v e t h e f o l l o w i n g c o m p o n e n t s : 1 . a g e n e t i c r e p r e s e n t a t i o n f o r p o t e n t i a l s o l u t i o n s , 2 . w a y s t o c r e a t e a n i n i t i a l p o p u l a t i o n o f p o t e n t i a l s o l u t i o n s , 3 . a n e v o l u t i o n f u n c t i o n t h a t p l a y s t h e r o l e o f t h e e n v i r o n m e n t , r a t i n g s o l u t i o n s i n t e r m s o f t h e i r " f i t n e s s " , 4 . g e n e t i c o p e r a t o r s t h a t a l t e r t h e c o m p o s i t i o n o f c h i l d r e n d u r i n g r e p r o d u c t i o n , 5 . c r i t e r i a f o r a c c e p t a n c e c r i t e r i o n o f n e w s o l u t i o n s , a n d 6 . v a l u e s f o r v a r i o u s p a r a m e t e r s t h a t t h e e v o l u t i o n p r o g r a m u s e s ( p o p u l a t i o n s i z e , p r o b a b i l i t i e s o f a p p l y i n g g e n e t i c o p e r a t o r s , e t c . ) . T h e s e s i x c o m p o n e n t s w i l l n o w b e e x p l a i n e d i n d e t a i l . 3.1 S o l u t i o n R e p r e s e n t a t i o n R e p r e s e n t i n g t h e s o l u t i o n o n a s i n g l e c h r o m o s o m e s t r i n g i s o n e o f t h e m o s t c h a l l e n g i n g t a s k s a s s o c i a t e d w i t h e v o l u t i o n p r o g r a m s . T h i s i s f r e q u e n t l y r e f e r r e d t o a s " e n c o d i n g " t h e s o l u t i o n o n t h e c h r o m o s o m e . T h e c r i t i c a l p r o b l e m i s h o w t o r e p r e s e n t t h e r e l e v a n t s o l u t i o n i n f o r m a t i o n u s i n g o n e c h r o m o s o m e . I f y o u c a n i d e n t i f y t h e b l o c k h a r v e s t i n g s c h e d u l e , y o u c a n c a l c u l a t e t h e r e m a i n i n g i n f o r m a t i o n . I r e p r e s e n t t h e h a r v e s t s c h e d u l e b y p l a c i n g t h e b l o c k n u m b e r s ( i n b a s e 1 0 ) i n g e n e 22 locations according to the oitring sequence. Additional data sets hold block attributes (age, area, adjacent blocks, road network access) necessary for decoding the solution. Roads are also a part of the block attributes. A lot of problem specific knowledge is incorporated into the evolution program. Specifically; 1) each chromosome (solution string) is divided into several lengths, called partitions, each representing one period of the planning horizon, 2) all the constraints, beginning with the solution initialisation right through to the genetic operations are included (e.g. always maintain feasibility), 3) the acceptance criteria of simulated annealing is used as the criteria to accept or reject the supposed transition made by a problem specific pushing operator, and 4) a greedy repair is used following the genetic operation to make the search space smaller and to maintain feasibility. The solution represents the block harvesting schedule, including those blocks that were not harvested during the planning horizon. The solution string is composed of several partitions, with each partition representing one period. The blocks to be harvested during this period are contained in this partition. The last partition represents the uncut or residual blocks. The total length of the chromosome is fixed and equal to the total number of blocks in the forest However, the length of the partitions which represent each period, can be changed during the genetic operations. I illustrate this representation (Figure 3.3) with a simple example of 12 blocks and 4 planning periods. Figure 3.1 A Sample Forest with 12 Blocks 0 1 2 3 6 5 4 7 8 9 12 11 10 B u i l t R o a d P r o p o s e d R o a d 1000 Age(years) F i g u r e 3 . 2 V o l u m e ( m 3 / h a ) g r o w t h c u r v e a g a i n s t a g e 24 Table 3.1 Block attributes for the sample forest B l o c k - N o . C u r r e n t - a g e A r e a ( h a ) P r e d e c e s s o r - b l o c k D i s t a n c e ( k m ) B u i l t T io 1 5 0 To 1 2 1 0 0 1 8 1 1 5 0 3 7 0 1 0 2 1 5 0 4 1 2 0 1 1 5 1 5 0 5 9 0 1 9 6 1 5 0 6 5 0 1 6 1 1 0 1 7 7 0 2 2 6 1 0 1 8 3 0 2 5 7 1 5 1 9 1 5 0 2 0 8 1 5 0 1 0 1 2 0 1 8 1 1 1 5 0 1 1 8 0 2 3 8 1 0 1 1 2 9 0 2 0 1 1 1 5 0 F o r t h i s s p e c i f i c s a m p l e p r o b l e m , t h e m i n i m u m h a r v e s t a g e i s 9 0 y e a r s ( o n e r o t a t i o n ) , e a c h r o t a t i o n h a s 4 p e r i o d s , w i t h e a c h p e r i o d e q u a l t o 2 0 y e a r s . T h e m i n i m u m a d j a c e n c y g r e e n - u p t i m e i s 2 0 y e a r s . T o a v o i d a d j a c e n c y c o n f l i c t s , t h e t i m e b e t w e e n p e r i o d s c a n n o t b e l e s s t h a n t h e m i n i m u m g r e e n - u p t i m e . A l l h a r v e s t s a r e a s s u m e d t o o c c u r a t t h e m i d p o i n t o f e a c h p e r i o d . Figure 3.3. Block harvest schedule for the sample forest (Figure 3.1) represented by blocks placed in the gene positions on a chromosome. Partitions represent the planning periods. Gene Position 1 2 3 4 5 6 7 8 9 10 11 12 Block Number 12 9 4 10 7 6 3 11 2 8 5 1 Partition Number (Period) 1 2 3 4 Residual T h e o b j e c t i v e o f t h e p l a n i s t o m a x i m i s e t h e t o t a l v o l u m e h a r v e s t e d , w h i l e m a m t a i n i n g a p p r o x i m a t e l y e q u a l h a r v e s t s d u r i n g e a c h p e r i o d . F r o m T a b l e 3 . 1 , a n d t h e v o l u m e g r o w t h c u r v e s ( F i g u r e 3 . 2 ) , w e c a n c a l c u l a t e t h e t i m b e r v o l u m e f o r e a c h 25 block by period and for the entire planning horizon. By tracking the road link from the current block to its predecessor block and ultimately to the start of the road network, the road construction costs and transportation costs can be calculated. 3.2 Greedy Solution Initialization The chromosomes are initialised randomly, however, each block placement in a gene position is must satisfy all constraints. For example, to find which block goes to gene position 1, first find all the blocks which are eligible to be in this position at period 1 (stand age>=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<E1 [1] f m = V + m)*JN [2], and /2(A0 = l + ( 2 & ) 2 [3]. 36 where: P- Acceptance probability, N - Iteration Number £, - Fitness of the old solution (objective function value) E2 - Fitness of the new solution (objective function value) Functions f}(N) and / . ( A O are usually specific to the problem being analysed. Usually, at the beginning iterations, these two functions should make P large enough so that the process can escape the local optimum. Gradually the acceptance probability P is reduced to zero as the iterations increase in order to freeze the solution (Figure 3.4). Generation Number (100) • (E2-E1)/E1=-1% -*-(E2-E1)/E1=-0.1% (E2-E1)/E1=-0.01% Figure 3.4. The acceptance probability varies with the generation number and the percentage of fitness decreased. 37 T h e p u s h i n g p r o c e s s i s i l l u s t r a t e d b y t h e f o l l o w i n g s a m p l e c h r o m o s o m e : 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 1 2 9 4 1 0 7 6 3 1 1 2 8 5 1 S i x s t e p s o f t h e p u s h i n g p r o c e d u r e : S t e p 1 . R a n d o m l y i d e n t i f y p a r t i t i o n A , f o r t h i s e x a m p l e , l e t A = 2 . S t e p 2 . R a n d o m l y i d e n t i f y p a r t i t i o n B a m o n g { 3 , 4 , 5 } , l e t B = 4 . P a r t i t i o n N o . 1 2 ( A ) 3 4 ( B ) R e s i d u a l B l o c k s 1 2 9 4 1 0 7 6 3 1 1 2 8 5 1 S t e p 3 . I n p a r t i t i o n B , r a n d o m l y s e l e c t o n e o f a l l t h e e l i g i b l e b l o c k s w h i c h c a n g o t o p a r t i t i o n A . R a n d o m l y i n s e r t i t i n p a r t i t i o n A . I n t h i s e x a m p l e , b l o c k 2 i s t h e o n l y o n e e l i g i b l e . P a r t i t i o n N o . 1 2 ( A ) 3 4 ( B ) R e s i d u a l B l o c k s 1 2 9 4 2 1 0 7 6 3 1 1 8 5 1 S t e p 4 . I n p a r t i t i o n A , m o v e a l l a d j a c e n t b l o c k s o f b l o c k 2 t o t h e r e s i d u a l p a r t i t i o n . B l o c k 4 i s a d j a c e n t t o b l o c k 2 , a n d i t g o e s t o t h e r e s i d u a l p a r t i t i o n . P a r t i t i o n N o . 1 2 ( A ) 3 4 ( B ) R e s i d u a l B l o c k s 1 2 9 2 1 0 7 6 3 1 1 8 5 4 1 S t e p 5a. T r y t o p u s h e v e r y e l i g i b l e b l o c k t o p a r t i t i o n A f r o m p a r t i t i o n s 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 . I n t h i s e x a m p l e , t h e r e a r e n o e l i g i b l e b l o c k s t h a t c a n b e p u s h e d . 38 P a r t i t i o n N o . 1 2 ( A ) 3 4 ( B ) R e s i d u a l B l o c k s 1 2 9 2 1 0 7 6 3 1 1 8 5 4 1 S t e p 5 b . T r y t o p u s h e v e r y e l i g i b l e b l o c k t o p a r t i t i o n 3 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 . A g a i n , n o b l o c k s a r e e l i g i b l e f o r p u s h i n g i n t h i s a m p l e . P a r t i t i o n N o . 1 2 ( A ) 3 4 ( B ) R e s i d u a l B l o c k s 1 2 9 2 1 0 7 6 3 1 1 8 5 4 1 S t e p 5 c . T r y t o p u s h e v e r y e l i g i b l e b l o c k t o p a r t i t i o n 4 f r o m t h e r e s i d u a l p a r t i t i o n . N o b l o c k s a r e e l i g i b l e h e r e , a n d t h e n e w c h r o m o s o m e i s : P a r t i t i o n N o . 1 2 ( A ) 3 4 ( B ) R e s i d u a l B l o c k s 1 2 9 2 1 0 7 6 3 1 1 8 5 4 1 S t e p 6 . E v a l u a t e t h e n e w c h r o m o s o m e , a n d d e c i d e t o a c c e p t o r r e j e c t t h e t r a n s i t i o n ( t h e n e w s o l u t i o n ) . I f t h e n e w o n e i s n o w o r s e t h a n t h e o l d o n e , a c c e p t t h e n e w o n e i m m e d i a t e l y . I f t h e n e w s o l u t i o n i s w o r s e t h a n t h e o l d o n e , t h e p r o b a b i l i t y o f a c c e p t a n c e d e p e n d s o n t h e r e l a t i v e d e c r e a s e a n d t h e i t e r a t i o n n u m b e r . A s s h o w n i n F i g u r e 3 . 4 , t h e p o o r e r s o l u t i o n s h a v e a l o w a c c e p t a n c e p r o b a b i l i t y . T h e h i g h i t e r a t i o n n u m b e r s a l s o h a v e a l o w a c c e p t a n c e p r o b a b i l i t y . T h r e e s a m p l e c a l c u l a t i o n s o f P a r e p r o v i d e d b e l o w i n T a b l e 3 . 3 . T a b l e 3 . 3 R e s u l t s o f s a m p l e c a l c u l a t i o n s f o r p r o b a b i l i t y P . 1 0 0 % * ( I v E J / E , G e n e r a t i o n N u m b e r i P r o b a b i l i t y P C a s e 1 - 0 . 1 % 5 0 0 7 8 . 2 6 1 . 0 6 2 5 0 . 8 7 0 3 C a s e 2 - 0 . 1 % 3 0 0 0 8 7 6 . 3 6 3 . 2 5 0 0 0 . 1 2 8 1 C a s e 3 - 0 . 0 1 % 3 0 0 0 8 7 6 . 3 6 3 . 2 5 0 0 0 . 2 8 1 9 39 Chapter 4 Modifications for Simulated Annealing and Hill Climbing 4.1 Model Modification for Simulated Annealing The simulated annealing in my model is very similar to the evolution program, however, the "population" consists of only one solution. Therefore, operations such as new population selection and crossover that are related to multiple solutions are not applicable in simulated annealing. The advantage of simulated annealing is that the procedure is simple and can progress rapidly, whereas the advantage of the evolution program is that a wide variety of solutions can be manipulated as a means for searching out global optimum. As outlined below, there are many components common to evolution programs: 1. a set of possible configurations (solution representation), 2. an objective function (solution evaluation), 3. a way of randomly changing the configurations, and 4. an annealing or cooling schedule for changing the control parameters (new solution acceptance criterion). The simulated annealing process developed in this thesis begins by generating an initial solution. The procedure starts with a feasible solution and proceeds toward an improved solution, while always maintaining feasibility. Following this, random changes are made to the current solution. If the new 40 solution is an improvement over the previous solution's objective value, the new solution is selected as the current solution. If the new solution is not an improvement, it can still be selected depending on a probability function. The probability function P is the same one used in the evolution program (equation [1], [2], and [3]). The simulated annealing technique eliminates most disadvantages of the hill climbing method: solutions do not depend on the starting point as much as hill climbing and they usually converge on very high solutions. The algorithm terminates at some high iteration number where virtually no inferior changes are accepted. The advantage of simulated annealing is that the process spends most of the time refirting one solution. Thus, the good solution can be reached in a much shorter time than with evolution programs. The detailed procedure of simulated annealing is identical to the procedures for evolution program, described in chapter 3, however the population is limited to one individual, and new population selection and crossover are not applicable. 4.2 Modification for Hill Climbing With only one exception, the hill climbing procedure is identical to the simulated annealing procedure. The difference between the two methods is the acceptance/rejection criterion for new solutions. In hill climbing, inferior solutions are never accepted. It/ s major disadvantage is that it can stall on a local optimum. 41 Hill climbing methods use the iterative improvement technique; the technique is applied to a single point (the current point) in the search space. During a single iteration, a new point is selected from the neighborhood of the current point (this is why this technique is known also as neighborhood search or local search). If the new point provides a better value of the objective function, the new point becomes the current point. The method terminates if no further improvement is possible. It is clear that the hill climbing methods provide local optimum values which depend on selection of the starting point. Hill climbing can be very efficient provided that the initial solution is in close proximity to the global optimum. To increase the chances of success, hill climbing methods are usually executed for a large number of starting points. 42 Chapter 5 Test of the Models, Results and Discussions A l l t h r e e m e t h o d s ( e v o l u t i o n p r o g r a m , s i m u l a t e d a n n e a l i n g a n d r a n d o m h i l l d i m b i n g ) w e r e t e s t e d o n a f o r e s t p l a n n i n g d a t a s e t d e v e l o p e d f o r H a r d w i c k I s l a n d . T h i s f o r e s t , l o c a t e d i n t h e c o a s t a l r e g i o n o f B r i t i s h C o l u m b i a h a s 4 3 1 h a r v e s t b l o c k s , c o v e r i n g 7 0 3 4 h e c t a r e s . H a r d w i c k I s l a n d h a s a l o n g h i s t o r y o f l o g g i n g , r e s u l t i n g i n a f o r e s t s t r u c t u r e c o m p r i s e d o f m o s t l y y o u n g , s e c o n d - g r o w t h s t a n d s . T h e H a r d w i c k I s l a n d s c h e d u l i n g p r o b l e m w a s t o m a x i m i s e t h e t o t a l v o l u m e h a r v e s t e d o v e r a 1 0 0 y e a r p l a n n i n g h o r i z o n . T h e o b j e c t i v e f u n c t i o n m e a s u r e s t h e t o t a l t i m b e r p r o d u c t i o n o v e r t h e p l a n n i n g h o r i z o n , s u b j e c t t o t h e c o n s t r a i n t s : 1 ) m i n i m u m h a r v e s t a g e i s 9 0 y e a r s , 2 ) t h e m i n i m u m a d j a c e n c y g r e e n - u p a g e i s 1 5 y e a r s , a n d 3 ) a p p r o x i m a t e l y e v e n v o l u m e f l o w f o r e a c h p e r i o d . S u b s e q u e n t l y , a s i m u l a t i o n m o d e l ( A T L A S ) w a s u s e d t o g e n e r a t e s o l u t i o n s t h a t w e r e u s e d a s a d a t u m t o c o m p a r e p e r f o r m a n c e o f t h e s i m u l a t e d a n n e a l i n g a l g o r i t h m . T a b l e 5 . 1 E v o l u t i o n p r o g r a m p a r a m e t e r s u s e d i n t h e H a r d w i c k I s l a n d p r o b l e m . P o p u l a t i o n s i z e 3 0 C r o s s o v e r r a t e 0 . 1 4 P u s h i n g o p e r a t o r r a t e 0 . 0 5 % M a x i m u m g e n e r a t i o n n u m b e r 1 0 0 0 0 F o r s i m u l a t e d a n n e a l i n g a n d h i l l c l i m b i n g , t h e p u s h i n g o p e r a t o r i s a p p l i e d o n c e e v e r y i t e r a t i o n , o n o n e b l o c k a t a t i m e . E a c h a l g o r i t h m w a s r a n d o m l y s t a r t e d 2 0 43 times. T a b l e 5 . 2 s h o w s t h e h i g h e s t a n d t h e m e a n v a l u e o f t h e o b j e c t i v e f u n c t i o n f o r t h e 2 0 s o l u t i o n s g e n e r a t e d b y e a c h m e t h o d . T h e s e a r e a l s o p r e s e n t e d a s p e r c e n t a g e s o f t h e h i g h e s t s o l u t i o n f o u n d . F i g u r e 5 . 1 p r o v i d e s a g r a p h i c a l d i s p l a y o f t h e o b j e c t i v e f u n c t i o n f o r e a c h s o l u t i o n . T a b l e 5 . 2 M e a n v a l u e o f t h e o b j e c t i v e f u n c t i o n f o r 2 0 s o l u t i o n s g e n e r a t e d w i t h t h e e v o l u t i o n p r o g r a m , s i m u l a t e d a n n e a l i n g a n d h i l l c l i m b i n g f o r t h e H a r d w i c k I s l a n d p r o b l e m . A l g o r i t h m s B e s t S o l u t i o n ( c u b i c m e t r e s ) B e s t S o l u t i o n ( p e r c e n t ) P o o r e s t S o l u t i o n ( c u b i c m e t e r s ) A v e r a g e S o l u t i o n ( c u b i c m e t r e s ) A v e r a g e S o l u t i o n ( p e r c e n t ) E v o l u t i o n P r o g r a m 5 , 6 1 8 , 2 4 5 9 9 . 5 5 , 5 0 3 , 9 5 6 5 , 5 8 5 , 4 3 0 9 9 . 3 S i m u l a t e d A n n e a l i n g 5 , 6 4 7 , 5 9 5 1 0 0 5 , 5 9 0 , 9 7 6 5 , 6 2 3 , 0 4 7 1 0 0 H i l l C l i m b i n g 5 , 6 3 8 , 0 3 3 9 9 . 8 5 , 4 7 1 , 3 8 5 5 , 5 3 9 , 4 7 5 9 8 . 5 F r o m F i g u r e 5 . 1 , a l l s o l u t i o n s a r e w i t h i n 3 . 1 2 % o f t h e b e s t s o l u t i o n , a n d a l l t h e s o l u t i o n s f o u n d b y s i m u l a t e d a n n e a l i n g a r e w i t h i n 1 . 0 0 % ; e v o l u t i o n p r o g r a m , 2 . 5 4 % a n d h i l l c l i m b i n g , 3 . 1 2 % . 44 F i g u r e 5 . 1 T w e n t y s o l u t i o n s f o r t h e H a r d w i c k I s l a n d p r o b l e m g e n e r a t e d w i t h t h e e v o l u t i o n p r o g r a m , s i m u l a t e d a r m e a l i n g , a n d h i l l c l i m b i n g . A l l t h r e e m e t h o d s w o r k e d v e r y w e l l f o r t h i s p r o b l e m . H o w e v e r , s i m u l a t e d a n n e a l i n g a n d h i l l c l i m b i n g c o n v e r g e d m u c h f a s t e r o n t h e o p t i m u m t h a n d i d t h e e v o l u t i o n p r o g r a m . U s i n g a 4 8 6 / 5 0 M H z c o m p u t e r , t h e e v o l u t i o n p r o g r a m t o o k 3 7 8 m i n u t e s w i t h a p o p u l a t i o n o f 3 0 c h r o m o s o m e s a n d 1 0 , 0 0 0 g e n e r a t i o n s . S i m u l a t e d a n n e a l i n g t o o k o n l y 3 6 . 8 m i n u t e s , w h i l e h i l l c l i m b i n g t o o k 3 2 . 7 m i n u t e s f o r 1 0 , 0 0 0 i t e r a t i o n s ( T a b l e 5 . 3 ) . T a b l e 5 . 3 C o m p u t i n g t i m e f o r t h e e v o l u t i o n p r o g r a m , s i m u l a t e d a n n e a l i n g , a n d h i l l c l i m b i n g w i t h 4 3 1 b l o c k s , 4 8 6 / 5 0 p e r s o n a l c o m p u t e r . C o m p u t i n g t i m e ( m i n u t e s ) I t e r a t i o n N o . 1 0 0 0 2 0 0 0 6 0 0 0 1 0 0 0 0 E v o l u t i o n p r o g r a m 6 3 1 1 2 2 8 8 3 7 8 S i m u l a t e d A n n e a l i n g 4 . 5 8 . 6 2 3 . 5 3 6 . 8 R a n d o m H i l l C l i m b i n g 3 . 9 7 . 6 2 0 . 8 3 2 . 7 45 The computing time of the evolution program is very dependent on parameters such as population size and the crossover rate. Typical performance patterns relative to the iteration number for each algorithm are shown in Figure 5.2. 5800 | I Generation Number ^ ™ Simulated Annealing— Evolution Programg""»Hill Climbing Figure 5.2 Performance of the evolution program, simulated annealing, and random hill climbing. The evolution program was inefficient in the earlier iterations because the crossover operation tended to direct the search too far away from the previous location. This caused the evolution program to waste time in re-estabhshing its previous location. This suggests that the crossover operation should be improved. 46 A s t h e e v o l u t i o n p r o g r a m p r o g r e s s e d , i t w a s o b s e r v e d t h a t s o l u t i o n s i n t h e p o p u l a t i o n b e c a m e v i r t u a l l y i d e n t i c a l , a s w o u l d b e e x p e c t e d w h e n s e l e c t i n g f o r t h e h i g h v a l u e d s o l u t i o n s . D u r i n g l a t e i t e r a t i o n s , c r o s s o v e r c a n e x c h a n g e h a l f t h e c h r o m o s o m e b e t w e e n t w o p a r e n t c h r o m o s o m e s , b e c a u s e a l l t h e m e m b e r s i n t h e p o p u l a t i o n a r e s i m i l a r . T h e h a l f c h r o m o s o m e e x c h a n g e c a n s p r e a d g o o d g e n e s q u i c k l y . H i l l c l i m b i n g a c h i e v e s r a p i d g a i n s i n t h e e a r l y i t e r a t i o n s , a n d g e n e r a l l y a c h i e v e s v e r y g o o d r e s u l t s . I n t e r m s o f c o m p u t a t i o n a l e f f o r t , m u l t i p l e s t a r t s o f t h e h i l l c l i m b i n g a l g o r i t h m m a y b e a n e f f e c t i v e s o l u t i o n t e c h n i q u e . T h e r e m a y a l s o b e o p p o r t u n i t i e s t o s w i t c h a c c e p t a n c e c r i t e r i a a s t h e i t e r a t i o n s i n c r e a s e ( r a p i d h i l l c l i m b i n g , t h e n u s e t h e p r o b a b i l i t y f u n c t i o n P ) . T h e s i m u l a t i o n m o d e l A T L A S w a s t h e n u s e d i n a c o m p a r i s o n w i t h t h e s i m u l a t e d a n n e a l i n g a l g o r i t h m . T h e H a r d w i c k I s l a n d d a t a s e t w a s m o d i f i e d s l i g h t l y t o m a t c h a n e x i s t i n g A T L A S d a t a s e t . S o l u t i o n s w e r e g e n e r a t e d w i t h a n d w i t h o u t e v e n f l o w c o n s t r a i n t s , d i f f e r e n t i n i t i a l a g e c o n d i t i o n s , a n d d i f f e r e n t p l a n n i n g p e r i o d s . T a b l e 5 . 4 . a . C o m p a r i s o n o f s i m u l a t e d a n n e a l i n g a n d A T L A S f o r H a r d w i c k I s l a n d w h e n n o f l o w c o n s t r a i n t s a r e a p p l i e d ( 5 p l a n n i n g p e r i o d s ) . S i m u l a t e d A n n e a l i n g A T L A S % i n c r e a s e o f S A r e l a t i v e t o A T L A S P e r i o d 1 2 9 1 1 4 9 3 1 2 6 0 1 - 6 . 7 P e r i o d 2 6 6 7 6 6 3 7 4 8 5 4 5 - 1 0 . 8 P e r i o d 3 1 0 8 7 4 5 5 1 0 4 6 5 2 0 + 3 . 9 P e r i o d 4 1 2 4 1 8 2 5 9 7 4 2 8 5 + 2 7 . 5 P e r i o d 5 1 2 3 3 5 8 0 9 5 6 1 1 0 + 2 9 . 0 T o t a l 4 5 2 1 6 7 2 4 0 3 8 0 6 1 + 1 2 . 0 S o l u t i o n T i m e ( m ) 3 4 0 . 5 47 N o t e t o T a b l e 5 . 4 . a : t o t a l p l a n n i n g a r e a = 6 3 7 4 h e c t a r e s ; m i n i m u m h a r v e s t a g e i s 1 0 0 y e a r s ; m i n i m u m a d j a c e n c y g r e e n - u p a g e i s 2 0 y e a r s ; a n d p e r i o d l e n g t h = 2 0 y e a r s . T a b l e 5 . 4 . a s h o w s s i m u l a t e d a n n e a l i n g p r o d u c e d a t o t a l o f 1 2 % m o r e t i m b e r t h a n A T L A S . I f t h e i n i t i a l a g e o f a l l s t a n d s i s 9 0 y e a r s , t h e r e s u l t s a r e a s s h o w n i n T a b l e 5 . 4 . b . T a b l e 5 . 4 . b . C o m p a r i s o n o f A T L A S a n d s i m u l a t e d a n n e a l i n g w h e n t h e i n i t i a l a g e o f a l l s t a n d s i s 9 0 y e a r s . S o l u t i o n s w i t h a n d w i t h o u t e v e n f l o w c o n s t r a i n t s a r e p r e s e n t e d ( 5 p l a n n i n g p e r i o d s ) . S i m u l a t e d A n n e a l i n g ( e v e n f l o w ) A T L A S ( e v e n f l o w ) A T L A S ( n o e v e n f l o w ) % i n c r e a s e o f S A r e l a t i v e t o A T L A S E v e n F l o w N o E v e n F l o w P e r i o d 1 9 7 4 6 9 7 8 4 5 6 4 0 1 3 8 7 5 3 0 + 1 5 . 3 - 2 9 . 8 P e r i o d 2 1 0 1 5 5 7 5 8 5 2 2 2 5 1 2 5 6 3 5 8 + 1 9 . 2 - 1 9 . 2 P e r i o d 3 1 0 4 3 0 4 8 8 4 9 0 9 0 1 0 9 2 3 8 9 + 2 2 . 8 - 4 . 5 P e r i o d 4 1 0 9 5 8 0 0 8 4 4 2 4 3 7 7 8 7 9 1 + 2 9 . 8 + 4 0 . 7 P e r i o d 5 1 1 3 1 4 6 0 8 0 2 6 1 0 5 9 6 7 7 0 + 4 1 . 0 + 8 9 . 6 T o t a l 5 2 5 8 5 8 0 4 1 9 3 8 0 8 5 1 1 1 8 3 8 + 2 5 . 4 + 2 . 9 S o l u t i o n T i m e ( m ) 3 4 0 . 5 0 . 5 N o t e t o T a b l e 5 . 4 . b : t o t a l p l a n n i n g a r e a = 6 3 7 4 h e c t a r e s ; m i n i m u m h a r v e s t a g e i s 1 0 0 y e a r s ; m i n i m u m a d j a c e n c y g r e e n - u p a g e i s 2 0 y e a r s ; p e r i o d l e n g t h = 2 0 y e a r s . 48 T a b l e 5 . 4 . c . C o m p a r i s o n o f A T L A S a n d S i m u l a t e d A n n e a l i n g w h e n 4 p l a n n i n g p e r i o d s a r e u s e d . S o l u t i o n s w i t h a n d w i t h o u t e v e n f l o w c o n s t r a i n t s a r e s h o w n . S i m u l a t e d A n n e a l i n g ( e v e n f l o w ) A T L A S ( e v e n f l o w ) A T L A S ( n o e v e n f l o w ) % i n c r e a s e o f S A r e l a t i v e t o A T L A S E v e n F l o w N o E v e n F l o w P e r i o d 1 1 2 6 7 5 2 3 9 3 1 9 3 8 1 3 9 1 8 1 2 + 3 6 . 0 - 8 . 9 P e r i o d 2 1 2 9 1 0 8 0 9 2 8 7 7 0 1 2 6 3 9 7 2 + 3 9 . 0 + 2 . 2 P e r i o d 3 1 2 5 6 5 2 8 9 3 0 4 2 1 1 0 9 2 3 8 9 + 3 5 . 1 + 1 5 . 2 P e r i o d 4 1 2 8 6 6 7 0 9 1 9 0 6 1 7 7 8 7 9 1 + 4 0 . 0 + 6 5 . 2 T o t a l 5 1 0 1 8 0 1 3 7 1 0 1 9 0 4 5 2 6 9 6 4 + 3 7 . 5 + 1 2 . 6 C u t A r e a ( h a ) 6 1 8 7 ( 9 7 % ) 4 4 9 4 ( 7 0 % ) 5 4 9 0 ( 8 6 % ) S o l u t i o n T i m e ( m ) 3 4 0 . 5 0 . 5 N o t e t o T a b l e 5 . 4 . c : t o t a l p l a n n i n g a r e a = 6 3 7 4 h e c t a r e s ; m i n i m u m h a r v e s t a g e i s 1 0 0 y e a r s ; m i n i m u m a d j a c e n c y g r e e n - u p a g e i s 2 5 y e a r s ; p e r i o d l e n g t h = 2 5 y e a r s . . T h e r e s u l t s i n t a b l e 5 . 4 a , 5 . 4 b , a n d 5 . 4 . c s h o w t h a t t h e s i m u l a t e d a n n e a l i n g a l g o r i t h m a l w a y s p r o d u c e s b e t t e r r e s u l t s t h a n A T L A S . I m p r o v e m e n t s b e c o m e m o r e p r o n o u n c e d w h e n e v e n f l o w c o n s t r a i n t s a r e a p p l i e d ( T a b l e 5 . 4 . b ) a n d w h e n t h e n u m b e r o f p l a r i n i n g p e r i o d s i s d e c r e a s e d ( 5 . 4 . c ) . T h i s o c c u r s b e c a u s e f e w e r p e r i o d s a n d f l o w c o n s t r a i n t s m a k e a d j a c e n c y p r o b l e m s m o r e b i n d i n g . C l e a r l y , t h e s i m u l a t e d a n n e a l i n g a l g o r i t h m i s m o r e e f f e c t i v e i n s o l v i n g t h e a d j a c e n c y p r o b l e m s t h a n i s A T L A S . A s t h e n u m b e r o f p l a n n i n g p e r i o d s i n c r e a s e s , ( e . g . 1 0 ) , a d j a c e n c y i s l e s s b i n d i n g d u e t o t h e s c h e d u l i n g f l e x i b i l i t y o f f e r e d a t e a c h p e r i o d . F o r t h i s r e a s o n , i t i s e x p e c t e d t h a t d i f f e r e n c e s b e t w e e n s i m u l a t e d a n n e a l i n g a n d A T L A S s o l u t i o n s w i l l 49 decline as the number of planning periods increases. Also note the rapid solution times for ATLAS (0.5 minute versus 34 minutes). More complex problems than those illustrated here would include numerous harvest units, more planning periods, more complex objective functions, and evaluation of multiple rotations. Adding more units and more planning periods will add computation time, but these do not seriously limit the potential of any of the three algorithms. Adding more land use constraints means extra time in computing a feasible solution, however, the feasible region is generally reduced every time a constraint is added. The trade-off involves the extra cost of computing a feasible solution versus the reduced cost of searching a smaller feasible region. More complex objective functions like profitability and net present value increase the time to decode a solution, but relative to the overall procedure, these increases will be relatively minor. As yet, I have not formulated a true, simultaneous solution procedure for the multiple rotation problem. The only method for evaluating subsequent rotations using the current solution presented here is to first solve the initial rotation, and second, to use the ending inventory projection as the starting inventory for the next rotation. This appears to be a common limitation of all of the algorithms examined except simulation, and it is an area where future research efforts need to be focused. From my experience, I believe that simulated annealing is the best of these three methods for the problems examined, because it is almost as simple as random hill climbing and it performs very well. Hill climbing was very fast at 50 the early iterations, and all solutions found by hill climbing were within 3% of the best solution found. These are very good results considering the inherent uncertainty in planning problems. Hill climbing can get "good" results with a minimum computation effort. The evolution program is very dependent on its parameters and it is very complicated. It can perform as well as simulated annealing provided sufficient time is available, chromosome structure and crossover are identified properly and the parameters are properly adjusted. Incorporating problem specific knowledge into evolution programs and simulated annealing makes the search space smaller and makes these algorithms much more efficient for highly complex problems. 51 Chapter 6 Conclusions and Recommendations 6 . 1 C o n c l u s i o n s F o r t h e p r o b l e m s e x a m i n e d h e r e , a l l 3 m e t h o d s , t h e e v o l u t i o n p r o g r a m , s i m u l a t e d a n n e a l i n g a n d r a n d o m h i l l c l i m b i n g p e r f o r m e d v e r y w e l l . A l l s o l u t i o n s g e n e r a t e d b y a l l t h e s e m e t h o d s w e r e w i t h i n 3 . 1 2 % o f t h e b e s t s o l u t i o n f o u n d . A l l t h e s o l u t i o n s f o u n d b y s i m u l a t e d a n n e a l i n g a r e w i t h i n 1 . 0 0 % ; e v o l u t i o n p r o g r a m s , 2 . 5 4 % a n d h i l l c l i m b i n g , 3 . 1 2 % o f t h i s b e s t s o l u t i o n . H i l l c l i m b i n g i s t h e s i m p l e s t a n d c a n g e t " g o o d " r e s u l t s w i t h a m i r u m u m c o m p u t a t i o n e f f o r t H o w e v e r , i t t e n d s t o c o n v e r g e o n a l o c a l o p t i m u m f r e q u e n t l y . S i m u l a t e d a n n e a l i n g a p p e a r s t o b e o n e o f t h e b e s t m e t h o d s f o r t h i s k i n d o f f o r e s t p l a n n i n g p r o b l e m , b e c a u s e i t i s a l m o s t a s s i m p l e a s r a n d o m h i l l c l i m b i n g a n d i t i s a l m o s t a s e f f i c i e n t a s h i l l c l i m b i n g . T h e e v o l u t i o n p r o g r a m s a r e t h e m o s t c o m p l i c a t e d a n d n e e d t h e m o s t c o m p u t a t i o n e f f o r t H o w e v e r , t h e e v o l u t i o n p r o g r a m i s a p r o m i s i n g m e t h o d f o r s o l v i n g t h i s c l a s s o f p r o b l e m i f t h e p a r a m e t e r s , c h r o m o s o m e s t r u c t u r e a n d c r o s s o v e r c a n b e i d e n t i f i e d p r o p e r l y . T h e r e m a y b e w a y s t o c o m b i n e e v o l u t i o n p r o g r a m s , s i m u l a t e d a n n e a l i n g a n d h i l l c l i m b i n g t o i m p r o v e c o m p u t a t i o n a l e f f i c i e n c y . T h e s e a l t e r n a t i v e s n e e d f u r t h e r i n v e s t i g a t i o n . 52 The models are easily modified to make net profit the objective function by adding columns (predecessor block label, the length of the road linkage from the current block to predecessor block, the status of road linkage as built or not, costs and revenues) to the block attribute data set. Comparisons with a simulation model indicate the superior performance of simulated annealing in solving adjacency problems related to even-flow constraints combined with a small number of planning periods. As the number of planning periods increases, these gains are expected to decline. 6.2 Recommendations for Future Research 1. Scheduling Block by Block and Year by Year In this study, I assumed that the next period can not start until the rninimum green-up age has passed, and that the harvests takes places (instantly) at the middle of the planning period. If the harvest operation is continuous (e.g. annual), scheduling block by block and year by year is a more appropriate formulation, and may be able to generate solutions which are closer to the optimum solution. This formulation also allows us to specify green-up rules for individual blocks, which is a practical reality. Scheduling block by block and year by year will make the algorithms a little more difficult and require more computing time. 53 2. Hard Constraints and Soft Constraints In this study, adjacency constraints and other constraints are used as hard constraints which can not be violated. In some cases, soft constraints seem to make more sense, especially, when only a few blocks are binding the entire solution. Both hard and soft constraints have advantages and disadvantages. A combination value of the opening area and age can be used as a soft constraint to control the adjacency green-up and maximum opening size instead of using these two value as separate hard constraints. Penalty functions can also be used for these constraints. An analysis of hard and soft constraints could produce some useful information on the costs of rigid harvest rules, as opposed to harvest objectives. 3. Evolution Programs and Simulated Annealing for Other Problems I believe that the evolution programs and simulated annealing are promising methods for solving large-scale forest planning problems. Any type of forest planning problem, with any constraints, like forest cover, hydrology, visual, etc. must be solved efficiently. Future studies need to focus on these types of problems which are rapidly being implemented in BC watersheds. 4. Combination of Evolution Programs, Simulated Annealing and Hill Climbing In this study, I successfully applied simulated annealing theory for controlling the mutation transformation acceptance. In the evolution program, I believe that the 54 application of new solution acceptance criteria to crossover solutions might make the evolution program work better. Further studies must examine the effective parameters, like chromosome structure, crossover operators, population size, new solution transformations, and solution acceptance criteria. 55 Literature Cited B a r a h o n a , F . , W e i n t r a u b , A . a n d E p s t e i n , R . 1 9 9 2 . H a b i t a t d i s p e r s i o n i n f o r e s t p l a n n i n g a n d s t a b l e s e t p r o b l e m . O p e r a t i o n s R e s e a r c h 4 0 S u p p . N o . 1 , S 1 4 - S 2 1 . C l e m e n t s , S . E . , D a l l a i n , P . L . a n d J a m n i c k , M . S . 1 9 9 0 . A n o p e r a t i o n a l , s p a t i a l l y c o n s t r a i n e d h a r v e s t s c h e d u l i n g m o d e l . C a n . J . F o r . R e s . 2 0 , 1 4 3 8 - 1 4 4 7 . D a h l i n , B . a n d S a l i n a s , 0 . 1 9 9 3 . H a r v e s t s c h e d u l i n g u n d e r a d j a c e n c y c o n s t r a i n t s , A c a s e s t u d y f r o m S w e d i s h s u b - a l p i n e r e g i o n . S c a n d i n a v i a n J o u r n a l o f F o r e s t R e s e a r c h 8 , 2 8 1 - 2 9 0 . D a v i s , L . , ( E d i t o r ) 1 9 9 1 . H a n d b o o k o f G e n e t i c A l g o r i t h m s , T i c a A s s o c i a t e s , 3 6 H a m p s h i r e S t . , C a m b r i d g e , M A 0 1 2 3 9 . D a v i s , L . ( E d i t o r ) 1 9 8 7 . G e n e t i c A l g o r i t h m s a n d S i m u l a t e d A n n e a l i n g , M o r g a n K a u f m a n n P u b l i s h e r s , I n c . , L o s A l t o s , C A . D a v i s , L . 1 9 8 5 . J o b S h o p S c h e d u l i n g w i t h G e n e t i c A l g o r i t h m s , i n t h e P r o c e e d i n g s o f t h e f i r s t i n t e r n a t i o n a l c o n f e r e n c e o n G e n e t i c A l g o r i t h m s , K a w r e n c e E r l b a u m A s s o c i a t e s , H i l l s d a l e , N J . D e j o n g , K . A . 1 9 8 8 . L e a r n i n g w i t h G e n e t i c A l g o r i t h m : A n O v e r v i e w , M a c h i n e L e a r n i n g . V o l . 3 , p p . 1 2 1 - 1 3 8 . D e W e r r a , D . a n d H e r t z , A . 1 9 8 9 . T a b u s e a r c h t e c h n i q u e s : A t u t o r i a l a n d a n a p p l i c a t i o n t o n e u r a l n e t w o r k s . O R S p e k t r u m 1 1 , 1 3 1 - 1 4 1 . G l o v e r , F . 1 9 9 0 . T a b u s e a r c h : A t u t o r i a l . I n t e r f a c e s 2 0 , 2 6 4 - 2 8 0 . G l o v e r , F . 1 9 8 9 . T a b u s e a r c h - P a r t I . O R S A J o u r n a l o n c o m p u t i n g 1 , 1 9 0 - 2 0 6 . G r e f e n s t e t t e , J . 1 9 8 7 . I n c o r p o r a t i n g 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 g e n e t i c a l g o r i t h m , ' G e n e t i c A l g o r i t h m s a n d S i m u l a t e d A n n e a l i n g ' e d i t e d b y D a v i s L . , M o r g a n K a u f m a n n P u b l i s h e r s , I n c . , L o s A l t o s , p p . 4 2 - 6 0 . 56 G r e f e n s t e t t e , J . J . , ( E d i t o r ) 1 9 8 5 . P r o c e e d i n g s o f t h e f i r s t i n t e r n a t i o n a l C o n f e r e n c e o n G e n e t i c A l g o r i t h m s , K a w r e n c e E r l b a u m A s s o c i a t e s , H i l l s d a l e , N J . G l o v e r , D . E . 1 9 8 7 . S o l v i n g a C o m p l e x K e y b o a r d C o n f i g u r a t i o n P r o b l e m T h r o u g h G e n e r a l i z e d A d a p t i v e S e a r c h i n t h e B o o k " G e n e t i c A l g o r i t h m s a n d S i m u l a t e d A n n e a l i n g " , M o r g a n K a u f m a n n P u b l i s h e r s , I n c . , L o s A l t o s , C A . H e r z , A . a n d d e W e r r a , D . 1 9 9 0 . T h e T a b u s e a r c h m e t a h e u r i s t i c : H o w w e u s e d i t A n n a l s o f M a t h e m a t i c s a n d A r t i f i c i a l I n t e l l i g e n c e 1 , 1 1 1 - 1 2 1 . H o w a r d , A . F . , a n d N e l s o n , J . D . J u n e , 1 9 9 3 . A r e a - b a s e d h a r v e s t s c h e d u l i n g a n d a l l o c a t i o n o f f o r e s t l a n d u s i n g m e t h o d s f o r m u l t i p l e c r i t e r i a d e c i s i o n m a k i n g . C a n . J . F o r . R e s . 2 3 : 1 5 1 - 1 5 8 . H u s b a n d s , P . , M i l l , F . , a n d W a r r i n g t o n , S . 1 9 9 0 . G e n e t i c A l g o r i t h m s , P r o d u c t i o n P l a n O p t i m i z a t i o n , a n d S c h e d u l i n g , i n T h e P r o c e e d i n g s o f F i r s t I n t e r n a t i o n a l C o n f e r e n c e o n P a r a l l e l P r o b l e m S o l v i n g f r o m N a t u r e ( P P S N ) , D o r t m u n d , G e r m a n y , p p . 8 0 - 8 4 . J a m n i c k , M . S . a n d W a l t e r s , K 1 9 9 1 . H a r v e s t b l o c k i n g , a d j a c e n c y c o n s t r a i n t s a n d t i m b e r h a r v e s t v o l u m e s . S y s t e m s A n a l y s i s i n F o r e s t R e s o u r c e s S y m p o s i u m , S o u t h C a r o l i n a , M a r c h 3 - 7 , 2 5 5 - 2 6 1 . J o n e s , J . G . , W e i n t r a u b , A . , M e a c h a m , M . a n d M a g e n d z o , A . 1 9 9 1 . A h e u r i s t i c p r o c e s s f o r s o l v i n g m i x e d - i n t e g e r l a n d m a n a g e m e n t a n d t r a n s p o r t a t i o n p l a n n i n g m o d e l s . I n t e r m o u t a i n R e s e a r c h S t a t i o n T e c h n i c a l R e p o r t I N T - 4 7 7 , U . S . D . A . F o r e s t S e r v i c e . K i r b y , M . , H a g e r , W . a n d W o n g , P . 1 9 8 6 . S i m u l t a n e o u s p l a n n i n g o f w i l d l a n d m a n a g e m e n t a n d t r a n s p o r t a t i o n a l t e r n a t i v e s . T I M S S t u d i e s i n t h e M a n a g e m e n t S c i e n c e s 2 1 , 3 7 1 - 3 8 7 . K i r k p a t r i c k , S . , G e l a t t , C . a n d V e c c h i , M . 1 9 8 3 . O p t i m i z a t i o n b y s i m u l a t e d a n n e a l i n g . S c i e n c e 2 2 0 , 6 7 1 - 6 8 0 . 57 L o c k w o o d , C , a n d M o o r e , T . 1 9 9 3 . H a r v e s t s c h e d u l i n g w i t h a d j a c e n c y c o n s t r a i n t s : a s i m u l a t e d a n n e a l i n g a p p r o a c h . C a n . J . F o r . R e s . 2 3 : 4 6 8 - 4 7 8 . L a a r h o v e n , P . J . M . a n d A a r t s , E . H . L . 1 9 8 7 , S i m u l a t e d a n n e a l i n g : T h e o r y a n d A p p l i c a t i o n s , D . R e i d e l , D o r d r e c h t , H o l l a n d . M e a l e y , S . P . , L i p s c o m b , J . F . a n d J o h n s o n , K . N . 1 9 8 2 . S o l v i n g t h e h a b i t a t d i s p e r s i o n p r o b l e m i n f o r e s t p l a n n i n g . T r a n s . N . A m . W i l d . N a t u r a l . R e s o u r c e C o n f e r e n c e 4 7 , 1 4 2 - 1 5 3 . M i c h a l e w i c z , Z . 1 9 9 1 , G e n e t i c A l g o r i t h m s + D a t a S t r u c t u r e s = E v o l u t i o n P r o g r a m s , D e p t . o f C o m p u t e r S c i e n c e , U n i v e r s i t y o f N o r t h C a r o l i n a , C h a r l o t t e , N C 2 8 2 2 3 , U S A . M i c h a l e w i c z , Z . , J a n i k o w , C , a n d K r a w c z y k , J . 1 9 9 2 . A M o d i f i e d G e n e t i c A l g o r i t h m f o r O p t i m a l C o n t r o l P r o b l e m s , C o m p u t e r & M a t h e m a t i c s w i t h A p p l i c a t i o n s , V o l . 2 3 , N o . 1 2 , p p . 8 3 - 9 4 . M u r r a y , A . T . a n d C h u r c h , R . L . 1 9 9 3 a . C o n s t r u c t i n g a n d s e l e c t i n g a d j a c e n c y c o n s t r a i n t s . S u b m i t e d t o I N F O R . M u r r a y , A . T . a n d C h u r c h , R . L . 1 9 9 3 b . M e a s u r i n g t h e e f f i c i e n c y o f a d j a c e n c y c o n s t r a i n t s t r u c t u r e i n f o r e s t p l a n n i n g . M u r r a y , A . T . , a n d C h u r c h , R . L . 1 9 9 3 . H e u r i s t i c s o l u t i o n a p p r o a c h e s t o o p e r a t i o n a l f o r e s t p l a n n i n g p r o b l e m s . O R S p e c t r u m , 2 0 p . N e l s o n , J . D . a n d B r o d i e , J . D . 1 9 9 0 . C o m p a r i s o n o f a r a n d o m s e a r c h a l g o r i t h m a n d m i x e d - i n t e g e r p r o g r a m f o r s o l v i n g a r e a - b a s e d f o r e s t p l a n s . C a n . J . F o r . R e s . 2 0 : 9 3 4 - 9 4 2 . N e l s o n , J . D . , B r o d i e J . D . a n d S e s s i o n s , J . 1 9 9 1 . m t e g r a t i n g s h o r t - t e r m l o g g i n g p l a n s w i t h l o n g - t e r m h a r v e s t s c h e d u l e s . F o r e s t S c i e n c e . V o l . 3 7 , N o . 1 : 1 0 1 - 1 2 2 . N e l s o n , J . D . a n d E r r i c o , D . 1 9 9 3 . M u l t i p l e - p a s s h a r v e s t i n g a n d s p a t i a l c o n s t r a i n t s : A n o l d t e c h n i q u e a p p l i e d t o a n e w p r o b l e m . F o r e s t S c i e n c e . 3 9 ( 1 ) : 1 - 1 5 . 58 N e l s o n , J . D . a n d F i n n , S . T . 1 9 9 1 . T h e i n f l u e n c e o f c u t - b l o c k s i z e a n d a d j a c e n c y r u l e s o n h a r v e s t l e v e l s a n d r o a d n e t w o r k s . C a n . J . F o r . R e s . 2 1 : 5 9 5 - 6 0 0 . N e l s o n , J . , L i u , G . 1 9 9 4 . S i m u l a t e d a n n e a l i n g a n d f o r e s t p l a n n i n g p r o b l e m s , i n P r o c e e d i n g s o f 1 9 9 4 i n t e r n a t i o n a l c o n f e r e n c e o f I n t e r n a t i o n a l U n i o n o f F o r e s t R e s e a r c h O r g a n i s a t i o n , J u l y 2 5 - 2 8 , H a r b i n , 1 9 9 4 ( i n p r e s s ) . N e l s o n , J . , L i u , G . a n d D . E r r i c o . 1 9 9 3 . U s i n g a g e - c l a s s c o n s t r a i n t s t o a p p r o x i m a t e a d j a c e n c y a n d g r e e n - u p r e g u l a t i o n s , I n P r o c e e d i n g s o f t h e 1 9 9 3 S o c i e t y o f A m e r i c a n F o r e s t e r s S y m p o s i u m o n S y s t e m s A n a l y s i s i n F o r e s t r y , M a r c h 3 - 6 , V a l d i v i a , C h i l e , p p . 3 3 0 - 3 3 5 . M e t r o p o l i s , N . , R o s e n b l u t h , A . , R o s e n b l u t h , M . , T e l l e r , A . a n d T e l l e r , E . 1 9 5 3 . E q u a t i o n o f s t a t e c a l c u l a t i o n s b y f a s t c o m p u t i n g m a c h i n e , J o u r n a l o f C h e m i c a l P h y s i c s 2 1 , 1 8 8 7 - 1 0 9 2 . O ' H a r a , A . , F a a l a n d , B . a n d B a r e , B . 1 9 8 9 . S p a t i a l l y c o n s t r a i n e d t i m b e r h a r v e s t s c h e d u l i n g . C a n . J . F o r . R e s . 1 9 , 7 1 5 - 7 2 4 . R o i s e , J . P . 1 9 9 0 . M u l t i c r i t e r i a n o n - l i n e a r p r o g r a m m i n g f o r o p t i m a l s p a t i a l a l l o c a t i o n o f s t a n d s . F o r e s t S c i e n c e 3 6 , 4 8 7 - 5 0 1 . S e s s i o n s , J . , a n d J . B . S e s s i o n s . 1 9 9 1 . T a c t i c a l F o r e s t P l a n n i n g . I n P r o c . S o c . A m . F o r . N a t i o n a l C o n v e n t i o n , S o c . A m . F o r . , S a n F r a n c i s c o , C A , A u g . 4 - 7 . S y s w e r d a , G . a n d P a l m u c c i , J . 1 9 9 1 . T h e a p p l i c a t i o n o f G e n e t i c A l g o r i t h m s t o R e s o u r c e S c h e d u l i n g , i n t h e P r o c e e d i n g s o f t h e f o u r t h I n t e r n a t i o n a l C o n f e r e n c e o n G e n e t i c A l g o r i t h m s , M o r g a n K a u f m a n n P u b l i s h e r s , L o s A l t o s , C A , p p . 5 0 2 - 5 0 8 . T h o m p s o n , E . F . , H a l t e r m a n , B . G . , L y o n , T . J . a n d M i l l e r , R . L . 1 9 7 3 . I n t e g r a t i n g t i m b e r a n d w i l d l i f e m a n a g e m e n t p l a n n i n g . F o r e s t r y C h r o n i c l e 4 9 , 2 4 7 - 2 5 0 . T o r r e s , R . , J . M . a n d B r o d i e , J . D . 1 9 9 0 . A d j a c e n c y c o n s t r a i n t s i n h a r v e s t s c h e d u l i n g : a n a g g r e g a t i o n h e u r i s t i c . C a n . J . F o r . R e s . 2 0 , 9 7 8 - 9 8 6 . 59 U l r y c h T . J . 1 9 9 3 , O p t i m i s a t i o n b y m e a n s o f n a t u r a l a l g o r i t h m s , u n p u b l i s h e d n o t e , D e p t . o f G e o p h y s i c s a n d A s t r o n o m y , U n i v e r s i t y o f B r i t i s h C o l u m b i a , V a n c o u v e r , C a n a d a . V i g n a u x , G . A . a n d M i c h a l e w i c z , Z . 1 9 8 9 . G e n e t i c A l g o r i t h m s f o r t h e t r a n s p o r t a t i o n p r o b l e m . P r o c e e d i n g s o f t h e 4 t h I n t e r n a t i o n a l S y m p o s i u m o n M e t h o d o l o g i e s f o r I n t e l l i g e n t S y s t e m s . N o r t h - H o l l a n d , A m s t e r d a m , p p . 2 5 2 - 2 5 9 . V i g n a u x , G . A . a n d M i c h a l e w i c z , Z . 1 9 9 1 . G e n e t i c A l g o r i t h m f o r t h e l i n e a r t r a n s p o r t a t i o n p r o b l e m . L E E E T r a n s a c t i o n s o n S y s t e m s , M a n , a n d C y b e r n e t i c s . V o l . 2 1 , N o . 2 , p p . 4 4 5 - 4 5 2 . W h i t l e y D . , S t a r k w e a t h e r , T . , a n d F u q u a y , D . 1 9 8 9 . S c h e d u l i n g P r o b l e m s a n d T r a v e l l i n g S a l e s m a n : T h e G e n e t i c E d g e R e c o m b i n a t i o n O p e r a t o r , i n t h e T h i r d I n t e r n a t i o n a l C o n f e r e n c e o n G e n e t i c A l g o r i t h m s , M o r g a n K a u f m a n n P u b l i s h e r s , L o s A l t o s , C A . 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0075216/manifest

Comment

Related Items