Digital Elevation Models (DEM) generation using evolutionary computation
The use of Geographic Information Systems (GIS) for watershed delineation and stream definition is a current practice in water resources engineering today. This technique is mainly based on Digital Elevations Models (DEM) developed by interpolation of topographic data. Although more accurate data can be obtained using Light Detection And Ranging (LiDAR), traditional GIS-based interpolation methods for the creation of DEMs have difficulty to process such large amounts of data. To address this issue, my current research is to evaluate different forms of DEM generation from LiDAR data to find the best way to generate DEMs that are adequate to watershed delineations. My idea for the term project is to explore the interpolation techniques for terrain creation available in MATLAB and apply evolutionary computation to search for solutions that can handle LiDAR data and also result in a more accurate representation of the earth surface. At this point I think my decision variables will be the different parameters of the interpolation methods and my fitness functions will be an error metric that will evaluate the accuracy of the interpolated values. Future work and applications to my research line would be to use the best DEMs generated during the exercise to watershed delineation in GIS and to evaluate the accuracy of the resultants watersheds.
Monday, February 8, 2010
Tuesday, January 26, 2010
Homework #1
Part 1) Blog your review of any of the readings that you have completed. There are currently five articles/chapters available on-line. Make sure to review one of these. You can summarize the chapter, answer questions or problems that are posed in the reading, or discuss any thoughts and ideas that were provoked through the reading.
Chapter 6 – A history of evolutionary computation
Kenneth De Jong, David B. Fogel and Hans-Paul Schwefel
This chapter presents an interesting and comprehensive review of the history of evolutionary computation. The authors traced it back to the mid 1950s citing researchers such as Fridberg(1958), Fraser(1957), Bremermann, 1962) and Spendley (1962) that developed the simplex design model. Although most of the work done during the 50s was seeing with skepticism, the major part of the basis that today form the evolutionary algorithms were developed by the mid-1960s. The main responsible for developing the evolutionary programming roots was Lawrence Fogel (1966) and Holland (1967) developed the genetic algorithms while in the other side of Atlantic Bienert, Rechenberg and Schwefel (1965) developed evolution strategies.
The efforts of Fogel on evolutionary programming in syntheses showed the early attempts to: “(i)use simulated evolution to perform prediction; (ii)include variable length encodings; (iii) use representations that take the form of a sequence of instructions; (iv) incorporate a population of candidate solutions and (v) coevolved evolutionary programs.
The genetic algorithms idea proposed by Holland (1962) already aimed to understand and apply the concepts of adaptive systems that are capable of self modification in response to their interactions with the environment in which they function (competition and innovation). As his students developed the theme, mechanisms of reproductions and inheritance such as mutation, cross-over and inversion were added to the process. Curiously, some theories developed by Holland could not be observed experimentally, explained latter by the small population sizes provided by the limited computational capacity. By the 1970s it was clear that the GAs had the potential to solve difficult optimization problems and other universities were also researching the topic. The field continued to grow and Golderberg (1989) published a book that synthesized the advances in the field up to that date consolidating it.
The evolution strategies have its roots traced back to Berlin, where Bienert, Rechenberg and Schwefel were initially working with fluid mechanics in wind tunnel and as part of their experiment developed the idea of using a dice for random decisions creating the first version of evolutionary strategy called (1+1). Since their early work, strategies that were concerned not only with real-valued parameter optimization where developed to fit real world problems.
For the past 25 years this three branches developed independently of each other with little interaction until around 1990 where cooperation between this researchers began to become more common. An international workshop at Dortmund in 1991 and following conferences ICGA91, EP92 and PPSN provided opportunities of interaction that resulted in a Journal published by the MIT press and a name for the field Evolutionary Computation.
Part 2) Read “Improving the computational efficiency of highway alignment optimization models through a stepwise genetic algorithms approach” by Kim et al. (2005). Answer these questions on your blog.
a. Many different methods have been applied for highway alignment optimization. What are the deficiencies and advantages of using these methods? Why was a GA chosen in this work?
b. What are the differences among the different scenarios tested in the problem?
c. How does the GA perform for each of the different scenarios? What are the major conclusions of the article?
Most of the answers were copied directly from the paper and edited to answer the questions.
a)
Calculus of variations:
• Requires differentiable objective functions
• Not suitable for discontinuous factors
• Tendency to get trapped in local optima
Network optimization:
• Outputs are not smooth
• Not for continuous search space
Dynamic programming:
• Outputs are not smooth
• Not suitable for continuous search space
• Not applicable for implicit functions
• Requires independencies among subproblems
Enumeration:
• Not suitable for continuous search space
• Inefficient
Linear programming:
• Not suitable for non-linear cost functions
• Only covering limited number of points for gradient and curvature constraints
Numerical search:
• Tendency to get trapped in local optima
• Complex modeling
• Difficulty in handling discontinuous cost items
GA:
(1) GAs work with a coding of the parameter set, not the parameters themselves.
(2) GAs search from a population rather than a single point.
(3) GAs use payoff (objective function) information, not derivatives or other auxiliary knowledge.
(4) GAs use probabilistic transition rules, not deterministic rules.
In addition it is found that GA is highly efficient means of searching a large solution space.
b)
Scenarios 1 and 2 are devised for a one-step optimization while scenario 3 is for a two step
optimization. The results of scenarios 1 and 2 can be used for assessing the effects of the population size on computational time and the quality of solutions while the result of scenario 3 can be compared to the results of both scenario 1 and 2 for checking how much improvement is found with a two-step optimization.
Also the:
• Number of points of intersections (Pi_s);
• Population size
c)
The proposed stepwise approach is implemented in an artificial test example, which indicates that substantial improvement in computing efficiency can be achieved with the stepwise approach. The approach also improves the solution (i.e., an economical alignment is obtained) compared to the traditional one stage approach. More test cases with larger problem size and additional GA scenarios are needed to be run to investigate the full potential of the stepwise approach. To subdivide a study area, it is recommended that a one-step optimization be run with a relatively small number of decision variables (Pi_s). Then the relevant Pi_s location for subdivision should be selected based on: (1) natural break points in the study section (2) the possibility for construction of structures and (3) the precision requirements. The lengths of segments may also differ depending on the precision requirements and need for savings in computing time.
Chapter 6 – A history of evolutionary computation
Kenneth De Jong, David B. Fogel and Hans-Paul Schwefel
This chapter presents an interesting and comprehensive review of the history of evolutionary computation. The authors traced it back to the mid 1950s citing researchers such as Fridberg(1958), Fraser(1957), Bremermann, 1962) and Spendley (1962) that developed the simplex design model. Although most of the work done during the 50s was seeing with skepticism, the major part of the basis that today form the evolutionary algorithms were developed by the mid-1960s. The main responsible for developing the evolutionary programming roots was Lawrence Fogel (1966) and Holland (1967) developed the genetic algorithms while in the other side of Atlantic Bienert, Rechenberg and Schwefel (1965) developed evolution strategies.
The efforts of Fogel on evolutionary programming in syntheses showed the early attempts to: “(i)use simulated evolution to perform prediction; (ii)include variable length encodings; (iii) use representations that take the form of a sequence of instructions; (iv) incorporate a population of candidate solutions and (v) coevolved evolutionary programs.
The genetic algorithms idea proposed by Holland (1962) already aimed to understand and apply the concepts of adaptive systems that are capable of self modification in response to their interactions with the environment in which they function (competition and innovation). As his students developed the theme, mechanisms of reproductions and inheritance such as mutation, cross-over and inversion were added to the process. Curiously, some theories developed by Holland could not be observed experimentally, explained latter by the small population sizes provided by the limited computational capacity. By the 1970s it was clear that the GAs had the potential to solve difficult optimization problems and other universities were also researching the topic. The field continued to grow and Golderberg (1989) published a book that synthesized the advances in the field up to that date consolidating it.
The evolution strategies have its roots traced back to Berlin, where Bienert, Rechenberg and Schwefel were initially working with fluid mechanics in wind tunnel and as part of their experiment developed the idea of using a dice for random decisions creating the first version of evolutionary strategy called (1+1). Since their early work, strategies that were concerned not only with real-valued parameter optimization where developed to fit real world problems.
For the past 25 years this three branches developed independently of each other with little interaction until around 1990 where cooperation between this researchers began to become more common. An international workshop at Dortmund in 1991 and following conferences ICGA91, EP92 and PPSN provided opportunities of interaction that resulted in a Journal published by the MIT press and a name for the field Evolutionary Computation.
Part 2) Read “Improving the computational efficiency of highway alignment optimization models through a stepwise genetic algorithms approach” by Kim et al. (2005). Answer these questions on your blog.
a. Many different methods have been applied for highway alignment optimization. What are the deficiencies and advantages of using these methods? Why was a GA chosen in this work?
b. What are the differences among the different scenarios tested in the problem?
c. How does the GA perform for each of the different scenarios? What are the major conclusions of the article?
Most of the answers were copied directly from the paper and edited to answer the questions.
a)
Calculus of variations:
• Requires differentiable objective functions
• Not suitable for discontinuous factors
• Tendency to get trapped in local optima
Network optimization:
• Outputs are not smooth
• Not for continuous search space
Dynamic programming:
• Outputs are not smooth
• Not suitable for continuous search space
• Not applicable for implicit functions
• Requires independencies among subproblems
Enumeration:
• Not suitable for continuous search space
• Inefficient
Linear programming:
• Not suitable for non-linear cost functions
• Only covering limited number of points for gradient and curvature constraints
Numerical search:
• Tendency to get trapped in local optima
• Complex modeling
• Difficulty in handling discontinuous cost items
GA:
(1) GAs work with a coding of the parameter set, not the parameters themselves.
(2) GAs search from a population rather than a single point.
(3) GAs use payoff (objective function) information, not derivatives or other auxiliary knowledge.
(4) GAs use probabilistic transition rules, not deterministic rules.
In addition it is found that GA is highly efficient means of searching a large solution space.
b)
Scenarios 1 and 2 are devised for a one-step optimization while scenario 3 is for a two step
optimization. The results of scenarios 1 and 2 can be used for assessing the effects of the population size on computational time and the quality of solutions while the result of scenario 3 can be compared to the results of both scenario 1 and 2 for checking how much improvement is found with a two-step optimization.
Also the:
• Number of points of intersections (Pi_s);
• Population size
c)
The proposed stepwise approach is implemented in an artificial test example, which indicates that substantial improvement in computing efficiency can be achieved with the stepwise approach. The approach also improves the solution (i.e., an economical alignment is obtained) compared to the traditional one stage approach. More test cases with larger problem size and additional GA scenarios are needed to be run to investigate the full potential of the stepwise approach. To subdivide a study area, it is recommended that a one-step optimization be run with a relatively small number of decision variables (Pi_s). Then the relevant Pi_s location for subdivision should be selected based on: (1) natural break points in the study section (2) the possibility for construction of structures and (3) the precision requirements. The lengths of segments may also differ depending on the precision requirements and need for savings in computing time.
Subscribe to:
Posts (Atom)
