Wednesday 28 March 2007

## Random draw in a sphere

By nojhan, Wednesday 28 March 2007 at 19:00 :: Programming

When adapting combinatorial metaheuristics to continuous problems, one sometimes use a sphere as an approximation of the "neighborhood". The idea is thus to draw the neighbours around a solution, for example in order to apply a simple mutation in a genetic algorithm.

Sometimes, one choose to use an uniform law, but how to draw random vectors *uniformly* in an hyper-sphere ?

The first idea that comes to mind is to use a polar coordinate system and draw the radius *r* and the angles *a _{1}...a_{2}...a_{i}...a_{N}* with a uniform law. Then, one convert the coordinates in the rectangular system,

*x*.

_{1}...x_{2}...x_{i}...x_{N}The result is interesting for a metaheuristic design, but is not a uniform distribution:

The correct method is to draw each *x _{i}* according to:

*x*

_{i}=(r_{i}^{1/N}a_{i})/√(∑(a_{i}))(in L

^{A}T

_{E}X :

`$x_{i}=\frac{r^{\frac{1}{N}}_i\cdot a_{i}}{\sqrt{{\displaystyle \sum _{j=1}^{N}a_{i}}}}$`

)With *r _{i}* uniformly drawn in

*U*and

_{0,1}*a*following a normal law

*N*

_{O,1}The result is then a true uniform distribution:

Credits goes to Maurice Clerc for detecting and solving the problem.