Posts

Genetic algorithms

Mar 31, 2013

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...


… (Read More)

Quickhull algo in javascript - pt4

Mar 14, 2013

Finally got the hang of OOP in javascript.. the public functions for the classes are prototype methods.The quickhull works! Don't use the code for some serious stuff.. its come out of casual coding and might have some errors. Some escape sequences and optimizations remain, but as for the javascript experiment it looks good enough.. I had to put quite a bit of code in for even this simple algo, CVector, CPoint, CEdge and CHull classes. Perhaps a reusable good js geometry util can be written for general usage :-) More later..    


… (Read More)

Quickhull into js and html5- p3

Mar 7, 2013

After this, I will do an implementation for all the popular convex hull finding techniques. It would be so easy to write just a recursive function for the quickhull in c++/c#, but putting the algorithm into javascript is not so straight forward.. but its fun :-) More vector logic and triangle point inside checks added, the logic now checks for extreme points for each edge, I just need to add them into the edge and recourse through the whole logic for new edge definitions. Link to source: https://skydrive.live.com/redir?resid=700BE2A366278EA0!133&authkey=!AATEd_SmxpiGDW8 More later..


… (Read More)

Quickhull experiment in js & html5 - part2

Mar 5, 2013

Cleaning up the code for Quickhull. Added more math routines in it. Created classes inside javascript. Its simple to create classes(objects only) in javascript. One has to use the Java Script Object Notation (JSON) Example: var bounding_box = {     "min": {         "x":0,         "y":0     },     "max": {         "x":0,         "y":0     } }; The source code so far: QuickHull java script code.  Needs to recursively call on the edge subdivision. That will be when I get time next :-)


… (Read More)

Quickhull experiment in html5 - part1

Feb 25, 2013

More experiments on Javascript and html5 rendering.. Implementing the Quickhull algorithm. This will find out a fast optimal bounding volume encapsulating all the points. Steps: Find the bounding box Find the points lying on the box, they form a quad.. Eliminate the points lying inside the formed boundary Find the farthest point away from each edges and form a triangle of that edge with the point. Eliminate the points lying inside the triangle and add the two new edges to the hull Repeat the steps 3-5 till no points are found outside the hull.


… (Read More)

subscribe via RSS