Got very little time on this weekend. I was again interested in techniques for solving optimisation problems. Many of the problems in real-life are optimisation problems, where unknows are more than the information (equations) at hand. Examples: fitting of surface patches / curves on points, closest path - path planning computations, Nesting (manufacturing) for optimising the material cut from the raw material sheets, inverse kinematics, fluid mechanics, medicine, many other areas...
Optimisation techniques is a huge research area, and it would require considerable amount of time to study every technique. I have used basic optimization methods before, but I am starting to learn about advanced techniques. Many problems can be formulated and solved by calculus methods, but they become exceedingly complicated with more number of unknowns. A simple minima, maxima problem in single variable can be solved by calculus, where f`(x)=0... then solving by Newton Raphson method, other numerical methods, but when there are multiple variables we have to find partial derivatives which become complex with more variables. Some of the calculus approaches can only find out the local maximas for the functions, in that case optimization results heavily depend on the initial guesses. There are advanced numerical methods to solve non-linear optimization problems to get global roots.
GA uses a heuristic approach based on natural selection phenomenon. Got reading this book again about GA by David Goldberg, I am fascinated by the GA technique. Its a searching technique which narrows down to the answer in solution (search) space using different combination functions on the existing pool of intermediate solutions which they call as chromosomes. It can be used for problems that are NP-Hard as well. Most important part of this techniques is the problem formulation, we have to represent the problem in a particular form so that we can use GA. To get familiar with this technique I want to try and solve a problem with this, possibly Travelling salesman problem or best fit circle in points or both.
Useful links:
http://hyperphysics.phy-astr.gsu.edu/hbase/math/maxmin.html
http://en.wikipedia.org/wiki/Nonlinear_programming
http://www.ai-junkie.com/ga/intro/gat1.html
More later...
Optimisation techniques is a huge research area, and it would require considerable amount of time to study every technique. I have used basic optimization methods before, but I am starting to learn about advanced techniques. Many problems can be formulated and solved by calculus methods, but they become exceedingly complicated with more number of unknowns. A simple minima, maxima problem in single variable can be solved by calculus, where f`(x)=0... then solving by Newton Raphson method, other numerical methods, but when there are multiple variables we have to find partial derivatives which become complex with more variables. Some of the calculus approaches can only find out the local maximas for the functions, in that case optimization results heavily depend on the initial guesses. There are advanced numerical methods to solve non-linear optimization problems to get global roots.
GA uses a heuristic approach based on natural selection phenomenon. Got reading this book again about GA by David Goldberg, I am fascinated by the GA technique. Its a searching technique which narrows down to the answer in solution (search) space using different combination functions on the existing pool of intermediate solutions which they call as chromosomes. It can be used for problems that are NP-Hard as well. Most important part of this techniques is the problem formulation, we have to represent the problem in a particular form so that we can use GA. To get familiar with this technique I want to try and solve a problem with this, possibly Travelling salesman problem or best fit circle in points or both.
Useful links:
http://hyperphysics.phy-astr.gsu.edu/hbase/math/maxmin.html
http://en.wikipedia.org/wiki/Nonlinear_programming
http://www.ai-junkie.com/ga/intro/gat1.html
More later...
No comments:
Post a Comment